OFFSET
1,1
COMMENTS
This is an analog of Linnik's theorem for 3-almost primes. - Charles R Greathouse IV, Jun 30 2024
LINKS
Charles R Greathouse IV, Table of n, a(n) for n = 1..100000
Ramachandran Balasubramanian, Olivier Ramaré, and Priyamvad Srivastav, Product of three primes in large arithmetic progressions, International Journal of Number Theory, Vol. 19, No. 4 (2023), pp. 843-857; arXiv preprint, arXiv:2208.04031 [math.NT], 2022.
Barnabás Szabó, On the existence of products of primes in arithmetic progressions, Bulletin of the London Mathematical Society 56 (3), pp. 1227-1243, 2024.
FORMULA
Balasubramanian, Ramaré, & Srivastav prove that a(n) < n^e for each e > 3/2 and large enough n depending on e.
Szabó improves this to e > 6/5. - Charles R Greathouse IV, Jun 30 2024
EXAMPLE
From M. F. Hasler, Jul 02 2024: (Start)
For n = 1, there is only one residue class in Z/nZ = {Z}, and it is invertible (since 0 = 1 in this case), and p = q = r = 2 satisfies p*q*r = k (mod n) and gives clearly the smallest possible prime to satisfy the conditions, so a(1) = 2.
For n = 2, there is only one invertible residue class in Z/nZ, namely that of k = 1, and none of p, q, r may equal 2 (= 0 in Z/2Z) to yield p*q*r = 1 (mod n), so p = q = r = 3 is the smallest solution to p*q*r = 1 (mod n), whence a(2) = 3.
For n = 3, the two invertible residues (mod n) are k = 1 and k = 2. For p = q = r = 2, we have p*q*r = 8 = 2 (mod 3), but for the residue k = 1, we need a different solution, which therefore can't have as largest prime p = 2 (=> k = 2) nor p = 3 = 0 (mod 3) nor p = 5 = 2 (mod 3), but p = 7 >= q = r = 2 does work, with 4*7 = 28 = 1 (mod 3), so a(3) = 7. (End)
PROG
(PARI) do(m)=my(mod=m.mod); forprime(p=2, , if(mod%p==0, next); forprime(q=2, p, if(mod%q==0, next); forprimestep(r=2, q, m/p/q, return(p))))
a(n)=my(r=2); for(k=1, n-1, if(gcd(k, n)>1, next); r=max(do(Mod(k, n)), r)); r
(PARI) a(n)=my(N, s=eulerphi(n)); forprime(p=2, , if(n%p==0, next); forprime(q=2, p, if(n%q==0, next); my(pq=p*q%n); forprime(r=2, q, if(n%r==0, next); my(pqr=pq*r%n); if(bittest(N, pqr)==0, N+=1<<pqr; if(s--==0, return(p)))))) \\ Charles R Greathouse IV, Jun 30 2024
CROSSREFS
KEYWORD
nonn
AUTHOR
Charles R Greathouse IV, Jan 18 2023
EXTENSIONS
Definition clarified by Charles R Greathouse IV and M. F. Hasler, Jul 02 2024
STATUS
approved