|
%I #82 Mar 04 2023 02:02:51
%S 1,1,0,1,1,0,0,0,0,1,1,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,1,1,0,0,
%T 0,0,1,1,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
%U 0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,1,1,0,0,0,0,1,1,0,1,1,0,0,0,0,0,0,0,0,0,0,0
%N a(0) = 1; thereafter a(3n+2) = 0, a(3n) = a(3n+1) = a(n).
%C Number of partitions of n into distinct powers of 3.
%C Trajectory of 1 under the morphism: 1 -> 110, 0 -> 000. Thus 1 -> 110 ->110110000 -> 110110000110110000000000000 -> ... - _Philippe Deléham_, Jul 09 2005
%C Also, an example of a d-perfect sequence.
%C This is a composite of two earlier sequences contributed at different times by _N. J. A. Sloane_ and by _Reinhard Zumkeller_, Mar 05 2005. _Christian G. Bower_ extended them and found that they agreed for at least 512 terms. The proof that they were identical was found by _Ralf Stephan_, Jun 13 2005, based on the fact that they were both 3-regular sequences.
%H Reinhard Zumkeller, <a href="/A039966/b039966.txt">Table of n, a(n) for n = 0..10000</a>
%H David Applegate, Omar E. Pol and N. J. A. Sloane, <a href="/A000695/a000695_1.pdf">The Toothpick Sequence and Other Sequences from Cellular Automata</a>, Congressus Numerantium, Vol. 206 (2010), 157-191. [There is a typo in Theorem 6: (13) should read u(n) = 4.3^(wt(n-1)-1) for n >= 2.]
%H D. Kohel, S. Ling and C. Xing, <a href="http://www.maths.usyd.edu.au/u/kohel/doc/perfect.ps">Explicit Sequence Expansions</a>, in Sequences and their Applications, C. Ding, T. Helleseth, and H. Niederreiter, eds., Proceedings of SETA'98 (Singapore, 1998), 308-317, 1999.
%H N. J. A. Sloane, <a href="/wiki/Catalog_of_Toothpick_and_CA_Sequences_in_OEIS">Catalog of Toothpick and Cellular Automata Sequences in the OEIS</a>
%H <a href="/index/Fi#FIXEDPOINTS">Index entries for sequences that are fixed points of mappings</a>
%H <a href="/index/Ch#char_fns">Index entries for characteristic functions</a>
%F a(0) = 1, a(1) = 0, a(n) = b(n-2), where b is the sequence defined by b(0) = 1, b(3n+2) = 0, b(3n) = b(3n+1) = b(n). - _Ralf Stephan_
%F a(n) = A005043(n-1) mod 3. - _Christian G. Bower_, Jun 12 2005
%F a(n) = A002426(n) mod 3. - _John M. Campbell_, Aug 24 2011
%F a(n) = A000275(n) mod 3. - _John M. Campbell_, Jul 08 2016
%F Properties: 0 <= a(n) <= 1, a(A074940(n)) = 0, a(A005836(n)) = 1; A104406(n) = Sum(a(k), 1 <= k <= n). - _Reinhard Zumkeller_, Mar 05 2005
%F Euler transform of sequence b(n) where b(3^k) = 1, b(2*3^k) = -1 and zero otherwise. - _Michael Somos_, Jul 15 2005
%F G.f. A(x) satisfies A(x) = (1+x)*A(x^3). - _Michael Somos_, Jul 15 2005
%F G.f.: Product{k>=0} 1+x^(3^k). Exponents give A005836.
%e The triples of elements (a(3k), a(3k+1), a(3k+2)) are (1,1,0) if a(k) = 1 and (0,0,0) if a(k) = 0. So since a(2) = 0, a(6) = a(7) = a(8) = 0, and since a(3) = 1, a(9) = a(10) = 1 and a(11) = 0. - _Michael B. Porter_, Jul 11 2016
%p a := proc(n) option remember; if n <= 1 then RETURN(1) end if; if n = 2 then RETURN(0) end if; if n mod 3 = 2 then RETURN(0) end if; if n mod 3 = 0 then RETURN(a(1/3*n)) end if; if n mod 3 = 1 then RETURN(a(1/3*n - 1/3)) end if end proc; # _Ralf Stephan_, Jun 13 2005
%t (* first do *) Needs["DiscreteMath`Combinatorica`"] (* then *) s = Rest[ Sort[ Plus @@@ Table[UnrankSubset[n, Table[3^i, {i, 0, 4}]], {n, 32}]]]; Table[ If[ Position[s, n] == {}, 0, 1], {n, 105}] (* _Robert G. Wilson v_, Jun 14 2005 *)
%t CoefficientList[Series[Product[(1 + x^(3^k)), {k, 0, 5}], {x, 0, 111}], x] (* or *)
%t Nest[ Flatten[ # /. {0 -> {0, 0, 0}, 1 -> {1, 1, 0}}] &, {1}, 5] (* _Robert G. Wilson v_, Mar 29 2006 *)
%t Nest[ Join[#, #, 0 #] &, {1}, 5] (* _Robert G. Wilson v_, Jul 27 2014 *)
%o (PARI) {a(n)=local(A,m); if(n<0, 0, m=1; A=1+O(x); while(m<=n, m*=3; A=(1+x)*subst(A,x,x^3)); polcoeff(A,n))} /* _Michael Somos_, Jul 15 2005 */
%o (PARI) A039966(n)=vecmax(digits(n+!n,3))<2;
%o apply(A039966, [0..99]) \\ _M. F. Hasler_, Feb 15 2023
%o (Haskell)
%o a039966 n = fromEnum (n < 2 || m < 2 && a039966 n' == 1)
%o where (n',m) = divMod n 3
%o -- _Reinhard Zumkeller_, Sep 29 2011
%o (Python)
%o def A039966(n):
%o while n > 2:
%o n,r = divmod(n,3)
%o if r==2: return 0
%o return int(n!=2) # _M. F. Hasler_, Feb 15 2023
%Y For generating functions Product_{k>=0} (1+a*x^(b^k)) for the following values of (a,b) see: (1,2) A000012 and A000027, (1,3) A039966 and A005836, (1,4) A151666 and A000695, (1,5) A151667 and A033042, (2,2) A001316, (2,3) A151668, (2,4) A151669, (2,5) A151670, (3,2) A048883, (3,3) A117940, (3,4) A151665, (3,5) A151671, (4,2) A102376, (4,3) A151672, (4,4) A151673, (4,5) A151674.
%Y Cf. A062051, A000009, A000244, A004642.
%Y Characteristic function of A005836 (and apart from offset of A003278).
%K nonn
%O 0,1
%A _N. J. A. Sloane_, Dec 11 1999
%E Entry revised Jun 30 2005
%E Offset corrected by _John M. Campbell_, Aug 24 2011
|
