Skip to main content
MathOverflow

Return to Answer

better algorithmm (backtracking), numerical results up to 1000, pic for n=100
Source Link
Moritz Firsching
Moritz Firsching
  • 10.7k
  • 3
  • 63
  • 88

It might seem plausible that the answer to your question could be: for the even n. (At least this is true for all $n$ up to 1401000. This can be checked by finding the Hamiltonian cycles with backtracking). For a random graph with $O(n\log n)$ edges, the probability to contain a Hamiltonian cycle tends to $1$. If the edges you prescribe behave randomly for even $n$ and there are more of them, then the result seems plausible.

On the other hand, the edges might not behave randomly; in fact for $n=142$ and $n=146$ I couldn't find a cycle, and also no certificate that such a cycle does not exist. For $n\in\{144,148,150,152,154\}$ I could again find cycles. (This might just be my computer taking long on these instances...)

Graph for n=16

For larger $n$ such picture are less useful. For example for here is a picture for $n=100$.

enter image description here

It might seem plausible that the answer to your question could be: for the even n. (At least this is true for all $n$ up to 140). For a random graph with $O(n\log n)$ edges, the probability to contain a Hamiltonian cycle tends to $1$. If the edges you prescribe behave randomly for even $n$ and there are more of them, then the result seems plausible.

On the other hand, the edges might not behave randomly; in fact for $n=142$ and $n=146$ I couldn't find a cycle, and also no certificate that such a cycle does not exist. For $n\in\{144,148,150,152,154\}$ I could again find cycles. (This might just be my computer taking long on these instances...)

Graph for n=16

It might seem plausible that the answer to your question could be: for the even n. (At least this is true for all $n$ up to 1000. This can be checked by finding the Hamiltonian cycles with backtracking). For a random graph with $O(n\log n)$ edges, the probability to contain a Hamiltonian cycle tends to $1$. If the edges you prescribe behave randomly for even $n$ and there are more of them, then the result seems plausible.

Graph for n=16

For larger $n$ such picture are less useful. For example for here is a picture for $n=100$.

enter image description here

added picture and more computational results
Source Link
Moritz Firsching
Moritz Firsching
  • 10.7k
  • 3
  • 63
  • 88

So for small even $n$ there always seem to be such strings, and for no small odd $n$. See my comment for an explanation why odd is never possible.

It might seemsseem plausible that the answer to your question could be: for the even n. (At least this is true for all $n$ up to 100140). For a random graph with $O(n\log n)$ edges, the probability to contain a Hamiltonian cycle tends to $1$. If the edges you prescribe behave randomly for even $n$ and there are more of them, then the result seems plausible.

On the other hand, the edges might not behave randomly; in fact for $n=142$ and $n=146$ I couldn't find a cycle, and also no certificate that such a cycle does not exist. For $n\in\{144,148,150,152,154\}$ I could again find cycles. (This might just be my computer taking long on these instances...)

Of course this method can be adapted to simliar situation, when your are looking for the difference being prime or the sums belonging to some other set (e.g. fewer primes).

I attach a picture for the graph and the Hamiltonian cycle for $n=16$.

Graph for n=16

So for small even $n$ there always seem to be such strings, and for no small odd $n$. It might seems plausible that the answer to your question could be: for the even n. (At least this is true for all $n$ up to 100)

So for small even $n$ there always seem to be such strings, and for no small odd $n$. See my comment for an explanation why odd is never possible.

It might seem plausible that the answer to your question could be: for the even n. (At least this is true for all $n$ up to 140). For a random graph with $O(n\log n)$ edges, the probability to contain a Hamiltonian cycle tends to $1$. If the edges you prescribe behave randomly for even $n$ and there are more of them, then the result seems plausible.

On the other hand, the edges might not behave randomly; in fact for $n=142$ and $n=146$ I couldn't find a cycle, and also no certificate that such a cycle does not exist. For $n\in\{144,148,150,152,154\}$ I could again find cycles. (This might just be my computer taking long on these instances...)

Of course this method can be adapted to simliar situation, when your are looking for the difference being prime or the sums belonging to some other set (e.g. fewer primes).

I attach a picture for the graph and the Hamiltonian cycle for $n=16$.

Graph for n=16

Source Link
Moritz Firsching
Moritz Firsching
  • 10.7k
  • 3
  • 63
  • 88

I am not quite sure what notation of cycles you use, but to investigate this question for small $n$ you could do the following. Build a graph $G$ with vertices $1,\dots,n$ and edges $\{i,j\}$ whenever $i+j$ is prime. Then you seem to be looking for Hamiltonian cycles in that graph. Here is what you get for some small n:

n
4 [1, 2, 3, 4]
6 [1, 4, 3, 2, 5, 6]
8 [1, 2, 5, 8, 3, 4, 7, 6]
10 [1, 4, 7, 10, 3, 2, 9, 8, 5, 6]
12 [1, 10, 3, 8, 11, 12, 7, 6, 5, 2, 9, 4]
14 [1, 10, 3, 2, 5, 14, 9, 8, 11, 12, 7, 4, 13, 6]
16 [1, 12, 7, 16, 15, 14, 9, 8, 5, 2, 11, 6, 13, 10, 3, 4]
18 [1, 18, 11, 8, 15, 16, 13, 6, 7, 12, 17, 2, 5, 14, 9, 10, 3, 4]
20 [1, 2, 9, 10, 3, 20, 11, 8, 5, 18, 19, 12, 17, 14, 15, 16, 7, 6, 13, 4]
22 [1, 2, 9, 22, 7, 4, 15, 8, 3, 10, 13, 16, 21, 20, 17, 14, 5, 6, 11, 18, 19, 12]
24 [1, 10, 3, 20, 23, 14, 9, 4, 7, 12, 19, 24, 13, 16, 21, 22, 15, 8, 5, 2, 17, 6, 11, 18]
26 [1, 16, 25, 12, 5, 14, 15, 22, 9, 8, 3, 26, 21, 20, 23, 24, 17, 2, 11, 6, 13, 18, 19, 4, 7, 10]
28 [1, 18, 23, 24, 19, 4, 27, 2, 17, 14, 15, 26, 11, 8, 5, 12, 7, 16, 21, 22, 25, 28, 9, 20, 3, 10, 13, 6]
30 [1, 16, 13, 18, 23, 20, 3, 10, 27, 26, 15, 8, 29, 30, 11, 2, 21, 22, 9, 28, 25, 12, 5, 14, 17, 24, 19, 4, 7, 6]
32 [1, 16, 21, 2, 17, 14, 29, 30, 31, 6, 7, 22, 25, 28, 15, 26, 3, 10, 13, 4, 27, 32, 5, 8, 9, 20, 23, 24, 19, 12, 11, 18]

So for small even $n$ there always seem to be such strings, and for no small odd $n$. It might seems plausible that the answer to your question could be: for the even n. (At least this is true for all $n$ up to 100)