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

Question

If you're not familiar with the Rowland prime sequence, you can find out about it here. I've created an ugly, procedural monadic verb in J to generate the first n terms in this sequence, as follows:

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

This works perfectly, and it indeed generates the first n terms in the sequence. (By n terms, I mean the first n distinct primes.)

Here is the output of rowland 20:

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

My question is, how can I write this in more idiomatic J? I don't have a clue, although I did write the following function to find the differences between each successive number in a list of numbers, which is one of the required steps. Here it is, although it too could probably be refactored by a more experienced J programmer than I:

diffs =: monad : '}: (|@-/@(2&{.) , $:@}.) ^: (1 < #) y'

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.

Answer 2

While I already marked estanford's answer as the correct one, I've come a long, long way with J since I asked this question. Here's a much more idiomatic way to generate the rowland prime sequence in J:

~. (#~ 1&<) | 2 -/\ (, ({: + ({: +. >:@#)))^:(1000 - #) 7

The expression (, ({: + ({: +. >:@#)))^:(1000 - #) 7 generates the so-called original sequence up to 1000 members. The first differences of this sequence can be generated by | 2 -/\, i.e., the absolute values of the differences of every two elements. (Compare this to my original, long-winded diffs verb from the original question.)

Lastly, we remove the ones and the duplicate primes ~. (#~ 1&<) to get the sequence of primes.

This is vastly superior to the way I was doing it before. It can easily be turned into a verb to generate n number of primes with a little recursion.