[A25-10] Il più grande fattore primo di n2+1

[Quelo]

I numeri del tipo n2+1, con n naturale, formano la sequenza:

2, 5, 10, 17, 26, 37, 50, 65, 82, 101, 122, 145, 170, 197, 226, ...

Ecco una domanda molto difficile, ancora senza risposta:

Quanti sono i numeri primi del tipo n2+1?

La mia domanda, qui, è più semplice.

Usate il vostro linguaggio di programmazione preferito per trovare ed elencare i numeri primi p del tipo p = n2+1.

E se n2+1 non è primo, quanto è grande il suo fattore più grande? (così almeno sapete a che punto fermarvi facendo il test di primalità).

Rispondiamo alla prima domanda con (Python):

Codice: Seleziona tutto

from primality.primality import isprime as isp
print([n**2+1 for n in range(100) if isp(n**2+1)]

Risultato:
[2, 5, 17, 37, 101, 197, 257, 401, 577, 677, 1297, 1601, 2917, 3137, 4357, 5477, 7057, 8101, 8837]

Python dispone di un modulo con il test di primalità, ma se vogliamo farcelo in casa è sufficiente:

Codice: Seleziona tutto

def isprime(n):
    p = n>1
    for d in range(2,int(n**.5+1)): p &= n%d!=0
    return p

Estendendo la ricerca

Codice: Seleziona tutto

from primality.primality import isprime as isp
from time import time

z = time()
n = 0
t = 1		# tempo di eleborazione

while time()<z+t:
    n += 1
    if isp(n**2+1): m = n

print(f't={time()-z:.0f} sec. {m=}, {m**2+1=}')

Risultati:
t=1 sec. m=114024, m**2+1=13001472577
t=10 sec. m=881324, m**2+1=776731992977
t=60 sec. m=4776640, m**2+1=22816289689601

Per la seocnda domanda aggiungiamo una routine per la ricerca dei fattori primi

Codice: Seleziona tutto

def factors(n):
    f = []; e = 0
    for i in range(2,n//2+1):
        while n%i==0: e += 1; n //= i
        if e>0: f.append((i,e)); e = 0
        if isp(n): f.append((n,1)); break
    return f
    
Risultati:
t=600 sec. n=43737136, n**2+1=1912937065482497
max factor of (n-1)**2+1=1912936978008226 = 4078301