### Racket: Conway Numbers

Jun. 13th, 2017 06:03 pm**cbrachyrhynchos**

Based on the "climb to a prime" problem @ Programming Praxis

Select a number, then compute its prime factors, with multiplicity; for instance, 90 = 2 × 32 × 5. Then “bring down” the exponent and write the resulting digits, forming a new number; for instance, the exponent of 2 in the above factorization is brought down, forming the number 2325. Repeat the process with the new number, and again, and so on; for instance, starting from 90, the chain is 90, 2325, 35231, 72719, where the chain terminates. I conjecture that the process will eventually terminate with a prime number.

#lang racket (require math/number-theory) (define (factors-to-list n) (define factor-list (factorize n)) (define (iter fl results) (if (null? fl) (reverse results) (letrec ([p (car fl)] [x (first p)] [y (second p)]) (if (> y 1) (iter (cdr fl) (cons y (cons x results))) (iter (cdr fl) (cons x results)))))) (iter factor-list (list))) (define (list-to-integer li (result 0)) (if (null? li) result (list-to-integer (cdr li) (+ (car li) (* (expt 10 (digits (car li))) result))))) (define (digits n) (inexact->exact (floor (+ 1 (/ (log n) (log 10)))))) (define (next-conway n) (list-to-integer (factors-to-list n))) (define (conway-chain n (results (list))) (let ([next (next-conway n)]) ;;; (displayln n) (cond [(= next n) (reverse (cons n results))] [(prime? n) (reverse (cons n results))] [(> n (expt 10 20)) (printf "limit exceeded at ~a" (reverse (cons n results)))] [else (conway-chain next (cons n results))])))

I threw in a limiter of 10^20 because factoring numbers that big can get pretty obnoxious, even with the math/number-theory library.