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

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