OEIS A166944 — a kernel-decidable compositeness test for first differences
Definitiona166944_composite_testThis bundle fixes a single computable predicate on natural numbers: whether has a proper divisor.
For define
evaluated as a decidable Boolean by trial division over . Thus certifies that is not prime and not , and certifies that has no proper divisor at all.
The predicate exists so that statements about the first differences of the
A166944 recurrence can be settled by kernel evaluation rather than by appeal to a
prime predicate. Core Lean does not provide Nat.Prime — that is a Mathlib
declaration — and the recurrence-side development deliberately keeps Mathlib out
of its import closure so that iteration on the recurrence stays lightweight.
isComposite is therefore the Mathlib-free stand-in, and it is strong enough for
the classification results that follow: a difference that is not composite is
either or prime, and the statements below pin down exactly which indices
produce composite differences.
Formalization Note List.range (n+1) is used so the search space is bounded
and decide terminates; the condition m < n excludes , so = false really
does mean "no proper divisor" rather than "no divisor below ".
import Mathlib.Data.Nat.Prime.Defs import Definitions.Def_a166944_record_core namespace A166944Research /-- Trial-division compositeness test, decidable in the kernel. `isComposite n = true` iff there is `m` with `2 <= m < n` and `m | n`. Written with `List.range` so that `decide` can evaluate it: core Lean has no `Prime` (that lives in Mathlib), and the recurrence-side development deliberately avoids importing Mathlib. -/ def isComposite (n : Nat) : Bool := (List.range (n + 1)).any (fun m => 2 ≤ m && m < n && n % m == 0) end A166944Research