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,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:
      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 *)
Table[Sum[Times@@(IntegerDigits[m, 5]+1), {m, 0, n}], {n, 0, 67}] (* Vincenzo Librandi, Feb 18 2026 *)

Prog

(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
(Magma) [ &+[ &*[ d+1 : d in (m eq 0 select [0] else IntegerToSequence(m, 5))]: m in [0..n]]: n in [0..67]]; // Vincenzo Librandi, Feb 18 2026

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.

Sequence in context: A231672 A375750 A120993 * A083266 A334130 A054731

Adjacent sequences: A194455 A194456 A194457 * A194459 A194460 A194461

Keyword

nonn

Author

Paul Weisenhorn, Aug 24 2011

Extensions

Edited by Alois P. Heinz, Sep 06 2011

Status

approved