For those that may want to try having a go against this problem, a few observations are in place:
-
Let’s call Glowing Fish’s algorithm a function f(x) → x′ defined (for now) for all positive integers greater than one,1
-
The algorithm is defined for the prime factors of x, with multiplicity. A different version could be conceived where you add to x only its proper prime factors without repetition. This is left to the reader as an exercise,
-
It’s obvious that for every x, it’s true that x′ > x,
-
By necessity, every x′ must either be prime or composite,
-
The algorithm stops if and only if x′ is prime and continues if it’s composite. Therefore, all cases of stopping or continuing are covered,
-
There are infinitely many prime numbers—and therefore, infinitely many stopping points,
-
All prime numbers—with the exception of 2—are odd,
-
It follows that if x is even, it will always continue towards x′, with only one exception, namely x = 2,
-
If x is even and not a perfect power of 2, it can be observed that x′ will always be odd, since its factors will be one or more ’2’s and one or more odd factors,
Big blunder here. Thank you DonJaime for noticing this: «not so: it could have an even number of odd factors.» Curiously enough, both DonJaime and Glowing Fish sent me this correction within a 10 minute window. I apologize for not being very through here,
-
Conversely, if x is a perfect power of 2, x′ will always be even,
-
Remember the verse:
Chebyshev said it, but I’ll say it again;
There’s always a prime between n and 2n.
N. J. Fine (see Sondow and Weisstein 2020; Schechter 2000)
This simple fact hints that there must exist a prime number “not very far away” from any starting number. That said, the addition of prime factors does not ensure that this next “stopping point” will be reached.
-
(Andy fell asleep trying to analyze this further)
A simple Python implementation
In order to speed up the search, a dictionary will be used. The key will be our x and the value our x′. If x is prime, its value will be 0. This way, it’s possible to calculate lots of numbers at the beginning and following the chain will be faster than calculating the chain the whole way through.
It’s also advisable to start with a list of prime numbers. There are numerous such lists on the internet, so I won’t bother actually writing them down here. For the purposes of this script, it’s assumed that there is a file called 50kprimes.txt in the same folder as the script. This textfile has only one (prime) number per line and nothing else.
In this demonstration I use a file with the first 50,000 prime numbers, the last of them being 611953. The only hardcoded parameter needed is the variable upper, which can be set to a lower number (say, 100) to speed up the dictionary creation—but reducing this number will limit the search to those composite numbers below upper. For instance, if upper is set to 100, the number 95 will lead to 119 (because 95 = 5 × 19) and the search will stop with a cute (?) message.
Postscript (2020-01-07): This script does not check that all starting numbers in its range eventually terminate, but doing so is relatively easy: Instead of choosing a random integer, everything after creating the dictionary can be put inside a for loop, that goes through all numbers between 2 and upper, inclusive, and verifying that eventually they lead to a key whose value is 0—i. e. a prime number. If this route is chosen, I would advise against printing the whole chain, mostly because a) it would take a lot of space in your terminal, and b) because printing is computationally more expensive. One could choose to run the loop and print a message only if the chain has not ended after some reasonable time.
# -*- coding: utf-8 -*-
"""
Created on Mon Jan 6 22:29:16 2020
@author: Andycyca
Glowing Fish writes:
Pick a random integer.
1. If the integer is prime, you have finished.
2. If the integer is non-prime, take its prime factors and
add it to the original number.
3. If the resulting number is prime, you have finished
4. If the resulting number is non-prime, repeat step 2.
"""
import random
import time
# See:
# https://stackoverflow.com/questions/16996217/prime-factorization-list/
def primes(n):
primfac = []
d = 2
while d*d <= n:
while (n % d) == 0:
primfac.append(d) # supposing you want multiple factors repeated
n //= d
d += 1
if n > 1:
primfac.append(n)
return primfac
# Testing for the first 50 thousand primes.
# The largest of these is 611953
start_time = time.time() #Gentlemen, start your engines!
numbers = {}
with open("50kprimes.txt") as f:
for line in f:
numbers[int(line)] = 0
# 611954 is the 'real' upper value if using the whole 50k primes
upper = 611954
#upper = 100
for i in range(2, upper):
if i not in numbers:
numbers[i] = i + sum(primes(i))
print('All numbers up to {} checked and logged!'.format(upper))
print("--- %s seconds ---" % (time.time() - start_time))
print('\n\n')
start = random.randint(2, upper)
thank_u_next = numbers[start]
start_time = time.time() #Gentlemen, start your engines!
print('Testing for all primes below {}'.format(upper))
while thank_u_next != 0 and thank_u_next < upper:
print('{} goes to {}.\n'.format(start, thank_u_next))
start = thank_u_next
thank_u_next = numbers[start]
if thank_u_next == 0:
print('And finally, {} is prime!'.format(start))
elif thank_u_next >= upper:
print('{} goes to {}.\n'.format(start, thank_u_next))
print('And {} is outside the scope of this file'.format(thank_u_next))
print("--- %s seconds ---" % (time.time() - start_time))
A sample timed run done in my computer
In [1]:
All numbers up to 611954 checked and logged!
--- 19.660735368728638 seconds ---
Testing for all primes below 611954
408905 goes to 410593.
410593 goes to 416447.
416447 goes to 423335.
423335 goes to 423573.
423573 goes to 424368.
424368 goes to 424810.
424810 goes to 426687.
426687 goes to 430200.
430200 goes to 430461.
430461 goes to 430726.
430726 goes to 431772.
431772 goes to 435061.
435061 goes to 474623.
474623 goes to 502559.
502559 goes to 504503.
504503 goes to 511487.
And finally, 511487 is prime!
--- 0.0009999275207519531 seconds ---
Bibliography and resources
Caldwell, Chris K., and Yeng Xiong. 2012. “What Is the Smallest Prime?” Journal of Integer Sequences 12 (9). https://cs.uwaterloo.ca/journals/JIS/VOL15/Caldwell1/cald5.pdf.
Conway, John H., and Richard K. Guy. 1996. The Book of Numbers. Springer New York. https://doi.org/10.1007/978-1-4612-4072-3.
OEIS Foundation Inc., ed. 2013a. “Omega(n), Number of Prime Factors of N (with Multiplicity) — the on-Line Encyclopedia of Integer Sequences(OEIS) Wiki.” OEIS Foundation Inc. December 11, 2013. https://oeis.org/w/index.php?title=Omega(n),_number_of_prime_factors_of_n_(with_multiplicity)&oldid=1584073.
———, ed. 2013b. “Prime Factors Prime Factors (with Multiplicity) — the on-Line Encyclopedia of Integer Sequences(OEIS) Wiki.” OEIS Foundation Inc. December 11, 2013. https://oeis.org/w/index.php?title=Prime_factors&oldid=1624396.
Schechter, B. 2000. My Brain Is Open: The Mathematical Journeys of Paul Erdos. A Tochstone Book. Simon & Schuster. https://books.google.com/books?id=\_GsQiXvfNWkC.
Sondow, Jonathan, and Eric W. Weisstein. 2020. “Bertrand’s Postulate. — Mathworld–a Wolfram Web Resource.” 2020. http://mathworld.wolfram.com/BertrandsPostulate.html.
Wikipedia contributors. 2019a. “Fundamental Theorem of Arithmetic — Wikipedia, the Free Encyclopedia.” https://en.wikipedia.org/w/index.php?title=Fundamental_theorem_of_arithmetic&oldid=931496114.
———. 2019b. “Prime Number — Wikipedia, the Free Encyclopedia.” https://en.wikipedia.org/w/index.php?title=Prime_number&oldid=932859560.
-
The reason for this particular restriction is that the number 1 is neither a prime number nor a composite one. See the Bibliography for deeper reads into why this is the consensus among mathematicians.