A006048 -id:A006048

Search: a006048 -id:a006048

Displaying 1-2 of 2 results found.

page 1

A194459

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

+10
5

1, 2, 3, 4, 5, 2, 4, 6, 8, 10, 3, 6, 9, 12, 15, 4, 8, 12, 16, 20, 5, 10, 15, 20, 25, 2, 4, 6, 8, 10, 4, 8, 12, 16, 20, 6, 12, 18, 24, 30, 8, 16, 24, 32, 40, 10, 20, 30, 40, 50, 3, 6, 9, 12, 15, 6, 12, 18, 24, 30, 9, 18, 27, 36, 45, 12, 24, 36, 48, 60, 15, 30

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,2

COMMENTS

Pascal triangles modulo p with p prime have the dimension D = log(p*(p+1)/2)/log(p). [Corrected by Connor Lane, Nov 28 2022]

Also number of ones in row n of triangle A254609. - Reinhard Zumkeller, Feb 04 2015

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..10000

FORMULA

a(n) = Product_{d=1..4} (d+1)^b(n,d) with b(n,d) = number of digits d in base 5 expansion of n. The formula generalizes to other prime bases p.

a(n) = A194458(n) - A194458(n-1).

EXAMPLE

n = 32 = 112|_5: b(32,1) = 2, b(32,2) = 1, thus a(32) = 2^2 * 3^1 = 12.

MAPLE

a:= proc(n) local l, m, t;

m:= n;

l:= [0$5];

while m>0 do t:= irem(m, 5, 'm')+1; l[t]:=l[t]+1 od;

mul(r^l[r], r=2..5)

end:

seq(a(n), n=0..100);

MATHEMATICA

Nest[Join[#, 2#, 3#, 4#, 5#]&, {1}, 4] (* Jean-François Alcover, Apr 12 2017, after code by Robert G. Wilson v in A006047 *)

PROG

(Haskell)

a194459 = sum . map (signum . flip mod 5) . a007318_row

-- Reinhard Zumkeller, Feb 04 2015

CROSSREFS

Cf. A006046, A001316 (for p=2).

Cf. A006048, A006047 (for p=3).

Cf. A194458 (for p=5).

Cf. A007318, A254609.

KEYWORD

nonn,look

AUTHOR

Paul Weisenhorn, Aug 24 2011

EXTENSIONS

Edited by Alois P. Heinz, Sep 06 2011

STATUS

approved

A194458

Total number of entries in rows 0,1,...,n of Pascal's triangle not divisible by 5.

+10
2

1, 3, 6, 10, 15, 17, 21, 27, 35, 45, 48, 54, 63, 75, 90, 94, 102, 114, 130, 150, 155, 165, 180, 200, 225, 227, 231, 237, 245, 255, 259, 267, 279, 295, 315, 321, 333, 351, 375, 405, 413, 429, 453, 485, 525, 535, 555, 585, 625, 675, 678, 684, 693, 705, 720, 726

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,2

COMMENTS

The number of zeros in the first n rows is binomial(n+1,2) - a(n).

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..10000

Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Identities and periodic oscillations of divide-and-conquer recurrences splitting at half, arXiv:2210.10968 [cs.DS], 2022, p. 53.

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. See p. 1.

FORMULA

a(n) = ((C(d0+1,2)*15^0*(d1+1) + C(d1+1,2)*15^1)*(d1+1) + C(d1+1,2)*15^1)*(d2+1) + C(d2+1,2)*15^2 ..., where d_k...d_1d_0 is the base 5 expansion of n+1 and 15 = binomial(5+1,2). The formula generalizes to other prime bases p.

EXAMPLE

n = 38: n+1 = 39 = 124_5, thus a(38) = (C(5,2)*15^0*3 + C(3,2)*15^1)*2 + C(2,2)*15^2 = (10*1*3 + 3*15)*2 + 1*225 = 375.

MAPLE

a:= proc(n) local l, m, h, j;

m:= n+1;

l:= [];

while m>0 do l:= [l[], irem (m, 5, 'm')+1] od;

h:= 0;

for j to nops(l) do h:= h*l[j] +binomial (l[j], 2) *15^(j-1) od:

end:

seq (a(n), n=0..100);

MATHEMATICA

a[n_] := Module[{l, m, r, h, j}, m = n+1; l = {}; While[m>0, l = Append[l, {m, r} = QuotientRemainder[m, 5]; r+1]]; h = 0; For[j = 1, j <= Length[l], j++, h = h*l[[j]] + Binomial [l[[j]], 2] *15^(j-1)]; h]; Table [a[n], {n, 0, 100}] (* Jean-François Alcover, Feb 26 2017, translated from Maple *)

CROSSREFS

A006046(n+1) = A006046(n) + A001316(n) for p=2.

A006048(n+1) = A006048(n) + A006047(n+1) for p=3.

a(n+1) = a(n) + A194459(n+1) for p=5.