login
A339743
a(n) is the least k > 0 such that 1+k, 1+2*k, ..., 1+n*k are pairwise coprime.
3
1, 1, 2, 4, 6, 6, 6, 30, 30, 60, 60, 210, 210, 210, 210, 210, 210, 210, 2310, 2310, 2310, 2310, 18480, 120120, 120120, 150150, 150150, 150150, 150150, 660660, 1531530, 2492490, 3063060, 3063060, 4594590, 38798760, 38798760, 38798760, 38798760, 38798760, 48498450, 193993800
OFFSET
1,3
COMMENTS
In other words, a(n) is the least k such that A339749(k) >= n.
From David A. Corneth, Jan 01 2021: (Start)
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.
This sequence is weakly increasing. Proof: Let m > n. Then if a(m) < a(n) then by construction a(n) = a(m). Contradiction.
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)
LINKS
Patrick Nicodemus, Arithmetic progressions of coprime natural numbers, Mathematics Stack Exchange, Dec 15 2020.
EXAMPLE
For n = 5:
- A339749(1) = 2 < 5,
- A339749(2) = 3 < 5,
- A339749(3) = 2 < 5,
- A339749(4) = 4 < 5,
- A339749(5) = 2 < 5,
- A339749(6) = 7 >= 5,
- so a(5) = 6.
PROG
(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++)))) }
CROSSREFS
KEYWORD
nonn
AUTHOR
Rémy Sigrist, Dec 15 2020
STATUS
approved