|
%I #50 Aug 09 2017 16:38:36
%S 1,2,5,7,8,11,13,12,18,17,20,20,23,26,26,29,31,30,35,33,38,42,39,42,
%T 46,45,50,48,51,53,56,55,59,60,65,63,66,66,69,72,74,73,79,76,79,83,82,
%U 85,89,86,92,91,94,96,97,103,102,101,105,104,111,109,110,116,115,118,120,117,126,124,125
%N The number of Fibonacci type sequences which contain n after the initial terms.
%C 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.
%C Obviously, if we do not restrict n from being either a(0) or a(1), then there are infinitely many terms for any n.
%C 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.
%H Charles R Greathouse IV, <a href="/A277266/b277266.txt">Table of n, a(n) for n = 0..10000</a> (terms to 1250 from Bobby Jacobs and Robert G. Wilson v)
%F It appears that a(n) ~ kn for k near 89/50.
%F 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
%e a(0) = 1 since there is only the single sequence with {a(0),a(1)} = {0,0};
%e a(1) = 2 since there are 2 sequences with {a(0),a(1)} = {0,1} & {1,0} which contain 2 as a term;
%e a(2) = 5 since 2 is in the sequences with {a(0),a(1)} = {0,1}, {0,2}, {1,0}, {1,1}, {2,0};
%e 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};
%e 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};
%e 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.
%t g[x_, y_] := (Clear[a]; a[0] = x; a[1] = y; a[n_] := a[n] = a[n - 1] + a[n - 2]);
%t 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]
%o (PARI) test(x,y,s)=while(y<s, [x,y]=[y,x+y]); y==s
%o isFib(n)=my(k=n^2); k+=(k+1)<<2; issquare(k) || (n>0 && issquare(k-8))
%o 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
%o (PARI) isFib(n)=my(k=n^2); k+=(k+1)<<2; issquare(k) || (n>0 && issquare(k-8))
%o 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
%Y Cf. A000045, A290565.
%K nonn
%O 0,2
%A _Bobby Jacobs_ and _Robert G. Wilson v_, Oct 07 2016
|
