p. 472, Method 1 — classification of periodic seeds
ProvedCarryRNG.SWB.periodic_seed_iffp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1random-number-generationsubtract-with-borrow
Let , , and write and as base- integers. A Method 1 seed is strictly periodic exactly in these cases:
The two named seeds are fixed points; the strict inequalities classify every nontrivial periodic seed. This is the paper’s Method 1 rule, with digit strings interpreted as integers.
Preamble
import Definitions.Def_CarryRNG_SWB_step import Definitions.Def_CarryRNG_SWB_highBlock import Definitions.Def_CarryRNG_SWB_lowBlock import Definitions.Def_CarryRNG_AWC_zeroSeed import Definitions.Def_CarryRNG_AWC_topSeed
Formal statement
namespace CarryRNG.SWB
/-- Page 472, Method 1: the strict inequalities classify the nontrivial periodic seeds. -/
theorem periodic_seed_iff (b : ℕ) (L : CarryRNG.AWC.Lags) (hb : 2 ≤ b) (z : CarryRNG.AWC.State b L.r) :
z ∈ Function.periodicPts (step b L hb) ↔
(z.c.val = 0 ∧ highBlock b L z < lowBlock b L z) ∨
(z.c.val = 1 ∧ lowBlock b L z < highBlock b L z) ∨
z = CarryRNG.AWC.zeroSeed b L.r hb ∨ z = CarryRNG.AWC.topSeed b L.r hb := by sorry
end CarryRNG.SWB
Source
G. Marsaglia and A. Zaman, A new class of random number generators, Ann. Appl. Probab. 1 (1991), p. 472, Section 4.5, Method 1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.