OFFSET
1,2
COMMENTS
The Green-Tao theorem implies that this sequence is unbounded.
LINKS
Robert Israel, Table of n, a(n) for n = 1..10000
Wikipedia, Green-Tao theorem
FORMULA
a(2*n) = 2 for any n > 0.
a(prime(n)) > A109831(n) for any n > 1.
a(n) <= A020639(n) for n > 1. - Robert Israel, Apr 03 2020
EXAMPLE
The first terms, alongside a corresponding list, are:
n a(n) List
-- ---- ----
1 1 (1)
2 2 (1, 2)
3 3 (1, 2, 3)
4 2 (3, 4)
5 3 (1, 3, 5)
6 2 (5, 6)
7 4 (1, 3, 5, 7)
8 2 (7, 8)
9 3 (7, 8, 9)
10 2 (9, 10)
11 4 (5, 7, 9, 11)
12 2 (11, 12)
13 5 (5, 7, 9, 11, 13)
MAPLE
f:= proc(n) local d, m, p, x, mmax;
if n::even then return 2 fi;
if n mod 3 = 0 then return 3 fi;
mmax:= 1;
for d from 1 to n-1 do
if n <= mmax*d then return mmax fi;
p:= n;
for m from 1 to n/d do
x:= n - d*m;
if igcd(x, p) > 1 then break fi;
p:= p*x;
od;
mmax:= max(mmax, m)
od;
end proc:
f(1):= 1:
map(f, [$1..100]); # Robert Israel, Apr 03 2020
MATHEMATICA
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]]];
a[1] = 1;
Array[a, 100] (* Jean-François Alcover, Oct 25 2020, after Robert Israel *)
PROG
(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)) }
CROSSREFS
KEYWORD
nonn,look
AUTHOR
Rémy Sigrist, Mar 28 2020
STATUS
approved