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

7 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
    
  7. Abraham said

    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

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: