Near- and quasi-repunit PRPs

Batalov · 2014-09-22, 18:39

M.Kamada has been collecting the near- and quasi-repunit primes and PRPs for many years.

I've recently revisited this topic and remembered a few pitfalls that new searchers might fall in, so I decided to list them here:
1. Sieving is possible with sr*sieve, though a few tips are needed. First, because most forms have an implied denominator of 3 or 9, one needs to not sieve for p=3. For most forms srsieve works (with -p 5); start with srsieve to low limit, then use awk or similar to remove the 3-based composites. Then proceed with sr{1|2}sieve if possible (e.g. for +/-1 forms.
2. PRP testing is as fast as "normal" numbers (without denominator). For that, either use Prime95 (with worktodo entries like PRP={k},{b},{n},{c},"denominator") or LLR with ABC($a*$b^$c$d)/$e header! LLR runs a nice battery test: both SPRP and then a strong-Fermat, Lucas and Frobenius.
3. Use PFGW only for independent validation, because it uses general FFT and is many times slower.

Example of application (711...11 series):
1. Find current limits at Kamada's page.
2. Sieve with srsieve ... -p 5 -P 2e6 "64*10^n-1"
3. Remove all entries where n != 1 (mod 6). This is because even n's (0,2,4) generate diff.of squares; n=3 (mod 6) generate diff.of cubes; and n=5 (mod 6) are divisible by additional 3's after being divided by 9.
4. Sieve with sr1sieve (or combine with some other siblings, e.g. I did the 133..33 series, and sieve with sr2sieve)
5. Prepare P95 or LLR input files with awk and run them.
6. ??????
7. PROFIT! (64·10^762811-1)/9 is a (S-F-L-F)PRP.

Similarly, (64·10^779465-1)/81 is a (non-repunit) SPRP, and (89·10^411590+1)/9 is a Plateau-and-Depression SPRP ("988...889").

All these are still in the PRP Top processing queue.

Batalov · 2014-09-22, 19:35

P.S. We can imaginatively call the (64·10^779465-1)/81 a "rainbow" number, because it has all decimal digits (except 8) in order, over and over again.

Code:

79012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679...

davar55 · 2014-10-25, 03:25

Quote:

Originally Posted by Batalov

P.S. We can imaginatively call the (64·10^779465-1)/81 a "rainbow" number, because it has all decimal digits (except 8) in order, over and over again.

nice name

Batalov · 2014-10-27, 11:03

Here is a small but peculiar PRP. (self-describing, sort of)
It is from the "511..11" near-repunit series, and in decimal expansion it has a "5" followed by 51111 "ones".

Code:

(46*10^51111-1)/9 is strong-Fermat, Lucas and Frobenius PRP! (P = 5, Q = 3, D = 13)  Time : 88.194 sec.

pepi37 · 2014-10-31, 00:29

(91*10^112098-1)/9

One 1 then one 0 then 1 until end :)

Thanks Batalov for showing me way for sieving and llr-ing this type of PRP.

pepi37 · 2014-11-03, 22:28

Quote:

Originally Posted by pepi37

(91*10^112098-1)/9

One 1 then one 0 then 1 until end :)

Thanks Batalov for showing me way for sieving and llr-ing this type of PRP.

And new one: double in size :)
(73*10^248145-1)/9

sweety439 · 2019-06-04, 19:27

Found A200065(1033): (10^3376-1)/9-78 is prime!!!

sweety439 · 2019-06-04, 20:08

Quote:

Originally Posted by sweety439

Found A200065(1033): (10^3376-1)/9-78 is prime!!!

Another term is A200065(1079): (10^2553-1)/9-32 is prime!!!

sweety439 · 2019-06-04, 20:11

Note that A200065(1073)=0, since (10^n-1)/9-38 is divisible by either 3 or 37 for n not divisible by 3, and has algebra factors (divisible by (10^(n/3)-7)/3, this number is >1 for n>3) for n divisible by 3.

Dylan14 · 2019-09-12, 13:06

I'm looking to work on the 31111 series, and I want to make sure I have the procedure right before I start:

