Write about searching for widely digitally delicate primes in base 2

[grencez]

"widely binarily delicate prime"?

I think we can cover the high bits by only considering numbers that have particular values modulo 3, 5, 7, 13, 17, and 241 and have particular floor(log base 2) values modulo 24 (since 24=lcm(2, 4, 3, 12, 8, 24)). Hopefully that actually works out. Then hopefully some candidate numbers are small enough to actually perform "digitally delicate prime in binary" tests.

Perhaps contextualize as a DFA problem: Given natural numbers m, a<m, b<m, and c<m construct a DFA that accepts all 2**n such that, for all x where (lg x) mod (m-1) = c and x mod m = a, the following property holds: (2**(n+1+floor(lg x)) + x) mod m = b. (Does m have to be prime?)

[grencez]

Success! I think. Here's the first few widely delicate primes in base 2 that become divisible by 3, 5, 7, 13, 17, or 241 if any bit is changed from 0 to 1:

2131099
9208337
11788523
14740403
20025409
42762767
43747163
52504261
54593731
55414847
62058713
62602763
69650461
76963463
79933129
88148161
93086731
93545483
101567273

[grencez]

Looks like Jeremiah found these last year in https://scholarcommons.sc.edu/etd/5879/. Better be sure to cite that!

[grencez]

I'm attempting to brute force a smaller solution by generating prime numbers that satisfy a "best-effort" delicacy test, then offloading the harder verification to PARI/GP. The number 19249 seems promising... in a way. It doesn't seem to have periodic factors for the composite numbers made by setting subsequently higher bits. As such, it'll be tough to prove!

I validated it as a delicate prime up to 70k bits and am trying 100k overnight with the following PARI/GP program. Note that I'm using addition instead of bitxor. Both work in this case.

parfor(i=0, 10^5, if(isprime(19249 + 2^i), print(i)));

I wonder if it's undecidable in general to check if a prime number is widely digitally delicate. This 19249 case is definitely giving me an aperiodic "domino problem" vibe.

[grencez]

I'm torn about this 19249 thing. On one hand, I've validated it up to several hundred thousand bits and have narrowed down the "hard" instances to 19249+2^(22+180*i), 19249+2^(58+180*i), and 19249+2^(94+180*i), which all seem to have the modular exponentiation 2^exp = 1 only when exp is divisible by 13 and 4. Granted, I have only verified this for the first 6. But if true, the 13 would guarantee non-primality since 2^(22+36*i)+19248 is never divisible by 13, making Fermat's little theorem primality test fail in base 2.

On the other hand, there was a very similar question about whether 19249*2^n+1 is composite for all n (https://en.wikipedia.org/wiki/Seventeen_or_Bust). It isn't. 19249*2^3918990+1 is prime. I don't know if it translates to some "19249 plus a power of 2" being prime, but it is very suspicious.

It'll take over a year to test up to 4 million bits, but that seems like the right path forward until I have a proof. Might need a faster algorithm!

[grencez]

19249+2^551542 might be prime. In that case, 2^exp = 1 does not imply that exp % 13 = 0.

[grencez]

Jeremiah mentioned in https://scholarcommons.sc.edu/etd/5879/ that if p*2^n+1 is composite for all n, then 2^n+p is composite for all n. Therefore, finding a prime 2^n+p would prove that some p*2^n+1 (different n) is prime. I'll work up to the next number (21181) in https://en.wikipedia.org/wiki/Seventeen_or_Bust. EDIT: This statement isn't totally accurate because it also relies on numbers from some finite set dividing every 2^n+p.

Also, based on the difficulty of the 19249 case, I wonder if the converse is true: If a prime p*2^n+1 exists, does that imply some 2^n+p (different n) is prime?

[grencez]

Hmm... 21181+2^28, 22699+2^26, 24737+2^17, and 55459+2^14 are prime. That was too easy. I need to work through a proof to make sure it implies that 21181, 22699, 24737, and 55459 aren't Sierpinski numbers.

67607+2^16389 is probably prime as well. Needs to be properly verified. That should be an easier exercise than for 19249+2^551542.

[grencez]

After rereading, it's clear that a prime 2^n+p implies one of the following:

• Some p*2^k+1 is prime.
• The set of primes that covers all p*2^k+1 isn't finite.
• The set is finite and includes 2^n+p. (Or could we arbitrarily choose other factors for the covering set?)

https://oeis.org/A076336 says it's a conjecture whether the two forms have a prime for exactly the same p values, but I kinda doubt it. Finding a counterexample would almost prove that a "covering set" can be infinite. ("Almost" since there's still a possibility that a prime 2^n+p could be in the covering set of p*2^k+1).