Collatz Conjecture - Syracuse Function

Syracuse Function

If k is an odd integer, then 3k + 1 is even, so we can write 3k + 1 = 2ak′, with k' odd and a ≥ 1. We define a function f from the set of odd integers into itself, called the Syracuse function, by taking f (k) = k′ (sequence A075677 in OEIS).

Some properties of the Syracuse function are:

• f (4k + 1) = f (k) for all k in .
• For all p ≥ 2 and h odd, fp−1(2p h − 1) = 2·3p − 1h − 1 (here, f p−1 is function iteration notation).
• For all odd h, f(2h − 1) ≤ (3h − 1)/2

The Syracuse conjecture is that for all k in, there exists an integer n ≥ 1 such that fn(k) = 1. Equivalently, let E be the set of odd integers k for which there exists an integer n ≥ 1 such that fn(k) = 1. The problem is to show that E = . The following is the beginning of an attempt at a proof by induction:

1, 3, 5, 7, and 9 are known to be elements of E. Let k be an odd integer greater than 9. Suppose that the odd numbers up to and including k − 2 are in E and let us try to prove that k is in E. As k is odd, k + 1 is even, so we can write k + 1 = 2ph for p ≥ 1, h odd, and k = 2ph − 1. Now we have:

• If p = 1, then k = 2h − 1. It is easy to check that f (k) < k, so f (k) ∈ E; hence k ∈ E.
• If p ≥ 2 and h is a multiple of 3, we can write h = 3h′. Let k′ = 2p + 1h′ − 1; then f (k′) = k, and as k′ < k, k′ is in E; therefore k = f (k′) ∈ E.
• If p ≥ 2 and h is not a multiple of 3 but h ≡ (−1)p mod 4, we can still show that k ∈ E.

The problematic case is that where p ≥ 2, h not multiple of 3 and h ≡ (−1)p + 1 mod 4. Here, if we manage to show that for every odd integer k′, 1 ≤ k′ ≤ k − 2 ; 3k′ ∈ E we are done.