# Fibonacci and Lucas-type sequences modulo prime powers

> **Status: independently built and verified.** I wrote and reran the code,
> checked the outputs, and prepared the analysis and documentation myself. This
> project reproduces published Fibonacci results and explores Lucas and Pell
> cases. It does not claim the published results or the bounded Pell hypothesis
> as original research.

This folder has the code and results from a computational check of Nicholas Bragman and Eric Rowland's 2025 study of Fibonacci residue density modulo prime powers. It also applies the same experiment to Lucas and Pell sequences. The notebook and data are included so the computation can be rerun and checked.

The commands below assume the complete project directory from `fibonacci-prime-power-project.zip`. The individual files linked from the website are flattened convenience copies and are not a standalone runnable folder.

The program follows every state in the complete pair-state orbit for:

- Fibonacci: `F(0)=0`, `F(1)=1`, `F(n+2)=F(n+1)+F(n)`
- Lucas: `L(0)=2`, `L(1)=1`, `L(n+2)=L(n+1)+L(n)`
- Pell: `P(0)=0`, `P(1)=1`, `P(n+2)=2P(n+1)+P(n)`

The runs use the primes `2, 3, 5, 7, 11, 13, 19, 31`. I limited the exponent ranges so a laptop could still enumerate each full orbit exactly.

## project files

### read first

- `fibonacci_prime_power_study.ipynb`: executed notebook with the analysis, explanations, exact tables, and plots

### code

- `run_study.py`: runs the experiments, saves the outputs, and creates the figures
- `src/modular_recurrences.py`: recurrence definitions and complete pair-state orbit counter
- `tests/test_modular_recurrences.py`: tests for known periods, residue counts, and edge cases
- `scripts/build_notebook.py`: rebuilds the notebook

### data and checks

- `data/results.csv`: one exact result for each sequence, prime, and exponent
- `data/residue_sets_small.json`: exact residue lists for moduli up to 400
- `data/validation.json`: monotonicity checks and comparisons with published benchmarks

### figures

- `figures/density_by_k.png`: plot of observed proportion against exponent
- `figures/pell_lift_growth.png`: comparison of Pell period growth and residue-count growth at 13 and 31

## run it

With [`uv`](https://docs.astral.sh/uv/) installed, run:

```bash
uv run python run_study.py
uv run python -m unittest discover -s tests -v
uv run python scripts/build_notebook.py
uv run jupyter nbconvert --execute --to notebook --inplace fibonacci_prime_power_study.ipynb
```

## how it works

For `x(n+2)=a*x(n+1)+b*x(n) mod m`, the pair `(x(n),x(n+1))` determines every later term. When `gcd(b,m)=1`, the pair map is invertible, so the starting pair is on a finite cycle with no preperiod. The program follows the whole cycle, records the first coordinate, and stops when the starting pair returns. It then divides the number of different residues by `m=p^k`.

## scope and limits

The Fibonacci results reproduce published math. The Lucas and Pell comparisons are experiments. Researchers had already documented the unusual Pell periods at 13 and 31. The notebook's guess about residue counts is based only on the runs in this project. It is not proved, and I am not claiming it as a new result.

Primary source: N. Bragman and E. Rowland, ["Limiting density of the Fibonacci sequence modulo powers of a prime"](https://doi.org/10.1007/s40993-025-00667-1), *Research in Number Theory* 11 (2025), 88.

Pell-period context: J. Klaška, ["Donald Dines Wall's Conjecture"](https://www.fq.math.ca/Papers1/56-1/Klaska10917.pdf), *Fibonacci Quarterly* 56 (2018).

I wrote the code and text, reran the full study, inspected the outputs, and verified the saved checks myself. The notebook, data, tests, and figures are included so someone else can inspect exactly what I did.