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

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

Offset: 0

Author

Reinhard Zumkeller, Mar 23 2003

Keywords

• nonn

Comments

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

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 0..10000

Crossrefs

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

Programs

Haskell

a081611 n = a081611_list !! n
a081611_list = scanl1 (+) a039966_list
-- Reinhard Zumkeller, Jan 28 2012

Magma

R:=PowerSeriesRing(Integers(), 100); Coefficients(R!( (&*[1+x^(3^k): k in [0..5]])/(1-x) )); // G. C. Greubel, Mar 29 2019

Mathematica

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

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 */

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

PARI

my(x='x+O('x^100)); Vec(prod(k=0,5,1+x^(3^k))/(1-x)) \\ G. C. Greubel, Mar 29 2019

Python

from gmpy2 import digits
def A081611(n):
    l = (s:=digits(n,3)).find('2')
    if l >= 0: s = s[:l]+'1'*(len(s)-l)
    return int(s,2)+1 # Chai Wah Wu, Dec 05 2024

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

Formula

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

From Michael Somos, Aug 31 2006: (Start)

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

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

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