Newsgroup: it.hobby.enigmi
Titolo: Numeri primi sequenziali

stavo giocando coi numeri primi e mi è venuto in mente il seguente quesito:
è possibile trovare una sequenza arbitrariamente lunga di numeri primi in
modo che ciascun numero si ottenga dal precedente aggiungendo una cifra a
destra?
esempio:
2
23
233
2333
etc...
 tuttavia questo quesito probabilmente ha risposta negativa, visto che son
poche le cifre che posso aggiungere a destra.
ma cosa succede se lo faccio a sinistra?
per ora ho trovato questo numero:
6739234273831
739234273831
39234273831
9234273831
234273831
...
sono tutti numeri primi.
esiste il più grande tra questi?
e se posso aggiungere cifre sia a destra che a sinistra?
qualcuno ha in mente come si potrebbe implementare un algoritmo per cercare
numeri via via più grandi?
per ora mi limito ad andare di Brute Force: aggiungo le cifre da 1 a 9 in
capo al numero e verifico se il numero che ottengo è primo; se è primo
proseguo aggiungendo un'altra cifra. se non è mai primo, ripeto lo stesso
ragionamento ma con una cifra di meno. purtroppo non conosco abbastanza
informatica per implementare questo "semplice" algoritmo...
a dire il vero, il problema potrebbe essere indecidibile...
ciaooo
pazqo

 
2342738317
ops
ci va un 7 in coda a tutti!
(qua sopra è corretto)
:-P

il programma si implementa abbastanza semplicemente...
se vuoi provo a buttar giù qualche linea di codice e a proporla...
ma risolvere il problema via brute force può probabilmente richiedere troppo
tempo!
Il tutto sta nella definizione di numero primo: un numero primo è un numero
intero divisibile solo per 1 e per se stesso.
Per verificare se un numero è primo dovrei provare a dividerlo per 2, quindi
per 3, ecc. fino a dividerlo per la metà di quel numero. dovendo verificare
che il numero sia primo, devo verificare che tutti quei resti siano diversi
da zero.
aggiungendo una cifra a destra o a sinistra si incrementa il numero di un
ordine di grandezza quindi si aumenta la complessità di 5 volte.
non sarebbe un bel programma...
ciao,
  Ste

 tempo!
beh, ci son i famosi algoritmi di Millard-Rabin che funzionano a
meraviglia...
come programma per fare i conti uso il Parì, si trova distribuito
gratuitamente...
la funzione per la primalità è semplicemente isprime(x), che sbaglia con una
probabilità di (1/4)^10.
a me basterebbe un semplice programmino per vedere un po' come va avanti la
successione di questi primi...
pazqo

ok, domani do un okkiata ai progs che hai citato e ti faccio sapere...
adesso son troppo stanco...
ciao,
  ste

 che sbaglia con una probabilità di (1/4)^10.
O_o
in che senso sbaglia???
ciao,
  ste

 in che senso sbaglia???
nel senso che fa il test su 10 numeri più bassi di n (il numero che sto
testando).
ciascun test passa con probabilità 1/4 (cioè con probabilità 1/4 il numero è
composto ma l'algoritmo non se ne accorge)
quindi in tutto, la probabilità che passi tutti i test è di 1/4 ^ 10. cioè 1
volta su 4^10 tutti e 10 i numeri passano il test.
pazqo

 ha scritto nel
messaggio news:d_Ajc.26633$eR5....@tornado.fastwebnet.it...

ok
tnx
:-)
pazqo

 non li conosco!
io torno casa domani sera, verso le 19. se nessuno ha ancora postato il
procedimento, allora ci penso io.
ora è tardi
pazqo

