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.

From:
Anonymous( )Anonymous This account has disabled anonymous posting.
OpenID( )OpenID You can comment on this post while signed in with an account from many other sites, once you have confirmed your email address. Sign in using OpenID.
User
Account name:
Password:
If you don't have an account you can create one now.
Subject:
HTML doesn't work in the subject.

Message:

 
Notice: This account is set to log the IP addresses of everyone who comments.
Links will be displayed as unclickable URLs to help prevent spam.

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:00 pm
Powered by Dreamwidth Studios