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.

Advertisements

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

    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)
    
    $ ./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
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: