OEIS A166944 - factor predicates and the small-to-proper passage
Definitiona166944_factorsThe terminal argument for the OEIS A166944 recurrence certifies that the two neighbours and of the terminal horizon have no proper divisor. The certificate that argument actually produces is weaker and more useful: absence of a small divisor.
Write for the statement that no integer with divides , and for the statement that no with divides .
The passage from the first to the second is where the horizon bound enters. Write with both factors at least . If both exceeded , then
which the bound forbids. Hence the smaller of the two factors already lies in and divides , contradicting .
The reason this matters for the recurrence is that the replay produces only coprimality facts: a divisor found inside the quiet tail would force a nonunit increment there, contradicting quietness. Converting those coprimality facts into absence of a proper divisor is exactly the step above, and it is what makes the next difference record a twin prime.
Formalization Note Both predicates take a plain natural number rather than a Fin bound, so that the factorisation argument can name the cofactor directly. The module is core Lean: no Mathlib import, and the case analysis avoids by_contra, which is unavailable in this environment.
RETIRED 2026-11-19. This bundle is superseded by a166944_factor_layer in the same environment. The version here quantifies the factor predicates over plain naturals and proves the small-to-proper passage by factorising N = f * c directly, which was a workaround for an environment assumption that turned out to be unnecessary: Mathlib is available in this environment. The replacement uses the Fin-based predicates and routes through Nat.gcd, matching the recurrence-side development, so downstream work should import Definitions.Def_a166944_factor_layer instead.
namespace A166944Research
/-- No factor of `N` lies in `[2, root]`. -/
def NoSmallFactor (N root : Nat) : Prop :=
∀ f : Nat, 2 ≤ f → f ≤ root → ¬ f ∣ N
/-- No factor of `N` lies in `[2, N)`. -/
def NoProperFactor (N : Nat) : Prop :=
∀ f : Nat, 2 ≤ f → f < N → ¬ f ∣ N
/-- **No small divisor implies no proper divisor.**
Write `N = f * c`. Both factors are at least `2`. If both exceeded `root`, then
`N = f * c >= (root+1)^2`, contradicting the horizon bound. So the smaller factor
lies in `[2, root]` and divides `N`, which `NoSmallFactor` forbids. -/
theorem no_proper_factor_of_no_small_factor {N root : Nat}
(hcheck : NoSmallFactor N root) (hroot : N < (root + 1) * (root + 1)) :
NoProperFactor N := by
intro f hf2 hfN hdiv
obtain ⟨c, hc⟩ := hdiv
have hc2 : 2 ≤ c := by
rcases Nat.lt_or_ge c 2 with h | h
· rcases Nat.lt_or_ge c 1 with h0 | h1
· have : c = 0 := by omega
rw [this, Nat.mul_zero] at hc
omega
· have hc1 : c = 1 := by omega
rw [hc1, Nat.mul_one] at hc
omega
· exact h
by_cases hfl : f ≤ root
· exact hcheck f hf2 hfl ⟨c, hc⟩
· by_cases hcl : c ≤ root
· exact hcheck c hc2 hcl ⟨f, Nat.mul_comm c f ▸ hc⟩
· exfalso
have hf' : root + 1 ≤ f := by omega
have hc' : root + 1 ≤ c := by omega
have hprod : (root + 1) * (root + 1) ≤ f * c := Nat.mul_le_mul hf' hc'
rw [← hc] at hprod
exact Nat.lt_irrefl N (Nat.lt_of_lt_of_le hroot hprod)
end A166944Research