New repunit (PRP) primes found, 5794777 and 8177207 decimal digits (PRP records)

[axn]

Serge, one question. Does LLR use standard PRP test, 3^(N-1) == 1, or does it do 3^10^p == 3^10?

[Batalov]

Originally Posted by JeppeSN

Good one!

Maybe it will be clear when the PRP Top entry becomes visible, but what types of PRP tests has this one "passed", as of now?

/JeppeSN

We finished 3-PRP, 7-PRP, 11-PRP, 13-PRP (and their SPRP chasers are still running, the Lucas+Frobenius test phases -- they are ~10x slower even on 32 threads).

[paulunderwood]

Originally Posted by Batalov

We finished 3-PRP, 7-PRP, 11-PRP, 13-PRP (and their SPRP chasers are still running, the Lucas test phase).

I am currently testing it for Lucas over x^2-4*x+1

[Batalov]

Originally Posted by axn

Serge, one question. Does LLR use standard PRP test, 3^(N-1) == 1, or does it do 3^10^p == 3^10?

I'll have to doublecheck in the source, but as far as I remember the code does the honest modular exponentiation of b^(N-1) using (in this case) mod (10^p-1) and then converts to giants and does a slow/careful mod ((10^p-1)/9) and expects unit.
For N not being near a power of 2, there is no expected savings of doing exponentiation to N-1, to N or to N+1 (for Mersennes, for example). N-1 is just a binary string of both "1"s and "0"s, no difference from N or even 9N.

[axn]

Originally Posted by Batalov

For N not being near a power of 2, there is no expected savings of doing exponentiation to N-1, to N or to N+1 (for Mersennes, for example). N-1 is just a binary string of both "1"s and "0"s, no difference from N or even 9N.

But 9N+1 = 10^p = 5^p*2^p has a lot more zeros than 1s. Honestly, I don't know what is the impact of simple squaring vs squaring*3. Once upon a time, I recall there being low single digit % difference in performance between LLR and PRP on Riesel numbers (all 1s), but I could be mistaken.

[Cybertronic]

Congratulation , this is so cool !

[Batalov]

Originally Posted by axn

But 9N+1 = 10^p = 5^p*2^p has a lot more zeros than 1s. Honestly, I don't know what is the impact of simple squaring vs squaring*3. Once upon a time, I recall there being low single digit % difference in performance between LLR and PRP on Riesel numbers (all 1s), but I could be mistaken.

True, but we might hit some other 9th root of unity. (we can then rule the false positive out, of course, with subsequent traditional tests; no false negatives should result).
Worth trying; interesting. llr is not doing it now, but we can hack a patch, and test the speed gain (if it exists).

[LaurV]

Originally Posted by Batalov

It is R_5794777, and perhaps unsurprisingly it has 5794777 decimal digits (all "1"s).

Yaay! Congrats Serge and Ryan!

[axn]

Originally Posted by Batalov

True, but we might hit some other 9th root of unity. (we can then rule the false positive out, of course, with subsequent traditional tests; no false negatives should result).
Worth trying; interesting. llr is not doing it now, but we can hack a patch, and test the speed gain (if it exists).

Worth pointing out: after computing 3^5^p, the remaining p squarings can be protected with GEC.

PS:- In theory, even the 3^5^p could be protected by GEC, but it will cost 50% extra -- worth it only if used as an alternative for double checks

[R. Gerbicz]

Originally Posted by axn

Worth pointing out: after computing 3^5^p, the remaining p squarings can be protected with GEC.

PS:- In theory, even the 3^5^p could be protected by GEC, but it will cost 50% extra -- worth it only if used as an alternative for double checks

Much less extra cost, say you want a^(b^n) mod N using error checking, then choose e>0 and set a larger new base: B=b^e, for simplicity assume that e divides n, then

a^(b^n)=a^(B^(n/e))

and you can do the error checking using this new base, if we count only the squarings then the extra cost of using B>2 is
ceil(log2(B))/log2(B)-1 in 1 part.
[for B=2 this is zero].

One small drawback here is that when you would want to choose very large e so large B to lower the overhead then you can't error check that very frequently.

[MrRepunit]

Originally Posted by Batalov

The last two known repunits were found back in 2007. Welcome, the year 2021.

With Ryan Propper, we decided to give a boost to the project which changed a few homes over the years. (We don't know the latest live site. skoberne site is defunct. Perhaps, Kurt's subpage.)

So, we might go up to p<10,000,000 and so far found one. We are using MT llr and gr-mfaktc to 64 bits for presieve.
It is submitted to PRPtop (but has not showed up yet), to Mathworld and to UTM (in category of thesaurus of primes). Wikipedia and OEIS 004023 will be updated when sourced with other pages.

It is R_5794777, and perhaps unsurprisingly it has 5794777 decimal digits (all "1"s).

It also happens to be the largest currently known PRP.

Congratulations on finding the next repunit prime, well done.
I can give some infos on the current repunit search that our team is doing:


I extended the original database from skoberne (with complete new structure), but it is not publicly available. So every few weeks I send a new excerpt to Kurt, so his website Kurt's subpage is officially the new live site, but so far only up to n=6000000. The database itself contains all prime exponents up to 10000000, including known factors, Res64 and/or Res2048 values plus the current bit-depth of sieving. If somebody is interested I can send him a complete dump, or extract the needed information, just send me a PM.

As of today we have tested all of the exponents up to 4880957, with the exception of very few numbers around 4300459 (still waiting for the results of one user).

So how was the new number found, by random selection or systematic search? If you are still in favor of a systematic search we could combine our efforts. Currently I am doing a manual reservation of exponents via email, nothing like the professional search for Mersenne primes.

I would also suggest that you try out running the PRP test with prime95/mprime, it should be faster than llr. E.g. running the test for the found prp has the worktodo entry
PRP=1,10,5794777,-1,99,0,3,1,"9"
I am currently running the test with mprime on an 8 Core AMD, will post the results here once finished.


Cheers,
Danilo


PS.: @Batalov, I didn't see your comment on LLR vs mprime, only later. I should compare again, last time I tested mprime was like 10% faster. Also I am using it to get the Res2048 value, does LLR has the similar option to get the long residue?