Problems & Puzzles: Puzzles

Puzzle 437. A special set of binary numbers T. D. Noe poses the following question: 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 & Giovanni Resta.

***

Farideh wrote:

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 prime?

Jarek wrote:

Let Np be the number of primes in Sp. I have determined that:
N577=0
N2=N2819=1
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, but
those primes may be so rare that finding the second one may be really
hard. Similarly, I feel that Np may be arbitrariry large, but again, it
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:
http://www.math.uni.wroc.pl/~p-k1g4/437.txt

***

Jan wrote:

If p=577 then all terms of the form 2^(p+1)-1-2^i, with i in 0..p-1 are composite.

***

Paul wrote:

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.

***

Fred wrote:

The answer is no. For p=577, there are no primes in the set. That is
the minimum p. I wrote a little program in Pari to do a brute force
search.

***

Charles wrote:

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
(1-6/(p+1)log2)^(p-1) 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

***

Resta wrote:

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 http://www.research.att.com/~njas/sequences/A138290

Since he does not state how far did he search, I'm letting run my program.
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.

***