login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

Denominator of the limiting density of residues attained by the Fibonacci sequence modulo powers of the n-th prime.
1

%I #9 Feb 02 2022 23:40:33

%S 32,1,1,56,264,13,17,760,552,1740,31,37,1722,43,2256,53,7080,61,67,71,

%T 73,79,83,89,97,20604,10712,11556,109,113,16256,34584,137,38920,149,

%U 45904,157,163,28056,173,64440,65884,191,193,197,79600,89464,49952,227,105340

%N Denominator of the limiting density of residues attained by the Fibonacci sequence modulo powers of the n-th prime.

%C 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.

%H Nicholas Bragman and Eric Rowland, <a href="https://arxiv.org/abs/2202.00704">Limiting density of the Fibonacci sequence modulo powers of p</a>, arXiv:2202.00704 [math.NT], 2022.

%H Eric Rowland and Reem Yassawi, <a href="http://dx.doi.org/10.1016/j.indag.2016.11.019">p-adic asymptotic properties of constant-recursive sequences</a>, Indagationes Mathematicae 28 (2017) 205-220.

%e Let p = 2. For all m >= 5, the residues attained modulo 2^m by the Fibonacci sequence have density 21/32.

%e Let p = 3. For all m >= 1, every residue modulo 3^m is attained by the Fibonacci sequence, so the density is 1.

%e 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.

%t density[2] := 21/32

%t density[p_?PrimeQ /; p >= 3] := Module[{restrictedperiodlength = 1, periodlength, wallexponent, lucaszeros, fullresidues, partialresidues},

%t NestWhile[

%t Function[values,

%t restrictedperiodlength++;

%t Mod[{{0, 1}, {1, 1}}.values, p]

%t ],

%t {0, 1},

%t Function[values, Last[values] != 0]

%t ];

%t periodlength = SelectFirst[

%t {1, 2, 4} restrictedperiodlength,

%t Function[n, Mod[Fibonacci[n + 1], p] == 1]

%t ];

%t wallexponent = IntegerExponent[Fibonacci[restrictedperiodlength], p];

%t lucaszeros = Which[

%t OddQ[restrictedperiodlength], {},

%t !Divisible[restrictedperiodlength, 4], {restrictedperiodlength/2},

%t True, {restrictedperiodlength/2, (3 restrictedperiodlength)/2}

%t ];

%t fullresidues = DeleteDuplicates[Mod[Fibonacci[Complement[Range[0, periodlength - 1], lucaszeros]], p^wallexponent]];

%t partialresidues = DeleteDuplicates[Mod[Fibonacci[lucaszeros], p^wallexponent]];

%t Length[fullresidues]/p^wallexponent + Length[Complement[partialresidues, fullresidues]]/(2 p^(2 wallexponent - 1) (p + 1))

%t ]

%t Table[Denominator[density[p]], {p, Prime[Range[20]]}]

%Y The numerators are A350999.

%K nonn,frac

%O 1,1

%A _Eric Rowland_, Feb 02 2022