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.
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, 17, 17, 13, 17, 17, 17, 19, 19, 29, 17, 17, 13, 23, 19, 23, 19, 23, 17, 29, 17, 23, 23, 23, 19, 23, 19, 23, 17, 31, 23, 29, 19, 29, 29, 29, 19, 23
Offset: 1
Keywords
Examples
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)
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.
Programs
-
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<
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
Extensions
Definition clarified by Charles R Greathouse IV and M. F. Hasler, Jul 02 2024
Comments