cp's OEIS Frontend

A322269 a(n) is the largest minimal prime P such that, for any odd number b, the product P*b is a nonzero square modulo 8 and modulo each of the first n primes.

%I A322269 #29 Sep 11 2022 12:13:40
%S A322269 7,23,83,311,1873,3583,12289,33049,67369,174241,552841,1010881,
%T A322269 3267289,7921489,12537719,30706079,56988649,108345169,328583161,
%U A322269 880051561,1644946249
%N A322269 a(n) is the largest minimal prime P such that, for any odd number b, the product P*b is a nonzero square modulo 8 and modulo each of the first n primes.
%C A322269 When factoring a number b using the quadratic sieve, it can be practical to multiply b by a certain factor f so that the product f*b is a square modulo several small primes. It is desirable that f be prime, because the prime factors of f cannot be used in the factor base of the quadratic sieve.
%C A322269 To find such an f for a given b and the first n primes, it must be checked whether b is a square or not, modulo each of these primes. Then f is the smallest prime (or 1) which satisfies the same conditions, modulo each of these primes.
%C A322269 Letting p=prime(n), an f can be found for each of the possible values of b (mod p#, the primorial of p), coprime to p#. (Actually we are using a period of 4*(p#), because instead of mod 2 we check for mod 8.) a(n) is the largest of all these values of f.
%C A322269 8 was chosen instead of 2, because there is a unique quadratic residue (mod 8), i.e., 1, for all odd numbers.
%C A322269 Sequences A322271 to A322275 are separate listings for the sequences of all f, corresponding to n=2 to 6, which illustrate the idea further.
%C A322269 For finding the full sequences of all f, instead of checking all b mod 4*(p#), it is more practical to check all prime numbers (and also 1) in order, whether they are suitable as an f or not. Each prime receives a "code" of Boolean flags which indicate whether it is a square or not, modulo each of the first n primes. If it is the first prime with this specific "code", then every value of b mod 4*(p#) which has the same "code" is assigned this prime as its f. This process is repeated until all possible "codes" have an f assigned. (The flag for mod 8, instead of only signaling "is (not) a square", has four different values: 1, 3, 5, and 7.)
%C A322269 A322270(n) is the code corresponding to a(n).
%C A322269 In order to satisfy the conditions, both f and b must be coprime to p#, i.e., f must either be 1 or greater than prime(n).
%e A322269 For n=3, we want the product to be a square mod 8, mod 2, mod 3 and mod 5. The corresponding products b*f are, for all b < 120 and coprime to 120:
%e A322269 1*1, 7*7, 11*11, 13*13, 17*17, 19*19, 23*23, 29*29, 31*31, 37*13, 41*41, 43*43, 47*23, 49*1, 53*53, 59*11, 61*61, 67*43, 71*71, 73*73, 77*53, 79*31, 83*83, 89*41, 91*19, 97*73, 101*29, 103*7, 107*83, 109*61, 113*17, 119*71. (See A322272.)
%e A322269 The largest f in this set is 83 (associated with b=83 and b=107). Therefore a(3) = 83.
%o A322269 (PARI)
%o A322269 QresCode(n, nPrimes) = {
%o A322269   code = bitand(n,7)>>1;
%o A322269   for (j=2, nPrimes,
%o A322269     x = Mod(n,prime(j));
%o A322269     if (issquare(x), code += (1<<j));
%o A322269   );
%o A322269   return (code);
%o A322269 }
%o A322269 a322269(n) = {
%o A322269   totalEntries = 1<<(n+1);
%o A322269   f = vector(totalEntries);
%o A322269   f[totalEntries-3] = 1;  \\ 1 always has the same code: ...111100
%o A322269   counter = 1;
%o A322269   forprime(p=prime(n+1), +oo,
%o A322269     code = QresCode(p, n);
%o A322269     if (f[code+1]==0,
%o A322269       f[code+1]=p;
%o A322269       counter += 1;
%o A322269       if (counter==totalEntries, return(p));
%o A322269     )
%o A322269   )
%o A322269 }
%Y A322269 Binary codes as described above are given in A322270.
%Y A322269 Sequences for all f associated with a specific n are given in A322271 (n=2), A322272 (n=3), A322273 (n=4), A322274 (n=5), and A322275 (n=6).
%K A322269 nonn,more
%O A322269 1,1
%A A322269 _Hans Ruegg_, Dec 01 2018