login
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.
14

%I #73 Oct 25 2024 11:45:40

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

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

%U 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

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

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

%C From _Antti Karttunen_, Jan 21 2020: (Start)

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

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

%C (End)

%H Antti Karttunen, <a href="/A276781/b276781.txt">Table of n, a(n) for n = 1..16384</a> (terms for n = 2..1685 from R. J. Mathar, terms 1686..10000 from Chai Wah Wu).

%H Antti Karttunen, <a href="/A276781/a276781.txt">Data supplement: n, a(n) computed for n = 1..65537</a>

%H Christophe Soulé, <a href="https://vimeo.com/100212123">Le triangle de Pascal et ses propriétés</a>, Lecture, Soc. Math. de France, Feb 13 2008; <a href="https://smf.emath.fr/evenements-smf/soule-christophe-le-triangle-de-pascal-et-ses-proprietes-2008">SMF link</a> (in French).

%F If A010055(n) == 1, a(n) = 1, otherwise a(n) = 1 + a(n-1). - _Antti Karttunen_, Jan 21 2020

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

%p mygcd:=proc(lis) local i,g,m;

%p m:=nops(lis); g:=lis[1];

%p for i from 2 to m do g:=gcd(g,lis[i]); od:

%p g; end;

%p f:=proc(n) local b,lis; global mygcd;

%p for b from floor(n/2) by -1 to 1 do

%p lis:=[seq(binomial(n,i),i=b..n-b)];

%p if mygcd(lis)=1 then break; fi; od:

%p b+1;

%p end;

%p [seq(f(n),n=2..120)];

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

%o (PARI) A276781(n) = if(1==n,1,forstep(k=n,1,-1,if(isprimepower(k),return(1+n-k)))); \\ _Antti Karttunen_, Jan 21 2020

%o (Python)

%o from sympy import factorint

%o def A276781(n): return 1+n-next(filter(lambda m:len(factorint(m))<=1, range(n,0,-1))) # _Chai Wah Wu_, Oct 25 2024

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

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

%K nonn,look

%O 1,6

%A _N. J. A. Sloane_, Sep 29 2016, following a suggestion from _Eric Desbiaux_

%E Term a(1) = 1 prepended and alternative simpler definition added to the name by _Antti Karttunen_, Jan 20 2020