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