independent computational replication

Fibonacci residues modulo prime powers

Status and authorship: I rebuilt this project independently. I wrote and tested the code, reran all 147 finite computations, checked 78 small cases with a separate implementation, compared selected outputs with published benchmarks, and wrote the explanation myself. The benchmark values are published mathematics; I do not claim them as a new discovery.

I counted the residues appearing in Fibonacci, Lucas, and Pell sequences modulo prime powers. The Fibonacci computations match selected benchmark values from Bragman and Rowland's 2025 paper, then apply the same finite experiment to Lucas and Pell cases.

the question

Take a recurrence modulo p^k and keep generating terms. Which residues ever appear? Does their proportion change as k grows? I compared Fibonacci and Lucas with Pell, where the coefficient changes from 1 to 2.

My dataset contains 147 runs for eight primes, with exponents limited so a laptop could enumerate the complete orbit.

method

One value can repeat before the whole recurrence cycles. To avoid stopping too early, the code tracks pairs of consecutive values.

x(n + 2) = a x(n + 1) + b x(n) mod m
state(n) = (x(n), x(n + 1))

Choose m = p^k.
Move to the next pair and record its first coordinate.
Stop when the original pair comes back.
Count the different residues and divide that number by p^k.

All three recurrences have b = 1, so their pair maps are invertible for each tested modulus. I worked through and checked this pure-cycle behavior before using it.

results

My output agrees with selected published Fibonacci benchmarks. I then ran the same finite experiment for Lucas and Pell sequences.

Selected values from the 147 runs
Sequence and prime	Tested k	Observed residue proportion
Fibonacci, p = 13	1 to 5	9/13 at every tested exponent
Lucas, p = 5	1 to 7	4/5 down to 26,044/78,125, about 0.33336
Lucas, p = 13	1 to 5	12/13 at every tested exponent
Pell, p = 13	1 to 5	9/13 at k = 1, then 1/13
Pell, p = 31	1 to 4	19/31 at k = 1, then 22/961

Three stacked line charts show the observed residue proportion at each exponent for Fibonacci, Lucas, and Pell sequences, with one line for each of eight primes. — The chart shows full Fibonacci coverage for the tested powers of 3 and 5, a Lucas trend at 5, and sharp first-lift Pell drops at 13 and 31.

the observed Pell pattern

At p = 13, the Pell period is 28 for both k = 1 and k = 2, while the residue count only goes from 9 to 13. That drops the proportion from 9/13 to 1/13. In the later saved runs, the period and residue count both multiply by 13, so the proportion stays fixed. At p = 31, my output similarly shows a first-lift drop and later stabilization.

Two line charts show Pell state-period growth and residue-count growth when lifting powers of 13 and 31. — The chart compares the Pell period and residue-count growth that motivated the question below.

a question from the results

If the Pell state period and residue count both grow by p at one prime-power lift, maybe the residue proportion stays fixed at the later non-exceptional lifts.

These runs motivated the bounded hypothesis. It is not a proof or a claim of a new theorem. A next step would be to test a predeclared wider range and look for counterexamples.

how I checked it

I checked starting-pair returns, confirmed that observed density did not increase under lifting, and completed 78 small-modulus comparisons with a separate implementation. The archive contains five unit tests. These checks support the displayed finite results, but they do not prove the bounded pattern.

I tested eight primes and only finitely many exponents. That cannot prove a limit.
Large prime powers take longer because the full state orbit can be long.
Published work already explains the Fibonacci benchmarks and the unusual Pell periods at 13 and 31.
My literature search for Lucas and Pell results was targeted, so it cannot be called exhaustive.
I wrote and tested the code and analysis myself. The files below make every displayed result inspectable and rerunnable.

project files

I included the notebook, code, data, and checks so the project can be inspected and rerun from the saved files.

read and rerun

executed Jupyter notebook.ipynb The analysis, code cells, tables, and plots.
complete project.zip The folder structure with code, data, tests, figures, and setup files.
project guide.md Definitions, rerun commands, outputs, and what I am not claiming.

code

core Python source.py The recurrence definitions and pair-state counter.
unit tests.py Checks for known periods, residue counts, and edge cases.

data and checks

results.csv All 147 runs, one row per sequence, prime, and exponent.
validation record.json The separate checks and published benchmark comparisons.

sources

main paper

Bragman and Rowland, Limiting density of the Fibonacci sequence modulo powers of a primeDOI The Fibonacci paper I used as a benchmark.

background reading

Klaška, Donald Dines Wall's ConjecturePDF Background on the unusual Pell period lifts.
Avila and Chen, Lucas numbers and complete residue systemsPDF Known results about which Lucas residues appear.
Bundschuh and Bundschuh, Fibonacci and Lucas numbers modulo powers of 3PDF Published Fibonacci and Lucas results modulo powers of 3.