Methodology of2³⁶ Verification

1. Inductive Principle

Recall (Day 02) that the stopping time is \(\sigma(n)=\min\{k\ge 1:T^k(n)

Suppose it has already been established that \(\sigma(m)<\infty\) for all \(2\le m

Consequently, verifying the Collatz conjecture for all positive integers less than \(B\) reduces to confirming that every such integer eventually drops strictly below its starting value. The only cycle that must be known a priori is the trivial cycle containing 1 (which is immediate).

Hesaplandı The verification performed on this site establishes the claim for \(B=2^{36}\).

2. Residue-Class Optimisation

• If \(n\) is even, \(T(n)=n/2
• If \(n\equiv 1\pmod{4}\), write \(n=4k+1\). Then \(T(n)=(3n+1)/2=6k+2\), and \(T^2(n)=3k+1\). For \(k\ge 1\) one has \(3k+1<4k+1\), so \(\sigma(n)\le 2\).
• The only residue class that may require a longer trajectory is \(n\equiv 3\pmod{4}\).

Hence it is sufficient to simulate the map only for integers congruent to 3 modulo 4. All other integers descend in at most two steps of \(T\).

Bilinen literatür This elementary reduction is classical (see Terras 1976 and later verification literature).

3. Block-Table Acceleration

For any fixed modulus \(2^r\) the first several iterates of \(T\) on a residue class are given by an affine function

where \(q\) is the number of odd steps and the constant \(c\) depends only on the residue and the parity sequence. Precomputing, for a moderate \(r\) (typically 16–20), the pairs \((s,q,c)\) that guarantee an immediate descent, or the next residue and the net multiplicative factor, produces a compact lookup table.

Numbers whose residue modulo \(2^r\) is known to drop below the starting value in a fixed number of steps can be eliminated without simulation. The remaining candidates are examined by direct iteration of \(T\) until a descent is observed.

Hesaplandı The implementation used for the \(2^{36}\) bound employs such modular block tables (see code.html and verification.html).

Bilinen literatür Larger-scale verifications (Barina et al., up to \(2^{68}\) and beyond) employ analogous sieves and compressed tables; the principle is identical.

4. Algorithm and Pseudocode

Input: bound B = 2^36
Output: confirmation that σ(n) < ∞ for all 2 ≤ n < B

1. Precompute block table M of size 2^r (r ≈ 16–20):
   for each residue a mod 2^r do
       simulate a short orbit of T;
       record the first descent length s and the image residue if descent occurs.

2. For n from 2 to B-1:
   if n even or n ≡ 1 (mod 4) then
       continue;          // σ(n) ≤ 2, already proved
   end if
   // n ≡ 3 (mod 4)
   if block table M[n mod 2^r] guarantees descent then
       continue;
   end if
   // full simulation
   m ← n;
   steps ← 0;
   while m ≥ n and steps < MAX_STEPS do
       if m even then m ← m/2 else m ← (3m+1)/2;
       steps ← steps + 1;
   end while
   if m ≥ n then
       report failure;   // never observed for n < 2^36
   end if
end for
report success.

Hesaplandı The concrete C implementation (referenced on the code page) completed the loop for \(B=2^{36}\) in 157 seconds using exact 64-bit integer arithmetic. No failure was reported.

All arithmetic is exact; no floating-point approximation is used. Overflow is impossible for the intermediate values that arise while checking integers below \(2^{36}\) on a 64-bit machine, because the known peak values remain well below \(2^{64}\) for these starting values.

5. Correctness Argument

1. Kanıtlandı. Even integers and integers ≡ 1 (mod 4) satisfy σ(n) ≤ 2 by the short explicit orbits given in Section 2.
2. Kanıtlandı. The block table correctly classifies residues: any residue declared “guaranteed descent” has been exhaustively simulated for a length sufficient to force the image below the starting value, independently of higher bits.
3. Hesaplandı. For every remaining integer n < 2^{36} congruent to 3 (mod 4), the direct iteration terminates with a value strictly smaller than n. This is a finite machine computation.
4. Kanıtlandı. By the inductive principle of Section 1, σ(n) < ∞ for all 2 ≤ n < 2^{36}. Therefore every such n eventually reaches the cycle containing 1.

6. Reproducibility Notes

• Reference implementation: verify.c (see code page).
• Compilation: gcc -O2 -o verify verify.c.
• Reported wall-clock time for the 2^{36} run: 157 seconds.
• Exact integer arithmetic only; no external libraries required beyond a standard C compiler.

Hesaplandı Timing and successful termination are properties of one concrete execution. Independent re-verification in a second language is scheduled for Day 04.

7. Relation to Larger Bounds

Bilinen literatür Independent projects have verified the conjecture to substantially higher bounds (Barina et al.: 2^{68}, later 2^{71}). The algorithmic skeleton (inductive first descent + modular sieves) is the same; only the scale of the tables, the use of 128-bit arithmetic, and distributed execution differ.

Varsayım/Sezgi Extending the present implementation beyond 2^{36} is limited primarily by memory bandwidth and the growth of intermediate values, not by any conceptual obstacle. Higher bounds are a matter of engineering, not of new mathematics.