Problems & Puzzles:
A special set of binary numbers
T. D. Noe poses the
Let p be a prime number.
Consider the set of numbers Sp whose binary representation has p
1's and one zero. This set has p-1 odd numbers. For example, for
p=5, the set S5 contains binary numbers 111110, 111101, 111011,
110111, 101111, which are 62, 61, 59, 55, 47 in decimal. So S5
contains 3 prime numbers
Q. Does Sp
always contain at least one prime number?
Contributions came from Farideh Firoozbakht, J. Wroblewski, Jan van
Delden, Paul Underwood, Frederick Schneider, Charles Greathouse &
All members of S577 are composite... 5569 is the second prime p
such that all members of Sp are composite. What is the third such
Let Np be the number of primes in Sp. I have determined that:
Np>=2 for all other prime p<3000.
My feeling is that on average Np doesn't really depend on size of p
and therefore I conjecture that Np=0 for infinitely many primes p,
those primes may be so rare that finding the second one may be
hard. Similarly, I feel that Np may be arbitrariry large, but again,
may be hard to find convincing numerical evidence for that.
The largest I have found so far is N2399=19.
The results (currently the table of Np for primes p below 3000)
are in the file:
If p=577 then all terms of the form 2^(p+1)-1-2^i, with i in
0..p-1 are composite.
S_p can be represented by 2^(p+1)-2^k-1 with 0<=k<p. When k==0
then S_p[k] is even and therefore not prime. With a simple Pari/GP
program, using its simple composite test function, ispseudoprime(),
I checked for the existence of a prime for each set S_n for all
integers n<3000. I found that S_577 has no prime; 577 is prime. I
also gathered the following data for n (mod 8) where S_n has no
prime: [18, 8, 77, 4, 21, 10, 238, 0] showing, seemingly, for odd n
that S_n has more chance of containing a prime. However, of the 1499
odd numbers less than 3000 there are 429 primes. The fact there is
only one S_p without primes is intriguing.
The answer is no. For p=577, there are no primes in the set. That
the minimum p. I wrote a little program in Pari to do a brute force
S577 contains only composite numbers.
A naive analysis, relying on the fact that 2 and 3 do not divide
2^p-1-2^k, gives the chance that all numbers in Sp are composite is
which basic calculus shows limits toward a constant, about 0.000174.
In fact many numbers cannot divide 2^p-1-2^k, which complicates
analysis. Still, I would expect more counterexamples like S577
Once I've found the first two primes p such that the set Sp =
2^(p+1)-1-2^k for k=1,...,p-1, does not contains primes, i.e. 577
and 5569, I made a routinely check on OEIS and I found that T. D. Noe
has already submitted the result (see the comment) in
Since he does not state how far did he search, I'm letting run my
So far I've checked primes up to 12000 (which means numbers with
about 3600 digits in the set Sp) without finding any other such
prime... I let my program run. I reached up to prime 15373 without
finding any other
exception beside 577 and 5569.