# A conjecture regarding the sum of a number and its prime factorization

I am not sure if this a known problem, but I have a conjecture regarding the prime numbers. Since I don't know much analytic number theory, I thought maybe someone here could prove/disprove it.

Let $$n\in \mathbb{N}$$ and $$p_1^{\alpha_1}p_2^{\alpha_2}\cdot \cdot \cdot p_k^{\alpha_k}$$ be the prime factorization of $$n$$. Define $$\mathcal{S}(n)$$ to be the sum of the prime factorization of $$n$$.

That is $$\mathcal{S}(n)=\sum_{i=1}^{k}\alpha_{i}p_{i}.$$

Conjecture: Let $$n\in \mathbb{N},$$ $$n>2$$ and $$\tau(n)=\mathcal{S}(n)+n$$. Then for any such $$n$$ there exists a $$k\in \mathbb{N}$$ such that $$\tau^{k}(n)$$ is prime.

Here, $$\tau^k(n)=\tau(\tau(\tau(\cdot \cdot \tau(n))))$$ is the composition of $$\tau$$ taken $$k-$$times.

To understand the conjecture, let us look at some examples.

For $$n=15$$, $$\tau(15)=15+\mathcal{S}(15)=15+8=23$$ thus for $$15$$, $$k=1$$.

For $$n=30$$, $$\tau(30)=30+\mathcal{S}(30)=30+10=40$$, $$\tau(40)=51$$ and finally $$\tau(51)=71$$ is a prime. So $$k=3$$.

I have verified this to be true up to $$10^7$$. Moreover, on average, I believe the number of iteration $$k$$ required to obtain a prime for any $$N$$ grows at the rate of $$\ln(N).$$

Any ideas on how to prove it or find a counterexample? Also, if it a known problem or equivalent to a known problem, can someone provide a reference? Thanks.

• Algorithm works quickly on my computer with Mersenne Primes up to $2^{127}-1$. Using $2^{127}-1$ gives a new prime $2437520251998980409772357517906985597413$ quite quickly according to Mathematica PrimeQ test. Trying now with $2^{521}-1$ and algorithm does not appear to be terminating even after a few minutes. Commented May 1, 2021 at 21:20
• @JamesArathoon That’s awesome! I think this iterative process is quite good(and probably fast) for selecting candidates for finding new prime numbers. Commented May 1, 2021 at 21:28
• I agree very interesting conjecture. Although not a starting prime, starting with $2^{200}-1$ just for the fun of it terminates after a few minutes on my modest PC, with the prime (according to Mathematica PrimeQ) 6022652426117572672285869714543951974454197303495522196962153 Commented May 1, 2021 at 22:05
• It seems like a reasonable conjecture just because you're typically increasing $n$ by a relatively small amount at each iteration $n \rightarrow \tau(n)$, and sampling $\Theta(\log n)$ random numbers of size around $n$ is expected to yield a prime. But barring any additional numerical evidence, I don't see why you think this is better for nominating new prime candidates than just picking random large numbers. Commented May 3, 2021 at 21:02