Expand Cut Tags

No cut tags
cbrachyrhynchos: (Default)
[personal profile] 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.

Profile

cbrachyrhynchos: (Default)
cbrachyrhynchos

July 2017

S M T W T F S
       1
234 5678
91011 1213 1415
16 17 1819202122
23 2425 26272829
3031     

Most Popular Tags

Style Credit

Page generated Jul. 28th, 2017 07:01 pm
Powered by Dreamwidth Studios