Sieve needed for a^(2^b)+(a+1)^(2^b)

[robert44444uk]

Some basic stats for lower b

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

[robert44444uk]

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.

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

[fivemack]

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.

[robert44444uk]

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

[geoff]

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:

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 m-1 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
}

[robert44444uk]

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?

[geoff]

Robert, I have uploaded a sieve here. See the README for instructions.

[R.D. Silverman]

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?

[robert44444uk]

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.

[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

[robert44444uk]

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

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