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.

Pages: 1 2

6 Responses to “Climb To A Prime”

1. Zack said

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

2. Rutger said

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:  19

```
3. Paul said

In 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))
```
```y= 2
y= 3
y= 4
y= 5
13532385396179
13532385396179
```
4. programmingpraxis said

@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.

5. Globules said

```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)
```
```\$ ./climb 90 12345 13532385396179
90 => [90,2325,35231,72719]: climbed to a prime
12345 => [12345,35823,311941,744563,4191777,33155251]: climbed to a prime
13532385396179 => [13532385396179]: climbed to a non-prime
```
6. Globules said

Hmm, I just noticed that my first case in fromDigits is redundant. The function could be written more succinctly as:

```fromDigits :: Integral a => [a] -> a
fromDigits = foldl' (\p d -> 10*p + d) 0
```