Test di primalità e fattorizzazione di Lepore

[P_1_6]

Ho pensato a questa soluzione però non so risolvere questo sistema

$X*10000000-Z*45459487=3*4540513+500000$

${(INTERO)[100000000/(Z*10+3)]} *X=45459487$

per $(INTERO)$ intendo parte intera

qualcuno potrebbe darmi una mano

EDIT
l'ho risolta ma non porta a niente

$4836929/(10*Z+3)$

ma ho un'altra idea di trovare il fattore una cifra alla volta
ora non ho tempo ma riflettete su questo

$X*10000000−Z*45459487=3*4540513+500000$
$(X*10000000−Z*45459487)/100=X*(100000-(1000000/(Z*10+3))*Z+1)$
ho fatto tutti questi calcoli per portare un numero all'ultimo 1 che è un approssimazione

l'idea sembra buona

[P_1_6]

Per chi ha seguito il post e non

siamo giunti quà
$p*10^7-Z*45459487=$

ora conoscendo il numero delle cifre di $p$
e conoscendo che $p>4545$
possiamo dedurre
$p*10^7 - 45459487*(10^3)=$un numero qualsiasii
$(+-p+-H)+$il restante ricordate
$H$ e $p$ sono uguali

FINE

EDIT:

Ovviamente non è la fine la fine è questa

$p*10^7 - 45459487*(10^3)=$un numero qualsiasii

dobbiamo conoscre di quante cifre è la differenza

$H$ e $p$ sono uguali

e agire una o più cifre alla volta


EDIT

per fattorizzare un numero n impiego al massimo
[2^al numero delle cifre di sqrt(n)]
è un buon risultato ?

[P_1_6]

Test di primalità e fattorizzazione di Lepore


L'idea è che un numero n=p*q e n ha Cn cifre e p Cp cifre inserite nel algoritmo di Euclide per il calcolo del massimo comun divisore in questo modo
Euclide[ p*(10^(Cn-Cp)) , n] ad un certo punto le Cp cifre davanti scompaiono quindi scompariranno.
Quindi avremo un albero binario che avrà come radice p*(10^(Cn-Cp))-n=A
non sapendo se n>A
al primo livello lato destro avremo
da un lato p*(10^(Cn-Cp))-2n=B
e al primo livello lato sinistro
n-A=C
al secondo livello partendo da destra avremo
p*(10^(Cn-Cp))-3n=D
n-B
n-2A
A-C
e così via
Dal fatto che ogni risultato del algoritmo di Euclide è maggiore di 0 possiamo stabilire valori massimi e valori minimi per p e scegliere la strada giusta,
in più per scegliere la quantità di strada giusta si usa la tecnica della ricerca binaria


In questo esempio non percorrerò tutte le strade perchè faccio tutto a mano
ma è per spiegare il metodo

ESEMPIO

20737

massimo per p =sqrt(20737)=144,.....
minimo=1

Livello 0
p*10^3-20737=(p-21)*10^3+263 si testa 20737 modulo 21 == 0
siccome p-21>0 avremo
massimo = 144,...
minimo =21

Livello 1 lato sinisro
20737-[(p-21)*10^3+263]=(-p+41)*10^3+474 si testa 20737 modulo 41 == 0
siccome -p+41>0
massimo=41
minimo =21

