OFFSET
1,2
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.
LINKS
Rémy Sigrist, Table of n, a(n) for n = 1..10000
EXAMPLE
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 |
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 *)
PROG
(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
(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; ); ); }
CROSSREFS
KEYWORD
nonn
AUTHOR
Nathan M Epstein, Dec 06 2021
EXTENSIONS
More terms from Michel Marcus, Dec 07 2021
STATUS
approved