mersenneforum.org Sieve needed for a^(2^b)+(a+1)^(2^b)
 Register FAQ Search Today's Posts Mark Forums Read

 2009-05-21, 03:39 #12 robert44444uk     Jun 2003 Suva, Fiji 23·3·5·17 Posts Some basic stats for lower b Code: b # of prp-3 in series a from 1 to 10000 1 1645 2 1699 3 612 4 601 5 273 6 143 7 70 8 68 b=1, 3 and 7 demonstrating the prime [2^(b+1)]+1 = 5,17,257 effect Last fiddled with by robert44444uk on 2009-05-21 at 03:41
2009-05-21, 10:59   #13
robert44444uk

Jun 2003
Suva, Fiji

23·3·5·17 Posts

Quote:
 Originally Posted by robert44444uk This looks the key. Shame I did not spot this by observation. So the sieve only has to calculate all the primes in x*2^(b+1)+1, x integer and increasing.
I can't make rhyme or reason regarding the incidence of prime factors in a^(2^b)+(a+1)(2^b). For b =12, i.e 2^b=4096 small prime factors appear as follows. Maybe someone can enlighten on the modular positions and frequency. I know that, if a prime factor p appears in a=A, then it will appear also for for the a values which are Amod[p]. Looking at a modulo order 4096 does not appear to enlighten. Maybe it has to do with primitive roots.

Code:
a     factors

1	114689
2	286721	1810433
5	270337	737281
6	147457
7	114689	147457
10	114689
12	163841
16	147457	1417217
19	4300801
28	5308417
31	114689
32	5824513
33	1769473
36	40961	65537
37	11370497
40	65537	5726209
42	286721
44	557057
45	40961	1097729
47	40961	147457
48	3489793
49	65537
51	4759553
52	19701761
53	286721	14770177
54	163841
55	40961
56	65537
57	65537
58	1417217
60	15900673
62	2482177	7413761	13664257
63	13066241
70	163841
71	114689	5849089	20586497
73	147457	417793	925697
76	65537
77	188417
78	114689
79	40961
84	286721
85	188417
87	147457
92	286721	9379841
95	40961	65537	1589249
96	40961

Last fiddled with by robert44444uk on 2009-05-21 at 11:13

 2009-05-21, 12:24 #14 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 2·7·461 Posts Well, you're talking about the roots of a degree-4096 polynomial modulo the prime, so you'd expect 114689 to appear 4096 times for every 114689 exponents, repeating with period 114689. I don't see any reason for the polynomial to have particularly tractable roots, though obviously if X is a root then p-(X+1) is.
 2009-05-22, 14:00 #15 robert44444uk     Jun 2003 Suva, Fiji 23·3·5·17 Posts This appears to have been studied as a form for small a by Henri Lifchitz - he has some prp listed in his site. There is also at least one prp with exponent 16384 and a few of 8192 and 4096 Last fiddled with by robert44444uk on 2009-05-22 at 14:06
 2009-05-25, 04:03 #16 geoff     Mar 2003 New Zealand 115710 Posts Here is a sieving algorithm I think will work, but I can't find any way to exploit the fact that b=a+1 in a^2^m + b^2^m. Does anyone know a better algorithm? (By "maximal prime power factor" I mean a factor p^m, m>0, where p is prime but p^{m+1} is not a factor. A list L of length N has elements L[1], L[2], ..., L[N].) Algorithm to sieve candidates a^2^m + b^2^m for factors k*2^n+1, with m
 2009-05-31, 13:24 #17 robert44444uk     Jun 2003 Suva, Fiji 23×3×5×17 Posts Thank you Geoff for your contribution. I have come to an early conclusion that these series are not terribly prime, despite having so few possible prime factors p, as those prime factors crop up with a much higher frequency than 1/p. Given the difficulties of finding a nice quick algorithm to determine amod(p)=0 for a given p, then the sieve approach Geoff suggested may be too slow to be of use. Do others agree?
 2009-06-03, 01:18 #18 geoff     Mar 2003 New Zealand 13×89 Posts Robert, I have uploaded a sieve here. See the README for instructions.
2009-06-03, 12:04   #19
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

22·1,877 Posts

Quote:
 Originally Posted by robert44444uk Thank you Geoff for your contribution. I have come to an early conclusion that these series are not terribly prime,
I told you that some time ago. Such primes will be rare.

A more interesting question is whether there exists values of a for
which there are no primes. If so, what is the density of that set?

2009-06-05, 15:29   #20
robert44444uk

Jun 2003
Suva, Fiji

23×3×5×17 Posts

Quote:
 Originally Posted by geoff Robert, I have uploaded a sieve here. See the README for instructions.
Thank you Geoff. Been travelling with no internet connection. Just catching up. Will let you know how I get on.

 2009-06-05, 17:26 #21 henryzz Just call me Henry     "David" Sep 2007 Liverpool (GMT/BST) 37·163 Posts i accidentally left b=12 running quite a lot longer than i meant to and found: 311^(2^12)+312^(2^12) 2741^(2^12)+2742^(2^12) 3582^(2^12)+3583^(2^12) 5293^(2^12)+5294^(2^12) are all 3-prp i expect they are already known
2009-06-06, 05:55   #22
robert44444uk

Jun 2003
Suva, Fiji

23×3×5×17 Posts

Quote:
 Originally Posted by henryzz i accidentally left b=12 running quite a lot longer than i meant to and found: 311^(2^12)+312^(2^12) 2741^(2^12)+2742^(2^12) 3582^(2^12)+3583^(2^12) 5293^(2^12)+5294^(2^12) are all 3-prp i expect they are already known
These are the listed prp on the Lifchitz site, all found by H Lifchitz

Code:
Form  digits  date
2741^4096+2742^4096	14083	10/2002
311^4096+312^4096	10217	10/2002
3508^8192+3509^8192	29043	11/2002
5183^16384+5182^16384	60860	Jan-07
1829^16384+1828^16384	53449	Jan-07
14082^4096+14083^4096	16994	01/2007
12080^4096+12081^4096	16721	01/2007
6289^4096+6290^4096	15560	01/2007
5293^4096+5294^4096	15253	01/2007
3582^4096+3583^4096	14559	01/2007

 Similar Threads Thread Thread Starter Forum Replies Last Post pinhodecarlos NFS@Home 46 2018-03-12 22:43 binu Factoring 3 2013-04-13 16:32 beyastard Software 55 2009-07-29 12:51 AntonVrba Math 3 2007-03-06 10:55 MooooMoo Twin Prime Search 9 2007-01-01 21:13

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

Mon Jan 30 13:42:47 UTC 2023 up 165 days, 11:11, 0 users, load averages: 2.35, 1.93, 1.81