login
A351000
Denominator of the limiting density of residues attained by the Fibonacci sequence modulo powers of the n-th prime.
1
32, 1, 1, 56, 264, 13, 17, 760, 552, 1740, 31, 37, 1722, 43, 2256, 53, 7080, 61, 67, 71, 73, 79, 83, 89, 97, 20604, 10712, 11556, 109, 113, 16256, 34584, 137, 38920, 149, 45904, 157, 163, 28056, 173, 64440, 65884, 191, 193, 197, 79600, 89464, 49952, 227, 105340
OFFSET
1,1
COMMENTS
For a prime p, the limiting density of residues attained by the Fibonacci sequence modulo powers of p is the limit as m -> infinity of |{F(n) mod p^m : n >= 0}|/p^m.
LINKS
Nicholas Bragman and Eric Rowland, Limiting density of the Fibonacci sequence modulo powers of p, arXiv:2202.00704 [math.NT], 2022.
Eric Rowland and Reem Yassawi, p-adic asymptotic properties of constant-recursive sequences, Indagationes Mathematicae 28 (2017) 205-220.
EXAMPLE
Let p = 2. For all m >= 5, the residues attained modulo 2^m by the Fibonacci sequence have density 21/32.
Let p = 3. For all m >= 1, every residue modulo 3^m is attained by the Fibonacci sequence, so the density is 1.
Let p = 11. Rowland and Yassawi showed that the residues attained modulo 11^m by the Fibonacci sequence have approach density 145/264 as m -> infinity.
MATHEMATICA
density[2] := 21/32
density[p_?PrimeQ /; p >= 3] := Module[{restrictedperiodlength = 1, periodlength, wallexponent, lucaszeros, fullresidues, partialresidues},
NestWhile[
Function[values,
restrictedperiodlength++;
Mod[{{0, 1}, {1, 1}}.values, p]
],
{0, 1},
Function[values, Last[values] != 0]
];
periodlength = SelectFirst[
{1, 2, 4} restrictedperiodlength,
Function[n, Mod[Fibonacci[n + 1], p] == 1]
];
wallexponent = IntegerExponent[Fibonacci[restrictedperiodlength], p];
lucaszeros = Which[
OddQ[restrictedperiodlength], {},
!Divisible[restrictedperiodlength, 4], {restrictedperiodlength/2},
True, {restrictedperiodlength/2, (3 restrictedperiodlength)/2}
];
fullresidues = DeleteDuplicates[Mod[Fibonacci[Complement[Range[0, periodlength - 1], lucaszeros]], p^wallexponent]];
partialresidues = DeleteDuplicates[Mod[Fibonacci[lucaszeros], p^wallexponent]];
Length[fullresidues]/p^wallexponent + Length[Complement[partialresidues, fullresidues]]/(2 p^(2 wallexponent - 1) (p + 1))
]
Table[Denominator[density[p]], {p, Prime[Range[20]]}]
CROSSREFS
The numerators are A350999.
Sequence in context: A062543 A086820 A354946 * A174923 A369651 A351809
KEYWORD
nonn,frac
AUTHOR
Eric Rowland, Feb 02 2022
STATUS
approved