A277266 The number of Fibonacci type sequences which contain n after the initial terms.

1, 2, 5, 7, 8, 11, 13, 12, 18, 17, 20, 20, 23, 26, 26, 29, 31, 30, 35, 33, 38, 42, 39, 42, 46, 45, 50, 48, 51, 53, 56, 55, 59, 60, 65, 63, 66, 66, 69, 72, 74, 73, 79, 76, 79, 83, 82, 85, 89, 86, 92, 91, 94, 96, 97, 103, 102, 101, 105, 104, 111, 109, 110, 116, 115, 118, 120, 117, 126, 124, 125

Offset: 0

Author

Bobby Jacobs and Robert G. Wilson v, Oct 07 2016

Keywords

• nonn

Comments

We define a "Fibonacci" type sequence to be any two term recursive sequence with a(n) = a(n-2) + a(n-1) with a(0) and a(1) being any two nonnegative integers.

Obviously, if we do not restrict n from being either a(0) or a(1), then there are infinitely many terms for any n.

Even if {x, y} generates n, {y, x} may not generate n. For example, {1, 2} generates 5, but {2, 1} does not generate 5. Similarly, {2, 1} generates 4, but {1, 2} does not generate 4.

Examples

			a(0) = 1 since there is only the single sequence with {a(0),a(1)} = {0,0};
a(1) = 2 since there are 2 sequences with {a(0),a(1)} = {0,1} & {1,0} which contain 2 as a term;
a(2) = 5 since 2 is in the sequences with {a(0),a(1)} = {0,1}, {0,2}, {1,0}, {1,1}, {2,0};
a(3) = 7 since 3 is in the sequences with {a(0),a(1)} = {0,1}, {0,3}, {1,0}, {1,1}, {1,2}, {2,1}, {3,0};
a(4) = 8 since 4 is in the sequences with {a(0),a(1)} = {0,2}, {0,4}, {1,3}, {2,0}, {2,1}, {2,2}, {3,1}, {4,0};
a(5) = 11  since 5 is in the sequences with {a(0),a(1)} = {0,1}, {0,5}, {1,0}, {1,1}, {1,2}, {1,4}, {2,3}, {3,1}, {3,2}, {4,1}, {5,0}; etc.
		

Links

• Charles R Greathouse IV, Table of n, a(n) for n = 0..10000 (terms to 1250 from Bobby Jacobs and Robert G. Wilson v)

Crossrefs

Cf. A000045, A290565.

Programs

Mathematica

g[x_, y_] := (Clear[a]; a[0] = x; a[1] = y; a[n_] := a[n] = a[n - 1] + a[n - 2]);
f[n_] := Block[{c = 0}, Do[ g[x, y]; If[ MemberQ[ Rest@ Rest@ Array[a, Floor[n/((x + y + 1) GoldenRatio)] + 10, 0], n], c++], {x, 0, n}, {y, 0, n}]; c]; Array[f, 70, 0]

PARI

test(x,y,s)=while(y0 && issquare(k-8))
a(n)=if(n<2, return(n+1)); sum(i=1,n-1, sum(j=1,n-i, test(j,i+j,n))) + 2*sumdiv(n,d, isFib(d)) \\ Charles R Greathouse IV, Oct 12 2016

PARI

isFib(n)=my(k=n^2); k+=(k+1)<<2; issquare(k) || (n>0 && issquare(k-8))
first(n)=my(v=2*vector(n,k,sumdiv(k,d, isFib(d)))); for(i=1,n-1, for(j=1,n-1, my(x=j,y=i+j); while(y<=n, v[y]++; [x,y]=[y,x+y]))); concat(1,v) \\ Charles R Greathouse IV, Oct 12 2016

Formula

It appears that a(n) ~ kn for k near 89/50.

The constant k = 1.773877583285132... = A290565. Proof: Take a number n. For any Fibonacci sequence containing n after the first two terms, the number m immediately before n in the sequence satisfies 0 <= m <= n. The sequences (0, n), (1, n-1), (2, n-2), ..., (n, 0) all contain n as the next term. There are n+1 of these sequences. As n->infinity, the ratio of the number of these sequences to n approaches 1. If n/2 <= m <= n, then the sequence (2m-n, n-m) contains n after 2 terms. There are floor(n/2)+1 of these sequences. As n->infinity, the ratio of the number of these sequences to n approaches 1/2. Similarly, there are approximately n/(Fibonacci(x)*Fibonacci(x+1)) sequences that contain n after x terms. As n->infinity, the ratio of the number of these sequences to n approaches 1/(Fibonacci(x)*Fibonacci(x+1)). Therefore, as n->infinity, the ratio of the number of Fibonacci sequences containing n to n approaches 1 + 1/2 + 1/6 + 1/15 + ... = 1/(1*1) + 1/(1*2) + 1/(2*3) + 1/(3*5) + ... = Sum_{x>=1} 1/(Fibonacci(x)*Fibonacci(x+1)) = 1.773877583285132... - Bobby Jacobs, Aug 07 2017