A276781 a(n) = 1+n-(nearest power of prime <= n); for n > 1, a(n) = minimal b such that the numbers binomial(n,k) for b <= k <= n-b have a common divisor greater than 1.

1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 2, 1, 2, 3, 1, 1, 2, 1, 2, 3, 4, 1, 2, 1, 2, 1, 2, 1, 2, 1, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 2, 1, 2, 3, 4, 1, 2, 1, 2, 3, 4, 1, 2, 3, 4, 5, 6, 1, 2, 1, 2, 3, 1, 2, 3, 1, 2, 3, 4, 1, 2, 1, 2, 3, 4, 5, 6, 1, 2, 1, 2, 1, 2, 3, 4, 5, 6, 1, 2, 3, 4, 5, 6, 7, 8, 1, 2, 3, 4, 1, 2

Offset: 1

Author

N. J. A. Sloane, Sep 29 2016, following a suggestion from Eric Desbiaux

Keywords

• nonn
• look

Comments

The definition in the video has "b < k < n-b" rather than "b <= k <= n-b", but that appears to be a typographical error.

From Antti Karttunen, Jan 21 2020: (Start)

a(n) = 1 if n is a power of prime (term of A000961), otherwise a(n) is one more than the distance to the nearest preceding prime power.

For n > 1, a(n) indicates the maximum region on the row n of Pascal's triangle (A007318) such that binomial terms C(n,a(n)) .. C(n,n-a(n)) all share a common prime factor. Because for all prime powers, p^k, the binomial terms C(p^k,1) .. C(p^k,p^k-1) have p as their prime factor, we have a(A000961(n)) = 1 for all n, while for each successive n that is not a prime power, the region of shared prime factor shrinks one step more towards the center of the triangle. From this follows that this is the ordinal transform of A025528 (equally, of A065515, or of A003418(n) from n >= 1 onward), equivalent to the simple definition given above.

(End)

Examples

			Row 6 of Pascal's triangle is 1,6,15,20,15,6,1 and [15,20,15] have a common divisor of 5. Since 15 = binomial(6,2), a(6)=2.
		

Links

• Antti Karttunen, Table of n, a(n) for n = 1..16384 (terms for n = 2..1685 from R. J. Mathar, terms 1686..10000 from Chai Wah Wu).
• Antti Karttunen, Data supplement: n, a(n) computed for n = 1..65537
• Christophe Soulé, Le triangle de Pascal et ses propriétés, Lecture, Soc. Math. de France, Feb 13 2008; SMF link (in French).

Crossrefs

Cf. A007318, A010055, A276782 (positions of records), A000961 (positions of ones), A024619 (positions of terms > 1).

Cf. A002944, A003418, A025528, A065515, A175851.

Programs

Maple

mygcd:=proc(lis) local i,g,m;
m:=nops(lis); g:=lis[1];
for i from 2 to m do g:=gcd(g,lis[i]); od:
g; end;
f:=proc(n) local b,lis; global mygcd;
for b from floor(n/2) by -1 to 1 do
lis:=[seq(binomial(n,i),i=b..n-b)];
if mygcd(lis)=1 then break; fi; od:
b+1;
end;
[seq(f(n),n=2..120)];

Mathematica

Table[b = 1; While[GCD @@ Map[Binomial[n, #] &, Range[b, n - b]] == 1, b++]; b, {n, 92}] (* Michael De Vlieger, Oct 03 2016 *)

PARI

A276781(n) = if(1==n,1,forstep(k=n,1,-1,if(isprimepower(k),return(1+n-k)))); \\ Antti Karttunen, Jan 21 2020

Python

from sympy import factorint
def A276781(n): return 1+n-next(filter(lambda m:len(factorint(m))<=1, range(n,0,-1))) # Chai Wah Wu, Oct 25 2024

Formula

If A010055(n) == 1, a(n) = 1, otherwise a(n) = 1 + a(n-1). - Antti Karttunen, Jan 21 2020

Extensions

Term a(1) = 1 prepended and alternative simpler definition added to the name by Antti Karttunen, Jan 20 2020