Livello 2 lato sinistro figlio del 1 livello lato sinistro
[(p-21)*10^3+263]-(-p+41)*10^3+474=(2p-63)*10^3+789 63/2 [STRADA DA PERCORRERE CHE SI RIVELERA' CHIUSA]

Livello 2 lato destro figlio del 1 livello lato sinistro
20737-2*[(p-21)*10^3+263]=(-2p+62)*10^3+211 si testa 20737 modulo (62/2) == 0
massimo =31
minimo = 21

Livello 3 lato sinistro figlio del 2 livello lato destro figlio del 1 livello lato sinistro
[(p-21)*10^3+263]-[(-2p+62)*10^3+211]=(3p-93)*10^3+52
massimo 31
minimo 31
[STRADA CHIUSA]

Livello 3 lato destro figlio del 2 livello lato destro figlio del 1 livello lato sinistro
20737-3*[(p-21)*10^3+263]=(-3p+82)*10+948 82/3 [STRADA DA PERCORRERE CHE SI RIVELERA' CHIUSA]


[qui vi farò vedere la ricerca binaria che non vi ho fatto vedere fino ad adesso per non confondervi]
[vi farò vedere che al 5 livello non è buona la strada mentre fino al 4 si]

Livello 4 lato destro figlio di tutti destri
p*10^3-4*20737=(p-83)*10^3+052 si testa 20737 modulo 83 == 0
massimo 144
minimo 83

Livello 5 lato destro figlio di tutti destri
p*10^3-5*20737=(p-104)+315 si testa 20737 modulo 104 == 0
massimo 144
minimo 104

Livello 6 lato sinistro figlio di tutti destri
20737-[(p-104)*10^3+315]=(-p+124)*10^3+422 si testa 20737 modulo 124 == 0
massimo =124
minimo =104

Livello 7 lato sinistro figlio del livello 6 lato sinistro figlio di tutti destri
(p-104)*10^3+315-[(-p+124)*10^3+422]=(2p-229)*10^3+893 229/2 [STRADA DA PERCORRERE CHE SI RIVELERA' CHIUSA]

Livello 7 lato destro figlio del livello 6 lato sinistro figlio di tutti destri
20737-2*[(p-104)*10^3+315]=(-2p+228)*10^3+107 si testa 20737 modulo 114 == 0
massimo =114
minimo =104

Livello 8 lato sinistro figlio del livello 7 lato destro figlio del livello 6 lato sinistro figlio di tutti destri
[(p-104)*10^3+315]-[(-2p+228)*10^3+107]=(3p-332)*10^3+208 332/3 [STRADA DA PERCORRERE CHE SI RIVELERA' CHIUSA]

Livello 8 lato destro figlio del livello 7 lato destro figlio del livello 6 lato sinistro figlio di tutti destri
20737-3*[(p-104)*10^3+315]=(-3p+331)*10^3+792 331/3 [STRADA DA PERCORRERE CHE SI RIVELERA' CHIUSA]

Livello 5 lato sinistro

ecc.ecc

La strada giusta che troveremo è quetsa

20737-3*[(p-83)*10^3+052]=(-3p+269)*1000+581

(p-83)*10^3+052-2*[(-3p+269)*10^10^3+581]=(7p-623)+890 si testa 20737 modulo 623/7=89 ==0 e va bene

Perchè usare la ricerca binaria?
Perchè si potrebbe verificare questo

Esempio

45459487

45610000-45459487=150513

45459487/150513=302


Con i numeri piccoli non si vede la velocità del algoritmo

Che complessità ha questo algoritmo?

Ovviamente c'è da moltiplicare la complessità che mi direte per il numero di cifre di sqrt(n) in quanto non sappiamo il fattore di quante cifre è

P.s. Spero di non aver commesso errori

[P_1_6]

Vediamo un metodo per fattorizzare un numero

Vediamo tutti i procedimenti da fare per fattorizzare $45459487=p*q$

La prima cifra $4$ + $1$ ci da la forma di $p$ cioè $p=5Z-C$

imponiamo $5Z-C=1$ e avremo la forma di $C$ ovvero $5m-1$

togliamo la prima cifra al numero da fattorizzare e cioè $5459487$ e facciamo $10000000-5459487=4540513$

poi $4540513* [(Intero)(10000000/4540513+1)]=13621539$

poi $13621539-10000000=3621539$

quindi $C*3621539-K*4540513=4540513*n+458643$

la $n$ può assumere in questo caso valori da $0$ a $10$ poichè

$p*10000000-(Z*45459487)=4540513*n+458643$

infatti $45459487/4540513=10,....$

quindi andremo a provare tutti i valori di $n$ possibili

nel nostro caso $n=3$

andando a mettere in $C*3621539-K*4540513=4540513*n+(C*3621539)mod(4540513)$

$((C*3621539-(C*3621539)mod(4540513))/4540513=(K+n)$

i valori possibili di $C$ vediamo che $K+n$ si muove di $4$ in $4$ e che $(K+n)mod(4)=2$

quindi $K+n$ lo scriviamo come $4s-2$


analogamente andando a mettere in $4540513*n+(C*3621539)mod(4540513)=(Z)*4540513-C*10000000$

i valori possibili di $C$ vediamo che $Z$ si muove di $11$ in $11$ e che $(Z)mod(11)=2$

quindi $Z$ lo scriviamo come $11t+2$

Ho notato che $s=m=t$ (Questo pezzo potrebbe non essere giusto ancora non lo provo)

Quindi possiamo procedere così

$C*3621539-K*4540513=4540513*n+(C*3621539)mod(4540513)$

$(11*s+2)*4540513-(5*s-1)*10000000=3*4540513 +500000 $

$s=100,....$

e ovviamente scalando si arriva a $s=91$

quindi $p=5Z-C=55s+10-5s+1=50s+11=4561$

------------------------------------------------------------------------------------------------------------------------------------
EDIT:

Questo numero $(C*3621539)mod(4540513)$ è di 7 cifre

se becchiamo le prime 2 cifre avremo

$(11*s+2)*4540513-(5*s-1)*10000000=3*4540513+500000$

quindi $s=91,....$

quindi troveremo il nostro s in al massimo $45*11=495$ in effetti lo troveremo a $5*11=55$

l'$11$ ricordate sono i possibili valori di $n$



Qual'è la complessità computazionale di questo algoritmo?


-----------------------------------------------------------------------------------------------------------------------------------
EDIT
Per questo numero

$140089267639071478002348819284711337427$

si avrà questa soluzione

$(3*X+646278519063201834)*59910732360928521997651180715288662573-(2*X-1)*100000000000000000000000000000000000000=30000000000000000000000000000000000000$

in $30*3=90$ da osservare che $n=0$

dovrebbe essere al massimo

$59*3=177$

$3$ è il valore di n che può assumere valori $0$,$1$,$2$

guardare

$(11*s+2)*4540513-(5*s-1)*10000000=3*4540513+500000$

vi ricordate che il problema era individurae il $2$
bene se la dentro superiamo il $2$ si avrà che p supera la radice quadrata
infatti
$(11*s+3)*4540513-(5*s-1)*10000000=3*4540513+500000$
$s=174,77$
$p=5Z-C=55s+15-5s+1=50s+16=8754,.....$
quindi avremo il nostro bel logaritmo

Vi prego datemi conferma.

[P_1_6]

-----------------------------------------------------------------------------------------------------------------------------------
EDIT
Per questo numero

$140089267639071478002348819284711337427$

si avrà questa soluzione

$(3*X+646278519063201834)*59910732360928521997651180715288662573-(2*X-1)*100000000000000000000000000000000000000=30000000000000000000000000000000000000$

Ho notato che questo valore $646278519063201834$ cresce costantemente quindi sostituendo in $C=(2*X-1)$ ad esempio il
valore $10^19$ si avrà $169150018022750097$ quindi avremo


$(3*X+|169150018022750097*(2*X-1)/(10^18)|+2)*59910732360928521997651180715288662573−(2*X−1)⋅10^38=((2*X-1)*19821464721857043995302361430577325146)mod (59910732360928521997651180715288662573)$


Per $|169150018022750097*(2*X-1)/(10^18)|$ intendo la parte intera

che non so risolvere
quindi se sapete risolvere questa equazione avrete la fattorizzazzione in un tempo costante $O(K)$

EDIT:
ho modificato

EDIT 2:
si potrebbe anche approssimare facendo crescere il 10^19 e il 10^18 ad esempio portandoli a 10^100 e 10^99
ma purtroppo non riesco a fare questi calcoli con gli strumenti che ho

Edit 3:
Dopo l'aiuto di http://math.stackexchange.com/users/1827/ross-millikan che mi ha detto che quella non si poteva risolvere sono giunto qui

$(3*X+\lfloor 169150018022750097*(2*X−1)/10^18 \rfloor+2)*59910732360928521997651180715288662573−(2*X−1)*10^38=3*10^37$

EDIT4
Per la soluzione guardare
viewtopic.php?f=26&t=164206

EDIT5:
non guardare EDIT3 e per il numero $45459487$ grazie al aiuto EDIT4
ho scoperto una nuova cosa
$(11*x+(x-8)/83+1)$ qua dentro il $+1$ varia di poco in generale
quindi risolvendo questa
$(11*x+(x-8)/83+1)*4540513-(5*x-1)*10^7=3*4540513+((5*x-1)*3621539)-((\lfloor((5*x-1)*3621539)/(4540513)\rfloor)*4540513)$
si ha la soluzione

[P_1_6]

Vediamo un metodo per fattorizzare un numero

Vediamo tutti i procedimenti da fare per fattorizzare $45459487=p*q$

La prima cifra $4$ + $1$ ci da la forma di $p$ cioè $p=5Z-C$

imponiamo $5Z-C=1$ e avremo la forma di $C$ ovvero $5s-1$

togliamo la prima cifra al numero da fattorizzare e cioè $5459487$ e facciamo $10000000-5459487=4540513$

poi $4540513* [(Intero)(10000000/4540513+1)]=13621539$

poi $13621539-10000000=3621539$

quindi $C*3621539-K*4540513=n*4540513+(C*3621539)mod(4540513)$

la $n$ può assumere in questo caso valori da $0$ a $10$ poichè

$p*10000000-(Z*45459487)=4540513*n+(C*3621539)mod(4540513)$

infatti $45459487/4540513=10,....$

quindi andremo a provare tutti i valori di $n$ possibili

nel nostro caso $n=3$ (ma non lo sappiamo)

in più si puo notare che $(C*3621539)mod(4540513) < 4540513$

quindi prendendo le prime $2$ cifre andremo da $0$ a $45$

quindi $46$

ma non spaventatevi da $11*46$ in quanto è costante di ordine per ogni numero

infatti se $11$ diventa $12$ diminuisce di una cifra l altro

andando a mettere in $(Z)*4540513-C*10000000=4540513*n+(C*3621539)mod(4540513)$

i valori possibili di $C$ vediamo che $Z$ si muove di $11$ in $11$

quindi $Z$ lo scriviamo come $11s+Y$ e $C=5s-1$

Quindi quando siamo nel nostro caso cioè

$(11*s+Y)*4540513-(5*s-1)*10000000=3*4540513+500000$

avremo

$(11*s+Y)*4540513-(5*s-1)*10000000=3*4540513+((5s-1)*3621539)mod(4540513)$

andando a sostituire un numero al posto di $5s-1$ ad esempio $10^20$

quindi si avrà $Y=239431095120749572$

quindi si avrà

$(11*x+\lfloor239431095120749572*(5*x-1)/10^20\rfloor+1)*4540513-(5*x-1)*10^7=3*4540513+500000$

Con la spiegazione di piercammello che riporto integralmente

*******************************************************************************************
ok allora vediamo insieme come risolverla, ma solo per darti spunti in merito alla parte intera.
Vediamo di calcolare prima la quantità entro l'operatore "parte intera" e cioè:
$239431095120749572*(5*x-1)/(10^{20})$
la divisione tra $239431095120749572$ e $(10^{20})$
da come risultato il decimale:
$0.00239431095120749$
quindi l'espressione diventa:
$239431095120749572*(5*x-1)/(10^{20})= 0.00239431095120749*(5*x-1)$
con altro passaggio abbiamo:
$0.0119715547560375*x - 0.00239431095120749$
vogliamo per adesso tenerci solo tre cifre significative per evitare di rendere illeggibile il topic?
Ed allora scriviamo
$0.0120 *x - 0.00239$
che in notazione esponenziale diventa:
$1.2e-3*x-2.39e-4$
Il secondo numero noterai che è di un ordine di grandezza inferiore rispetto al coefficiente della $x$
Cerchiamo adesso di capire la parte intera che sarà per forza di cosa un numero naturale.
Finchè il risultato di questa espressione di mantiene inferiore ad 1 (ma comunque maggiore di zero) allora la sua parte intera sarà banalmente 0 (sempre se non assume valore negativo. Ricorda che la parte intera di $-1.25$ non è $-1$ bensi $-2$)
Lasciamo perdere per adesso la questione dei valori negativi ed occupiamoci dei positivi.
Per poter portare quel $0.0120$ ad un numero maggiore di 1 occorre che $x$ sia del'ordine del $10^2$ cioe un centinaio o giù di li.
Ma noi non possiamo andarci per tentativi e quindi forse ci conviene impostare una uguaglianza per capire per quale valore di $x$ scatta altro intero
$0.0120 *x - 0.00239=1$
che risolta ci da:
$x=(1+ 0.00239)/0.0120 =83.73$
Ma ci serve anche capire quando vale $x$ per cui si va nei negativi. Quindi
$0.0120 *x - 0.00239=0$
da cui:
$x= 0.00239/0.0120 =0.2$
Questo significa che per $0.2<=x<83.73$
l'espressione $0.0119715547560375*x - 0.00239431095120749$, da come risultato zero.
*********************************************************************************************

Siccome $sqrt(45459487)$ è il massimo valore per $p$ e $p$ e nella forma $5*Z-C$ dobbiamo dividere per $5$

e siccome $c=5*s-1$ dobbiamo sottrarre $1$ e dividere per $5$ il tutto per avere il massimo valore per $s$

$((sqrt(45459487)/5)-1)/5=269$

quindi l'intervallo per $s$ è $[0,269]$

$269/83,...=3$

quindi avremo quattro possibili valori per $Y$ e cioè $0,1,2,3$

che sono troppi

quindi sostituiamo $x=10^18$ in

$(11*x+Y)*4540513-(5*x-1)*10^7-3*4540513=((5*x-1)*3621539)mod(4540513)$

e avremo $Y=11971554756037480$

$(11*x+\lfloor11971554756037480*(5*x-1)/10^18\rfloor-3)*4540513-(5*x-1)*10^7=3*4540513+500000$

si avrà la soluzione $91.2392$

ci rimane da capire quel $-3$

[P_1_6]

-----------------------------------------------------------------------------------------------------------------------------------
EDIT
Per questo numero

$140089267639071478002348819284711337427$

si avrà questa soluzione

$(3*X+646278519063201834)*59910732360928521997651180715288662573-(2*X-1)*100000000000000000000000000000000000000=30000000000000000000000000000000000000$

ho notato grazie a piercammello che guardando le variazioni di valore di $X$ si può arrivare alla soluzione di questo numero
in $1665$ step per una costante
io ho approssimato perchè non so calcolare la variabile nel modulo

dovremmo vedere le soluzioni di questa
$(3*X+1)*59910732360928521997651180715288662573−(2*X−1)*10^38=((2*X-1)*19821464721857043995302361430577325146)mod (59910732360928521997651180715288662573)$

e confrontarla con la soluzione di questa
$(3*X+1)*59910732360928521997651180715288662573−(2*X−1)*10^38=3*10^37$

e scegliere quella del modulo

comunque vi faccio vedere con le approssimazioni

$(3*X+1)*59910732360928521997651180715288662573−(2*X−1)*10^38=3*10^37$
$X=6.4097096706$
$(3*X+2)*59910732360928521997651180715288662573−(2*X−1)*10^38=3*10^37$
$X=9.3656656075$
$9.3656656075 - 6.4097096706 =2.9559559369$

$(3*X+2.9559559369*1)*59910732360928521997651180715288662573−(2*X−1)*10^38=3*10^37$
$X=12.191429235$
$(3*X+2.9559559369*2)*59910732360928521997651180715288662573−(2*X−1)*10^38=3*10^37$
$X=20.92910735$
$20.92910735 - 12.191429235 =8.737678115$

$(3*X+2.9559559369*8.737678115*1)*59910732360928521997651180715288662573−(2*X−1)*10^38=3*10^37$
$X=79.8007$
$(3*X+2.9559559369*8.737678115*2)*59910732360928521997651180715288662573−(2*X−1)*10^38=3*10^37$
$X=156.148$
$156.148 - 79.8007 = 76.3473$

$(3*X+2.9559559369*8.737678115*76.3473*1)*59910732360928521997651180715288662573−(2*X−1)*10^38=3*10^37$
$X=5832.34$
$(3*X+2.9559559369*8.737678115*76.3473*2)*59910732360928521997651180715288662573−(2*X−1)*10^38=3*10^37$
$X=11661.2$
$11661.2 - 5832.34 =5828.68$

$(3*X+2.9559559369*8.737678115*76.3473*5828.68*1)*59910732360928521997651180715288662573−(2*X−1)*10^38=3*10^37$
$X=33974720.577844091$
$(3*X+2.9559559369*8.737678115*76.3473*5828.68*2)*59910732360928521997651180715288662573−(2*X−1)*10^38=3*10^37$
$X=67949437.701934449$
$67949437.701934449 - 33974720.577844091 =33974717.124090358$

$(3*X+2.9559559369*8.737678115*76.3473*5828.68*33974717.124090358*1655)*59910732360928521997651180715288662573−(2*X−1)*10^38=3*10^37$
$X=1910335723060541440$
Quello che cercavamo è $1910370825311646108$

Se avessimo usato il modulo le due combacerebbero

[P_1_6]

Vediamo un metodo per fattorizzare un numero

Vediamo tutti i procedimenti da fare per fattorizzare $45459487=p*q$

La prima cifra $4$ + $1$ ci da la forma di $p$ cioè $p=5Z-C$



togliamo la prima cifra al numero da fattorizzare e cioè $5459487$ e facciamo $10000000-5459487=4540513$

poi $4540513* [(Intero)(10000000/4540513+1)]=13621539$

poi $13621539-10000000=3621539$

quindi $C*3621539-K*4540513=n*4540513+(C*3621539)mod(4540513)$

la $n$ può assumere in questo caso valori da $0$ a $10$ poichè

$p*10000000-(Z*45459487)=4540513*n+(C*3621539)mod(4540513)$

infatti $45459487/4540513=10,....$

quindi andremo a provare tutti i valori di $n$ possibili

nel nostro caso $n=3$ (ma non lo sappiamo)

in più si puo notare che $(C*3621539)mod(4540513) < 4540513$

quindi prendendo le prime $2$ cifre andremo da $0$ a $45$

quindi $46$

ma non spaventatevi da $11*46$ in quanto è costante di ordine per ogni numero

infatti se $11$ diventa $12$ diminuisce di una cifra l altro

quindi $(Z)*4540513-C*10000000=4540513*n+(C*3621539)mod(4540513)$

quindi quando ci troviamo nel caso $n =3$ e le prime due cifre di cui vi parlavo sono 05

ci troveremo la sequenza che si ripete , i salti e proveremo per tutti i salti
viewtopic.php?f=26&t=164364

in questo caso c'è un salto nell'intervallo $[0,1348]$ ma noi troveremo i nostri valori prima del primo e unico salto

abbiamo quasi finito ci manca un'ultima cosa
\begin{equation}
\begin{cases}
Z*4540513-(D*84+5+29)*10^7-3*4540513=((D*84+5+29)*3621539)mod(4540513)
\\
[3*4540513+(((D*84+5+29)*3621539)mod(4540513) ) ]mod (5*Z-(D*84+5+29))=0
\end{cases}
\end{equation}


risolto questo si ha la fattorizzazione di 45459487
che è $(5*Z-(D*84+5+29))$
$Z=1003$
$D=5$

qualcuno gentilmente mi aiuta a risolverla

EDIT: ho modificato

[P_1_6]

Ulteriori passi in avanti
Abbiamo visto il caso $(6a+1)*(6b+1)=6*G+1$

Ora vedremo $(6a+5)*(6b+1)=6*G+5$
dove andremoa trovarci $q$ anzichè $p$

$1489999*890003=1326103579997$

$q=2Z-C$

$A= 673896420003 $
$B= 347792840006 $

$n =1$
$m 67$

quando ci troviamo nel caso
$n=1$
e le prime due cifre sono $27$ quindi l'intervallo è
$[270000000000 , 280000000000]$

quindi dobbiamo vedere

\begin{equation}
\begin{cases}
(347792840006*X) mod (673896420003)>270000000000
\\
(347792840006*X) mod (673896420003)<280000000000
\end{cases}
\end{equation}

Ho notato che si ripete sempre la stessa sequenza anche del salto
la sequenza è $31;31;31;31;31;31;31;31;31;31;31;31;498$
però ovviamente la prima volta ha un $31$ in meno (il primo) sostituito da $119$
come si può osservare
vediamo la sequenza completa

inizialmente è $4;2;2$
ora vi mostro


$4$

Codice:

valore=279666340531           i=119          salto=119
valore=278901660669           i=150          salto=31
valore=278136980807           i=181          salto=31
valore=277372300945           i=212          salto=31
valore=276607621083           i=243          salto=31
valore=275842941221           i=274          salto=31
valore=275078261359           i=305          salto=31
valore=274313581497           i=336          salto=31
valore=273548901635           i=367          salto=31
valore=272784221773           i=398          salto=31
valore=272019541911           i=429          salto=31
valore=271254862049           i=460          salto=31
valore=270490182187           i=491          salto=31
valore=279944564404           i=989          salto=498
valore=279179884542           i=1020          salto=31
valore=278415204680           i=1051          salto=31
valore=277650524818           i=1082          salto=31
valore=276885844956           i=1113          salto=31
valore=276121165094           i=1144          salto=31
valore=275356485232           i=1175          salto=31
valore=274591805370           i=1206          salto=31
valore=273827125508           i=1237          salto=31
valore=273062445646           i=1268          salto=31
valore=272297765784           i=1299          salto=31
valore=271533085922           i=1330          salto=31
valore=270768406060           i=1361          salto=31
valore=270003726198           i=1392          salto=31
valore=279458108415           i=1890          salto=498
valore=278693428553           i=1921          salto=31
valore=277928748691           i=1952          salto=31
valore=277164068829           i=1983          salto=31
valore=276399388967           i=2014          salto=31
valore=275634709105           i=2045          salto=31
valore=274870029243           i=2076          salto=31
valore=274105349381           i=2107          salto=31
valore=273340669519           i=2138          salto=31
valore=272575989657           i=2169          salto=31
valore=271811309795           i=2200          salto=31
valore=271046629933           i=2231          salto=31
valore=270281950071           i=2262          salto=31
valore=279736332288           i=2760          salto=498
valore=278971652426           i=2791          salto=31
valore=278206972564           i=2822          salto=31
valore=277442292702           i=2853          salto=31
valore=276677612840           i=2884          salto=31
valore=275912932978           i=2915          salto=31
valore=275148253116           i=2946          salto=31
valore=274383573254           i=2977          salto=31
valore=273618893392           i=3008          salto=31
valore=272854213530           i=3039          salto=31
valore=272089533668           i=3070          salto=31
valore=271324853806           i=3101          salto=31
valore=270560173944           i=3132          salto=31
valore=279249876299           i=3661          salto=529

successivamente $2$

Codice:

valore=278485196437           i=3692          salto=31
valore=277720516575           i=3723          salto=31
valore=276955836713           i=3754          salto=31
valore=276191156851           i=3785          salto=31
valore=275426476989           i=3816          salto=31
valore=274661797127           i=3847          salto=31
valore=273897117265           i=3878          salto=31
valore=273132437403           i=3909          salto=31
valore=272367757541           i=3940          salto=31
valore=271603077679           i=3971          salto=31
valore=270838397817           i=4002          salto=31
valore=270073717955           i=4033          salto=31
valore=279528100172           i=4531          salto=498
valore=278763420310           i=4562          salto=31
valore=277998740448           i=4593          salto=31
valore=277234060586           i=4624          salto=31
valore=276469380724           i=4655          salto=31
valore=275704700862           i=4686          salto=31
valore=274940021000           i=4717          salto=31
valore=274175341138           i=4748          salto=31
valore=273410661276           i=4779          salto=31
valore=272645981414           i=4810          salto=31
valore=271881301552           i=4841          salto=31
valore=271116621690           i=4872          salto=31
valore=270351941828           i=4903          salto=31
valore=279806324045           i=5401          salto=498
valore=279041644183           i=5432          salto=31
valore=278276964321           i=5463          salto=31
valore=277512284459           i=5494          salto=31
valore=276747604597           i=5525          salto=31
valore=275982924735           i=5556          salto=31
valore=275218244873           i=5587          salto=31
valore=274453565011           i=5618          salto=31
valore=273688885149           i=5649          salto=31
valore=272924205287           i=5680          salto=31
valore=272159525425           i=5711          salto=31
valore=271394845563           i=5742          salto=31
valore=270630165701           i=5773          salto=31
valore=279319868056           i=6302          salto=529

successivamente $2$

Codice:

valore=278555188194           i=6333          salto=31
valore=277790508332           i=6364          salto=31
valore=277025828470           i=6395          salto=31
valore=276261148608           i=6426          salto=31
valore=275496468746           i=6457          salto=31
valore=274731788884           i=6488          salto=31
valore=273967109022           i=6519          salto=31
valore=273202429160           i=6550          salto=31
valore=272437749298           i=6581          salto=31
valore=271673069436           i=6612          salto=31
valore=270908389574           i=6643          salto=31
valore=270143709712           i=6674          salto=31
valore=279598091929           i=7172          salto=498
valore=278833412067           i=7203          salto=31
valore=278068732205           i=7234          salto=31
valore=277304052343           i=7265          salto=31
valore=276539372481           i=7296          salto=31
valore=275774692619           i=7327          salto=31
valore=275010012757           i=7358          salto=31
valore=274245332895           i=7389          salto=31
valore=273480653033           i=7420          salto=31
valore=272715973171           i=7451          salto=31
valore=271951293309           i=7482          salto=31
valore=271186613447           i=7513          salto=31
valore=270421933585           i=7544          salto=31
valore=279876315802           i=8042          salto=498
valore=279111635940           i=8073          salto=31
valore=278346956078           i=8104          salto=31
valore=277582276216           i=8135          salto=31
valore=276817596354           i=8166          salto=31
valore=276052916492           i=8197          salto=31
valore=275288236630           i=8228          salto=31
valore=274523556768           i=8259          salto=31
valore=273758876906           i=8290          salto=31
valore=272994197044           i=8321          salto=31
valore=272229517182           i=8352          salto=31
valore=271464837320           i=8383          salto=31
valore=270700157458           i=8414          salto=31
valore=279389859813           i=8943          salto=529


poi si ripete sempre $4;2;2$; fino a $694607$
dove inizierà a ripetersi $1;2;2;2$

$1$

Codice:

valore=278678952199           i=694607          salto=31
valore=277914272337           i=694638          salto=31
valore=277149592475           i=694669          salto=31
valore=276384912613           i=694700          salto=31
valore=275620232751           i=694731          salto=31
valore=274855552889           i=694762          salto=31
valore=274090873027           i=694793          salto=31
valore=273326193165           i=694824          salto=31
valore=272561513303           i=694855          salto=31
valore=271796833441           i=694886          salto=31
valore=271032153579           i=694917          salto=31
valore=270267473717           i=694948          salto=31
valore=279721855934           i=695446          salto=498
valore=278957176072           i=695477          salto=31
valore=278192496210           i=695508          salto=31
valore=277427816348           i=695539          salto=31
valore=276663136486           i=695570          salto=31
valore=275898456624           i=695601          salto=31
valore=275133776762           i=695632          salto=31
valore=274369096900           i=695663          salto=31
valore=273604417038           i=695694          salto=31
valore=272839737176           i=695725          salto=31
valore=272075057314           i=695756          salto=31
valore=271310377452           i=695787          salto=31
valore=270545697590           i=695818          salto=31
valore=279235399945           i=696347          salto=529


$2$

Codice:

valore=278470720083           i=696378          salto=31
valore=277706040221           i=696409          salto=31
valore=276941360359           i=696440          salto=31
valore=276176680497           i=696471          salto=31
valore=275412000635           i=696502          salto=31
valore=274647320773           i=696533          salto=31
valore=273882640911           i=696564          salto=31
valore=273117961049           i=696595          salto=31
valore=272353281187           i=696626          salto=31
valore=271588601325           i=696657          salto=31
valore=270823921463           i=696688          salto=31
valore=270059241601           i=696719          salto=31
valore=279513623818           i=697217          salto=498
valore=278748943956           i=697248          salto=31
valore=277984264094           i=697279          salto=31
valore=277219584232           i=697310          salto=31
valore=276454904370           i=697341          salto=31
valore=275690224508           i=697372          salto=31
valore=274925544646           i=697403          salto=31
valore=274160864784           i=697434          salto=31
valore=273396184922           i=697465          salto=31
valore=272631505060           i=697496          salto=31
valore=271866825198           i=697527          salto=31
valore=271102145336           i=697558          salto=31
valore=270337465474           i=697589          salto=31
valore=279791847691           i=698087          salto=498
valore=279027167829           i=698118          salto=31
valore=278262487967           i=698149          salto=31
valore=277497808105           i=698180          salto=31
valore=276733128243           i=698211          salto=31
valore=275968448381           i=698242          salto=31
valore=275203768519           i=698273          salto=31
valore=274439088657           i=698304          salto=31
valore=273674408795           i=698335          salto=31
valore=272909728933           i=698366          salto=31
valore=272145049071           i=698397          salto=31
valore=271380369209           i=698428          salto=31
valore=270615689347           i=698459          salto=31
valore=279305391702           i=698988          salto=529

$2$

Codice:

valore=278540711840           i=699019          salto=31
valore=277776031978           i=699050          salto=31
valore=277011352116           i=699081          salto=31
valore=276246672254           i=699112          salto=31
valore=275481992392           i=699143          salto=31
valore=274717312530           i=699174          salto=31
valore=273952632668           i=699205          salto=31
valore=273187952806           i=699236          salto=31
valore=272423272944           i=699267          salto=31
valore=271658593082           i=699298          salto=31
valore=270893913220           i=699329          salto=31
valore=270129233358           i=699360          salto=31
valore=279583615575           i=699858          salto=498
valore=278818935713           i=699889          salto=31
valore=278054255851           i=699920          salto=31
valore=277289575989           i=699951          salto=31
valore=276524896127           i=699982          salto=31
valore=275760216265           i=700013          salto=31
valore=274995536403           i=700044          salto=31
valore=274230856541           i=700075          salto=31
valore=273466176679           i=700106          salto=31
valore=272701496817           i=700137          salto=31
valore=271936816955           i=700168          salto=31
valore=271172137093           i=700199          salto=31
valore=270407457231           i=700230          salto=31
valore=279861839448           i=700728          salto=498
valore=279097159586           i=700759          salto=31
valore=278332479724           i=700790          salto=31
valore=277567799862           i=700821          salto=31
valore=276803120000           i=700852          salto=31
valore=276038440138           i=700883          salto=31
valore=275273760276           i=700914          salto=31
valore=274509080414           i=700945          salto=31
valore=273744400552           i=700976          salto=31
valore=272979720690           i=701007          salto=31
valore=272215040828           i=701038          salto=31
valore=271450360966           i=701069          salto=31
valore=270685681104           i=701100          salto=31
valore=279375383459           i=701629          salto=529

$2$

Codice:

valore=278610703597           i=701660          salto=31
valore=277846023735           i=701691          salto=31
valore=277081343873           i=701722          salto=31
valore=276316664011           i=701753          salto=31
valore=275551984149           i=701784          salto=31
valore=274787304287           i=701815          salto=31
valore=274022624425           i=701846          salto=31
valore=273257944563           i=701877          salto=31
valore=272493264701           i=701908          salto=31
valore=271728584839           i=701939          salto=31
valore=270963904977           i=701970          salto=31
valore=270199225115           i=702001          salto=31
valore=279653607332           i=702499          salto=498
valore=278888927470           i=702530          salto=31
valore=278124247608           i=702561          salto=31
valore=277359567746           i=702592          salto=31
valore=276594887884           i=702623          salto=31
valore=275830208022           i=702654          salto=31
valore=275065528160           i=702685          salto=31
valore=274300848298           i=702716          salto=31
valore=273536168436           i=702747          salto=31
valore=272771488574           i=702778          salto=31
valore=272006808712           i=702809          salto=31
valore=271242128850           i=702840          salto=31
valore=270477448988           i=702871          salto=31
valore=279931831205           i=703369          salto=498
valore=279167151343           i=703400          salto=31
valore=278402471481           i=703431          salto=31
valore=277637791619           i=703462          salto=31
valore=276873111757           i=703493          salto=31
valore=276108431895           i=703524          salto=31
valore=275343752033           i=703555          salto=31
valore=274579072171           i=703586          salto=31
valore=273814392309           i=703617          salto=31
valore=273049712447           i=703648          salto=31
valore=272285032585           i=703679          salto=31
valore=271520352723           i=703710          salto=31
valore=270755672861           i=703741          salto=31
valore=279445375216           i=704270          salto=529

e quindi si ripeterà $1;2;2;2$; fino al prossimo salto dei salti

quindi il nostro valore sarà $11*12*31+7*498+4*529=9694$

ora bisognerebbe sapere la posizione del nostro $C$ nella sequenza ma siccome non la conosciamo dovremo provare per tutti i posti della sequenza

fino ad arrivare alla posizione giusta che ho segnato con gli asterischi

Codice:

valore=278689411129           i=752771          salto=31
valore=277924731267           i=752802          salto=31
valore=277160051405           i=752833          salto=31
valore=276395371543           i=752864          salto=31
valore=275630691681           i=752895          salto=31
valore=274866011819           i=752926          salto=31
valore=274101331957           i=752957          salto=31
valore=273336652095           i=752988          salto=31
valore=272571972233           i=753019          salto=31
valore=271807292371           i=753050          salto=31
valore=271042612509           i=753081          salto=31
valore=270277932647           i=753112          salto=31
valore=279732314864           i=753610          salto=498
valore=278967635002           i=753641          salto=31
valore=278202955140           i=753672          salto=31
valore=277438275278           i=753703          salto=31
valore=276673595416           i=753734          salto=31
valore=275908915554           i=753765          salto=31
valore=275144235692           i=753796          salto=31
valore=274379555830           i=753827          salto=31
valore=273614875968           i=753858          salto=31
valore=272850196106           i=753889          salto=31
valore=272085516244           i=753920          salto=31
valore=271320836382           i=753951          salto=31
valore=270556156520           i=753982          salto=31
valore=279245858875           i=754511          salto=529
valore=278481179013           i=754542          salto=31
valore=277716499151           i=754573          salto=31
valore=276951819289           i=754604          salto=31
valore=276187139427           i=754635          salto=31
valore=275422459565           i=754666          salto=31
valore=274657779703           i=754697          salto=31
valore=273893099841           i=754728          salto=31
valore=273128419979           i=754759          salto=31
valore=272363740117           i=754790          salto=31
valore=271599060255           i=754821          salto=31
valore=270834380393           i=754852          salto=31
valore=270069700531           i=754883          salto=31
valore=279524082748           i=755381          salto=498
valore=278759402886           i=755412          salto=31
valore=277994723024           i=755443          salto=31
valore=277230043162           i=755474          salto=31
valore=276465363300           i=755505          salto=31
valore=275700683438           i=755536          salto=31
valore=274936003576           i=755567          salto=31
valore=274171323714           i=755598          salto=31
valore=273406643852           i=755629          salto=31
valore=272641963990           i=755660          salto=31
valore=271877284128           i=755691          salto=31
valore=271112604266           i=755722          salto=31
valore=270347924404           i=755753          salto=31
valore=279802306621           i=756251          salto=498
valore=279037626759           i=756282          salto=31
valore=278272946897           i=756313          salto=31
valore=277508267035           i=756344          salto=31
valore=276743587173           i=756375          salto=31
valore=275978907311           i=756406          salto=31
valore=275214227449           i=756437          salto=31
valore=274449547587           i=756468          salto=31
valore=273684867725           i=756499          salto=31
valore=272920187863           i=756530          salto=31
valore=272155508001           i=756561          salto=31
valore=271390828139           i=756592          salto=31
valore=270626148277           i=756623          salto=31
valore=279315850632           i=757152          salto=529
valore=278551170770           i=757183          *****************************************************

quindi il nostro valore sarà

$5*12*31+3*498+2*529=4412$

quindi avremo $(X-4412-694607)/9694=D$

nel nostro caso $D=6$

si ricostruisce il solito sistema che ancora non so risolvere
e si trovano le soluzioni

$C=757183$
$Z=1123591$


P.s. le sequenze si possono trovare in tempi logaritmici
P.s.2.se c'è un metodo matematico per trovare quelle sequenze gentilmente qualcuno me lo indichi

[P_1_6]

Mi è venuto in mente un altro algoritmo di fattorizzazione.
Ora ve lo mostro:
Ragioniamo su un numero $N=p*q$ prodotto di due primi nella forma $p=6a+1$ e $q=6b+1$
segue che $N=36ab+6a+6b+1$
riscriviamo
$N-1=36ab+6*(a+b)$
quindi $r=(N-1)mod (36)$
quindi $6*(a+b)=K*36+r$

quindi facendo variare il K abbiamo un primo metodo per fattorizzare

Esempio:
$N=101461$
$101460 mod 36 =12$
$6*(a+b)=18*36+12$
dove abbiamo fatto variare il $K$ da $0$ a $18$ quindi $19$ cicli

Ma procediamo
eravamo rimasti
$N=36ab+6a+6b+1$
$6*(a+b)=K*36+r$
quindi ci calcoliamo $a*b$
$a*b=[N-1-(K*36+r)]/36$
quindi
$a*b=(N-1-r)/36-K$
quindi
imponiamo
$a*b=(N-1-r)/36$
perchè $K$ è molto più piccolo di $a*b$

facendo il sistema
$N=36ab+6a+6b+1$
$a*b=(N-1-r)/36$
e partendo dal massimo valore di $(N-1-r)/36$ e che il sistema non abbia soluzioni con parte immaginaria
scalando di una unità

Ve lo spiego con un esempio
Esempio:
$N=101461$
$101460 mod 36 =12$
$6*(a+b)=K*36+12$
$a*b=(N-1-r)/36=2818$

Facciamo il sistema:
$101461=36ab+6a+6b+1$
$a*b=2818$
ed esce la parte immaginaria come si può vedere
https://www.wolframalpha.com/input/?i=1 ... %3D%3D2818

il primo valore valido è da testare senza che nelle soluzioni ci sia la parte immaginaria è 2800
$101461=36ab+6a+6b+1$
$a*b=2800$
https://www.wolframalpha.com/input/?i=1 ... a*b%3D2800
che ci dà la soluzione ma non lasciatevi ingannare, vi mostro un altro esempio dove non è così rapido

Esempio
N=71054743

$71054742 mod 36 = 30$
$a*b=(71054743-1-30)/36=1973742$

quindi il nostro sistema
$71054743=36ab+6a+6b+1$
$a*b=1973742$
https://www.wolframalpha.com/input/?i=a ... ,+(6*a%2B1)*(6*b%2B1)%3D71054743
come si vede abbiamo la parte immaginaria

il primo valore valido è 1973274
$71054743=36ab+6a+6b+1$
$a*b=1973274$
https://www.wolframalpha.com/input/?i=a ... ,+(6*a%2B1)*(6*b%2B1)%3D71054743

Quindi facendo variarare
$1973274$
$1973273$
$1973272$
......
......
arriveremo a $1973268$
$71054743=36ab+6a+6b+1$
$a*b=1973268$
infatti
https://www.wolframalpha.com/input/?i=a ... ,+(6*a%2B1)*(6*b%2B1)%3D71054743

Gentilmente vi chiedo qual'è la complessità computazionale di questo algoritmo?
sperando di non aver commesso errori