cp's OEIS Frontend

A333600 a(n) is the greatest possible length of a list of pairwise coprime distinct positive integers in arithmetic progression with greatest element n.

%I A333600 #18 Oct 26 2020 11:29:02
%S A333600 1,2,3,2,3,2,4,2,3,2,4,2,5,2,3,2,5,2,5,2,3,2,5,2,5,2,3,2,5,2,6,2,3,2,
%T A333600 5,2,7,2,3,2,6,2,8,2,3,2,7,2,7,2,3,2,8,2,5,2,3,2,9,2,6,2,3,2,5,2,7,2,
%U A333600 3,2,6,2,8,2,3,2,7,2,9,2,3,2,8,2,5,2,3
%N A333600 a(n) is the greatest possible length of a list of pairwise coprime distinct positive integers in arithmetic progression with greatest element n.
%C A333600 The Green-Tao theorem implies that this sequence is unbounded.
%H A333600 Robert Israel, <a href="/A333600/b333600.txt">Table of n, a(n) for n = 1..10000</a>
%H A333600 Wikipedia, <a href="https://en.wikipedia.org/wiki/Green%E2%80%93Tao_theorem">Green-Tao theorem</a>
%F A333600 a(2*n) = 2 for any n > 0.
%F A333600 a(prime(n)) > A109831(n) for any n > 1.
%F A333600 a(n) <= A020639(n) for n > 1. - _Robert Israel_, Apr 03 2020
%e A333600 The first terms, alongside a corresponding list, are:
%e A333600   n   a(n)  List
%e A333600   --  ----  ----
%e A333600    1     1  (1)
%e A333600    2     2  (1, 2)
%e A333600    3     3  (1, 2, 3)
%e A333600    4     2  (3, 4)
%e A333600    5     3  (1, 3, 5)
%e A333600    6     2  (5, 6)
%e A333600    7     4  (1, 3, 5, 7)
%e A333600    8     2  (7, 8)
%e A333600    9     3  (7, 8, 9)
%e A333600   10     2  (9, 10)
%e A333600   11     4  (5, 7, 9, 11)
%e A333600   12     2  (11, 12)
%e A333600   13     5  (5, 7, 9, 11, 13)
%p A333600 f:= proc(n) local d, m, p, x, mmax;
%p A333600   if n::even then return 2 fi;
%p A333600   if n mod 3 = 0 then return 3 fi;
%p A333600   mmax:= 1;
%p A333600   for d from 1 to n-1 do
%p A333600     if n <= mmax*d then return mmax fi;
%p A333600     p:= n;
%p A333600     for m from 1 to n/d do
%p A333600       x:= n - d*m;
%p A333600       if igcd(x,p) > 1 then break fi;
%p A333600       p:= p*x;
%p A333600     od;
%p A333600     mmax:= max(mmax, m)
%p A333600   od;
%p A333600 end proc:
%p A333600 f(1):= 1:
%p A333600 map(f, [$1..100]); # _Robert Israel_, Apr 03 2020
%t A333600 a[n_] := Module[{d, m, p, x, mmax}, If[EvenQ[n], Return[2]]; If[Mod[n, 3] == 0, Return[3]]; mmax = 1; For[d = 1, d <= n-1, d++, If[n <= mmax d, Return[mmax]]; p = n; For[m = 1, m <= n/d, m++, x = n - d m; If[GCD[x, p] > 1, Break[]]; p = p x]; mmax = Max[mmax, m]]];
%t A333600 a[1] = 1;
%t A333600 Array[a, 100] (* _Jean-François Alcover_, Oct 25 2020, after _Robert Israel_ *)
%o A333600 (PARI) a(n) = { if (n%2==0, return (2), my (v=1); for (s=1, n-1, if (v>=ceil(n/s), break); my (p=1, w=0); forstep (k=n, 1, -s, if (gcd(p,k)==1, p*=k; w++, break)); v=max(v,w)); return (v)) }
%Y A333600 Cf. A020639, A109831.
%K A333600 nonn,look
%O A333600 1,2
%A A333600 _Rémy Sigrist_, Mar 28 2020