3n+1


The Collatz conjecture is fairly well known (one example). Given a positive integer n, as long as n is greater than 1 repeatedly replace n by 3n + 1 if n is odd or by n/2 otherwise. The sequence of integers created is called the cycle for n.

Whether all cycles where n is a positive integer eventually terminate at 1 is currently unproven and among the most well-known open problems in mathematics. Paul Erdős offered a reward of $500 for its solution.

Given two positive integers i and j, the max-cycle for i and j is the largest cycle for all integers between i and j inclusive at both ends. Write a program that reads pairs of integers and finds the max-cycle for each pair read.

 (use-modules (ice-9 format)) 
  
 (define (main port) 
  
   (define (int-reader f) 
     (let 
       ((i (read port))) 
       (if (integer? i) 
         (f i)))) 
  
   (let loop () 
     (int-reader 
       (lambda (i) 
         (int-reader 
           (lambda (j) 
             (format #t "~d ~d ~d" i j (max-cycle i j)) 
             (newline) 
             (loop))))))) 
  
  
 (define (max-cycle i j) 
  
   (define (max-cycle' i j max-cyc) 
     (if (> i j) 
       max-cyc 
       (max-cycle' (+ i 1) j (max max-cyc (cycle i))))) 
  
   (max-cycle' (min i j) (max i j) 0)) 
  
  
 (define (cycle i) 
  
   (define (cycle' i len) 
     (if (= i 1) 
       len 
       (cycle' 
         (if (odd i) 
           (+ (* 3 i) 1) 
           (/ i 2)) 
         (+ len 1)))) 
  
   (if (> i 0) 
     (cycle' i 1) 
     0)) 
  
  
 (define (odd n) 
   (= 1 (remainder n 2))) 
  
 guile> (define inp (open-file "t" "r")) 
  
 guile> (main inp) 
 1 10 20 
 100 200 125 
 201 210 89 
 900 1000 174 
  
 guile> 

category-code