A349958 a(n) is the index of the first row in Pascal's triangle that contains a multiple of n.

0, 2, 3, 4, 5, 4, 7, 8, 9, 5, 11, 9, 13, 8, 6, 16, 17, 9, 19, 6, 7, 11, 23, 10, 25, 13, 27, 8, 29, 10, 31, 32, 11, 17, 7, 9, 37, 19, 13, 10, 41, 9, 43, 12, 10, 23, 47, 16, 49, 25, 18, 13, 53, 27, 11, 8, 19, 29, 59, 10, 61, 32, 9, 64, 13, 11, 67, 17, 23, 8, 71, 12, 73, 37, 25

Offset: 1

Author

Nathan M Epstein, Dec 06 2021

Keywords

• nonn

Comments

a(n) is the minimum j such that binomial(j,k) is divisible by n for some k in 0..j.

a(n) is at most equal to A058084(n), the least m such that binomial(m,k) = n for some k.

Examples

			In the table below, the k value shown is the minimum k such that n divides binomial(a(n), k).
.
   n  a(n)  k  C(a(n), k)
  --  ----  -  ----------
   1    0   0       1
   2    2   1       2
   3    3   1       3
   4    4   1       4
   5    5   1       5
   6    4   2       6
   7    7   1       7
   8    8   1       8
   9    9   1       9
  10    5   2      10
  11   11   1      11
  12    9   2      36
.
The table below shows the left half (and middle column) of rows j = 0..12 of Pascal's triangle; each number in parentheses there is the first term encountered in Pascal's triangle (read by rows from left to right) that is a multiple of some number n in 1..12, and the corresponding term of {a(n)} whose value is j appears in the column at the right.
E.g., the first multiple of 12 encountered in Pascal's triangle is binomial(9,2) = 36; it appears in row 9, so a(12) = 9, and the column at the right includes a(12) in row 9.
                                               | terms in a(1)..a(12)
   j | left half of row j of Pascal's triangle | that are equal to j
  ---+-----------------------------------------+---------------------
   0 |                                    (1)  |        a(1)  =  0
   1 |                                  1      |
   2 |                               1    (2)  |        a(2)  =  2
   3 |                            1    (3)     |        a(3)  =  3
   4 |                         1    (4)   (6)  |  a(4), a(6)  =  4
   5 |                      1    (5)  (10)     |  a(5), a(10) =  5
   6 |                   1     6    15    20   |
   7 |                1    (7)   21    35      |        a(7)  =  7
   8 |             1    (8)   28    56    70   |        a(8)  =  8
   9 |          1    (9)  (36)   84   126      |  a(9), a(12) =  9
  10 |       1    10    45   120   210   252   |
  11 |    1   (11)   55   165   330   462      |        a(11) = 11
  12 | 1    12    66   210   496   792   924   |
		

Links

• Rémy Sigrist, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A007318, A058084, A374959.

Programs

Mathematica

a[n_] := Module[{k = 0}, While[!AnyTrue[Binomial[k, Range[0, Floor[k/2]]], Divisible[#, n] &], k++]; k]; Array[a, 75] (* Amiram Eldar, Dec 07 2021 *)

PARI

a(n) = my(k=0); while (!#select(x->(x==1), apply(denominator, vector((k+2)\2, i, binomial(k, i-1))/n)), k++); k; \\ Michel Marcus, Dec 07 2021

PARI

a(n) = { my (r = [1 % n]); for (i = 0, oo, if (vecmin(r)==0, return (i), r = (concat(0, r) + concat(r, 0)) % n;);); }

Python

import numpy as np
def pascals(n):
  a = np.ones(1)
  f = np.ones(2)
  triangle = [a]
  for i in range(n):
    a = np.convolve(a,f)
    triangle.append(a)
  return triangle
def test(n,tri):
  for i, element in enumerate(tri):
    for sub_e in element:
      if sub_e % n == 0:
        return i
tri = pascals(500)
for i in range(1,50):
  print(test(i,tri),end=',')

Python

from math import comb
def A349958(n):
    for j in range(n+1):
        for k in range(j+1):
            if comb(j,k) % n == 0: return j # Chai Wah Wu, Dec 10 2021

Extensions

More terms from Michel Marcus, Dec 07 2021