%I
%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 to 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 nth 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 including 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[totalEntries3] = 1; \\ 1 has always 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
