cp's OEIS Frontend

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

%I A006047 M0422 #116 Apr 25 2025 12:54:18
%S A006047 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 A006047 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 A006047 6,12,18,9,18,27,6,12,18,12,24,36,18,36,54,9,18,27,18,36,54,27,54
%N A006047 Number of entries in n-th row of Pascal's triangle not divisible by 3.
%C A006047 Fixed point of the morphism a -> a, 2a, 3a, starting from a(1) = 1. - _Robert G. Wilson v_, Jan 24 2006
%C A006047 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 A006047 a(n) = A206424(n) + A227428(n); number of nonzero terms in row n of triangle A083093. - _Reinhard Zumkeller_, Jul 11 2013
%D A006047 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A006047 Antti Karttunen, <a href="/A006047/b006047.txt">Table of n, a(n) for n = 0..19683</a> (terms 0..1000 from Reinhard Zumkeller).
%H A006047 J.-P. Allouche and Jeffrey 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 A006047 Michael Gilleland, <a href="/selfsimilar.html">Some Self-Similar Integer Sequences</a>
%H A006047 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 A006047 Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, <a href="https://arxiv.org/abs/2408.06817">Periodic minimum in the count of binomial coefficients not divisible by a prime</a>, arXiv:2408.06817 [math.NT], 2024.
%H A006047 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 A006047 <a href="/index/Fi#FIXEDPOINTS">Index entries for sequences that are fixed points of mappings</a>
%F A006047 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 A006047 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 A006047 G.f.: Product_{n>=0} (1+2*x^(3^n)+3*x^(2*3^n)) (Northshield). - _Johannes W. Meijer_, Jun 05 2011
%F A006047 G.f. g(x) satisfies g(x) = (1 + 2*x + 3*x^2)*g(x^3). - _Robert Israel_, Oct 15 2015
%F A006047 From _Tom Edgar_, Oct 15 2015: (Start)
%F A006047 a(3^k) = 2 for k>=0;
%F A006047 a(2*3^k) = 3 for k>=0;
%F A006047 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 A006047 A056239(a(n)) = A053735(n). - _Antti Karttunen_, Jun 03 2017
%F A006047 a(n) = Sum_{k = 0..n} mod(C(n,k)^2, 3). - _Peter Bala_, Dec 17 2020
%e A006047 15 in base 3 is 120, here r=1 and s=1 so a(15) = 3*2 = 6.
%e A006047 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 A006047 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 A006047 f:= proc(n) option remember; ((n mod 3)+1)*procname(ceil((n+1)/3)-1) end proc:
%p A006047 f(0):= 1: f(1):= 2:
%p A006047 seq(f(i), i=0..100); # _Robert Israel_, Oct 15 2015
%t A006047 Nest[Flatten[ # /. a_Integer -> {a, 2a, 3a}] &, {1}, 4] (* _Robert G. Wilson v_, Jan 24 2006 *)
%t A006047 Nest[ Join[#, 2#, 3#] &, {1}, 4] (* _Robert G. Wilson v_, Jul 27 2014 *)
%o A006047 (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 A006047 (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 A006047 (PARI) A006047(n) = { my(m=1, d); while(n, d = (n%3); m *= (1+d); n \= 3); m; }; \\ _Antti Karttunen_, May 28 2017
%o A006047 (PARI) a(n) = prod(i=1,#d=digits(n, 3), (1+d[i])) \\ _David A. Corneth_, May 28 2017
%o A006047 (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 A006047 (Haskell)
%o A006047 a006047 = sum . map signum . a083093_row
%o A006047 -- _Reinhard Zumkeller_, Jul 11 2013
%o A006047 (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 A006047 (Python)
%o A006047 from sympy.ntheory.factor_ import digits
%o A006047 from sympy import prod
%o A006047 def a(n):
%o A006047     d=digits(n, 3)
%o A006047     return n + 1 if n<3 else prod(1 + d[i] for i in range(1, len(d)))
%o A006047 print([a(n) for n in range(51)]) # _Indranil Ghosh_, Jun 06 2017
%o A006047 (Python)
%o A006047 from sympy.ntheory import digits
%o A006047 def A006047(n): return 3**(s:=digits(n,3)).count(2)<<s.count(1) # _Chai Wah Wu_, Apr 24 2025
%Y A006047 Cf. A001316, A003586, A038148, A053735, A083093, A089898, A206424, A227428, A286586, A286587, A286633.
%K A006047 nonn
%O A006047 0,2
%A A006047 _Jeffrey Shallit_
%E A006047 More terms from _Ralf Stephan_, Sep 15 2003