|
| |
|
|
A277266
|
|
The number of Fibonacci type sequences which contain n after the initial terms.
|
|
2
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
|
|
|
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
|
|
|
|
STATUS
|
approved
|
| |
|
|
