OFFSET
0,2
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.
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)
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
EXAMPLE
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.
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]
PROG
(PARI) test(x, y, s)=while(y<s, [x, y]=[y, x+y]); y==s
isFib(n)=my(k=n^2); k+=(k+1)<<2; issquare(k) || (n>0 && 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
CROSSREFS
KEYWORD
nonn
AUTHOR
Bobby Jacobs and Robert G. Wilson v, Oct 07 2016
STATUS
approved