1. Since 31111 = 31w = (28*10^n-1)/9, there is no need to sieve p=3, and so we start with p = 5. Run srsieve to low limits (say, to 1e7) with the --newpgen flag, starting with n = 200001 (as it has been searched to 200000 from Kamada's website) to whatever max n (say, 500000).
2. Because by 2.4.1 of https://stdkmd.net/nrr/3/31111.htm, there is no need to test any n where n mod 3 = 0, so we can remove them. Not sure if it be worth removing the other factors shown in that section.
3. Continue sieve with sr1sieve up to desired sieve limit
4. Change the file header to an ABC header using srfile, and then add /9 at the end, so it would read

Code:

ABC (28*10^$a-1)/9

5. Use LLR to test and (hopefully) find PRP's.

Let me know.

Batalov · 2019-09-12, 13:31

ABC ($a*$b^$c$d)/$e
28 10 n -1 9

2014-09-22, 18:39	#1
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 3⁶·13 Posts	Near- and quasi-repunit PRPs M.Kamada has been collecting the near- and quasi-repunit primes and PRPs for many years. I've recently revisited this topic and remembered a few pitfalls that new searchers might fall in, so I decided to list them here: 1. Sieving is possible with srsieve, though a few tips are needed. First, because most forms have an implied denominator of 3 or 9, one needs to not sieve for p=3. For most forms srsieve works (with -p 5); start with srsieve to low limit, then use awk or similar to remove the 3-based composites. Then proceed with sr{1\|2}sieve if possible (e.g. for +/-1 forms. 2. PRP testing is as fast as "normal" numbers (without denominator). For that, either use Prime95 (with worktodo entries like PRP={k},{b},{n},{c},"denominator") or LLR with ABC($a$b^$c$d)/$e header! LLR runs a nice battery test: both SPRP and then a strong-Fermat, Lucas and Frobenius. 3. Use PFGW only for independent validation, because it uses general FFT and is many times slower. Example of application (711...11 series): 1. Find current limits at Kamada's page. 2. Sieve with srsieve ... -p 5 -P 2e6 "6410^n-1" 3. Remove all entries where n != 1 (mod 6). This is because even n's (0,2,4) generate diff.of squares; n=3 (mod 6) generate diff.of cubes; and n=5 (mod 6) are divisible by additional* 3's after being divided by 9. 4. Sieve with sr1sieve (or combine with some other siblings, e.g. I did the 133..33 series, and sieve with sr2sieve) 5. Prepare P95 or LLR input files with awk and run them. 6. ?????? 7. PROFIT! (64·10^762811-1)/9 is a (S-F-L-F)PRP. Similarly, (64·10^779465-1)/81 is a (non-repunit) SPRP, and (89·10^411590+1)/9 is a Plateau-and-Depression SPRP ("988...889"). All these are still in the PRP Top processing queue.

2014-09-22, 19:35	#2
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 3⁶×13 Posts	P.S. We can imaginatively call the (64·10^779465-1)/81 a "rainbow" number, because it has all decimal digits (except 8) in order, over and over again. Code: 79012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679...

2014-10-27, 11:03	#4
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 22405₈ Posts	A curio: "5" followed by 51111 "1"s is a PRP Here is a small but peculiar PRP. (self-describing, sort of) It is from the "511..11" near-repunit series, and in decimal expansion it has a "5" followed by 51111 "ones". Code: (46*10^51111-1)/9 is strong-Fermat, Lucas and Frobenius PRP! (P = 5, Q = 3, D = 13) Time : 88.194 sec.

2014-10-31, 00:29	#5
pepi37 Dec 2011 After milion nines:) 5·17² Posts	(9110^112098-1)/9 One 1 then one 0 then 1 until end :) Thanks Batalov for showing me way for sieving and llr-ing this type of PRP. Last fiddled with by pepi37 on 2014-10-31 at 00:30 Reason: edit PRP*

2019-06-04, 20:11	#9
sweety439 "99(4^34019)99 palind" Nov 2016 (P^81993)SZ base 36 5×7×83 Posts	Note that A200065(1073)=0, since (10^n-1)/9-38 is divisible by either 3 or 37 for n not divisible by 3, and has algebra factors (divisible by (10^(n/3)-7)/3, this number is >1 for n>3) for n divisible by 3. Last fiddled with by sweety439 on 2019-06-04 at 20:14

2019-06-04, 19:27	#7
sweety439 "99(4^34019)99 palind" Nov 2016 (P^81993)SZ base 36 B59₁₆ Posts	Found A200065(1033): (10^3376-1)/9-78 is prime!!!

2019-09-12, 13:06	#10
Dylan14 "Dylan" Mar 2017 3·193 Posts	I'm looking to work on the 31111 series, and I want to make sure I have the procedure right before I start: 1. Since 31111 = 31w = (2810^n-1)/9, there is no need to sieve p=3, and so we start with p = 5. Run srsieve to low limits (say, to 1e7) with the --newpgen flag, starting with n = 200001 (as it has been searched to 200000 from Kamada's website) to whatever max n (say, 500000). 2. Because by 2.4.1 of https://stdkmd.net/nrr/3/31111.htm, there is no need to test any n where n mod 3 = 0, so we can remove them. Not sure if it be worth removing the other factors shown in that section. 3. Continue sieve with sr1sieve up to desired sieve limit 4. Change the file header to an ABC header using srfile, and then add /9 at the end, so it would read Code: ABC (2810^$a-1)/9 5. Use LLR to test and (hopefully) find PRP's. Let me know.

2019-09-12, 13:31	#11
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 22405₈ Posts	ABC ($a*$b^$c$d)/$e 28 10 n -1 9

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Searching for generalized repunit PRP	sweety439	sweety439	231	2020-11-06 12:30
Generalized Repunit primes	Bob Underwood	Math	12	2020-10-11 20:01
PRPs not prime	schickel	FactorDB	1	2015-08-03 02:50
Proven PRPs?	Random Poster	FactorDB	0	2012-07-24 10:53