On Thu, 12 Mar 2009, Allan Wechsler wrote:
However, 10000971767 is prime.
Allan, Okay, now I see what you and Rich were getting at--especially Rich's comment that we know integers k such that k + 2^n is composite for nonnegative n. After searching for such numbers myself I finally found a few candidates which led me via online search to various results about Sierpinski numbers (k for which k*2^n + 1 are always composite) and their "duals" (k for which 2^n + k are always composite). No doubt this is what Rich was referring to. To account for changes in the binary representation of 1 to 0 it would be nice to also have the condition that k - 2^n is composite. Clearly both conditions k + 2^n and k - 2^n composite for all n together is much stronger than the differ-in-one-bit criterion. According to http://www.research.att.com/~njas/sequences/A076336 the Sierpinski numbers are conjectured to be the same as the dual Sierpinski numbers. (See comments about S1 and S2 in A076336.) Assuming this conjecture is true and checking the values given in A076336 the only prime in the OEIS list which "works", i.e., is isolated, (if I haven't made an error) is 2131099: That is, assuming this is a dual Sierpinski number one only needs to check that if any 1 digit is replaced by 0 in its binary representation then the corresponding value is composite. This seems to be the case. So assuming the conjecture that 2131099 is a dual Sierpinski number then it is an isolated vertex in the binary version of Rich's graph with Allan's extended definition of adjacency. Meanwhile I also found a paper by Yong-Gao Chen ,J. Number Theory 125 (2007), no.1, 14-15, wherein he apparently proves among other things that there exists an infinite arithmetic progression of positive odd integers k such that for any nonnegative integer n each of the four integers k-2^n,k+2^n,k2^n+1,k2^n-1 has at least two distinct odd prime factors. I glanced at the paper and so far as I can tell there is no evidence that the arithmetic progression he mentions contains a prime. Nevertheless one is encouraged to imagine that there is such a k that is prime. If so it would a fortiori be isolated in the binary version of Rich's graph with Allan's extension. Perhaps a base b Chen/Sierpinski-like number is too much to ask for? Namely, for base b >1 are there (hopefully prime) k such that k+a*b^n , k-a*b^n , k*b^n +a and k*b^n-a are composite for all n and positive a < b? This would give us isolated vertices for base b. A cursory search of MathSciNet didn't bring up any such stuff. Maybe someone knows more about such matters? A quick search found a few primes p such that for n from 0 to 20 and a from 1 to 9, p+a*10^n is composite. As things go in the Sierpinski -number-search-world this is very weak evidence, but suggestive enough for me to bet ( a small amount) on the graph having isolated vertices for all bases. Of course, it is trivial to find primes p such that p + 10^n is composite for all nonnegative integers n. For example, just choose p = 8 (mod 9). --Edwin