How to use collatz conjecture without if statements?

Question

I'm trying to use the collatz conjecture (basically divides an even number by 2, and if it's even if multiplies the number by 3 and adds 1) in a functional language (scheme). The obvious solution would be to use remainder to find a 0/1 for even/odd numbers and use an if statement on that for both. BUT, we can't use if statements, conditions, or recurcives. Only what we have learned in module one which is pretty much just basic operations as well as exponents, square roots, etc. Any suggestions?

Answer 1

In order to avoid problem for us I won't give you direct answer. I will just discuss about in term of math. Look at the problem:

• if even number then do: n/2
• if odd number then do: 3*n+1; however, 3*n+1 = n/2 + 5/2*n + 1.

So we can rewrite the problem as:

• if even number then do: n/2 + (5/2*n + 1) * 0;
• if odd number then do: n/2 + (5/2*n + 1) * 1;

To know when will we multiply the remain part with 0 or 1: you can use modulo function.

Grangle!!!

Answer 2

The half or thrice plus one (hotpo) function can be written as follows in purely mathematical terms:

hotpo n = n / 2 + n % 2 * (2.5 * n + 1)

In Racket you can define this function as follows:

(define (hotpo n)
     (+ (/ n 2) (* (remainder n 2) (+ (* 2.5 n) 1))))

For any positive number n the collatz conjecture states that generating a sequence of numbers by applying hotpo to n repeatedly will eventually result in the number 1.

Of course to test the collatz conjecture you'll need to make use of recursion and conditional statements. However the hotpo function itself can be defined in purely mathematical terms as demonstrated above.

Answer 3

I'm not sure what language you wish to code, but mathematically, this is the function for the Collatz Sequence.

Let Y be the next number in the sequence and X be the current number.

Y = (X mod 2)(X/2) + (1 - X mod 2)(3*X+1)

mod is the modulo operator, with A mod B being the remainder of A/B, so X mod 2 = 0 implies that X is even and X mod 2 = 1 implies X is odd.

X mod 2 I think is X%2 in C.

Answer 4

Don't cheat dude! You could get into big trouble for that.

I can however give you a hint, consider this problem:

If input is 1, return 2. If input is 2, return 1. Do not use conditionals.

Answer: f(x) = 3-x