A081611 - OEIS

%I #40 Dec 05 2024 10:19:53

%S 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 12,12,12,12,13,14,14,15,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,

%U 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 Number of numbers <= n having no 2 in their ternary representation.

%C 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 Reinhard Zumkeller, <a href="/A081611/b081611.txt">Table of n, a(n) for n = 0..10000</a>

%F a(n) + A081610(n) = n+1.

%F From _Michael Somos_, Aug 31 2006: (Start)

%F G.f. A(x) satisfies A(x)=(1+x)*(1+x+x^2)*A(x^3).

%F G.f.: (1/(1-x))*Product_{k>=0} (1+x^(3^k)).

%F a(n) = a(n-1) + A039966(n). (End)

%t CoefficientList[Series[Product[1+x^(3^k), {k,0,5}]/(1-x), {x,0,100}], x] (* _G. C. Greubel_, Mar 29 2019 *)

%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)*(1+x+x^2)*subst(A,x,x^3)); polcoeff(A,n))} /* _Michael Somos_, Aug 31 2006 */

%o (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 (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 (Haskell)

%o a081611 n = a081611_list !! n

%o a081611_list = scanl1 (+) a039966_list

%o -- _Reinhard Zumkeller_, Jan 28 2012

%o (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 (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 (Python)

%o from gmpy2 import digits

%o def A081611(n):

%o     l = (s:=digits(n,3)).find('2')

%o     if l >= 0: s = s[:l]+'1'*(len(s)-l)

%o     return int(s,2)+1 # _Chai Wah Wu_, Dec 05 2024

%Y Cf. A003278, A007089, A039966, A081603, A081608, A061392, A081610.

%K nonn

%O 0,2

%A _Reinhard Zumkeller_, Mar 23 2003