%I M0684 #53 Oct 29 2023 21:16:42
%S 1,2,3,5,8,11,16,21,29,40,51,67,88,109,138,167,207,258,309,376,443,
%T 531,640,749,887,1054,1221,1428,1635,1893,2202,2511,2887,3330,3773,
%U 4304,4835,5475,6224,6973,7860,8747,9801,11022,12243,13671,15306,16941
%N a(n) = a(n-1) + a(n - 1 - number of even terms so far).
%C From _T. D. Noe_, Jul 27 2007: (Start)
%C This is similar to A000123 and A005704, which both have a recursion a(n)=a(n-1)+a([n/k]), where k is 2 and 3, respectively. Those sequences count "partitions of k*n into powers of k". For the present sequence, k=phi. Does A006336(n) count the partitions of n*phi into powers of phi?
%C Answering my own question: If the recursion starts with a(0)=1, then I think we obtain "number of partitions of n*phi into powers of phi" (see A131882).
%C Here we need negative powers of phi also: letting p=phi and q=1/phi, we have
%C n=0: 0*p = {} for 1 partition,
%C n=1: 1*p = p = 1+q for 2 partitions,
%C n=2: 2*p = p+p = 1+p+q = 1+1+q+q = p^2+q for 4 partitions, etc.
%C So the present sequence, which starts with a(1)=1, counts 1/2 of the "number of partitions of n*phi into powers of phi". (End)
%H N. J. A. Sloane, <a href="/A006336/b006336.txt">Table of n, a(n) for n = 1..10000</a> (first 1000 terms from T. D. Noe)
%H Max Alekseyev, <a href="/A006336/a006336.txt">Proof of Paul Hanna's formula</a>.
%H D. R. Hofstadter, <a href="/A006336/a006336_1.pdf">Eta-Lore</a>. [Cached copy, with permission]
%H D. R. Hofstadter, <a href="/A006336/a006336_2.pdf">Pi-Mu Sequences</a>. [Cached copy, with permission]
%H D. R. Hofstadter and N. J. A. Sloane, <a href="/A006336/a006336.pdf">Correspondence, 1977 and 1991</a>.
%F It seems that A006336 can be generated by a rule using the golden ratio phi: a(n) = a(n-1) + a([n/Phi]) for n>1 with a(1)=1 where phi = (sqrt(5)+1)/2, I.e. the number of even terms up to position n-1 equals n-1 - [n/Phi] for n>1 where Phi = (sqrt(5)+1)/2. (This is true - see the Alekseyev link.) - _Paul D. Hanna_, Jul 22 2007
%F a(n) = a(n-1)+a(A060143(n)) for n>1; subsequence of A134409; A134408 and A134409 give first and second differences; A001950(n)=Min(m:A134409(m)=a(n)). - _Reinhard Zumkeller_, Oct 24 2007
%p # Maple code for first M terms of a(n) and A060144, from _N. J. A. Sloane_, Oct 25 2014
%p M:=100;
%p v[1]:=1; v[2]:=2; w[1]:=0; w[2]:=1;
%p for n from 3 to M do
%p v[n]:=v[n-1]+v[n-1-w[n-1]];
%p if v[n] mod 2 = 0 then w[n]:=w[n-1]+1 else w[n]:=w[n-1]; fi; od:
%p [seq(v[n],n=1..M)]; # A006336
%p [seq(w[n],n=1..M)]; # A060144 shifted
%t a[n_Integer] := a[n] = Block[{c, k}, c = 0; k = 1; While[k < n, If[ EvenQ[ a[k] ], c++ ]; k++ ]; Return[a[n - 1] + a[n - 1 - c] ] ]; a[1] = 1; a[2] = 2; Table[ a[n], {n, 0, 60} ]
%o (PARI) A006336(N=99) = local(a=vector(N,i,1), e=0); for(n=2,#a,e+=0==(a[n]=a[n-1]+a[n-1-e])%2);a \\ _M. F. Hasler_, Jul 23 2007
%o (Haskell)
%o a006336 n = a006336_list !! (n-1)
%o a006336_list = 1 : h 2 1 0 where
%o h n last evens = x : h (n + 1) x (evens + 1 - x `mod` 2) where
%o x = last + a006336 (n - 1 - evens)
%o -- _Reinhard Zumkeller_, May 18 2011
%Y Cf. A007604, A000123, A005704, A131882, A134408, A134409, A001950.
%Y "Number of even terms so far" is A060144(n+1).
%K nonn,easy,nice
%O 1,2
%A D. R. Hofstadter, Jul 15 1977
%E More terms from _Robert G. Wilson v_, Mar 07 2001
%E Entry revised by _N. J. A. Sloane_, Oct 25 2014