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

21, 1, 1, 41, 145, 9, 13, 441, 409, 541, 19, 29, 715, 33, 625, 37, 4321, 25, 51, 44, 57, 49, 63, 17, 69, 6937, 8009, 3349, 49, 33, 12161, 21385, 109, 8961, 61, 10945, 113, 123, 21001, 137, 39961, 22205, 119, 149, 149, 6001, 12297, 37409, 171, 36341, 21, 149

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

Table of n, a(n) for n=1..52.

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[Numerator[density[p]], {p, Prime[Range[20]]}]

Crossrefs

The denominators are A351000.

Sequence in context: A040442 A040441 A190581 * A291073 A172301 A022184

Adjacent sequences: A350996 A350997 A350998 * A351000 A351001 A351002

Keyword

nonn,frac

Author

Eric Rowland, Feb 02 2022

Status

approved