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

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

Offset: 0

Author

Paul Weisenhorn, Aug 24 2011

Keywords

• nonn

Comments

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

Examples

			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.
		

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.

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.

Programs

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:
      h
    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 *)

Python

from math import prod
from gmpy2 import digits
def A194458(n): return sum(prod(int(d)+1 for d in digits(m,5)) for m in range(n+1)) # Chai Wah Wu, Aug 10 2025

Python

from math import prod
from gmpy2 import digits
def A194458(n):
    d = list(map(lambda x:int(x)+1,digits(n+1,5)[::-1]))
    return sum((b-1)*prod(d[a:])*15**a for a, b in enumerate(d))>>1 # Chai Wah Wu, Aug 13 2025

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.

Extensions

Edited by Alois P. Heinz, Sep 06 2011