A006047 Number of entries in n-th row of Pascal's triangle not divisible by 3.
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
Offset: 0
Keywords
Examples
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
References
- N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Links
- Antti Karttunen, Table of n, a(n) for n = 0..19683 (terms 0..1000 from Reinhard Zumkeller).
- J.-P. Allouche and Jeffrey 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)
- Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Periodic minimum in the count of binomial coefficients not divisible by a prime, arXiv:2408.06817 [math.NT], 2024.
- 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
Crossrefs
Programs
-
Haskell
a006047 = sum . map signum . a083093_row -- Reinhard Zumkeller, Jul 11 2013
-
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 *) -
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
-
Python
from sympy.ntheory.factor_ import digits from sympy import prod def a(n): d=digits(n, 3) return n + 1 if n<3 else prod(1 + d[i] for i in range(1, len(d))) print([a(n) for n in range(51)]) # Indranil Ghosh, Jun 06 2017 -
Python
from sympy.ntheory import digits def A006047(n): return 3**(s:=digits(n,3)).count(2)<
-
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
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)
a(n) = Sum_{k = 0..n} mod(C(n,k)^2, 3). - Peter Bala, Dec 17 2020
Extensions
More terms from Ralf Stephan, Sep 15 2003
Comments