cp's OEIS Frontend

A358242 Consider all invertible residues k mod n. For each such k, find the product of three primes p*q*r = k (mod n) with the smallest max {p, q, r}. Then a(n) is the largest such p over the considered k.

%I A358242 #39 Jul 04 2024 09:21:16
%S A358242 2,3,7,5,11,7,5,7,7,11,7,11,11,11,13,11,13,11,11,13,17,13,13,13,19,17,
%T A358242 17,17,13,17,17,17,19,19,29,17,17,13,23,19,23,19,23,17,29,17,23,23,23,
%U A358242 19,23,19,23,17,31,23,29,19,29,29,29,19,23
%N A358242 Consider all invertible residues k mod n. For each such k, find the product of three primes p*q*r = k (mod n) with the smallest max {p, q, r}. Then a(n) is the largest such p over the considered k.
%C A358242 This is an analog of Linnik's theorem for 3-almost primes. - _Charles R Greathouse IV_, Jun 30 2024
%H A358242 Charles R Greathouse IV, <a href="/A358242/b358242.txt">Table of n, a(n) for n = 1..100000</a>
%H A358242 Ramachandran Balasubramanian, Olivier Ramaré, and Priyamvad Srivastav, <a href="https://doi.org/10.1142/S1793042123500422">Product of three primes in large arithmetic progressions</a>, International Journal of Number Theory, Vol. 19, No. 4 (2023), pp. 843-857; <a href="https://arxiv.org/abs/2208.04031">arXiv preprint</a>, arXiv:2208.04031 [math.NT], 2022.
%H A358242 Barnabás Szabó, <a href="https://londmathsoc.onlinelibrary.wiley.com/doi/full/10.1112/blms.12990">On the existence of products of primes in arithmetic progressions</a>, Bulletin of the London Mathematical Society 56 (3), pp. 1227-1243, 2024.
%F A358242 Balasubramanian, Ramaré, & Srivastav prove that a(n) < n^e for each e > 3/2 and large enough n depending on e.
%F A358242 Szabó improves this to e > 6/5. - _Charles R Greathouse IV_, Jun 30 2024
%e A358242 From _M. F. Hasler_, Jul 02 2024: (Start)
%e A358242 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.
%e A358242 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.
%e A358242 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)
%o A358242 (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))))
%o A358242 a(n)=my(r=2); for(k=1,n-1, if(gcd(k,n)>1, next); r=max(do(Mod(k,n)),r)); r
%o A358242 (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
%Y A358242 Cf. A358240, A038026, A085420, A014612.
%K A358242 nonn
%O A358242 1,1
%A A358242 _Charles R Greathouse IV_, Jan 18 2023
%E A358242 Definition clarified by _Charles R Greathouse IV_ and _M. F. Hasler_, Jul 02 2024