import math
import random
def v2(n: int) -> int:
"""2-adic valuation of an integer n."""
if n == 0:
return float('inf')
return (n & -n).bit_length() - 1
def odd_only_step(n: int):
"""Odd-only Collatz step: T(n)=(3n+1)/2^{v2(3n+1)} for odd n."""
assert n & 1 == 1, "odd-only step requires odd n"
x = 3*n + 1
v = v2(x)
return x >> v, v
class SingularChainCache:
"""
Cache for s_k ≡ -3^{-1} (mod 2^k).
Using pow(3, -1, 2^k) is correct since gcd(3,2^k)=1.
Caching avoids recomputing modular inverses repeatedly.
"""
def __init__(self):
self.cache = {} # k -> s_k
def s_k(self, k: int) -> int:
if k not in self.cache:
mod = 1 << k
inv3 = pow(3, -1, mod)
self.cache[k] = (-inv3) % mod
return self.cache[k]
def singular_match_depth(n: int, max_k: int, cache: SingularChainCache) -> int:
"""
Returns the largest k<=max_k such that n ≡ s_k (mod 2^k).
Strategy: doubling search then binary search.
"""
k = 1
best = 0
while k <= max_k:
if (n % (1 << k)) == cache.s_k(k):
best = k
k *= 2
else:
break
lo, hi = best, min(max_k, k-1)
while lo < hi:
mid = (lo + hi + 1) // 2
if (n % (1 << mid)) == cache.s_k(mid):
lo = mid
else:
hi = mid - 1
return lo
def contraction_drift_certificate(n: int, max_depth: int = 200):
"""
Computes a short odd-only prefix and checks the exact inequality:
2^{V_m} > 3^m
which is equivalent to:
V_m > m*log2(3)
but avoids float issues.
Returns first m where the certificate triggers, if any.
"""
assert n & 1 == 1
V = 0
x = n
pow3 = 1 # 3^m
for m in range(1, max_depth + 1):
x, v = odd_only_step(x)
V += v
pow3 *= 3
# Exact check: 2^V > 3^m
if (1 << V) > pow3:
return {
"status": "DRIFT_CERTIFIED",
"m": m,
"V_m": V,
"pow2_V": 1 << V,
"pow3_m": pow3,
"next_n": x
}
return {
"status": "NOT_CERTIFIED_WITHIN_DEPTH",
"m": max_depth,
"V_m": V,
"pow3_m": pow3,
"next_n": x
}
def audit_integer(n: int, max_depth: int = 200, singular_k_max: int = 256, singular_threshold: int = 8):
"""
Public auditor:
- drift certificate on a short odd-only prefix (exact integer comparison)
- singular chain matching depth k (exact congruence)
"""
assert n & 1 == 1
cache = SingularChainCache()
drift = contraction_drift_certificate(n, max_depth=max_depth)
k_match = singular_match_depth(n, max_k=singular_k_max, cache=cache)
drift["singular_match_k"] = k_match
drift["singular_threshold"] = singular_threshold
if k_match >= singular_threshold:
drift["singular_flag"] = f"MATCHES_SINGULAR_CHAIN_MOD_2^{k_match}"
else:
drift["singular_flag"] = f"NO_MATCH_ABOVE_THRESHOLD (k_match={k_match})"
return drift
def demo(num_samples=5, min_bits=100, max_bits=120, max_depth=200, singular_k_max=256, singular_threshold=8):
print("--- COLLATZ STRUCTURAL AUDITOR (PUBLIC DEMO) v2.1 ---")
print("This tool computes a short odd-only prefix and checks an exact drift certificate.")
print("It is not a proof of Collatz and does not run trajectories to completion.\n")
for _ in range(num_samples):
bits = random.randint(min_bits, max_bits)
n = random.getrandbits(bits) | 1 # odd
res = audit_integer(
n,
max_depth=max_depth,
singular_k_max=singular_k_max,
singular_threshold=singular_threshold
)
print(f"Input n: {str(n)[:24]}... [{n.bit_length()} bits]")
print(f"Singular match depth: k_match={res['singular_match_k']} (threshold={res['singular_threshold']})")
print(f"Singular flag: {res['singular_flag']}")
if res["status"] == "DRIFT_CERTIFIED":
print(f" ✅ Drift certified at m={res['m']}")
print(f" Exact: 2^V_m > 3^m (V_m={res['V_m']})")
else:
print(f" ⚠️ No drift certificate within m={res['m']} (non-conclusive)")
print("-" * 70)
if __name__ == "__main__":
demo()
