8
$\begingroup$

Udpate 4: Trying to characterize finite and infinite cycles.

Update 3: All primes $a_0\ge29$ seem to either have infinite cycles or finite non-terminating cycles that converge to infinite cycles of other primes. More examples added at the end of the post (visualized as graphs). Also, renamed the post.

Update 2: I've found it can be shown that $29$ and $31$ will never terminate. I believe the same can be done for all other primes. Explanation is added at the end of the post.

Update 1: Turns out my initial question is a degenerate case of a broader observation. The broader observation ("Conjecture") is added at the bottom of the post.



Defining the sequence

Pick any starting number $a_0\in\mathbb N$ on the number line.

At $n$th step (starting at step $n=1$ on your starting number):

  • jump $a_0+n$ numbers to the right (add $a_0+n$) if current number is not composite
  • jump $a_0+n$ numbers to the left (subtract $a_0+n$) if current number is composite
  • If $a_0\lt0$, then reverse the condition (subtract for not composite and add for composite).
  • If $a_0=0$, you stop jumping.

By "not composite", it is meant "prime or one" (zero is stopping condition).

For example, If we start with $a_0=6$, we have $(6)-7\rightarrow(-1)-8\rightarrow(-9)+9\rightarrow0$.

This process can be defined as:

Pick a starting number $a_0\in\mathbb N$ and define a sequence: $a_{n+1}=$

$$ \begin{cases} a_{n}+(a_0+n+1), & \text{if $a_n>0$ and $a_n$ is not composite or $a_n<0$ and $|a_n|$ is composite} \\ a_{n}-(a_0+n+1), & \text{if $a_n<0$ and $|a_n|$ is not composite or $a_n>0$ and $a_n$ is composite} \\ 0, & \text{if $a_n=0$} \end{cases} $$

"Not composite" in the above definition means that it "is prime or is $1$".
"Composite" is then "not prime and not one", while zero ends the sequence.

If there exists $k\in\mathbb N$ such that $a_k=0$, then we say the sequence terminates (converges to $0$).


Examining the sequence

It is easy to show that if $a_0$ is composite, the sequence always terminates:
(One can write down the sequence for even $a_0$ and for odd $a_0$ to conclude:)

  • $a_3=0$ if $a_0$ is odd and composite, or $a_0$ is even and $a_0+3$ is composite
  • $a_{11}=0$ if $a_0$ is even and $a_0+3$ is not composite and $a_0+11$ is composite
  • $a_{19}=0$ if $a_0$ is even and $a_0+3$ is not composite and $a_0+11$ is not composite


But when $a_0$ is prime or equal to $1$ (not composite), I have (computed):

  • $a_0=1 \rightarrow a_{14}=0, \space(1, 3, 6, 2, 7, 13, 20, 12, 3, 13, 24, 12, -1, -15, 0)$
  • $a_0=2 \rightarrow a_{8}=0, \space(2, 5, 9, 4, -2, -9, -1, -10, 0) $
  • $a_0=3 \rightarrow a_{6}=0, \space(3, 7, 12, 6, -1, -9, 0) $
  • $a_0=5 \rightarrow a_{22}=0, \space(5, 11, 18, 10, 1, 11, 22, 10, -3, -17, -32, -16, 1, 19, 38,\dots, 0) $
  • $a_0=7 \rightarrow a_{14}=0, \space(7, 15, 6, -4, 7, 19, 32, 18, 3, 19, 36, 18, -1, -21, 0) $
  • $a_0=11 \rightarrow a_{14}=0, \space(11, 23, 36, 22, 7, 23, 40, 22, 3, 23, 44, 22, -1, -25, 0) $
  • $a_0=13 \rightarrow a_{42}=0, \space(13, 27, 12, -4, 13, 31, 50, 30, 9, -13, -36, -12, 13, 39, 12,\dots, 0) $
  • $a_0=17 \rightarrow a_{38}=0, \space(17, 35, 16, -4, 17, 39, 16, -8, 17, 43, 70, 42, 13, 43, 74, 42, 9, \dots, 0) $
  • $a_0=19 \rightarrow a_{110}=0, \space(19, 39, 18, -4, 19, 43, 68, 42, 15, -13, -42, -12, 19, 51, 18,\dots, 0) $
  • $a_0=23 \rightarrow a_{106}=0, \space(23, 47, 72, 46, 19, 47, 76, 46, 15, -17, -50, -16, 19, 55, 18, \dots,0) $

Prime numbers $\ge29$ seem to never reach $0$.

Are these truly the only primes that reach zero?

Can we show that no other prime will reach zero?



