Climb To A Prime

June 13, 2017

The central action of the program is to bring down powers and calculate the next number in the chain; we use flatten and uniq-c from the Standard Prelude:

(define (bring-down-powers fs)
  (string->number
    (apply string-append
      (map number->string
        (filter (lambda (n) (not (= n 1)))
          (flatten
            (uniq-c = fs)))))))

Then the program to climb to a prime just calls bring-down-powers repeatedly until it reaches a prime:

(define (climb-to-a-prime n)
  (let loop ((n n))
    (let ((fs (factors n)))
      (display fs) (newline)
      (when (pair? (cdr fs))
        (loop (bring-down-powers fs))))))

The hard part of the program is factoring the numbers, which increase quickly. For demonstration, the code at ideone uses a 2,3,5-wheel; in practice, you will need something better. Here are some examples:

> (climb-to-a-prime 90)
(2 3 3 5)
(3 5 5 31)
(7 7 719)
(72719)
> (climb-to-a-prime 284)
(2 2 71)
(3 757)
(13 17 17)
(2 2 37 89)
(31 7219)
(7 45317)
(3 3 82813)
(3 3 23 15859)
(23 14013733)
(3 3 29 8865953)
(3 2963 3633577)
(3 34327 3200917)
(13 181 1420855589)
(131811420855589)

And here’s the infinite loop:

> (climb-to-a-prime 13532385396179)
(13 53 53 3853 96179)
(13 53 53 3853 96179)
(13 53 53 3853 96179)
(13 53 53 3853 96179)
...

You can run the program at http://ideone.com/woHTqi.


					
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: