Climb To A Prime
June 13, 2017
The British mathematician John Horton Conway, famous for inventing the Game of Life cellular automaton, made this conjecture:
Select a number, then compute its prime factors, with multiplicity; for instance, 90 = 2 × 32 × 5. Then “bring down” the exponent and write the resulting digits, forming a new number; for instance, the exponent of 2 in the above factorization is brought down, forming the number 2325. Repeat the process with the new number, and again, and so on; for instance, starting from 90, the chain is 90, 2325, 35231, 72719, where the chain terminates. I conjecture that the process will eventually terminate with a prime number.
At his YouTube channel, Numberphile revealed that the conjecture is false. The number 13532385396179 = 13 × 532 × 3853 × 96179, so at each step it replaces itself, resulting in an infinite loop that will never reach a prime, thus disproving the conjecture. The discoverer of that number, James Davis, is entitled to a $1000 prize from Conway.
Your task is to write a program that calculates the climb to a prime for a given input number. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
That was a very nice video indeed! Here is my take on the problem, using Julia. I could have written my own factoring method, but life is too short for replicating stuff that’s already on the base package…
function BringDown(x::Int64)
F = factor(x)
factors = collect(keys(F))
exponents = collect(values(F))
F = sortrows(hcat(factors, exponents))
n = length(factors)
Z = Array(AbstractString, n)
for i = 1:n
if F[i, 2] == 1
Z[i] = string(F[i, 1])
else
Z[i] = join(F[i,:])
end
end
return parse(Int64, join(Z))
end
function main(x::Int64)
y = string(x)
if !isprime(x)
if x != 13532385396179
while !isprime(x)
x = BringDown(x)
y = string(y, “, “, x)
end
else
return “This number cannot be processed!”
end
end
if y[end] == ‘ ‘
y = y[1:(end-2)]
end
return y
end
In Python. For n=20, my program runs rather long and I don’t know whether it will return (well, the conjecture is disproven in general, but still a curious on n=20 already). Perhaps a faster factorization algorithm might help.
from collections import Counter def factorize(number): # gives a list of all prime factors of number factors = [] while not (number % 2): number = number // 2 factors.append(2) i = 3 while i <= number**0.5 and number-1: if not (number % i): factors.append(i) number = number // i else: i += 2 if number != 1 and i >= number**0.5: factors.append(number) return factors def bring_down(factors): result = "" c = Counter(factors) for x in sorted(c): result += str(x) if c[x] > 1: result += str(c[x]) return int(result) for i in range(1,100): n = i factors = factorize(n) while len(factors) > 1: n_new = bring_down(factors) if n_new == n: print('-- recursive case') break n = n_new factors = factorize(n) print(i, ' result: ', n) #output # 1 result: 1 # 2 result: 2 # 3 result: 3 # 4 result: 211 # 5 result: 5 # 6 result: 23 # 7 result: 7 # 8 result: 23 # 9 result: 2213 # 10 result: 2213 # 11 result: 11 # 12 result: 223 # 13 result: 13 # 14 result: 311 # 15 result: 1129 # 16 result: 233 # 17 result: 17 # 18 result: 17137 # 19 result: 19In Python. I added function to find the counter example. It prints the counterexample after a few seconds.
def f(n): if not is_prime(n): nums = [] for k, g in itertools.groupby(brent_factors(n)): nums.append(k) L = len(list(g)) if L > 1: nums.append(L) n = int("".join(str(i) for i in nums)) return n def conway(n): while not is_prime(n): oldn, n = n, f(n) if oldn == n: raise ValueError("Failed for {}".format(n)) return n def find_counter_example(): """ try n = x*p = f(x) * 10^y + p with x = m * 10^y + 1 then p = fx / m see: http://aperiodical.com/ """ for y in range(2, 10): print("y=", y) ty = 10 ** y for m in range(2, 10**4): x = m * ty + 1 fx = f(x) p = fx // m cand = p * x if fx == m * p and is_prime(p) and f(cand) == cand: return cand ans = find_counter_example() print(ans) print(f(ans))@Rutger: Your program at 20 will run for a while: A195265 gives the first 110 values in the sequence for 20, and ends in a 178-digit composite that has not yet been factored. At A195264 you will find everything that is known about all numbers up to 10000.
Here’s a Haskell version.
import Data.Bool (bool) import Data.List (foldl', unfoldr) import Data.Tuple (swap) import Math.NumberTheory.Primes (factorise, isPrime) import Text.Printf (printf) import System.Environment (getArgs) -- Return the "climb to a prime" list for a given number. climb :: Integer -> [Integer] climb n = let ns = iterate bringDown n in n : map snd (takeWhile (uncurry (/=)) $ zip ns (tail ns)) -- Perform one step of "climb to a prime" by converting a number's sequence of -- factors and their multiplicities into a new number. bringDown :: Integer -> Integer bringDown = fromDigits . concatMap toDigits . concatMap toNums . factorise -- Convert a factor and its multiplicity to a list of two numbers. toNums :: (Integer, Int) -> [Integer] toNums (x, 1) = [x] toNums (x, y) = [x, fromIntegral y] -- Return the sequence of digits corresponding to a number. -- E.g. toDigits 123 = [1,2,3] toDigits :: Integral a => a -> [a] toDigits = reverse . unfoldr step where step 0 = Nothing step n = Just $ swap $ n `quotRem` 10 -- Return the number corresponding to a sequence of digits. -- E.g. fromDigits [1,2,3] = 123 fromDigits :: Integral a => [a] -> a fromDigits [] = 0 fromDigits ns = foldl' (\p d -> 10*p + d) 0 ns printClimb :: Integer -> IO () printClimb n = let ms = climb n m = last ms in printf "%d => %s: climbed to a %sprime\n" n (show ms) (bool "non-" "" (isPrime m)) main :: IO () main = getArgs >>= mapM_ (printClimb . read)Hmm, I just noticed that my first case in fromDigits is redundant. The function could be written more succinctly as: