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

Pages: 1 2

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:

Skype has opened its online-based customer beta on the entire world, after establishing it broadly inside the United states and U.K.

previous this calendar month. Skype for Website also now can handle

Linux and Chromebook for instant online messaging conversation (no

voice and video nevertheless, all those call for a connect-in installing).

The expansion of the beta adds assist for an extended listing of spoken languages to aid bolster that international functionality