prima di andare a nanna butto lì anche questa cosa...
magari serve...
se non mi ricordo male... sia sui miei libri di scuola di mate che nel libro
di introduzione alla programmazione dell'uni si parlava del crivello di
eratostene come algoritmo per scoprire i numeri primi.
non ricordo nè i passi dell'algoritmo nè la complessità...
i metodi di brute force potrebbero quindi essere 2.
metodo pazqo
* parto da un numero primo ad 1 cifra (semplice: 1, 2, 3, 5, 7 o 9)
* poi ci aggiungo una cifra a dx o sx
* verifico se il numero ottenuto è primo e torno al punto precedente
* se non è primo, sostituisco la cifra appena aggiunta con una diversa cifra
(qui di cifre ne avrei 10, ma posso escludere: 2, 4, 5, 6, 8, 0 e forse
delle altre dovendo aggiungere a dx che generano di sicuro numeri non primi.
analoghe considerazioni non possono essere fatte per l'aggiunta a sx)
dopodichè torno al punto precedente
* se ho provato tutte la cifre e non ne ho trovata nemmeno una valida,
allora la mia catena di numeri primi si interrompe ed esco dal programma
metodo braga
se il crivello di eratostene si dovesse dimostrare più efficiente potrei al
passo n dell'algoritmo:
* generare tutti i numeri primi composti da n+1
* verificare se la stringa che contiene la catena attuale di numeri è
interamente contenuta in uno o più numeri precedentemente genrati
* in caso di risposta affermativa aggiungo l'ultimo anello della catena di
numeri primi e richiamo ricorsivamente questa funzione con n = n + 1
* in caso di risposta negativa, quando tutti i confronti sono stati
effettuati senza successo, chiudo l'istanza di ricorsione e torno al livello
precedente.
in pratica è un algoritmo di esplorazione che costruisce un albero non
binario in cui per ogni foglia si deve eseguire un po' di crivello di
eratostene ed un certo numero di confronti. anche questa implementazione
come complessità tende a esplodere prestissimo...
vista l'ora e la stanchezza però, non riesco a produrre di meglio...
ciao,
  ste

 esiste il piů grande tra questi?
Esiste ed ha 24 cifre. Non penso che sia facile da trovare :o)
Naturalmente non sono risultati miei, mi ero posto il problema qualche tempo
fa e, dopo averli cercati per conto mio con scarsi esiti, avevo trovato
qualche referenza annotandomene i risultati. Non riporto le soluzioni, per
ora, perchč ci state ancora provando ma se doessero servire in un secondo
tempo sono qui a portata di mano.
Un saluto e buona giornata a tutti,
GaS


Se non sbaglio per vedere se un numero e' primo basta verificare fino alla
radice del numero, non alla meta' (se e' divisibile per la meta' e'
divisibile anche per 2 ...). Quindi la complessita' aumenta di piu' o meno
sqrt(10).

 e se posso aggiungere cifre sia a destra che a sinistra?
Mah, in questo caso non saprei dire.
Di sicuro, anche forzando ad aggiungere ogni volta una cifra
a destra ed una a sinistra si raggiungono facilmente numeri
ragguardevoli, tipo questo di 85 cifre:
9723899723521665329718558536583655613465892937393177799133971111911997911777719737171
o questo di 91 cifre
2124823821573876118235373589673496371976538993773311199797313939377713911311719399973179339
Nonostante questo, ho la sensazione che in questo caso possano essere 
finiti.
ciao,
g.

 e se posso aggiungere cifre sia a destra che a sinistra?
Direi che se si parte da un numero primo di una cifra (2,3,5,7)
e ad ogni passo si puo' aggiungere una sola cifra a destra o a sinistra,
e il numero risultante deve essere primo, allora le catene piu'
lunghe possibili di questo tipo finiscono in 5 numeri primi di 31 cifre,
se il mio programmino e' corretto.
ciao,
g.

 grosso...)
qual č questa funzione che hai scritto?
sempre tu voglia svelare i segreti del mestiere!
tnx
pazqo

 > è possibile trovare una sequenza arbitrariamente lunga di numeri primi


spoilerate invece di stare così abbottonati sulle vostre...
;-D
Ste

 (da nessuna parte si vieta che "1" e "se stesso" non debbano coincidere).
Spigolatura per spigolatura....
I numeri primi sono definiti come quei numeri naturali maggiori di 1
divisibili solo per 1 e per se stessi.
E' un problema di convenzione per semplificare un po' le cose (per esempio
l'enunciato del teorema fondamentale dell'algebra che afferma che ogni
numero intero è scomponibile nel prodotto di numeri primi in maniera
univoca).
Per non fare una mail con solo questa pignoleria ho pensato di farvi
partecipi di questo bel numero:
N=100000......0007=10^60+7
è primo, contiene 61 cifre e, togliendo una cifra per volta a sinistra,
continua a rimanere sempre primo.
E cosi batto Giovanni Resta!!!!
:o))))))))
Ciao,
GaS

 sempre tu voglia svelare i segreti del mestiere!
