6
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – James Arathoon
    Commented May 1, 2021 at 21:20
  • $\begingroup$ @JamesArathoon That’s awesome! I think this iterative process is quite good(and probably fast) for selecting candidates for finding new prime numbers. $\endgroup$
    – BR Pahari
    Commented May 1, 2021 at 21:28
  • $\begingroup$ 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 $\endgroup$
    – James Arathoon
    Commented May 1, 2021 at 22:05
  • 7
    $\begingroup$ 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. $\endgroup$
    – mjqxxxx
    Commented May 3, 2021 at 21:02

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .