## 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 × 3

^{2}× 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 × 53^{2} × 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.

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.

In Python. I added function to find the counter example. It prints the counterexample after a few seconds.

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

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