Dr. Pickover commented:
In 1848, Camille Armand Jules Marie, better known as the “Prince de Polignac,” conjectured that every odd number is the sum of a power of two and a prime. (For example 13 = 23+5.) He claimed to have proved this to be true for all numbers up to three million, but de Polignac probably would have kicked himself if he had know that he missed 127, which leaves residuals of 125, 123, 119, 111, 95 and 63 (all composites) when the possible powers of two are subtracted from it. There are another 16 of these odd numbers—which my colleague Andy Edwards calls “obstinate numbers”—that are less than 1000. There are an infinity of obstinate numbers greater than 1000. Most obstinate numbers we have discovered are prime themselves. The first composite obstinate number is 905.
Then he asked:
What is the largest obstinate number you can compute?
Can you find an obstinate number terminating in every digit from 0 to 9, or are certain terminal digits impossible to find?
Other unanswered questions:
1) What is the smallest difference between adjacent obstinates?
2) Do any obstinates undulate? (Undulating numbers are of the form: ababababab… For example, 171717 and 28282 are undulating numbers, but they’re not obstinate, as far as I know.)
If you make discoveries, give us some ideas about the kinds of search programs you used.
Curiosity piqued, I looked into the subject. As far as I can tell, the only upper limit as to the size of potentially “obstinate” numbers would be the amount of computer processing power you’d want to put into it. I ran an extensive search and there was no appreciable lessening to the frequency of the numbers and no suggestion that they would “level off” at any point, so I have no reason to not suppose they are an infinite set. The largest I have found so far is:
999999999999999999999999999999999999999999999999999999999999999
999999999999999999999999999999999999999999999999999999999999999
9999999999999999999999999999999999999999999999999999999999037
I stopped there not because I’d reached the limits of my processing power, but only because I’d reached the limit of my patience for waiting for further results. It leaves a composite residue for all 621 possible powers of two than can be subtracted from it. Later, this result increased to:
999999999999999999999999999999999999999999999999999999999999999
999999999999999999999999999999999999999999999999999999999999999
999999999999999999999999999999999999999999999999999999999999999
999999999999999999999999999999999999999999999999999999999999999
999999999999999999999999999999999999999999999999999999999999999
999999999999999999999999999999999999999999999999999999999999999
999999999999999999999999999999999999999999999999999999999999999
999999999999999999999999999999999999999999999999999999999999999
9999999011
This leaves 1,708 powers of two in the residue. (This number has since been increased; see the article, Obstinate Numbers in the Triangle of the Gods.)
Dr. Pickover also asked if obstinate numbers could terminate in all ten natural digits. I suspect he was trying to trip one up with that since the very definition of obstinate numbers requires them to be odd—as such, they cannot end with an even digit. All odd digits are accounted for, however, in the results I have so far found. As far as the question about the smallest difference between adjacent obstinates, it has to be two. Both 905 and 907 are obstinate, and since obstinate numbers must be odd, two is the smallest possible difference. I would be interested, myself, in the largest difference, and I will probably run a search for it later, but I haven’t yet. When I do, I’ll update these notes. He asked about undulation, and from what I can see, it doesn’t seem to be at all uncommon with these numbers. At a glance, these undulating numbers are all obstinate:
6161
14141
39393
91919
1313131
1818181
7070707
7474747
7676767
7979797
59595959
73737373
343434343
757575757
797979797
929292929
1717171717
3131313131
9191919191
12121212121
14141414141
18181818181
32323232323
54545454545
78787878787
91919191919
7171717171717
25252525252525
29292929292929
37373737373737
43434343434343
67676767676767
97979797979797
I’m certain there are others; I simply didn’t bother continuing the search at higher numbers.
As far as the question as to what search programs were used, for the above I simply wrote two Maple functions—one to check for obstinacy and another to print a list of composite residues. Once those two were in place, the search was easy—just a matter of waiting. For any interested parties, I’ll reproduce the body of the two functions here. They can probably be optimized, but I’m not an especially adept Maple coder (Maple code reminds me far too much of BASIC and that gives me nightmares).
with(numtheory):
isObstinate := proc(o)
local pp, p, a, z:
if o mod 2 <> 0 then
pp := 0: a := floor(log[2](o)):
for z to a do
p := o - 2^z:
if isprime(p) then pp := 1 fi:
od:
if pp = 0 then true else false fi:
else
printf("Must be oddn"):
fi:
end:
showResidue := proc(n)
local a, z, p:
a := floor(log[2](n)):
for z to a do
p := n - 2^z:
if not isprime(p) then
printf("2^%d + %dn",z,p)
fi:
od:
end:With those it’s simply a matter of running through the odd numbers and checking isObstinate(number). If a residue list is desired, just throw an obstinate number to showResidue(number). (Note that the latter function assumes you’re feeding it an obstinate number: it doesn’t check to see if you have, or if all of the residue values printed are composite. With the way I used it, there was no point in having the redundant code so I omitted it.)
Slightly more structured test conditions for Mathematica:
ObstinateQ[n_Integer /; n > 0] :=
If[OddQ[n],
If[Intersection[
Table[PrimeQ[n - 2^j], {j, 1, Floor[Log[2, n]]}],
{True}] == {},
True, False
],
Print["Must be odd."]
]
NPResidue[n_Integer /; ObstinateQ[n]] :=
If[
rt = Table[n - 2^j, {j, 1, Floor[Log[2, n]]}];
Intersection[Map[PrimeQ, rt], {True}] == {},
rt,
Print["Residue includes Prime(s)."]
]
A last note, Dr. Pickover remarked that “most” obstinate numbers they’d found were prime numbers themselves. It leads me to believe that they didn’t research much beyond the 1000 point since from the lowest obstinate number, 127, to 100,000, I found a total of 3,392 obstinate numbers, 2,147 of which were composite: the 1,245 prime values were clearly the minority. Considering the decreasing frequency of primes in general as numbers grow increasingly larger, and the seeming continued regularity of obstinate numbers, it seems that the nonprime values will naturally continue to widen the gap between themselves and their prime counterparts.
