Skip to main content
MathOverflow

Return to Answer

slight mathematical improvement
Source Link
Johan Wästlund
Johan Wästlund
  • 5.5k
  • 3
  • 28
  • 35

Here is a construction that allowed me to verify with a few minutes of computer time that such cycles exist for all even $N \leq 10^{12}$. Let $G_n$ be the "prime-sum" graph with vertices labeled $1,\dots,n$ and edges connecting numbers that sum to a prime. First notice that if $N$ is even and there is a twin prime pair $N+2k-1$ and $N+2k+1$ with $2k<N$, then there is a path in $G_N$ from $2k-1$ to $2k$ that includes all larger numbers up to $N$ (just follow the edges that correspond to sums $N+2k-1$ and $N+2k+1$). So if there is a hamilton path in $G_{2k}$ from $2k-1$ to $2k$, then combining these two paths yields a hamilton cycle in $G_N$.

It is relatively straightforward to construct inductively such hamilton paths for $2k<10^7$, again using twin primes. If $2k-1$ and $2k+1$ are prime, the edges of those two sums immediately yield the desired path (this would give Douglas Zare's construction). Otherwise let $2k+a-1, 2k+a+1$ be the next twin prime pair. The edges corresponding to these two sums will give a path from $2k-1$ to $2k$ leaving out only the numbers $1,\dots, a$. Assuming that we already obtained a hamilton path from $a-1$ to $a$ in $G_a$, we can now "glue" that path to the path from $2k-1$ to $2k$ by replacing an appropriate edge. Alternatively we can use the hamilton path from $a+1$ to $a+2$ in $G_{a+2}$ and "glue" with two suitably chosen edges.

This means that whenever $N$ is even and there is a twin prime pair larger than $N$ and within distance $10^7$, there is a hamilton cycle in $G_N$. We can therefore check the existence of such hamilton cycles for $N\leq 10^{12}$ (and probably way larger) by finding a sequence of twin prime pairs with distances just below $10^7$, without performing any calculations for individual values of $N$.

EDIT: A modification of this argument shows that there are infinitely many values of $N$ for which $G_N$ is hamiltonian.

If $N+1$ and $N+2k+1$ are prime, we can use all edges with these two sums to obtain a collection of $k$ paths that start and end in $\{1,\dots, 2k\}$ so that for each path, the sum of the two endpoints is congruent to $N+1$ modulo $2k$.

By the famous theorem of Zhang, Maynard, Tao and others (Polymath 8a, 8b) on bounded gaps between primes, there are infinitely many $N$ for which this holds with $2k\leq 246$.

We can now check that for each $k\leq 123$ and each possible congruence class of $N$ modulo $2k$ (the even classes), these paths can be combined with $k$ more edges (matching $1, 3, 5,\dots, 2k-1$ to $2,4,6,\dots, 2k$) into a hamilton cycle. With only one exception, this completion can be obtained by taking either the edges that sum to $2k+1$ or the edges that sum to two primes of the form $p$ and $p+2k$.

The only exception is when $2k=20$ and $N\equiv 6$ (mod 20). In that case the long paths will connect numbers in $\{1,\dots,20\}$ that sum to 7 or 27, and none of the three prime-pairs $(3, 23)$, $(11, 31)$ or $(17, 37)$ will connect them into a single cycle. But it is easy to find an ad-hoc solution to that single case.

Here is a construction that allowed me to verify with a few minutes of computer time that such cycles exist for all even $N \leq 10^{12}$. Let $G_n$ be the "prime-sum" graph with vertices labeled $1,\dots,n$ and edges connecting numbers that sum to a prime. First notice that if $N$ is even and there is a twin prime pair $N+2k-1$ and $N+2k+1$ with $2k<N$, then there is a path in $G_N$ from $2k-1$ to $2k$ that includes all larger numbers up to $N$ (just follow the edges that correspond to sums $N+2k-1$ and $N+2k+1$). So if there is a hamilton path in $G_{2k}$ from $2k-1$ to $2k$, then combining these two paths yields a hamilton cycle in $G_N$.

It is relatively straightforward to construct inductively such hamilton paths for $2k<10^7$, again using twin primes. If $2k-1$ and $2k+1$ are prime, the edges of those two sums immediately yield the desired path (this would give Douglas Zare's construction). Otherwise let $2k+a-1, 2k+a+1$ be the next twin prime pair. The edges corresponding to these two sums will give a path from $2k-1$ to $2k$ leaving out only the numbers $1,\dots, a$. Assuming that we already obtained a hamilton path from $a-1$ to $a$ in $G_a$, we can now "glue" that path to the path from $2k-1$ to $2k$ by replacing an appropriate edge. Alternatively we can use the hamilton path from $a+1$ to $a+2$ in $G_{a+2}$ and "glue" with two suitably chosen edges.

This means that whenever $N$ is even and there is a twin prime pair larger than $N$ and within distance $10^7$, there is a hamilton cycle in $G_N$. We can therefore check the existence of such hamilton cycles for $N\leq 10^{12}$ (and probably way larger) by finding a sequence of twin prime pairs with distances just below $10^7$, without performing any calculations for individual values of $N$.

Here is a construction that allowed me to verify with a few minutes of computer time that such cycles exist for all even $N \leq 10^{12}$. Let $G_n$ be the "prime-sum" graph with vertices labeled $1,\dots,n$ and edges connecting numbers that sum to a prime. First notice that if $N$ is even and there is a twin prime pair $N+2k-1$ and $N+2k+1$ with $2k<N$, then there is a path in $G_N$ from $2k-1$ to $2k$ that includes all larger numbers up to $N$ (just follow the edges that correspond to sums $N+2k-1$ and $N+2k+1$). So if there is a hamilton path in $G_{2k}$ from $2k-1$ to $2k$, then combining these two paths yields a hamilton cycle in $G_N$.

It is relatively straightforward to construct inductively such hamilton paths for $2k<10^7$, again using twin primes. If $2k-1$ and $2k+1$ are prime, the edges of those two sums immediately yield the desired path (this would give Douglas Zare's construction). Otherwise let $2k+a-1, 2k+a+1$ be the next twin prime pair. The edges corresponding to these two sums will give a path from $2k-1$ to $2k$ leaving out only the numbers $1,\dots, a$. Assuming that we already obtained a hamilton path from $a-1$ to $a$ in $G_a$, we can now "glue" that path to the path from $2k-1$ to $2k$ by replacing an appropriate edge. Alternatively we can use the hamilton path from $a+1$ to $a+2$ in $G_{a+2}$ and "glue" with two suitably chosen edges.

This means that whenever $N$ is even and there is a twin prime pair larger than $N$ and within distance $10^7$, there is a hamilton cycle in $G_N$. We can therefore check the existence of such hamilton cycles for $N\leq 10^{12}$ (and probably way larger) by finding a sequence of twin prime pairs with distances just below $10^7$, without performing any calculations for individual values of $N$.

EDIT: A modification of this argument shows that there are infinitely many values of $N$ for which $G_N$ is hamiltonian.

If $N+1$ and $N+2k+1$ are prime, we can use all edges with these two sums to obtain a collection of $k$ paths that start and end in $\{1,\dots, 2k\}$ so that for each path, the sum of the two endpoints is congruent to $N+1$ modulo $2k$.

By the famous theorem of Zhang, Maynard, Tao and others (Polymath 8a, 8b) on bounded gaps between primes, there are infinitely many $N$ for which this holds with $2k\leq 246$.

We can now check that for each $k\leq 123$ and each possible congruence class of $N$ modulo $2k$ (the even classes), these paths can be combined with $k$ more edges (matching $1, 3, 5,\dots, 2k-1$ to $2,4,6,\dots, 2k$) into a hamilton cycle. With only one exception, this completion can be obtained by taking either the edges that sum to $2k+1$ or the edges that sum to two primes of the form $p$ and $p+2k$.

The only exception is when $2k=20$ and $N\equiv 6$ (mod 20). In that case the long paths will connect numbers in $\{1,\dots,20\}$ that sum to 7 or 27, and none of the three prime-pairs $(3, 23)$, $(11, 31)$ or $(17, 37)$ will connect them into a single cycle. But it is easy to find an ad-hoc solution to that single case.

Source Link
Johan Wästlund
Johan Wästlund
  • 5.5k
  • 3
  • 28
  • 35

Here is a construction that allowed me to verify with a few minutes of computer time that such cycles exist for all even $N \leq 10^{12}$. Let $G_n$ be the "prime-sum" graph with vertices labeled $1,\dots,n$ and edges connecting numbers that sum to a prime. First notice that if $N$ is even and there is a twin prime pair $N+2k-1$ and $N+2k+1$ with $2k<N$, then there is a path in $G_N$ from $2k-1$ to $2k$ that includes all larger numbers up to $N$ (just follow the edges that correspond to sums $N+2k-1$ and $N+2k+1$). So if there is a hamilton path in $G_{2k}$ from $2k-1$ to $2k$, then combining these two paths yields a hamilton cycle in $G_N$.

It is relatively straightforward to construct inductively such hamilton paths for $2k<10^7$, again using twin primes. If $2k-1$ and $2k+1$ are prime, the edges of those two sums immediately yield the desired path (this would give Douglas Zare's construction). Otherwise let $2k+a-1, 2k+a+1$ be the next twin prime pair. The edges corresponding to these two sums will give a path from $2k-1$ to $2k$ leaving out only the numbers $1,\dots, a$. Assuming that we already obtained a hamilton path from $a-1$ to $a$ in $G_a$, we can now "glue" that path to the path from $2k-1$ to $2k$ by replacing an appropriate edge. Alternatively we can use the hamilton path from $a+1$ to $a+2$ in $G_{a+2}$ and "glue" with two suitably chosen edges.

This means that whenever $N$ is even and there is a twin prime pair larger than $N$ and within distance $10^7$, there is a hamilton cycle in $G_N$. We can therefore check the existence of such hamilton cycles for $N\leq 10^{12}$ (and probably way larger) by finding a sequence of twin prime pairs with distances just below $10^7$, without performing any calculations for individual values of $N$.