A064414 -id:A064414 - cp's OEIS frontend

A000057 Primes dividing all Fibonacci sequences.

2, 3, 7, 23, 43, 67, 83, 103, 127, 163, 167, 223, 227, 283, 367, 383, 443, 463, 467, 487, 503, 523, 547, 587, 607, 643, 647, 683, 727, 787, 823, 827, 863, 883, 887, 907, 947, 983, 1063, 1123, 1163, 1187, 1283, 1303, 1327, 1367, 1423, 1447, 1487, 1543, 1567, 1583

Offset: 1

N. J. A. Sloane

nonn

Here a Fibonacci sequence is a sequence which begins with any two integers and continues using the rule s(n+2) = s(n+1) + s(n). These primes divide at least one number in each such sequence. - Don Reble, Dec 15 2006
Primes p such that the smallest positive m for which Fibonacci(m) == 0 (mod p) is m = p + 1. In other words, the n-th prime p is in this sequence iff A001602(n) = p + 1. - Max Alekseyev, Nov 23 2007
Cubre and Rouse comment that this sequence is not known to be infinite. - Charles R Greathouse IV, Jan 02 2013
Number of terms up to 10^n: 3, 7, 38, 249, 1894, 15456, 130824, 1134404, 10007875, 89562047, .... - Charles R Greathouse IV, Nov 19 2014
These are also the fixed points of sequence A213648 which gives the minimal number of 1's such that n*[n; 1,..., 1, n] = [x; ..., x], where [...] denotes simple continued fractions. - M. F. Hasler, Sep 15 2015
It appears that for n >= 2, all first differences are congruent to 0 (mod 4). - Christopher Hohl, Dec 28 2018
The comment above is equivalent to a(n) == 3 (mod 4) for n >= 2. This is indeed correct. Actually it can be proved that a(n) == 3, 7 (mod 20) for n >= 2. Let p != 2, 5 be a prime, then: A001175(p) divides (p - 1)/2 if p == 1, 9 (mod 20); p - 1 if p == 11, 19 (mod 20); (p + 1)/2 if p == 13, 17 (mod 20). So the remaining cases are p == 3, 7 (mod 20). - Jianing Song, Dec 29 2018

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Christian G. Bower and T. D. Noe, Table of n, a(n) for n = 1..1000
U. Alfred, Primes which are factors of all Fibonacci sequences, Fib. Quart., 2 (1964), 33-38.
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.
D. M. Bloom, On periodicity in generalized Fibonacci sequences, Am. Math. Monthly 72 (8) (1965) 856-861.
H. E. A. Campbell and David L. Wehlau, Zigzag polynomials, Artin's conjecture and trinomials, Finite Fields and Their Applications (2023) Vol. 89, 102198.
Paul Cubre and Jeremy Rouse, Divisibility properties of the Fibonacci entry point, arXiv:1212.6221 [math.NT], 2012.
Ron Knott, General Fibonacci Series.
Rishi Kumar, Kepler Sets of Second-Order Linear Recurrence Sequences Over Q_p, arXiv:2406.05890 [math.NT], 2024. See pp. 2, 7.
N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021 (Includes this sequence).

Subsequence of A064414.

Cf. A001175, A001602, A079346, A106535, A213648.

Select[Prime[Range[1000]], Function[p, a=0; b=1; n=1; While[b != 0, t=b; b = Mod[(a+b), p]; a=t; n++]; n>p]] (* Jean-François Alcover, Aug 05 2018, after Charles R Greathouse IV *)

select(p->my(a=0,b=1,n=1,t);while(b,t=b;b=(a+b)%p; a=t; n++); n>p, primes(1000)) \\ Charles R Greathouse IV, Jan 02 2013

is(p)=fordiv(p-1,d,if(((Mod([1,1;1,0],p))^d)[1,2]==0,return(0)));fordiv(p+1,d,if(((Mod([1,1;1,0],p))^d)[1,2]==0,return(d==p+1 && isprime(p)))) \\ Charles R Greathouse IV, Jan 02 2013

