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