Update 1: After letting the sequence continue after numbers hit $0$, and observing sequences:

(If $0$ in the above definition is treated as composite and does not terminate the sequence:)

Conjecture:

If we observe $a_0=a\ne23$, then:

If $(a\gt19)$ is not prime, and $(a+4k)$ is prime number for some $k\in\mathbb N$, then the sequence starting with $a_0=a$ will hit $0$ exactly $k$ times for terms $a_3,a_7,a_{11},\dots,a_{4k-1}$, and no other terms.

The case $k=0$ is a degenerate case of the previous claim and is:
If $(a\gt19)$ is prime, we never hit $0$.

It is easily shown that the above holds for $k\ne0$ (all cases of $k$ but the degenerate one) as odd composite numbers will reach zero at $a_3$ after which we have a new odd number, and the same thing will repeat unless we have a prime number; which causes the sequence to enter a cycle which seems to contains no further zeroes (entering the $k=0$ case).

Trivial observation for cases not included above:

If $(1\le a\le19)$ or $(a\gt2$ and is even$)$, $a_0=a$ will hit zero infinitely many times.

This is true (can be easily shown) for even numbers since we know that even numbers $\gt2$ will reach zeroes at one of $a_3,a_{11},a_{19}$ terms for the first time, after which we are left with a new even number, which repeats the cycle indefinitely.

It is true as well for first $19$ numbers and number $23$ since they are computed to continue at an even number after reaching their first zero, which enters the infinite cycle of the even numbers.

It still remains to show that prime numbers $\ge29$ themselves will not reach zero, as those primes seem to enter cycles that do not contain zeroes.

I suspect one should be able to show cycles that do not contain zero for odd prime numbers, similar to the cycle for even numbers which revisits the zero infinitely many times.


Update 2: I've observed that consecutive prime numbers reach same values infinitely many times. For example, primes $29,31$ will reach numbers ${25,26,27,28,29,30,31}$ infinitely many times as some $a_k$ members of their sequences.

Turns out it can be shown that $29$ and $31$ will never reach $0$.

This can be done by observing $a_k=29$ and assuming $k$ is even. By looking at all cases while writing out the sequence, eventually a full cycle will be shown and we can use induction. (Also for example; If you assume $59+k$ is prime and follow the blue arrow as shown below, that implies $k$ is even in the following nodes.)

A simplified proof can be shown as a graph that generates the sequences for $29$ and $31$:

enter image description here

Red arrows imply the previous node is composite, and blue arrows imply it is prime.

Note that constants summed with $k$ in nodes are based on the starting position $a_k=29$ and assuming shorter paths back to $29$; taking longer paths results in larger summing constants in some nodes (meaning nodes being visited repeatedly or in different order following the longer paths before reaching $29$ and substituting $a_{k+l}=29$ with $a_k=29$ again); but the graph remains the same nonetheless.

The nonconstant nodes clearly grow in absolute value for $k\ge0$ and $\ne0$.


I believe we can construct a generating graph for all sequences starting with primes and show that the ones where $a_0\ge29$ will never reach $0$.

Is it possible to prove this for all primes, rather than confirming it one by one for individual (finitely many) cases?



Update 3: It seems that every starting prime number $a_0\ge29$ will either revisit itself infinitely many times (infinite cycle) for some $a_k$ terms, or revisit itself finitely many times (finite cycle), and after that its sequence will converge to a sequence of some other prime; which again either has an finite or infinite cycle.

We can revisit the $(29,31)$ example from above, where we have that the sequences of these two primes are the same infinite cycle. We can draw the same graph from above in a circular form:

enter image description here

Nodes represent some terms $a_k$ of their sequences, and following the arrows you get the next term $a_{k+1}$. Nonconstant nodes have decimal names which were generated while drawing the graph. Constant nodes have their exact values; these are ${25,26,27,28,29,30,31}$ for this particular example, as already mentioned above.

Nonconstant nodes $a_k$ are either always composite, or take both composite and prime values for different $k$; which is shown by having either one or two different paths leaving them.


We can also look at an example involving finite cycles.

Prime number $157$ has a finite cycle and its sequence converges to the prime number $163$.
(Last time it is revisited is for $a_{116}=157$, and in total it is visited $23$ times)

Prime numbers $(163,167)$ share the same finite cycle, and it converges to the prime number $173$.
(Last time $a_0=163$ is revisited is for $a_{152}=163$, and in total it is visited $27$ times; Last time $a_0=167$ is revisited is for $a_{12}=167$, and in total it is visited $4$ times)

