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

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: