login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A006047 Number of entries in n-th row of Pascal's triangle not divisible by 3.
(Formerly M0422)
26
1, 2, 3, 2, 4, 6, 3, 6, 9, 2, 4, 6, 4, 8, 12, 6, 12, 18, 3, 6, 9, 6, 12, 18, 9, 18, 27, 2, 4, 6, 4, 8, 12, 6, 12, 18, 4, 8, 12, 8, 16, 24, 12, 24, 36, 6, 12, 18, 12, 24, 36, 18, 36, 54, 3, 6, 9, 6, 12, 18, 9, 18, 27, 6, 12, 18, 12, 24, 36, 18, 36, 54, 9, 18, 27, 18, 36, 54, 27, 54 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

Fixed point of the morphism a -> a, 2a, 3a, starting from a(1) = 1. - Robert G. Wilson v, Jan 24 2006

This is a particular case of the number of entries in n-th row of Pascal's triangle not divisible by a prime p, which is given by a simple recursion using ⊗, the Kronecker (or tensor) product of vectors. Let v_0=(1,2,...,p). Then v_{n+1)=v_0 ⊗ v_n, where the vector v_n contains the values for the first p^n rows of Pascal's triangle (rows 0 through p^n-1). - William B. Everett (bill(AT)chgnet.ru), Mar 29 2008

a(n) = A206424(n) + A227428(n); number of nonzero terms in row n of triangle A083093. - Reinhard Zumkeller, Jul 11 2013

REFERENCES

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

LINKS

Reinhard Zumkeller (terms 0..1000) & Antti Karttunen, Table of n, a(n) for n = 0..19683

J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197.

Michael Gilleland, Some Self-Similar Integer Sequences

H. Harborth, Number of Odd Binomial Coefficients, Proc. Amer. Math. Soc. 62.1 (1977), 19-22. (Annotated scanned copy)

Sam Northshield, Sums across Pascal’s triangle modulo 2, Congressus Numerantium, 200, pp. 35-52, 2010.

Index entries for sequences that are fixed points of mappings

FORMULA

Write n in base 3; if the representation contains r 1's and s 2's then a(n) = 3^s * 2^r. Also a(n) = Sum_{k=0..n} (C(n, k)^2 mod 3). - Avi Peretz (njk(AT)netvision.net.il), Apr 21 2001

a(n) = b(n+1), with b(1)=1, b(2)=2, b(3n)=3b(n), b(3n+1)=b(n+1), b(3n+2)=2b(n+1). - Ralf Stephan, Sep 15 2003

G.f.: Product_{n>=0} (1+2*x^(3^n)+3*x^(2*3^n)) (Northshield). - Johannes W. Meijer, Jun 05 2011

G.f. g(x) satisfies g(x) = (1 + 2*x + 3*x^2)*g(x^3). - Robert Israel, Oct 15 2015

From Tom Edgar, Oct 15 2015: (Start)

a(3^k) = 2 for k>=0;

a(2*3^k) = 3 for k>=0;

a(n) = Product_{b_j != 0} a(b_j*3^j) where n = Sum_{j>=0} b_j*3^j is the ternary representation of n. (End)

A056239(a(n)) = A053735(n). - Antti Karttunen, Jun 03 2017

EXAMPLE

15 in base 3 is 120, here r=1 and s=1 so a(15) = 3*2 = 6.

William B. Everett's comment with p=3, n=2: v_0 = (1,2,3), v_1 = (1,2,3) => v_2 = (1*1,1*2,1*3,2*1,2*2,2*3,3*1,3*2,3*3) = (1,2,3,2,4,6,3,6,9), the first 3^2 values of the present sequence. - Wolfdieter Lang, Mar 19 2014

MAPLE

p:=proc(n) local ct, k: ct:=0: for k from 0 to n do if binomial(n, k) mod 3 = 0 then else ct:=ct+1 fi od: end: seq(p(n), n=0..82); # Emeric Deutsch

f:= proc(n) option remember; ((n mod 3)+1)*procname(ceil((n+1)/3)-1) end proc:

f(0):= 1: f(1):= 2:

seq(f(i), i=0..100); # Robert Israel, Oct 15 2015

MATHEMATICA

Nest[Flatten[ # /. a_Integer -> {a, 2a, 3a}] &, {1}, 4] (* Robert G. Wilson v, Jan 24 2006 *)

Nest[ Join[#, 2#, 3#] &, {1}, 4] (* Robert G. Wilson v, Jul 27 2014 *)

PROG

(PARI) b(n)=if(n<3, n, if(n%3==0, 3*b(n/3), if(n%3==1, 1*b((n+2)/3), 2*b((n+1)/3)))) \\ Ralf Stephan

(PARI) A006047(n) = b(1+n); \\ (The above PARI-program by Ralf Stephan is for offset-1-version of this sequence.) - Antti Karttunen, May 28 2017

(PARI) A006047(n) = { my(m=1, d); while(n, d = (n%3); m *= (1+d); n \= 3); m; }; \\ Antti Karttunen, May 28 2017

(PARI) a(n) = prod(i=1, #d=digits(n, 3), (1+d[i])) \\ David A. Corneth, May 28 2017

(PARI) upto(n) = my(res = [1], v); while(#res < n, v = concat(2*res, 3*res); res = concat(res, v)); res \\ David A. Corneth, May 29 2017

(Haskell)

a006047 = sum . map signum . a083093_row

-- Reinhard Zumkeller, Jul 11 2013

(Scheme) (define (A006047 n) (if (zero? n) 1 (let ((d (mod n 3))) (* (+ 1 d) (A006047 (/ (- n d) 3)))))) ;; For R6RS standard. Use modulo instead of mod in older Schemes like MIT/GNU Scheme. - Antti Karttunen, May 28 2017

(Python)

from sympy.ntheory.factor_ import digits

from operator import mul

def a(n):

    d=digits(n, 3)

    return n + 1 if n<3 else reduce(mul, [1 + d[i] for i in xrange(1, len(d))])

print [a(n) for n in xrange(151)] # Indranil Ghosh, Jun 06 2017

CROSSREFS

Cf. A001316, A003586, A038148, A053735, A083093, A089898, A206424, A227428, A286586, A286587, A286633.

Sequence in context: A214943 A202864 A291290 * A285712 A062068 A130542

Adjacent sequences:  A006044 A006045 A006046 * A006048 A006049 A006050

KEYWORD

nonn

AUTHOR

Jeffrey Shallit

EXTENSIONS

More terms from Ralf Stephan, Sep 15 2003

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified November 19 21:13 EST 2017. Contains 294954 sequences.