is(p)=if((p-2)%5>1, return(0)); my(f=factor(p+1)); for(i=1, #f~, if((Mod([1, 1; 1, 0], p)^((p+1)/f[i, 1]))[1, 2]==0, return(0))); isprime(p) \\ Charles R Greathouse IV, Nov 19 2014

More terms from Don Reble, Nov 14 2006

A230457 Numbers k such that there exists a Fibonacci-like sequence without multiples of k.

Original entry on oeis.org

5, 8, 10, 11, 12, 13, 15, 16, 17, 18, 19, 20, 21, 22, 24, 25, 26, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 44, 45, 46, 47, 48, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 82, 84, 85, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 99, 100

Offset: 1

Brandon Avila and Tanya Khovanova, Oct 19 2013

nonn

This sequence is a complement of A064414.

The primes in the sequence are A230359.

			The Lucas numbers form a Fibonacci-like sequence such that no term is divisible by 5.

Amiram Eldar, Table of n, a(n) for n = 1..10000
Brandon Avila and Tanya Khovanova, Free Fibonacci Sequences, Journal of Integer Sequences, Vol. 17 (2014), Article 14.8.5; arXiv preprint, arXiv:1403.4614 [math.NT], 2014.

Cf. A230359, A064414.

selQ[n_] := Do[test = Do[ If[ Divisible[ Fibonacci[k-2]*i + Fibonacci[k-1]*j, n], Return[True]], {k, 1, 2*n}]; If[test == Null, Return[False]], {i, 1, Floor[Sqrt[n]]}, {j, 1, Floor[Sqrt[n]]}]; Reap[ Do[ If[ selQ[n] =!= Null, Sow[n]], {n, 1, 100}]][[2, 1]] (* Jean-François Alcover, Oct 21 2013 *)

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

Original entry on oeis.org

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

Brandon Avila and Tanya Khovanova, Nov 27 2013

nonn

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.

			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.

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.

Cf. A064414, A230457, A232357.

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

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

A232357 The number of pairs of numbers below n that, when generating a Fibonacci-like sequence modulo n, do not contain zero.

Original entry on oeis.org

0, 0, 0, 0, 4, 0, 0, 24, 0, 16, 20, 48, 84, 0, 36, 120, 144, 144, 36, 64, 288, 80, 0, 360, 104, 336, 0, 288, 448, 144, 60, 504, 580, 864, 196, 912, 684, 792, 756, 760, 880, 1152, 0, 920, 324, 1056, 1472, 1800, 0, 416, 1296, 1344, 1404, 1440, 2504, 2040, 1620, 1792, 116, 1584, 2820, 2040, 2880

Offset: 1

Brandon Avila and Tanya Khovanova, Nov 22 2013

nonn

a(n) = 0 iff n is in A064414, a(n) is not equal to zero iff n is in A230457.

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

			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) = 4.
Any Fibonacci like sequence contains elements divisible by 2, 3, or 4. Thus, a(2) = a(3) = a(4) = 0.

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.

Cf. A064414, A230457, A232656.

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

A233248 The average cycle length of cycles in Fibonacci-like sequences modulo n over all starting pairs of remainders.

Original entry on oeis.org

1, 2, 7, 5, 17, 18, 16, 10, 22, 42, 10, 21, 28, 39, 32, 21, 36, 23, 18, 48, 16, 24, 48, 22, 84, 70, 66, 45, 14, 79, 30, 41, 36, 36, 66, 24, 76, 18, 53, 50, 40, 40, 88, 28, 93, 48, 32, 24, 110, 210, 68, 80, 108, 67, 20, 47, 66, 34, 58, 91, 60, 30

Offset: 1

Brandon Avila and Tanya Khovanova, Dec 06 2013

nonn

a(n) = round(A233246(n)/n^2).
If n is in A064414, then a(n) is the average distance between two neighboring multiples of n.
If n is in A064414, then a(n)/2 is the average distance to the next zero over all starting pairs of remainders.

			For n=4 there are four possible cycles: A trivial cycle of length 1: 0; two cycles of length 6: 0,1,1,2,3,1; and a cycle of length 3: 0,2,2. Hence, a(4) = round((1+9+36+36)/16) = 5.

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

Cf. A233246, A064414

cl[i_, j_, n_] := (step = 1; first = i; second = j;
  next = Mod[first + second, n];
  While[second != i || next != j, step++; first = second;
   second = next; next = Mod[first + second, n]]; step)
Table[Round[
  Total[Flatten[Table[cl[i, j, n], {i, 0, n - 1}, {j, 0, n - 1}]]]/
   n^2], {n, 70}]

A233246 Sum of squares of cycle lengths for different cycles in Fibonacci-like sequences modulo n.

Original entry on oeis.org

1, 10, 65, 82, 417, 650, 769, 658, 1793, 4170, 1151, 3026, 4705, 7690, 7137, 5266, 10369, 7562, 6319, 19218, 6977, 11510, 25345, 12818, 52417, 47050, 48449, 35410, 11565, 71370, 28351, 42130, 39615, 41482, 81057, 30674, 103969, 25282, 80033

Offset: 1

Brandon Avila and Tanya Khovanova, Dec 06 2013

nonn

Here Fibonacci-like means a sequence following the Fibonacci recursion: b(n)=b(n-1)+b(n-2). These sequences modulo n cycle. The number of different cycles is A015134(n).
This sequence divided by n^2 is the average cycle length per different starting pairs modulo n, see A233248.
If n is in A064414, then a(n)/n^2 is the average distance between two neighboring multiples of n.
If n is in A064414, then a(n)/2n^2 is the average distance to the next zero over all starting pairs of remainders.

			For n=4 there are four possible cycles: A trivial cycle of length 1: 0; two cycles of length 6: 0,1,1,2,3,1; and a cycle of length 3: 0,2,2. Hence, a(4)=1+9+36+36=82.

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

Cf. A233248, A064414.

cl[i_, j_, n_] := (step = 1; first = i; second = j;
  next = Mod[first + second, n];
  While[second != i || next != j, step++; first = second;
   second = next; next = Mod[first + second, n]]; step)
Table[Total[
  Flatten[Table[cl[i, j, n], {i, 0, n - 1}, {j, 0, n - 1}]]], {n, 50}]

cp's OEIS Frontend

A000057 Primes dividing all Fibonacci sequences.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

PARI

PARI

Extensions

A230457 Numbers k such that there exists a Fibonacci-like sequence without multiples of k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A232357 The number of pairs of numbers below n that, when generating a Fibonacci-like sequence modulo n, do not contain zero.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A233248 The average cycle length of cycles in Fibonacci-like sequences modulo n over all starting pairs of remainders.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A233246 Sum of squares of cycle lengths for different cycles in Fibonacci-like sequences modulo n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica