6
$\begingroup$

By defining the following algorithm I was able to generate some interesting graphs using the values of the gaps between consecutive primes:

  1. Start in any prime $p_i$, this will be the initial node, and calculate the distance to the next prime, then define $d_1 = d(p_i,p_{i+1})$
  2. The next node will be the prime $p_{i+d_1}$. Then calculate the distance to the previous prime as $d_2 = -d(p_{i+d_1},p_{i+d_1-1})$
  3. The next node will be the prime $p_{i+d_1+d_2}$ and do as in step 1 to define $d_3$ for the current node (forward step).
  4. Then next node will be the prime $p_{i+d_1+d_2+d_3}$ and do as in step 2 to define $d_4$ for the current node (backward step).
  5. Continue doing alternatively as in steps 3 and 4, defining the subsequent forward-backward jumps $d_5,d_6...$ etc.

(There are three examples below).

If $d_0=0$ is defined as the initial value of the sequence of $d_k$'s, then a generic calculation for $d_k$ for an initially given $p_i$ can be defined as:

$d_k=(-1 + 2(k\ mod\ 2)) \cdot d(p_{(i+\sum_{t=0}^{t=k-1} d_{t})},p_{(i+\sum_{t=0}^{t=k-1} d_{t})-1+2(k\ mod\ 2)})$

And each node $n_k$ of the graph is defined for $k \gt 0$ as:

$n_k = p_{(i+\sum_{t=0}^{t=k-1} d_{t})}$

In other words, the node $n_k$ is the $(i+\sum_{t=0}^{t=k} d_{t})^{th}$ prime, and the starting node is $n_1 = p_i$.

My observation (the questions are related to this) is that the graph is always (1) itself a cycle (a clean Hamiltonian path) or (2) it arrives to a sub graph that is a cycle, so from that point if subsequent $d_k$'s are generated, the nodes will never escape from the cycle. Please note that I consider a cycle only the case in which we arrive to an already existing node $n_k$ in a second or a third time, then the next $d_k$ is calculated, and the next node $n_{k+1}$ still is not included in the graph. The reason is that it is possible two calculations when arriving to a node, jumping $d_k$ primes forwards or backwards, depending on which step of the algorithm we did arrive to the node.

For instance, that happens in the case of $p_i=11$. The algorithm arrives twice to $11$ but the second time the jump to the next node is backwards (a negative $d_k$) so the nodes $11 \gt 17 \gt 5 \gt 11$ are not considered to be in a cycle. In other hand, when the algorithm arrives to $2 \gt 3$ there is not possibility to escape from that continuous loop, so it is considered a real cycle and the algorithm ends.

enter image description here

For instance this is an example of a clean Hamiltonian path (the graph is itself a cycle):

$p_i=13$

$d_1=d(13,17)=4$

$p_{i+d_1}=29$

$d_2=-d(29,23)=-6$

$p_{i+d_1+d_2}=7$

$d_3=d(7,11)=4$

$p_{i+d_1+d_2+d_3}=19$

$d_4=-d(19,17)=-2$

$p_{i+d_1+d_2+d_3+d_4}=13$

So the complete graph is as follows (black arrows are odd, thus positive-valued, $d_k$'s, red arrows are even, thus negative-valued, $d_k$'s):

enter image description here

When the graph is itself a clean cycle, a Hamiltonian path, then:

$\exists k \in \Bbb N: \sum_{k=0}^{k=t} d_k = 0$.

In the other hand this is an example of graph containing a cyclical sub graph (following the same algorithm to generate the graph):

enter image description here

Tested with Python for $\forall \ p_i \in [0,47864431]$ (it gets quite slow after that point) in all cases it is possible to generate a finite graph like the ones above. There is not an example of a prime number capable of generating a graph with infinite nodes (continuously escaping to a greater prime while following the algorithm). In all cases the graphs have finite nodes and usually the elements of the graph are part of a "local region" around the initial prime $p_i$ (meaning that the graphs do not have nodes whose values are very distant, they are located in a close range around the original starting prime number $p_i$).

The biggest graph in the tested range [0,47864431] was for $p_i=26730589$, including $60$ nodes:

Similar tests can be done over other strictly increasing sequences with a "pseudorandom" behavior in the gaps between consecutive elements, like in the case of the abundant numbers and even deficient numbers. I asked another question looking for more similar sequences to make more tests here. Initially all of them are related with the prime divisors of the numbers, so they are also indirectly related to the primes themselves, and somehow the behavior of the gaps regarding the graphs explained above seems to be similar as well.

My first thought is that this is possible because in all cases the gap $d_k$ for a given node is always smaller than or equal to the value of the counting function of the sequence up to that node. For instance the prime counting function $\pi(x)$ in the case of the prime numbers:

$\forall k: d_k \le \pi(p_{(i+\sum_{t=1}^{t=k-1} d_{t})})$

And it seems so by checking the maximal prime gaps list and the index of the $p^{th}$ prime. I would like to ask the following questions:

  1. Is this behavior similar to the "return to zero" concept in random walks?

  2. Does it imply that there is a relationship between the local gaps? according to the heuristics it seems that the graphs can not "escape" from the local region around the prime.

  3. Is there a counterexample of a $p_i$ prime whose gap with the next prime $g$ is strictly bigger than $i$, $g \gt i$?

  4. What implications could have a behavior like this, if any? Thank you!

$\endgroup$
  • 1
    $\begingroup$ my question here questionis probably related? I see a good degree of correlation in the gaps ti $\endgroup$ – scrx2 Feb 18 '17 at 7:25
  • $\begingroup$ +1 Funny, did you also find cubic graphs among your examples? $\endgroup$ – draks ... Sep 4 '18 at 11:55
  • $\begingroup$ @draks thanks, I had to check the definition of a "cubic graph" :) as far as I remember, not yet. A good question would be if it is possible or not. $\endgroup$ – iadvd Sep 5 '18 at 0:27

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.