The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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 n-th 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 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<

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified July 31 22:37 EDT 2021. Contains 346377 sequences. (Running on oeis4.)