Do you know how to write this Scheme function?

Question

Could you write a function that takes one argument (a positive integer) and

• divides it by two if it's even, or
• multiplies it by three and adds one if it's odd

and then returns the resulting number.

And then a separate function that takes one argument (a positive integer) and repeatedly passes it to the previous function until it reaches 1 (at which point it stops). The function would return the number of steps it took to reduce it to 1.

And then another function which takes two arguments a and b (both positive integers with a <= b) and returns the largest number of repeated Collatz steps it takes to reduce any single number in the range to 1 (including the endpoints). (Collatz steps refers to the previous function).

And finally, another function that takes two arguments a and b (both positive integers with a <= b) and returns the number between a and b (including the endpoints) that takes the largest number of Collatz steps to be reduced to 1.

These functions are related to the Collatz problem, and I find it very interesting. The subsequent functions will obviously borrow other function that were defined previously.

Any idea how we could show this in Scheme code?

Answer 1

A function that performs one iteration:

(define (collatz x)
  (if (even? x)
      (/ x 2)
      (+ (* x 3) 1)))

This function takes an input and loops until it reaches 1. The function returns the number of iterations required to get to that state (try graphing this - it looks pretty cool):

(define (collatz-loop x)
  (if (= x 1) 1
      (+ (collatz-loop (collatz x)) 1)))

As requested, here's a tail-recursive version of collatz-loop:

(define (collatz-loop x)
  (define (internal x counter)
    (if (= x 1) counter
    (internal (collatz x) (+ counter 1))))
  (internal x 1))

This function takes a range and returns the number that takes the most number of steps to reach the end along with the number of steps:

(define (collatz-range a b)
  (if (= a b)
      (cons a (collatz-loop a))
      (let ((this (collatz-loop a))
        (rest (collatz-range (+ a 1) b)))
        (if (< this (cdr rest)) rest
            (cons a this)))))

(collatz-range 1 20) ; returns (18 . 21), which means that (collatz-loop 18) returns 21

This is collatz-range, tail recursive:

(define (collatz-range a b)
  (define (internal a best)
    (if (< b a) best
        (internal (+ a 1)
        (let ((x (collatz-loop a)))
          (if (< x (cdr best))
              best
              (cons a x))))))
  (internal a (cons -1 -1)))

Answer 2

For the other two functions, using foldl:

(define (listfrom a b)
  (if (= a b)
      (cons a empty)
      (cons a (listfrom (+ 1 a) b))))

(define (max-collatz a b)
  (foldl max 0 (map collatz-loop (listfrom a b))))

(define (max-collatz-num a b)
  (foldl (lambda (c r)
           (if (> (collatz-loop c) (collatz-loop r)) c r))
         a
         (listfrom a b)))

Answer 3

i believe this is a great unsolved question of number theory. There is a hypothesis that every number when it goes through this operation enough times will reduce to one.

However i don't really think scheme is the right tool for this, plus since a lot of people have decided that this is homework and not a legit question I will provide my solution in c

inline unsigned int step(unsigned int i)
{
    return (i&0x1)*(i*3+1)+((i+1)&0x1)*(i>>1);
}

this will do one step on the number (with no branches!!!). Heres how you do the whole calculation:

unsigned int collatz(unsigned int i)
{
    unsigned int cur = i;
    unsigned steps = 0;
    while((cur=step(cur))!=1) steps++;
    return steps;
}

I don't think its possible to remove the branch entirely. this is number theory problem and thus it is suited to extreme (and possibly unnecessary) optimization. enjoy