Do you know how to write this Scheme function?

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?

From stackoverflow

• 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)))
  

• 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)))
  

• 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