20090521, 03:39  #12 
Jun 2003
Suva, Fiji
2^{3}·3·5·17 Posts 
Some basic stats for lower b
Code:
b # of prp3 in series a from 1 to 10000 1 1645 2 1699 3 612 4 601 5 273 6 143 7 70 8 68 Last fiddled with by robert44444uk on 20090521 at 03:41 
20090521, 10:59  #13  
Jun 2003
Suva, Fiji
2^{3}·3·5·17 Posts 
Quote:
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 20090521 at 11:13 

20090521, 12:24  #14 
(loop (#_fork))
Feb 2006
Cambridge, England
2·7·461 Posts 
Well, you're talking about the roots of a degree4096 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.

20090522, 14:00  #15 
Jun 2003
Suva, Fiji
2^{3}·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 20090522 at 14:06 
20090525, 04:03  #16 
Mar 2003
New Zealand
1157_{10} 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<n fixed, and odd k in k0 <= k < k1: Code:
Input A,B /* lists of remaining candidates A[i]^2^m + B[i]^2^m */ Input m, n, k0, k1 Let C be a list of unique elements in the union of A and B /* so the length of C could be anywhere from A+1 to 2*A */ Let S,T be lists (of the same length as A) such that: S[i] is the index of A[i] in C (so that A[i] = C[S[i]]) T[i] is the index of B[i] in C (so that B[i] = C[T[i]]) Let U be the list of unique maximal prime power factors of elements in C Let V be a list of the same length as U Let F be a list (of the same length as C) such that: F[i] is the list of j such that U[j] is a maximal prime power factor of C[i] /* so that F[i][0]*F[i][1]*... = C[i] */ Let G be a list of the same length as F For each odd k in k0 <= k < k1 such that k*2^n+1 is a probable prime { /* V < U^2^m mod k*2^n+1 */ For j from 1 to U { V[j] < U[j] Repeat m1 times V[j] < V[j]^2 mod k*2^n+1 } /* G < C^2^m mod k*2^n+1 */ For i from 1 to F { G[i] < V[F[i][1]] For j from 2 to F[i] G[i] < G[i]*V[F[i][j]] mod k*2^n+1 } For i from 1 to A If G[S[i]] + G[T[i]] = 0 (mod k*2^n+1) Report that k*2^n+1 divides A[i]^2^m + B[i]^2^m } 
20090531, 13:24  #17 
Jun 2003
Suva, Fiji
2^{3}×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? 
20090603, 12:04  #19  
"Bob Silverman"
Nov 2003
North of Boston
2^{2}·1,877 Posts 
Quote:
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? 

20090605, 17:26  #21 
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 3prp i expect they are already known 
20090606, 05:55  #22  
Jun 2003
Suva, Fiji
2^{3}×3×5×17 Posts 
Quote:
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 Jan07 1829^16384+1828^16384 53449 Jan07 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 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
More NFS@Home 16e Lattice Sieve V5 wu's needed  pinhodecarlos  NFS@Home  46  20180312 22:43 
Advantage of lattice sieve over line sieve  binu  Factoring  3  20130413 16:32 
Sieve needed for k*b1^m*b2^n+1  beyastard  Software  55  20090729 12:51 
Help needed  AntonVrba  Math  3  20070306 10:55 
Volunteer needed for sieve merging  MooooMoo  Twin Prime Search  9  20070101 21:13 