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

[robert44444uk]

Originally Posted by robert44444uk

This looks quite easy to do, so I might give this a go.

Results for a from 1 to 1000, and b from 0 to 9. Cannot see why series cannot start at b=0

b      Tested  Prp     Composite
0	1000	302	698
1	698	172	526
2	526	114	412
3	412	33	379
4	379	31	348
5	348	13	335
6	335	3	332
7	332	3	329
8	329	1	328
9	328	2	326

[fivemack]

11, 15, 18, 20, 28, 44, 46, 49, 51, 52, 53, 55, 57, 58, 61, 62, 64, 71, 73, 77, 81, 83, 91, 92, 94 have no primes for b=1..12; everything in 1..100 which has a prime for b=1..12 has it for b<=9.

I would be surprised if any of those numbers had a prime for b>12, since the probability is about 1/(4096 log b)

[robert44444uk]

Originally Posted by robert44444uk

I have sieved b=14 for the first 100,000 values of a for all possible prime factors up to 2^31 (=2^16*2^15+1 in fact) and 31652 candidates remain.

Actually sieved "a" from 5186 to 100000, so density of remaining candidates is higher

[robert44444uk]

Originally Posted by fivemack

11, 15, 18, 20, 28, 44, 46, 49, 51, 52, 53, 55, 57, 58, 61, 62, 64, 71, 73, 77, 81, 83, 91, 92, 94 have no primes for b=1..12; everything in 1..100 which has a prime for b=1..12 has it for b<=9.

Of which
11, 15, 18, 20, 44, 51, 53, 81, 83
are prime for b=0

[R.D. Silverman]

Originally Posted by robert44444uk

Results for a from 1 to 1000, and b from 0 to 9. Cannot see why series cannot start at b=0

b      Tested  Prp     Composite
0	1000	302	698
1	698	172	526
2	526	114	412
3	412	33	379
4	379	31	348
5	348	13	335
6	335	3	332
7	332	3	329
8	329	1	328
9	328	2	326

b = 0 simply. yields 2a+1; Whether b=0 should be included is a matter
of taste.

[R.D. Silverman]

Originally Posted by fivemack

11, 15, 18, 20, 28, 44, 46, 49, 51, 52, 53, 55, 57, 58, 61, 62, 64, 71, 73, 77, 81, 83, 91, 92, 94 have no primes for b=1..12; everything in 1..100 which has a prime for b=1..12 has it for b<=9.

I would be surprised if any of those numbers had a prime for b>12, since the probability is about 1/(4096 log b)

The density of this set should grow as the bound on a increases.

[ATH]

Originally Posted by fivemack

11, 15, 18, 20, 28, 44, 46, 49, 51, 52, 53, 55, 57, 58, 61, 62, 64, 71, 73, 77, 81, 83, 91, 92, 94 have no primes for b=1..12; everything in 1..100 which has a prime for b=1..12 has it for b<=9.

I would be surprised if any of those numbers had a prime for b>12, since the probability is about 1/(4096 log b)

I increased the table for b=1..12 and a<=1000. These are the following a's that has no prime b=1..12:

11,15,18,20,28,44,46,49,51,52,53,55,57,58,61,62,64,71,73,77,81,83,91,92,94
103,106,107,108,112,114,117,120,124,125,126,128,131,132,133,134,136,138,140,141,143,147,148,150,151,153,155,158,159,161,165,168,169,170,175,177,178,183,193,196
205,208,209,211,213,214,216,226,232,233,234,236,240,242,243,247,249,250,253,256,257,258,261,262,265,266,268,270,271,273,274,276,277,281,282,283,286,288,291,292,293,294,295,296,298,299
301,305,308,310,312,314,317,318,325,327,328,329,332,333,335,338,339,340,341,343,345,346,350,351,353,354,358,360,363,364,365,366,367,368,370,378,379,381,384,385,387,388,391,396,397
400,402,403,405,406,411,412,413,422,424,428,429,431,433,435,438,447,448,451,452,455,457,458,459,461,463,465,469,470,471,472,473,481,482,483,485,486,488,491,493,497,498,499
501,502,507,509,513,518,521,522,523,524,526,528,529,530,531,532,533,536,537,538,541,542,543,544,548,550,551,552,553,554,558,559,561,563,566,569,570,573,574,576,579,581,582,583,584,587,591,594,595,596,597,598,600
601,603,604,606,607,608,610,611,613,615,616,617,618,622,623,624,630,631,634,636,638,639,643,645,647,650,651,653,654,658,659,660,661,663,665,666,667,668,669,670,675,676,677,678,681,683,684,685,686,688,690,692,696,698,700
701,704,707,708,711,712,714,716,717,718,720,721,722,725,727,728,730,735,736,737,738,740,743,745,748,751,752,756,758,761,763,766,768,769,771,775,776,777,778,779,781,783,785,787,789,791,793,795,796,797,798
801,803,804,805,808,809,810,812,818,822,823,824,825,826,827,828,829,834,837,838,839,841,842,843,846,847,851,853,855,856,859,860,861,863,865,867,869,871,872,873,876,877,880,881,883,884,886,887,888,889,891,892,894,896,897,898
906,907,908,909,912,914,916,918,919,923,928,930,931,932,933,935,936,938,939,941,942,943,945,946,947,948,954,956,958,961,963,964,966,968,969,970,971,972,973,976,979,980,981,982,984,985,986,987,989,992,993,995,996,999

Number of a's:
001-100: 25
101-200: 40
201-300: 46
301-400: 45
401-500: 43
501-600: 53
601-700: 55
701-800: 51
801-900: 56
901-1000: 54
Total: 468

[geoff]

Originally Posted by robert44444uk

I have sieved b=14 for the first 100,000 values of a for all possible prime factors up to 2^31 (=2^16*2^15+1 in fact) and 31652 candidates remain. Although the sieve instructions mention that you need to do two sieves int(odd)*2^15+1 and then int(odd)*2^16+1, this misses out some important possible factors where int is even. So I had to construct multiple layers of sieve int(odd)*2^(15+x), x integer, to ensure that all int(even) were considered by the sieve.

The sieve only removes factors k*2^n+1 with odd k, so for b=14 you need to sieve seperately for factors k*2^n+1 with n=15,16,17,..., etc., not just n=15,16. Sorry if that was not clear.

Another limitation of the program is that the sieve does not reduce as factors are found, you will need to restart it using the output sieve file as input to get the speed increase.

Edit: To sieve all factors up to 2^31 you would sieve with:
1 <= k < 2^16 and n=15,
1 <= k < 2^15 and n=16,
1 <= k < 2^14 and n=17, etc.

[robert44444uk]

Originally Posted by R.D. Silverman

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?

Bob, why are these interesting questions?

[ATH]

Originally Posted by ATH

I increased the table for b=1..12 and a<=1000. These are the following a's that has no prime b=1..12:

I checked that list for b=13,14,15 and no new primes, so the list is valid for b=1..15 and a<=1000.

[R.D. Silverman]

Originally Posted by robert44444uk

Bob, why are these interesting questions?

Question. Singular.

For the same reason that the density of Mersenne primes is an
interesting question. For the same reason that the Prime Number
Theorem (once conjecture) is an interesting theorem.

The distribution of primes is an interesting topic of research.