Prime number $173$ has a finite cycle and its sequence converges to the prime number $179$.
(Only time it is visited is for $a_{0}=173$, in total that's only once)

Prime numbers $(179,181)$ share the same infinite cycle which can be displayed:

enter image description here

We can also visualize the previous finite cycles of primes which eventually converge to the above cycle (redrawn again as the rightmost cycle): $157\rightarrow (163,167)\rightarrow173\rightarrow (179,181).$

enter image description here

Click the image to see it in full size.


Another example; primes $(37,41,43)$ all share the same infinite cycle, and prime $47$ has a minimal finite cycle which converges to theirs:

enter image description here

There is also an example such as:
$359\rightarrow367\rightarrow373\rightarrow(379,383)\rightarrow389\rightarrow(397,401)\rightarrow(419,421)\leftarrow409$
Where we have two different sequences of finite cycles converging to the same infinite cycle.
The longer sequence of cycles from this example can be seen below: enter image description here

It seems that primes sharing cycles and primes that are a part of connected cycles, are consecutive primes. All primes $359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421$ from the last example are consecutive.

Seems like we could represent all sequences for all primes as one single graph, where consecutive primes build connected components of the graph.

All primes $a_0\ge29$ seem to only revisit constant nodes $a_k$ that are $a_0\approx a_k$ their size. All other nonconstant nodes diverge to either $\pm\infty$, for $k\to\infty$. No $0$ nodes have been found so far, which would defy the $a_0\approx a_k$ observation, for constant $a_k$ (by "constant term of the sequence" I mean "recurring term of the sequence"; $a_k=a$ for different $k$).

One can generate graphs for individual primes and prove this and the initial question (for finitely many terms); that primes $\ge29$ do not terminate (reach $0$). But I still do not know how can one prove this for all primes, rather than checking individual cases.


If we look at sequences of primes, every prime eventually converges to some other prime. If we observe only the first next prime they visit, we can represent the convergence relations with a graph and build the forest of primes. For primes up to $10009$ we have:
(Open the image in a new tab and zoom in)

enter image description here



Update 4: Characterization of cycles


I've noticed that the following seems to hold for prime $a_0$:

If $a_0\ge29$ is a Sophie Germain Prime ($2a_0+1$ is prime), then:

$a_0$ will have infinite cycle $\iff$ $a_0+2$ is prime

$a_0$ will have a finite cycle that does not revisit $a_0$ $\iff$ $a_0+2$ is not prime

If $a_0\ge29$ is not a Sophie Germain Prime, then then $a_0$ will be revisited at least $2$ times.

If $a_0\ge29$ is 1st term in Twin Prime pair ($a_0+2$ is prime), then:

$a_0$ will have an infinite cycle $\iff$ $a_0$ is not a 3rd term of a prime quadruple.

$a_0$ will have an finite cycle $\iff$ $a_0$ is a 3rd term of a prime quadruple.

If we have a Prime Triplet starting with $a_0\ge29$, then:

$a_0$ will have infinite cycle $\iff$ $a_0$ is not Median term of prime quintuplets.

$a_0$ will have finite cycle $\iff$ $a_0$ is Median term of prime quintuplets.

If we have tuples of $\ge4$ consecutive primes; that is:

If $a_0\ge29$ is 1st term of a Prime Quadruplet or a longer Prime Constellation, then that seems to imply that $a_0$ will have an infinite cycle.

Can we characterize the finite/infinite cycles more precisely; or find counterexamples to these claims?

$\endgroup$
  • $\begingroup$ I do not get $0$ in the case $a_0=3$, for example. $\endgroup$ – Peter Jun 23 '18 at 13:43
  • 2
    $\begingroup$ @Peter I forgot to mention that by "prime" I mean "prime or $1$" . Then for $a_0=3$ we have $(3, 7, 12, 6, -1, -9, 0)$ termination. I edited the post and replaced "is prime" with "not composite". $\endgroup$ – Vepir Jun 23 '18 at 18:29
  • $\begingroup$ In fact , beginning with $29$ , we seem to enter an infinite loop. $\endgroup$ – Peter Jun 23 '18 at 21:00
  • $\begingroup$ @Peter Indeed it seems so. In fact, if we let the sequence continue after $0$, it seems odd numbers visit zero finitely many times before entering a loop, where even numbers trivially revisit zero infinitely many times in their own loop. I've updated the question with a broader observation. $\endgroup$ – Vepir Jun 24 '18 at 14:18
  • 1
    $\begingroup$ @Vepir My calculations (see the comments) indicates that your conjecture is true, but a proof will probably be very difficult. $\endgroup$ – Peter Jun 25 '18 at 13:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.