cp's OEIS Frontend

A081611 Number of numbers <= n having no 2 in their ternary representation.

%I A081611 #40 Dec 05 2024 10:19:53
%S A081611 1,2,2,3,4,4,4,4,4,5,6,6,7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,9,10,10,11,12,
%T A081611 12,12,12,12,13,14,14,15,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,
%U A081611 16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16
%N A081611 Number of numbers <= n having no 2 in their ternary representation.
%C A081611 a(n) is also the size of the subset of [1..n] when numbers are added greedily so as to not contain a 3-term arithmetic progression, i.e., according to A003278: a(n) = the largest k such that A003278(k) <= n. (Cf. A003002, the size of the optimal (largest) 3-free subset of [1..n].) - _Shreevatsa R_, Oct 19 2009
%H A081611 Reinhard Zumkeller, <a href="/A081611/b081611.txt">Table of n, a(n) for n = 0..10000</a>
%F A081611 a(n) + A081610(n) = n+1.
%F A081611 From _Michael Somos_, Aug 31 2006: (Start)
%F A081611 G.f. A(x) satisfies A(x)=(1+x)*(1+x+x^2)*A(x^3).
%F A081611 G.f.: (1/(1-x))*Product_{k>=0} (1+x^(3^k)).
%F A081611 a(n) = a(n-1) + A039966(n). (End)
%t A081611 CoefficientList[Series[Product[1+x^(3^k), {k,0,5}]/(1-x), {x,0,100}], x] (* _G. C. Greubel_, Mar 29 2019 *)
%o A081611 (PARI) {a(n)=local(A,m); if(n<0, 0, m=1; A=1+O(x); while(m<=n, m*=3; A=(1+x)*(1+x+x^2)*subst(A,x,x^3)); polcoeff(A,n))} /* _Michael Somos_, Aug 31 2006 */
%o A081611 (PARI) first(n)=my(s,t); vector(n,k,t=Set(digits(k,3)); s+=t[#t]<2) \\ _Charles R Greathouse IV_, Sep 02 2015
%o A081611 (PARI) my(x='x+O('x^100)); Vec(prod(k=0,5,1+x^(3^k))/(1-x)) \\ _G. C. Greubel_, Mar 29 2019
%o A081611 (Haskell)
%o A081611 a081611 n = a081611_list !! n
%o A081611 a081611_list = scanl1 (+) a039966_list
%o A081611 -- _Reinhard Zumkeller_, Jan 28 2012
%o A081611 (Magma) R<x>:=PowerSeriesRing(Integers(), 100); Coefficients(R!( (&*[1+x^(3^k): k in [0..5]])/(1-x) )); // _G. C. Greubel_, Mar 29 2019
%o A081611 (Sage) (product(1+x^(3^k) for k in (0..5))/(1-x)).series(x, 100).coefficients(x, sparse=False) # _G. C. Greubel_, Mar 29 2019
%o A081611 (Python)
%o A081611 from gmpy2 import digits
%o A081611 def A081611(n):
%o A081611     l = (s:=digits(n,3)).find('2')
%o A081611     if l >= 0: s = s[:l]+'1'*(len(s)-l)
%o A081611     return int(s,2)+1 # _Chai Wah Wu_, Dec 05 2024
%Y A081611 Cf. A003278, A007089, A039966, A081603, A081608, A061392, A081610.
%K A081611 nonn
%O A081611 0,2
%A A081611 _Reinhard Zumkeller_, Mar 23 2003