This is an algorithm I invented one night, trying to deal with my insomnia. It involves rather simple arithmetic, but is very difficult to find a solution for.
Pick a random integer.
- If the integer is prime, you have finished.
- If the integer is non-prime, take its prime factors and add it to the original number.
- If the resulting number is prime, you have finished
- If the resulting number is non-prime, repeat step 2.
So, for example, from 75: 3,5,5 added to 75 produce 88. 2,2,2,11 added to 88 give us 105. + 3,5,7 = 120. + 2,2,2,3,5 = 134. + 2, 67 = 203, which is prime. This chain takes five steps, and terminates at a number that is between 2 and 3 times the original number.
My conjecture with this algorithm is that it will always terminate in a prime number. Various people who I have given this problem to, to experiment with, have tested it for values up to hundreds of thousands. Most people have also agreed that each one of these chains will terminate in a prime number. However, no one has managed to say exactly why.
Much like the Collatz Conjecture, this is a problem that involves rather basic arithmetic, but which seems untouchable by our current ability at number theory.