[yubneped] Primes of popcount 3

We seek primes with few bits set when written in binary.  2 is the best, with only 1 bit set.  Then, Fermat primes are the next best: they have only 2 bits set.  Here we investigate primes with 3 bits set: OEIS A081091.

Motivation is public exponents for RSA.  Fewer 1 bits means slightly less work required for modular exponentiation.  A prime public exponent decreases the chance that it shares a factor with eulerphi(modulus).  Traditionally, the public exponent is largest known Fermat prime, 65537.

2^2 + 2^1 + 1 = 7
2^3 + 2^1 + 1 = 11
2^3 + 2^2 + 1 = 13
2^4 + 2^1 + 1 = 19
2^5 + 2^2 + 1 = 37
2^5 + 2^3 + 1 = 41
2^6 + 2^1 + 1 = 67
2^6 + 2^3 + 1 = 73
2^6 + 2^5 + 1 = 97
2^8 none
2^7 + 2^1 + 1 = 131
2^7 + 2^3 + 1 = 137
2^7 + 2^6 + 1 = 193
2^9 + 2^3 + 1 = 521
2^9 + 2^6 + 1 = 577
2^9 + 2^7 + 1 = 641
2^9 + 2^8 + 1 = 769
2^10 + 2^3 + 1 = 1033
2^10 + 2^7 + 1 = 1153
2^11 + 2^2 + 1 = 2053
2^11 + 2^5 + 1 = 2081
2^11 + 2^6 + 1 = 2113
2^12 + 2^1 + 1 = 4099
2^12 + 2^5 + 1 = 4129
2^13 + 2^4 + 1 = 8209
2^13 + 2^12 + 1 = 12289
2^14 + 2^5 + 1 = 16417
2^14 + 2^11 + 1 = 18433
2^15 + 2^1 + 1 = 32771
2^15 + 2^5 + 1 = 32801
2^15 + 2^6 + 1 = 32833
2^15 + 2^13 + 1 = 40961
2^16 + 2^1 + 1 = 65539
2^17 + 2^11 + 1 = 133121
2^17 + 2^14 + 1 = 147457
2^17 + 2^15 + 1 = 163841
2^18 + 2^1 + 1 = 262147
2^18 + 2^3 + 1 = 262153
2^18 + 2^9 + 1 = 262657
2^18 + 2^13 + 1 = 270337
2^19 + 2^6 + 1 = 524353
2^19 + 2^9 + 1 = 524801
2^19 + 2^10 + 1 = 525313
2^19 + 2^15 + 1 = 557057
2^19 + 2^18 + 1 = 786433
2^20 + 2^5 + 1 = 1048609
2^20 + 2^9 + 1 = 1049089
2^20 + 2^17 + 1 = 1179649

Switch to more compact notation:

2^20 + 2^{5, 9, 17} + 1
2^21 + 2^{4, 12} + 1
2^22 + 2^{7} + 1
2^23 + 2^{3, 6, 14, 17, 18} + 1
2^24 + 2^{9} + 1
2^25 none
2^26 + 2^{17, 21} + 1
2^27 + 2^{15, 17, 21, 22, 25} + 1
2^28 + 2^{1, 21} + 1
2^29 + 2^{15, 18} + 1
2^30 + 2^{1, 3, 5, 7, 13, 17, 19, 25} + 1
2^31 + 2^{6, 7, 9, 22, 27, 30} + 1
2^32 none
2^33 + 2^{4, 7, 19, 20, 28} + 1
2^34 + 2^{9, 19, 27} + 1
2^35 + 2^{14, 15, 26, 29} + 1
2^36 + 2^{13, 33} + 1
2^37 + 2^{3, 27, 36} + 1
2^38 + 2^{11, 23} + 1
2^39 + 2^{25, 30} + 1
2^40 none
2^41 + 2^{6, 15, 39} + 1
2^42 + 2^{7, 23, 31, 33, 41} + 1
2^43 none
2^44 + 2^{17} + 1
2^45 + 2^{7, 15, 27, 34, 42} + 1
2^46 + 2^{15, 19, 43} + 1
2^47 + 2^{2, 3, 6, 11, 17, 30, 35} + 1
2^48 none
2^49 + 2^{30} + 1
2^50 + 2^{23, 29} + 1
2^51 + 2^{6, 25, 29, 34, 41} + 1
2^52 + 2^{21} + 1
2^53 + 2^{2, 36, 38, 42, 47} + 1
2^54 + 2^{33, 45} + 1
2^55 + 2^{1, 9, 13, 19, 34, 51} + 1
2^56 none
2^57 + 2^{3, 7, 10, 40, 46, 55} + 1
2^58 none
2^59 + 2^{14, 47} + 1
2^60 + 2^{5, 33, 41} + 1
2^61 + 2^{6, 51} + 1
2^62 + 2^{21} + 1
2^63 + 2^{19, 23} + 1
2^64 none

2^2047 + 2^{75,315,1234,1239,1693} + 1
2^4095 + 2^{785,963,1851,2117,3343,3509} + 1
2^8191 + 2^{898,2185,4785,4831,7029,7062} + 1
2^16383 + 2^{457,2813,4963,16015} + 1

We begin to see the curious pattern at 32 and 64 that there are none at powers of 2, that is, 2^2^i+2^j+1 for i>=5 and j<2^i is never prime.  We've confirmed this up to i=22.  Often the numbers are divisible by 7, or share a factor with some smaller Fermat number.  The only ones requiring more difficult primality tests had even i and j=1, i.e., 2^2^(2*t)+3, with no primes found larger than 65539.  Equivalently: is 16 the largest power of 2 in OEIS A057732?

for(emax=0,22,for(i=1,2^emax-1,x=2^2^emax+2^i+1;pp=((x%7)!=0);for(f=0,emax,gg=gcd(x,2^2^f+1);if(gg!=1,pp=0;break));if(pp,print(emax," ",i))))

for(t=0,11,i=2*t;x=2^2^i+3;print(i," ",ispseudoprime(x)))