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

Author

Brandon Avila and Tanya Khovanova, Nov 27 2013

Keywords

• nonn

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.

Examples

			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.
		

Links

• 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.

Crossrefs

Cf. A064414, A230457, A232357.

Programs

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}]

Formula

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

a(n) = 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