Sai che segreti ! non e' particolarmente meditato,
giusto per avere rapidamente il risultato:
nextset[S_] := Block[{newS = {}, mul = 10^Ceiling[Log[10, S[[1]]]]},
  Do[If[PrimeQ[mul j + S[[i]]], newS = Append[newS, mul j+S[[i]]]], 
{j,9}, {i, Length[S]}]; newS];
s[1] = {3, 7}; t = 1;
While[Length[s[t]] > 0,
    Print[{t, Length[s[t]], s[t][[1]]}]; t++;
    s[t] = nextset[s[t - 1]]];
Print["Totale = ",2+Sum[Length[s[i]], {i, 1, t}]]
La funzione nextset[S_] prende una lista di numeri
con lo stesso numero di cifre (che godono della
proprieta') e prova a aggiungere una cifra in testa
e restituisce la lista dei numeri cosi' ottenuti
(tutti quelli lunghi una cifra in piu').
Le istruzioni sotto inizializzano il primo set
(quello dei numeri di una cifra) a
s[1]={3,7};
poi itera, definendo ogni set in funzione di quello
precedente fino a che i set non diventano vuoti.
Per ogni ciclo, stampa
{numero di cifre, quanti numeri soddisfano, esempio di numero}
Alla fine somma quanti numeri in totale sono costruibili,
e aggiunge 2 per tener conto di 2 e 5.
L'output e'
{1, 2, 3}
{2, 11, 13}
{3, 39, 113}
{4, 99, 1223}
{5, 192, 12113}
{6, 326, 121283}
{7, 429, 1237547}
{8, 521, 12184967}
{9, 545, 124536947}
{10, 517, 1219861613}
{11, 448, 12181833347}
{12, 354, 121339693967}
{13, 276, 1213536676883}
{14, 212, 12673876537547}
{15, 117, 121848768729173}
{16, 72, 1275463876537547}
{17, 42, 12429121339693967}
{18, 24, 165678739293946997}
{19, 13, 1276812967623946997}
{20, 6, 15396334245663786197}
{21, 5, 315396334245663786197}
{22, 4, 5918918997653319693967}
{23, 3, 57686312646216567629137}
{24, 1, 357686312646216567629137}
Totale = 4260
quindi ci sono 11 numeri di 2 cifre, 39 di 3 cifre, etc.etc.
Per ottenere i 5 numeri di 31 cifre che si possono ottenere invece
aggiungendo ad ogni passo 1 cifra a destra o a sinistra ho scritto un 
programmino in C, usando la libreria gmp per i numeri interi in 
precisione arbitraria. In quel caso, temendo che ci fossero troppi
numeri, ho usato una soluzione simil-ricorsiva (simulata con uno stack)
senza quindi produrre esplicitamente i vari set ad ogni passo.
ciao,
g.

 (da nessuna parte si vieta che "1" e "se stesso" non debbano coincidere).
Ti hanno insegnato male.
Per "definizione" 1 non e' primo.
Il motivo fondamentale e' che questo semplifica
l'enunciato di parecchi teoremi (e quindi la loro dimostrazione).
L'esempio principale e' costituito dal teorema che afferma
che ogni numero intero puo' essere fattorizato in un unico
modo in fattori primi (ordine dei fattori a parte).
Questo teorema e' poi la base di innumerevoli altri.
Se 1 fosse considerato primo allora il teorema non potrebbe valere cosi'
nella sua forma piu' semplice, ma bisognerebbe ogni volta
aggiungere dei "distinguo" per evitare di considerare fattorizzazioni
del tipo 6=3*2=3*2*1=3*2*1*1 etc.
Quindi per semplicita' la cosa migliore e' definire 1 come
numero speciale che non e' ne' composto ne' primo
e a quel punto le cose si semplificano.
ciao.
g.

vabbè...
così sarà pure più preciso...
ma stiamo parlando del sesso degli angeli (come soleva dire il professore
che mi ha insegnato che 1 era un numero primo ^_^)
ciao,
  Ste