Come faccio a generare il primo sequenza di Rowland idiomaticamente in J?

Question

Se non hai familiarità con il Primo sequenza di Rowland, è possibile trovare su di esso qui . Ho creato un brutto, procedurale verbo monadica in J per generare il primo n termini in questa sequenza, come segue:

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
)

Questo funziona perfettamente, e genera infatti la prima n termini nella sequenza. (Con n termini, intendo il primo n distinti numeri primi.)

Ecco l'output del rowland 20:

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

La mia domanda è, come posso scrivere questo in più idiomatica J? Non ho la minima idea, anche se ho fatto scrivere la seguente funzione per trovare le differenze tra ogni numero successivo in una lista di numeri, che è uno dei passi necessari. Qui si tratta, anche se troppo potrebbe probabilmente essere riscritta da un programmatore più esperto di J I:

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

Answer 1

Non ho una risposta completa ancora, ma questo saggio da Roger Hui ha un costrutto tacita è possibile utilizzare per sostituire i loop mentre esplicite. Altro (legati) avenue sarebbe rendere la logica interna del blocco in un'espressione tacitamente questo modo:

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
)

(Si potrebbe voler mantenere il blocco if per l'efficienza, anche se, da quando ho scritto il codice in modo tale che result viene modificato, indipendentemente dal fatto che la condizione è stata soddisfatta - se non fosse stato, la modifica ha nessun effetto. la logica if potrebbe anche essere ripristinato nell'espressione tacita utilizzando l'operatore Agenda.)

Una soluzione completa consisterebbe di trovare il modo di rappresentare tutta la logica all'interno del ciclo while come una singola funzione, e quindi utilizzare il trucco di Roger per implementare la logica, mentre come espressione tacita. Vedrò cosa posso alzare.

Per inciso, ho avuto J di costruire FUNWITHTACIT per me prendendo le prime righe del codice, sostituendo manualmente nelle funzioni stati dichiarati i valori delle variabili (che ho potuto fare perché erano tutti operativo su un singolo argomento in modi diversi), sostituito ogni istanza di t con y e ha detto J per costruire l'equivalente tacita l'espressione risultante:

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

Utilizzo di 13 a dichiarare la monade è come J sa prendere una monade (altrimenti esplicitamente dichiarata con 3 : 0, o monad define come hai scritto nel programma) e convertire l'espressione esplicita in un'espressione tacita.

EDIT:

Ecco le funzioni che ho scritto per Avenue (2) di cui ho parlato nel commento:

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

Questa funzione genera i primi numeri candidati n-molti utilizzando la relazione di ricorrenza Rowland, valuta i prime differenze, rigetti tutti di prima differenze uguale a 1, rigetti tutti i duplicati, e le ordina in ordine crescente. Io non credo che sia ancora del tutto soddisfacente, dal momento che l'argomento imposta il numero di candidati per provare al posto del numero di risultati. Ma, è ancora progredire.

Esempio:

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

Ecco una versione della prima funzione che ho postato, mantenendo le dimensioni di ogni argomento al minimo:

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
) 

che trova i primi distinti numeri primi e li presenta Rowland y-molti in ordine crescente:

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

La maggior parte della complessità di questa funzione viene dalla mia manipolazione di array in scatola. Non è bello il codice, ma mantiene solo 4+#result molti elementi di dati (che si sviluppa su una scala logaritmica) in memoria durante il calcolo. La funzione rowland originaria mantiene elementi (#t)+(#result) in memoria (che cresce su una scala lineare). rowland2 y costruisce una matrice di elementi y-molti, che rende la sua memoria profilo quasi uguale rowland anche se non cresce oltre un determinato legato. Mi piace rowland2 per la sua compattezza, ma senza una formula per predire l'esatta dimensione di y necessaria a generare n-molti primi distinti, che compito dovrà essere fatto su una base di prova ed errore e quindi potenzialmente utilizzare molti cicli di rowland o rowland3 su calcoli ridondanti. rowland3 è probabilmente più efficiente rispetto la mia versione di rowland, dal momento che ricalcola FUNWITHTACIT #t su ogni iterazione del ciclo - rowland3 solo incrementa un contatore, che è meno computazionalmente intensive

.

Ancora, io non sono felice con strutture di controllo esplicito di rowland3. Sembra che ci dovrebbe essere un modo per ottenere questo comportamento utilizzando la ricorsione o qualcosa del genere.

Answer 2

Mentre io già segnato la risposta di estanford come quella corretta, sono venuto un lungo, lungo cammino con J da quando ho fatto questa domanda. Ecco un modo molto più idiomatico per generare la sequenza primaria Rowland in J:

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

Il (, ({: + ({: +. >:@#)))^:(1000 - #) 7 espressione genera i cosiddetti sequenza originale fino a 1000 membri. Le prime differenze di questa sequenza possono essere generate da | 2 -/\, cioè, i valori assoluti delle differenze di ogni due elementi. (Confrontare questo al mio originale, diffs prolisso verbo dalla domanda iniziale.)

Infine, togliamo gli uni e gli numeri primi duplicati ~. (#~ 1&<) per ottenere la sequenza dei numeri primi.

Questo è di gran lunga superiore al modo in cui facevo prima. Può essere facilmente trasformato in un verbo per generare il numero n di primi con un po 'di ricorsione.