Generare primi ...

[axpgn]

Ho la seguente successione definita ricorsivamente:
$a_(n+3)=a_n+a_(n+1)$

inizializzata così:
$a_0=3, a_1=0, a_2=2$

Faccio una tabella dei primi termini:

$n$	$a_n$
3	1
2	2
3	4
5	5
5	7
8	10
12	10
11	22
29	13

Noto che quando $a_n$ è un multiplo di $n$ allora $n$ è primo.

Ma com'è possibile?


Cordialmente, Alex

[hydro1]

Legge dei piccoli numeri. In generale non è vero, puoi verificare che $n=271441=521^2$ è un controesempio. Il viceversa invece è vero e facile da dimostrare: se $p$ è primo allora $p$ divide $a_p$.

[axpgn]

Per curiosità, conoscevi già questa successione ("Perrin sequence"), l'hai trovata su OEIS o hai trovato il controesempio a mano?


Cordialmente, Alex

[hydro1]

Nessuna di queste. Il fatto che il viceversa fosse vero mi ha fatto sospettare che il tuo claim non lo fosse. Una breve googlata di "divisibility of linear recurring sequences" o qualcosa del genere ha restituito tra i primi risultati esattamente questo. Comunque scrivere un programmino in Magma o Python che verifichi questa cosa è semplice.