mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Math (https://www.mersenneforum.org/forumdisplay.php?f=8)
-   -   Probable primality test for numbers of the form (10^n-1)/9-2 and (10^n+1)/11-2 ? (https://www.mersenneforum.org/showthread.php?t=27800)

 kijinSeija 2022-05-13 20:32

Probable primality test for numbers of the form (10^n-1)/9-2 and (10^n+1)/11-2 ?

Here is what I observed :

For (10^n−1)/9 - 2 :

Let the sequence Si=S^10(i-1)−10*S^8(i−1)+35*S^6(i−1)−50*S^4(i−1)+25*S^2(i−1)−2 with S0=123. Then N is prime if and only if Sn−1≡710647 (modN).

I choose 123 for S0 because this is the 10th Lucas number L10.

For the sequence, I choose the Lucas' polynomial L10(x) and alternate + and − for each part as shown in the sequence or 2^(-10)*[(S - sqrt(S^2 - 4))^10 + (S + sqrt(S^2 - 4))^10].

Interestingly, 710647 is the 28th Lucas Number

For example with (10^9-1)/9-2

[code]
Mod(123, 111111109)
Mod(51829516, 111111109)
Mod(44205291, 111111109)
Mod(61285299, 111111109)
Mod(10762512, 111111109)
Mod(7042864, 111111109)
Mod(86600637, 111111109)
Mod(105924187, 111111109)
Mod(710647, 111111109)
[/code]

And 111111109 is indeed prime.

Now for (10^n+1)/11-2 :

Let the sequence Si=S^10(i-1)−10*S^8(i−1)+35*S^6(i−1)−50*S^4(i−1)+25*S^2(i−1)−2 with S0=123. Then N is prime if and only if Sn-1≡4870847 (modN).

I choose 123 for S0 because this is the 10th Lucas number L10.

For the sequence, I choose the Lucas' polynomial L10(x) and alternate + and − for each part as shown in the sequence or 2^(-10)*[(S - sqrt(S^2 - 4))^10 + (S + sqrt(S^2 - 4))^10].

Interestingly, 4870847 is the 32th Lucas Number

For example with (10^23+1)/11-2 :

[code]
Mod(123, 9090909090909090909089)
Mod(792070839848372253127, 9090909090909090909089)
Mod(7013172659588921898968, 9090909090909090909089)
Mod(5376631768234272959764, 9090909090909090909089)
Mod(5567064784309146947242, 9090909090909090909089)
Mod(4454192417285686785591, 9090909090909090909089)
Mod(3887232900008722268298, 9090909090909090909089)
Mod(5857621439229082751516, 9090909090909090909089)
Mod(8657130616128185619457, 9090909090909090909089)
Mod(5342237526653964258324, 9090909090909090909089)
Mod(3638170586991402690760, 9090909090909090909089)
Mod(3794383004766300228342, 9090909090909090909089)
Mod(227556717345808697556, 9090909090909090909089)
Mod(6483026222090999362884, 9090909090909090909089)
Mod(3594924984182372500551, 9090909090909090909089)
Mod(8063944666165464610737, 9090909090909090909089)
Mod(4327641896999818513305, 9090909090909090909089)
Mod(8276896390005679891227, 9090909090909090909089)
Mod(1921266966330415715489, 9090909090909090909089)
Mod(7582518327012313526239, 9090909090909090909089)
Mod(6553601200532570675906, 9090909090909090909089)
Mod(8580008981791729157791, 9090909090909090909089)
Mod(4870847, 9090909090909090909089)
[/code]

And 9090909090909090909089 is indeed a prime number.

I tested some extensions with (20^n−1)/19-2 ,(40^n−1)/39-2 and (80p+1)/81-2 etc. and it seems the primality test works for
these too.

For ((10*2^n)^m−1)/(10*2^n−1)-2

Let the sequence Si=2^(-10*2^n)*[(S(i-1) - sqrt(S(i-1)^2 - 4))^(10*2^n) + (S(i-1) + sqrt(S(i-1)^2 - 4))^(10*2^n)] with S0=L(10*2^n)

Then N is prime if and only if Sn-1≡L(30*2^n-2)(modN).

For ((10*2^n)^m+1)/(10*2^n+1)-2

Let the sequence Si=2^(-10*2^n)*[(S(i-1) - sqrt(S(i-1)^2 - 4))^(10*2^n) + (S(i-1) + sqrt(S(i-1)^2 - 4))^(10*2^n)] with S0=L(10*2^n)

Then N is prime if and only if Sn-1≡L(30*2^n+2)(modN).

It seems it works if (10^m±1)/(10±1)-2 > L(30*2^n±2)

I found some new prime and PRP with that. Do you think it is useful ? :smile:

 All times are UTC. The time now is 18:42.