|
|
| (2 intermediate revisions by the same user not shown) |
| Line 1: |
Line 1: |
| ## Proof of Predictability
| | https://2ndbook.org/wiki/File:Collatz_formal.pdf |
| | |
| To prove the **predictability** of the Collatz conjecture, we demonstrate that for any starting number \( n \), we can predict when the sequence will produce a number smaller than \( n \). This involves analyzing the transformations \( n \to \frac{n}{2} \) (for even numbers) and \( n \to \frac{3n + 1}{2} \) (for odd numbers).
| |
| | |
| ### Step 1: Transformation Behavior
| |
| | |
| #### Case 1: \( n \) is even
| |
| When \( n \) is even:
| |
| \[
| |
| n \to \frac{n}{2}
| |
| \]
| |
| This transformation immediately produces a smaller number because division by 2 reduces the magnitude of any positive integer \( n > 1 \).
| |
| | |
| #### Case 2: \( n \) is odd
| |
| When \( n \) is odd:
| |
| \[
| |
| n \to \frac{3n + 1}{2}
| |
| \]
| |
| The result may be larger or smaller than \( n \), depending on the value of \( n \). For predictability, we aim to identify **when the sequence will drop below the initial value**.
| |
| | |
| ### Step 2: Predicting a Smaller Value
| |
| The sequence alternates between odd and even numbers after each transformation:
| |
| 1. If \( n \) is odd, apply \( n \to \frac{3n + 1}{2} \).
| |
| 2. If the result is even, repeatedly apply \( n \to \frac{n}{2} \) until another odd number is reached.
| |
| | |
| To predict when the sequence reaches a number smaller than \( n \), consider the "weight" of \( n \), defined by how many times it can be divided by 2 after any application of \( \frac{3n + 1}{2} \).
| |
| | |
| #### Key Observation
| |
| For a given number \( n \), the smallest number produced in its sequence depends on the number of times \( n \) (or subsequent terms) can be divided by 2.
| |
| | |
| ### Step 3: Formulating the Predictability Rule
| |
| To predict when the sequence produces a smaller number, calculate:
| |
| \[
| |
| k = \text{the highest power of 2 that divides } (n-1)
| |
| \]
| |
| This works because:
| |
| 1. The transformation \( n \to \frac{3n + 1}{2} \) introduces a factor of 3 and adds 1.
| |
| 2. Subtracting 1 from \( n \) aligns the number with the modular behavior of powers of 2, allowing deterministic prediction of when the sequence drops below \( n \).
| |
| | |
| #### Example
| |
| * For \( n = 7 \):
| |
| * \( n - 1 = 6 \), and the highest power of 2 dividing 6 is \( 2^1 = 2 \).
| |
| * The sequence for 7 will reach a smaller number after **1 division by 2**.
| |
| * For \( n = 15 \):
| |
| * \( n - 1 = 14 \), and the highest power of 2 dividing 14 is \( 2^1 = 2 \).
| |
| * The sequence for 15 will similarly reach a smaller number after **1 division by 2**.
| |
| | |
| ### Step 4: Exponential Reduction
| |
| Each transformation reduces the size of the number set exponentially:
| |
| 1. Even numbers are solved immediately.
| |
| 2. Odd numbers are transformed and alternate between odd/even, with predictable reductions through divisions by 2.
| |
| 3. The sequence becomes smaller at a predictable rate based on the modular properties of \( n - 1 \).
| |
| | |
| ### Conclusion
| |
| Predictability is proven because:
| |
| 1. Every \( n \) eventually produces a smaller number.
| |
| 2. The specific step where this happens can be calculated directly from \( n - 1 \).
| |
