A232656 The number of pairs of numbers below n that, when generating a Fibonacci-like sequence modulo n, contain zeros.

1, 4, 9, 16, 21, 36, 49, 40, 81, 84, 101, 96, 85, 196, 189, 136, 145, 180, 325, 336, 153, 404, 529, 216, 521, 340, 729, 496, 393, 756, 901, 520, 509, 292, 1029, 384, 685, 652, 765, 840, 801, 612, 1849, 1016, 1701, 1060, 737, 504, 2401, 2084, 1305, 1360, 1405, 1476, 521, 1096, 1629, 1572

Offset

1,2

Comments

a(n) = n^2 iff n is in A064414, a(n) is not equal to n^2 iff n is in A230457.

a(n) + A232357(n) = n^2.

Links

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

B. Avila and T. Khovanova, Free Fibonacci Sequences, arXiv preprint arXiv:1403.4614 [math.NT], 2014 and J. Int. Seq. 17 (2014) # 14.8.5.

Formula

Conjecture: a(n) = Sum_{d|n} phi(d)*A001177(d), where phi = Euler's totient function (A000010). - Logan J. Kleinwaks, Oct 28 2017

Sum_{d|n} phi(d)*A001177(d) = Sum_{k=1..n} A001177(n/gcd(n,k)) = Sum_{k=1..n} A001177(gcd(n,k))phi(gcd(n,k)/phi(n/gcd(n,k)). - Richard L. Ollerton, May 09 2021

Example

The sequence 2,1,3,4,2,1 is the sequence of Lucas numbers modulo 5. Lucas numbers are never divisible by 5. The 4 pairs (2,1), (1,3), (3,4), (4,2) are the only pairs that can generate a sequence modulo 5 that doesn't contain zeros. Thus, a(5) = 21, as 21 other pairs generate sequences that do contain zeros.
Any Fibonacci like sequence contains elements divisible by 2, 3, or 4. Thus, a(2) = 4, a(3) = 9, a(4) = 16.

Mathematica

fibLike[list_] := Append[list, list[[-1]] + list[[-2]]]; Table[k^2 -Count[Flatten[Table[Count[Nest[fibLike, {n, m}, k^2]/k, _Integer], {n, k - 1}, {m, k - 1}]], 0], {k, 70}]

Crossrefs

Cf. A064414, A230457, A232357.

Sequence in context: A313343 A261849 A246336 * A364699 A010460 A313344

Adjacent sequences: A232653 A232654 A232655 * A232657 A232658 A232659

Keyword

nonn

Author

Brandon Avila and Tanya Khovanova, Nov 27 2013

Status

approved