How can I generate the Rowland prime sequence idiomatically in J?

Answer 1

I don't have a full answer yet, but this essay by Roger Hui has a tacit construct you can use to replace explicit while loops. Another (related) avenue would be to make the inner logic of the block into a tacit expression like so:

FUNWITHTACIT =: ] , {: + {: +. 1 + #
rowland =: monad define
    result =. >a:
    t =. 7x
    while. (# result) < y do.
      t =. FUNWITHTACIT t
      d =.  | -/ _2 {. t
      result =. ~.result,((d>1)#d)
    end.
    result
)

(You might want to keep the if block for efficiency, though, since I wrote the code in such a way that result is modified regardless of whether or not the condition was met -- if it wasn't, the modification has no effect. The if logic could even be written back into the tacit expression by using the Agenda operator.)

A complete solution would consist of finding out how to represent all the logic inside the while loop of as a single function, and then use Roger's trick to implement the while logic as a tacit expression. I'll see what I can turn up.

As an aside, I got J to build FUNWITHTACIT for me by taking the first few lines of your code, manually substituting in the functions you declared for the variable values (which I could do because they were all operating on a single argument in different ways), replaced every instance of t with y and told J to build the tacit equivalent of the resulting expression:

]FUNWITHTACIT =: 13 : 'y,({:y)+(1+#y)+.({:y)'
   ] , {: + {: +. 1 + #

Using 13 to declare the monad is how J knows to take a monad (otherwise explicitly declared with 3 : 0, or monad define as you wrote in your program) and convert the explicit expression into a tacit expression.

EDIT:

Here are the functions I wrote for avenue (2) that I mentioned in the comment:

candfun =: 3 : '(] , {: + {: +. 1 + #)^:(y) 7'
firstdiff =: [: | 2 -/\ ]
triage =: [: /:~ [: ~. 1&~: # ]
rowland2 =: triage @firstdiff @candfun

This function generates the first n-many candidate numbers using the Rowland recurrence relation, evaluates their first differences, discards all first-differences equal to 1, discards all duplicates, and sorts them in ascending order. I don't think it's completely satisfactory yet, since the argument sets the number of candidates to try instead of the number of results. But, it's still progress.

Example:

   rowland2 1000
3 5 7 11 13 23 47 101 233 467 941

Here's a version of the first function I posted, keeping the size of each argument to a minimum:

NB. rowrec takes y=(n,an) where n is the index and a(n) is the
NB. nth member of the rowland candidate sequence. The base case
NB. is rowrec 1 7. The output is (n+1,a(n+1)).
rowrec =: (1 + {.) , }. + [: +./ 1 0 + ]

rowland3 =: 3 : 0
 result =. >a:
 t =. 1 7
 while. y > #result do.
  ts =. (<"1)2 2 $ t,rowrec t
  fdiff =. |2-/\,>(}.&.>) ts
  if. 1~:fdiff do.
   result =. ~. result,fdiff
  end.
  t =. ,>}.ts
 end.
 /:~ result
) 

which finds the first y-many distinct Rowland primes and presents them in ascending order:

   rowland3 20
3 5 7 11 13 23 47 53 101 233 467 941 1889 3779 7559 15131 30323 60647 121403 242807

Most of the complexity of this function comes from my handling of boxed arrays. It's not pretty code, but it only keeps 4+#result many data elements (which grows on a log scale) in memory during computation. The original function rowland keeps (#t)+(#result) elements in memory (which grows on a linear scale). rowland2 y builds an array of y-many elements, which makes its memory profile almost the same as rowland even though it never grows beyond a specified bound. I like rowland2 for its compactness, but without a formula to predict the exact size of y needed to generate n-many distinct primes, that task will need to be done on a trial-and-error basis and thus potentially use many more cycles than rowland or rowland3 on redundant calculations. rowland3 is probably more efficient than my version of rowland, since FUNWITHTACIT recomputes #t on every loop iteration -- rowland3 just increments a counter, which is less computationally intensive.

Still, I'm not happy with rowland3's explicit control structures. It seems like there should be a way to accomplish this behavior using recursion or something.