A322270 - OEIS

%I #23 Sep 11 2022 12:07:07

%S 11,11,1,1011,110100,111,11011100,11111100,1011111100,11110111100,

%T 101111111100,1111101111100,11011111111100,11111111111100,

%U 11010011001011,10011010011001011,11011111111111100,1011111111111111100,11111011111111111100

%N a(n) is a binary Boolean flag indicating whether A322269(n) is a square mod prime(x) for x = 1..n.

%C A322269 contains the largest of the minimal prime numbers P required to multiply any odd number b with, so that the product b*P is a nonzero square modulo 8, and modulo the first n primes.

%C When factoring a number b with 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. And 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 To find 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 Calling p the last of the n primes, an f can be found for each of the possible residues 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.) The largest of all these f is the n-th term in this sequence.

%C 8 was chosen instead of 2, because there is a unique quadratic residue (mod 8), i.e., 1, for all odd numbers.

%C 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 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 This sequence enumerates these codes, corresponding to each term of A322269. The codes are constructed in the following way: The first two bits encode b mod 8 (00=1, 01=3, 10=5, 11=7). The following bits are set if f is a square mod 3, mod 5, etc. (all prime numbers in order, up to prime(n)).

%e A322269(4) is 311. 311 mod 8 = 7, this is encoded as 11. 311 is not a square (mod 3), so the next bit is 0. 311 is a square (mod 5), so the next bit is 1. 311 is not a square (mod 7), so the next and last bit is 0. Together this gives the "code" 01011.

%e (However it is given above as 1011, because numbers starting with zero are not admitted.)

%o (PARI)

%o QresCode(n, nPrimes) = {

%o   code = bitand(n,7)>>1;

%o   for (j=2, nPrimes,

%o     x = Mod(n,prime(j));

%o     if (issquare(x), code += (1<<j));

%o   );

%o   return (code);

%o }

%o a322270(n) = {

%o   totalEntries = 1<<(n+1);

%o   f = vector(totalEntries);

%o   f[totalEntries-3] = 1;  \\ 1 always has the same code: ...111100

%o   counter = 1;

%o   forprime(p=prime(n+1), +oo,

%o     code = QresCode(p, n);

%o     if (f[code+1]==0,

%o       f[code+1]=p;

%o       counter += 1;

%o       if (counter==totalEntries, return(code));

%o     )

%o   )

%o }

%o \\ This program is the same as for A322269, except that "code" is returned instead of "p".

%Y This sequence is based on A322269.

%Y Related sequences are A322271, A322272, A322273, A322274, A322275.

%K nonn,base

%O 1,1

%A _Hans Ruegg_, Dec 01 2018