[Math] Can we remove any prime number with this strange process

number theoryprime numbersrecreational-mathematicsrecursive algorithms

This is a little algorithm I made today, which may appear to be quite complex so I will start with an example.

The process goes as follows:

  • Start with the first prime number, $2$.

  • From $2$, add the next prime number ($3$) to get $2+3=5$. There are no non-trivial factors, so we move on.

  • From $2+3$, add the next prime number ($5$) to get $2+3+5=10$. Since $10=2\times5$ and these two numbers appear in the sum, we remove $2$ and $5$.

  • We are left with $3$.

  • From $3$, add the next prime number ($5$) to get $3+5=8$. Now $8=2\times2\times2$, but $2$ does not appear in the sum, so we move on.

  • From $3+5$, add the next prime number ($7$) to get $3+5+7=15$. Since $15=3\times5$ and these two numbers appear in the sum, we remove $3$ and $5$.

  • We are left with $7$.

  • (and so on)

So essentially, we keep on adding consecutive prime numbers until we reach a sum whose prime factorisation contains some of those primes. We remove those primes and start the process once again. Great, except…

There is one more rule that needs to be added. If we continue doing this, we soon find ourselves in a rather strange scenario.

  • (and so on) a continuation:

  • From $37+47+59+\cdots+241+251+257$, add the next prime number ($263$) to get $$37+47+59+\cdots+251+257+263=5918.$$ Now $5918=2\times11\times269$, but neither of the three primes appear in the sum, so we move on.

  • From $37+47+59+\cdots+251+257+263$, add the next prime number ($269$) to get $$37+47+59+\cdots+251+257+263+269=6187.$$ Since $6187=23\times269$ and $269$ appears in the sum, we remove $269$.

  • We are left with $37+47+59+\cdots+251+257+263$.

This is a cycle! The sequence of $263$ and $269$ will continue forever, if we don't add another rule to this process. Therefore, I call $269$ a cyclic prime, and I propose this new rule.

  • From $37+47+59+\cdots+251+257+263$, add the next non-cyclic prime number ($271$) to get $$37+47+59+\cdots+251+257+263+271=6189.$$ Now $6189=2\times2063$ and these two numbers do not appear in the sum, so we move on.

I do not know whether there are any dicyclic primes; that is, primes that are still cyclic after more than one iteration. This is beyond current computation methods as such primes if any exist will be extremely large.

Questions

  1. Will every prime number in the sum eventually be removed? If not, which prime numbers will remain in the sum forever?

I believe so. With a few modifications, @EuxhenH has kindly shared their Python code. From the program, it is found that all primes up to $16903$ are eliminated at some point before overflow.

The following table shows how long it takes ($N$ iterations) for the smallest prime (not yet removed in the sum) $P$ to be removed. Although the value of $N$ fluctuates significantly, the general trend seems to be that it takes more iterations to remove a larger $P$.

   P: N
   3: 2
   7: 6
  11: 7
  23: 28
Found cyclic 269
  37: 44
  47: 48
  71: 3
 107: 47
 109: 142
 127: 232
 181: 9
 277: 247
 431: 8
 457: 316
 479: 217
 509: 969
 773: 977
1069: 92
1123: 1327
1451: 2059
1483: 1270
1801: 542
Found cyclic 94793
2281: 3558

  1. Follow-up: What is the asymptotic growth of $N(P)$? For instance, does it admit a $\log$ or $\log\log$ increase?

  2. Are there infinitely many cyclic prime numbers?

That is, are there infinitely many $n$ such that $p_{n+1}$ divides $\sum_{p_i\in S} p_i$? As of writing, the only known cyclic prime numbers are $269$ and $94793$ so they are rather rare to find.

Best Answer

I have no proof so far but also written a program that checked that the only cyclic primes among the first $10^5$ steps are $p = 269$ in $S(58) = 6187$, and $p = 94 793$ in $S(9141) = 377 844 898$, where I call $S(n)$ the value of the sum at step $n$ (after adding the "next larger prime", not considering the removal of terms as a step, with $S(1) = 2$ which can be seen as result of adding $2$ to the empty sum $S(0)$).

FWIW, I get \begin{align}S(1000) &= 3\,362\,713\\S(2000) &= 14\,797\,503\\S(5000) &= 105\,157\,142\\S(10\,000) &= 456\,622\,646\\S(20\,000) &= 1\,979\,852\,987\\S(50\,000) &= 13\,618\,461\,808\\S(10^5) &= 58\,316\,786\,321.\end{align}

The smallest prime in the sum at these points is \begin{align}p(1000) &= 457\\p(2000) &= 509\\p(5000) &= 1451\\p(10\,000) &= 2281\\p(20\,000) &= 4129\\p(50\,000) &= 10\,631\\p(77\,000) &= p(10^5) = 16\,903.\end{align}

To be precise, my program considers a prime cyclic if it would give twice the same result, $\widehat S(n+1) = S(n)$, if it were used, which is then however avoided by using the next larger prime. I agree that this may not be the conceptually most satisfying definition... On the other hand, $p_{k+1}\mid\sum p_i$ isn't complete either (as mentioned in a comment), because depending on the smaller primes removed at that step or the next one, this does not necessarily give a loop. [However, if I'm not wrong, it's excluded that the next smaller prime is a factor of the sum at the same time as the largest prime $p_{k+1}$, because the sum is at most $\sim p_{k+1}^2/2 < p_{k}\cdot p_{k+1}$.]

The experimental results seem to confirm that eventually all primes will be removed. I agree with the heuristic argument that, if there's no particular modular restriction on the sum, then any prime factor will eventually occur (even infinitely often), and thus be removed from the sum. Given the "sequential" way of adding one prime after the other to the sum, there appears indeed no reason that from some point on, a particular prime factor should never occur again. This would yield the required result, but again, it's not a proof.

PS: I proposed the sequence $S(n)$ as oeis.org/A332198, where my program can be found.

Related Question