Prove that for any n . . .?

Great question!

I have no proof, and don't even know if the approach below is useful. But just want to throw out a few ideas.

First, we can introduce some tools and terminology from graph theory. For each integer N, we let G(N) be the graph with vertices labeled 1 ... N, and edges between two vertices a,b if and only if a+b is prime. Vikram's conjecture is then

(V-conj): "Given G(N), the vertex 1 and the vertex N is Hamiltonian-connected."

where we abuse the terminology to say that two vertices are Hamiltonian connected if there exists a Hamiltonian path between them [1].

It is clear that for (V-conj) to be true, at minimum you need that G(N) is a connected graph. As it turns out, by using Bertrand's postulate, G(N) can be checked to be connected inductively: G(1),G(2), and G(3) are trivial cases to check. Assuming G(n) is connected, then if n > 2, there exists prime p such that 1+ n+ 1 = n + 2 < p < 2n + 2 = 2(n+1).

So that p can be written as a sum (n+1) + k for some k between 2 and n. Now using that G(n) is the induced subgraph of G(n+1), we have that G(n+1) is connected. Furthermore, we have also shown that there exists at least one edge from the vertex (n+1) to G(n) that does no connect to the vertex 1. [If the only path between 1 and (n+1) in G(n+1) is the edge between 1 and (n+1), then (V.conj) is false.]

Now, if G(n) were Hamiltonian connected, then (V.conj) is true by trivial induction. However,

(a) G(n) is bipartite. This is obvious from the fact that any prime bigger than 2 is odd. So any edge connecting two vertices in G(n) must link a even number with an odd number. This implies, by a counting argument, that at most half of the graph can be connected to 1 by a Hamiltonian path.

(b) In the case of G(5), we already see that there is no Hamiltonian path between 1 and 3, since 5+4 = 9 is composite.

But of course, that would've made the problem too easy and I wouldn't have starred it. :)

Looking at the small graphs gives some ideas:

First look at G(4), it looks like a square with edges 12, 14, 23, 24. Now add 5, the only allowed new edge is 25. Now add 6 to G(5), if 6 does not connected to 5, but to some other number, we would have a Box with two horns coming out, for which it would've been simple to see that 1 and 6 is not Hamiltonian-connected. Fortunately, 6 connects to 5 and 1 in G(6).

Therefore, a necessary condition for (V.conj) is

(lem1) "If there is only one edge connecting n with G(n-1), then 2n+1 must be prime."

However, this is not very useful, as by Nagura's strenghthening of Bertrand's postulate, if n > 24, then n+1 is connected to G(n) by at least 3 edges. In fact, as Vikram noted, by the prime number theorem, the minimal number of edges connecting n+1 to G(n) grows something like log.

------------------------

Below are just some incomplete thoughts:

(i) One may want to prove using some sort of strong induction: that any element g in G(n) such that g+n+1 is prime is Hamiltonian connected to 1. But I am pretty sure this statement is too strong to be true.

(ii) Perhaps a pigeon-hole type density argument? If one can show that the graph G(n) becomes more and more Hamiltonian connected Well, being bipartitite, we may ask whether the number of points Hamiltonian connected to 1 approach n/2 sufficiently fast as n grows. If so, the PMT may give an upper bound on where the counterexample may occur.

There is a relatively easy pattern to follow.

I am going to begin with n = 10, iterate a few steps, and then list the pattern.

n=10: 1, 2, 9, 4, 7, 6, 5, 8, 3, 10

n=11: 1, 10, 3, 8, 5, 6, 7, 4, 9, 2, 11

n=12: 1, 10, 3, 8, 5, 6, 7, 4, 9, 2, 11, 12

n=13: 1, 12, 11, 2, 9, 4, 7, 6, 5, 8, 3, 10, 13

update: Based on some further looking and Vikram's note, I concur that there is no simple pattern for rearranging any random n digits.

I will note that if you pick any given integer k, you *can* rearrange the integers so that the adjacent sums are all prime; by extension, you can easily rearrange the list for k+1. However, this doesn't mean that it is true for *all* integer values, unlike other induction proofs.

update2: I concur with jordan. I knew that there was some theorem/conjecture that there is always a prime number between n and 2n and that this is the key to showing that for any given integer an arrangement can be found.

However, there aren't any other clear patterns that I can see. In between prime numbers there are easy patterns, but the patterns always break down when n is prime because the arrangement for (n+1) has to be altered.

Although Vikram's Conjecture is true (you can construct the arrangement for any given n), it isn't possible to prove that it is true for *any* n.

Hi Vikram! Some months ago a frined of mine asked me the same question, but he didn't say me if it was a conjecture too or a solved exercise. It seems that we need to proceed by induction, assuming that for a fixed n there exist a permutazion σ(1),σ(2),...,σ(n) such that σ(i)+σ(i+1) is prime for all 1 ≤ i ≤ p-1. Now we add the new term n+1: we must prove that there exist a integer i such that 1 ≤ i ≤ p-1 and at least one of:

i) n+1+σ(1) is prime;

ii) n+1+σ(n) is prime;

iii) n+1+σ(i) and n+1+σ(i+1) are both prime.

By further generalization of Bertand postulate we know that for sufficiently large n there exist p,q primes such that n<p<q<2n. But it is again not sufficient to deduce your statement. So, what is the source?

---------

finehallibrary, if i don't wrong Erdos proved that for all e>0 there exist v>0 such that in [n,n(1+e)] there is always a prime for all n>v. But it don't help in proving the statement.

If also in Sloane there are a reference in a book "unsolved problem in number theory" is it really again a conjecture?

---------

@jaz_will: I like your idea to represent the problem with a hamiltonian path graph..however i don't think that some form of induction can work definitively. I'll try again with some lower bound on prime counting function, with the aim of proving it for all n sufficientely large, so unless a finite number of cases that can be done by hand (or, better, by computer XD).

Although.. thinking is different by proving.

-------

Wow, also Direc and Ore Theorems (1960 about) are too waek to prove our statement (it can be seen with some approximation bound with PNT)..I think this question is one the best on YA if it can be solved.

--------

I surrend. I searched everywhere and made estimates of all types, also all theorem on graph theory are too weak to prove the existence of a hamiltonian path. At the end I found this topic on Mathlinks in section "open problems", and also Rust didn't solve it http://www.mathlinks.ro/Forum/viewtopic.php?search... : he gave a trivial example related on the also unsolved twin prime coinjecture. And it does not solve again our problem..

I made this problem http://answers.yahoo.com/question/index?qid=200910... for you, i hope you like it (ps. this one is not a conjecture XD)

Cheers Vikram!

Paolo

I'm changing my answer completely...

This isn't a proof, but this should (hopefully) convince you that your conjecture is true.

Let k = 16597. For n > 2010759, there exists a prime p, such that n < p < n(1+1/k)

(See: http://www.unilim.fr/laco/theses/1998/T1998_01.pdf for proof)

As n grows larger, the value for k will increase as well.

But in any case, hurry up and get your program up from 10^5 to 2x10^6 =P

Then.... someone feel free to finish out my thoughts!

(PNT's growth rate is way slower than 2n!)

Should we give this problem a name, such as the "Vikram Conjecture"?

hello there