

A322270


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


2



11, 11, 1, 1011, 110100, 111, 11011100, 11111100, 1011111100, 11110111100, 101111111100, 1111101111100, 11011111111100, 11111111111100, 11010011001011, 10011010011001011, 11011111111111100, 1011111111111111100, 11111011111111111100
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,1


COMMENTS

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.
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.
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.
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.
8 was chosen instead of 2, because there is a unique quadratic residue (mod 8), i.e., 1, for all odd numbers.
Sequences A322271 to A322275 are separate listings for the sequences of all f, corresponding to n=2 to 6, which illustrate the idea further.
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.)
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)).


LINKS

Table of n, a(n) for n=1..19.


EXAMPLE

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.
(However it is given above as 1011, because numbers starting with zero are not admitted.)


PROG

(PARI)
QresCode(n, nPrimes) = {
code = bitand(n, 7)>>1;
for (j=2, nPrimes,
x = Mod(n, prime(j));
if (issquare(x), code += (1<<j));
);
return (code);
}
a322270(n) = {
totalEntries = 1<<(n+1);
f = vector(totalEntries);
f[totalEntries3] = 1; \\ 1 has always the same code: ...111100
counter = 1;
forprime(p=prime(n+1), +oo,
code = QresCode(p, n);
if (f[code+1]==0,
f[code+1]=p;
counter += 1;
if (counter==totalEntries, return(code));
)
)
}
\\ This program is the same as for A322269, except that "code" is returned instead of "p".


CROSSREFS

This sequence is based on A322269.
Related sequences are A322271, A322272, A322273, A322274, A322275.
Sequence in context: A287979 A268915 A332731 * A260589 A291367 A061186
Adjacent sequences: A322267 A322268 A322269 * A322271 A322272 A322273


KEYWORD

nonn,base


AUTHOR

Hans Ruegg, Dec 01 2018


STATUS

approved



