login
Number of entries in n-th row of Pascal's triangle not divisible by 3.
(Formerly M0422)
29

%I M0422 #103 Aug 06 2024 06:44:20

%S 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,

%T 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,

%U 6,12,18,9,18,27,6,12,18,12,24,36,18,36,54,9,18,27,18,36,54,27,54

%N Number of entries in n-th row of Pascal's triangle not divisible by 3.

%C Fixed point of the morphism a -> a, 2a, 3a, starting from a(1) = 1. - _Robert G. Wilson v_, Jan 24 2006

%C 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

%C a(n) = A206424(n) + A227428(n); number of nonzero terms in row n of triangle A083093. - _Reinhard Zumkeller_, Jul 11 2013

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

%H Reinhard Zumkeller (terms 0..1000) & Antti Karttunen, <a href="/A006047/b006047.txt">Table of n, a(n) for n = 0..19683</a>

%H J.-P. Allouche and J. Shallit, <a href="http://dx.doi.org/10.1016/0304-3975(92)90001-V">The ring of k-regular sequences</a>, Theoretical Computer Sci., 98 (1992), 163-197.

%H Michael Gilleland, <a href="/selfsimilar.html">Some Self-Similar Integer Sequences</a>

%H H. Harborth, <a href="/A006046/a006046_1.pdf">Number of Odd Binomial Coefficients</a>, Proc. Amer. Math. Soc. 62.1 (1977), 19-22. (Annotated scanned copy)

%H Sam Northshield, <a href="https://citeseerx.ist.psu.edu/pdf/a765e1f8064266bf3e36c34bf5c60bb8bb32d392">Sums across Pascal’s triangle modulo 2</a>, Congressus Numerantium, 200, pp. 35-52, 2010.

%H <a href="/index/Fi#FIXEDPOINTS">Index entries for sequences that are fixed points of mappings</a>

%F 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

%F 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

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

%F G.f. g(x) satisfies g(x) = (1 + 2*x + 3*x^2)*g(x^3). - _Robert Israel_, Oct 15 2015

%F From _Tom Edgar_, Oct 15 2015: (Start)

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

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

%F 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)

%F A056239(a(n)) = A053735(n). - _Antti Karttunen_, Jun 03 2017

%F a(n) = Sum_{k = 0..n} mod(C(n,k)^2, 3). - _Peter Bala_, Dec 17 2020

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

%e 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

%p 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_

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

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

%p seq(f(i), i=0..100); # _Robert Israel_, Oct 15 2015

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

%t Nest[ Join[#, 2#, 3#] &, {1}, 4] (* _Robert G. Wilson v_, Jul 27 2014 *)

%o (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_

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

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

%o (PARI) a(n) = prod(i=1,#d=digits(n, 3), (1+d[i])) \\ _David A. Corneth_, May 28 2017

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

%o (Haskell)

%o a006047 = sum . map signum . a083093_row

%o -- _Reinhard Zumkeller_, Jul 11 2013

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

%o (Python)

%o from sympy.ntheory.factor_ import digits

%o from sympy import prod

%o def a(n):

%o d=digits(n, 3)

%o return n + 1 if n<3 else prod(1 + d[i] for i in range(1, len(d)))

%o print([a(n) for n in range(51)]) # _Indranil Ghosh_, Jun 06 2017

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

%K nonn

%O 0,2

%A _Jeffrey Shallit_

%E More terms from _Ralf Stephan_, Sep 15 2003