"Prime-connectedness"

[spados at katamail.com]

Given a, b in {1,2,...,n} is it always possible to find a sequence x_{1}, x_{2},..., 
x_{k} in {1,2,...n}, such that a+x_{1}, x_{1}+x_{2},...,x_{k-1}+x_{k}, x_{k}+b 
are all primes?

I proved that there always exists a path from a to 1 if 2a<n as follows:

By Bertrand's Postulate there is a prime p_{1} between a and 2a, so there exists 
x_{1}<a such that a+x_{1}=p_{1}. Now x_{1}<a so 2x_{1}<p_{1}. So there 
exists a prime  p_{2} between x_{1} and 2x_{1} such that  p_{2}<p_{1} and so an 
integer x_{2}<x_{1} such that x_{1}+x_{2}=p_{2}... Since the sequence x_{i} 
decreases and we are dealing with positive integers it eventually stops at 1.

I verified the general conjecture up to n=100 as follows:

Define a graph G: (i,j) in E(G) iff i+j is prime with 1<= i,j <=n. Then the conjecture 
is equivalent to: "Is G connected for each n?"
Here's the Mathematica program I used

 <<DiscreteMath`Combinatorica`

g[n_] := MakeGraph[Range[n], (PrimeQ[#1 + #2]) &]

Table[ConnectedQ[g[n]], {n, 1, 100}]

Note that the (0,1)-matrix of my previous messages is the adjacency matrix of G.

Cheers,
Santi

__________________________________________


Fai i tuoi acquisti su www.kwshopping.it