A339743 - OEIS

%I #25 Jan 05 2021 21:42:46

%S 1,1,2,4,6,6,6,30,30,60,60,210,210,210,210,210,210,210,2310,2310,2310,

%T 2310,18480,120120,120120,150150,150150,150150,150150,660660,1531530,

%U 2492490,3063060,3063060,4594590,38798760,38798760,38798760,38798760,38798760,48498450,193993800

%N a(n) is the least k > 0 such that 1+k, 1+2*k, ..., 1+n*k are pairwise coprime.

%C In other words, a(n) is the least k such that A339749(k) >= n.

%C From _David A. Corneth_, Jan 01 2021: (Start)

%C If 2*p < n then p | a(n) for prime p. Proof: Suppose for such p, we don't have p | a(n). Then for some 1 <= k <= n/2 we have p | 1 + a(n)*k and so we have p | 1 + a(n) * (k + p) as well and gcd(1 + a(n) * k, 1 + a(n) * (k + p)) >= p > 1. Contradiction.

%C This sequence is weakly increasing. Proof: Let m > n. Then if a(m) < a(n) then by construction a(n) = a(m). Contradiction.

%C Let f(n) = Product_{i = 1..pi(n/2)} and let c(n) be a candidate for a(n) such that f(n) | c(n) where pi = A000720. If for some 1 + m*c(n) and 1 + (m + t)*c(n) we have gcd(1 + m * c(n), 1 + (m + t)*c) > 1 then n / 2 < t < n and t is prime. (End)

%H David A. Corneth, <a href="/A339743/b339743.txt">Table of n, a(n) for n = 1..200</a>

%H Patrick Nicodemus, <a href="https://math.stackexchange.com/questions/3949328/arithmetic-progressions-of-coprime-natural-numbers">Arithmetic progressions of coprime natural numbers</a>, Mathematics Stack Exchange, Dec 15 2020.

%e For n = 5:

%e - A339749(1) = 2 < 5,

%e - A339749(2) = 3 < 5,

%e - A339749(3) = 2 < 5,

%e - A339749(4) = 4 < 5,

%e - A339749(5) = 2 < 5,

%e - A339749(6) = 7 >= 5,

%e - so a(5) = 6.

%o (PARI) { n = 1; for (k=1, 38798760, p = 1; for (m=1, oo, if (gcd(p, 1+m*k)>1, break, p *= 1+m*k; if (m==n, print1 (k ", "); n++)))) }

%Y Cf. A000720, A339749, A339759.

%K nonn

%O 1,3

%A _Rémy Sigrist_, Dec 15 2020