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

%I #70 Jul 28 2024 10:07:13

%S 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,

%T 29,10,31,32,11,17,7,9,37,19,13,10,41,9,43,12,10,23,47,16,49,25,18,13,

%U 53,27,11,8,19,29,59,10,61,32,9,64,13,11,67,17,23,8,71,12,73,37,25

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

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

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

%H Rémy Sigrist, <a href="/A349958/b349958.txt">Table of n, a(n) for n = 1..10000</a>

%e In the table below, the k value shown is the minimum k such that n divides binomial(a(n), k).

%e .

%e n a(n) k C(a(n), k)

%e -- ---- - ----------

%e 1 0 0 1

%e 2 2 1 2

%e 3 3 1 3

%e 4 4 1 4

%e 5 5 1 5

%e 6 4 2 6

%e 7 7 1 7

%e 8 8 1 8

%e 9 9 1 9

%e 10 5 2 10

%e 11 11 1 11

%e 12 9 2 36

%e .

%e 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 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.

%e | terms in a(1)..a(12)

%e j | left half of row j of Pascal's triangle | that are equal to j

%e ---+-----------------------------------------+---------------------

%e 0 | (1) | a(1) = 0

%e 1 | 1 |

%e 2 | 1 (2) | a(2) = 2

%e 3 | 1 (3) | a(3) = 3

%e 4 | 1 (4) (6) | a(4), a(6) = 4

%e 5 | 1 (5) (10) | a(5), a(10) = 5

%e 6 | 1 6 15 20 |

%e 7 | 1 (7) 21 35 | a(7) = 7

%e 8 | 1 (8) 28 56 70 | a(8) = 8

%e 9 | 1 (9) (36) 84 126 | a(9), a(12) = 9

%e 10 | 1 10 45 120 210 252 |

%e 11 | 1 (11) 55 165 330 462 | a(11) = 11

%e 12 | 1 12 66 210 496 792 924 |

%t 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 *)

%o (Python)

%o import numpy as np

%o def pascals(n):

%o a = np.ones(1)

%o f = np.ones(2)

%o triangle = [a]

%o for i in range(n):

%o a = np.convolve(a,f)

%o triangle.append(a)

%o return triangle

%o def test(n,tri):

%o for i, element in enumerate(tri):

%o for sub_e in element:

%o if sub_e % n == 0:

%o return i

%o tri = pascals(500)

%o for i in range(1,50):

%o print(test(i,tri),end=',')

%o (Python)

%o from math import comb

%o def A349958(n):

%o for j in range(n+1):

%o for k in range(j+1):

%o if comb(j,k) % n == 0: return j # _Chai Wah Wu_, Dec 10 2021

%o (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

%o (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;);); }

%Y Cf. A007318, A058084, A374959.

%K nonn

%O 1,2

%A _Nathan M Epstein_, Dec 06 2021

%E More terms from _Michel Marcus_, Dec 07 2021