A322275 -id:A322275 - 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.

7, 23, 83, 311, 1873, 3583, 12289, 33049, 67369, 174241, 552841, 1010881, 3267289, 7921489, 12537719, 30706079, 56988649, 108345169, 328583161, 880051561, 1644946249

Offset: 1

Hans Ruegg, Dec 01 2018

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.
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.
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.
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 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.)
A322270(n) is the code corresponding to a(n).
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).

			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:
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.)
The largest f in this set is 83 (associated with b=83 and b=107). Therefore a(3) = 83.

Binary codes as described above are given in A322270.

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).

QresCode(n, nPrimes) = {
  code = bitand(n,7)>>1;
  for (j=2, nPrimes,
    x = Mod(n,prime(j));
    if (issquare(x), code += (1<

A322271 Smallest multiplication factors f, prime or 1, for all b (mod 24), coprime to 24, so that b*f is a nonzero square mod 8 and mod 3.

Original entry on oeis.org

1, 5, 7, 11, 13, 17, 19, 23

Offset: 1

Hans Ruegg, Dec 01 2018

See sequence A322269 for further explanations. This sequence is related to A322269(2).
The sequence is periodic, repeating itself after phi(24) terms. Its largest term is 23, which is A322269(2). In order to satisfy the conditions, both f and b must be coprime to 24.
The b(n) corresponding to each a(n) is A007310(n).
In this case, the sequence is trivial, since each term is being multiplied by itself. The next related sequence, A322272, corresponding to A322269(3), already has several nontrivial terms.

			The 4th number coprime to 24 is 11. a(4) is 11, because 11 is the smallest prime by which we can multiply 11, so that the product (11*11 = 121) is a square mod 8 and mod 3.

Cf. A322269, A322272, A322273, A322274, A322275, A007310.

QresCode(n, nPrimes) = {
  code = bitand(n,7)>>1;
  for (j=2, nPrimes,
    x = Mod(n,prime(j));
    if (issquare(x), code += (1<A322271, sequence(3) returns A322272, ... sequence(6) returns A322275.

A322273 Smallest multiplication factors f, prime or 1, for all b (mod 840), coprime to 840 (= 47#), so that bf is a nonzero square mod 8, mod 3, mod 5, and mod 7.

Original entry on oeis.org

1, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 43, 71, 73, 79, 83, 41, 73, 101, 103, 107, 109, 113, 1, 127, 59, 113, 19, 47, 29, 79, 13, 43, 47, 1, 173, 11, 61, 283, 71, 193, 53, 31, 41, 211, 29, 103, 83, 61, 113, 71, 241, 127, 59, 37, 17, 23

Offset: 1

Hans Ruegg, Dec 01 2018

See sequence A322269 for further explanations. This sequence is related to A322269(4).
The sequence is periodic, repeating itself after phi(840) = 192 terms. Its largest term is 311, which is A322269(4). In order to satisfy the conditions, both f and b must be coprime to 840. Otherwise, the product would be zero mod a prime <= 7.
The b(n) corresponding to each a(n) is A008364(n).
The first 15 terms are trivial: f=b, and then the product b*f naturally is a square modulo everything.

			The 16th number coprime to 840 is 67. a(16) is 43, because 43 is the smallest prime by which we can multiply 67, so that the product (67*43 = 2881) is a square mod 8, mod 2, mod 3, mod 5, and mod 7.

Hans Ruegg, Table of n, a(n) for n = 1..192

Cf. A322269, A322271, A322272, A322274, A322275, A008364.

QresCode(n, nPrimes) = {
  code = bitand(n,7)>>1;
  for (j=2, nPrimes,
    x = Mod(n,prime(j));
    if (issquare(x), code += (1<A322271, sequence(3) returns A322272, ... sequence(6) returns A322275.

A322274 Smallest multiplication factors f, prime or 1, for all b (mod 9240), coprime to 9240 (= 411#), so that bf is a square mod 8, mod 3, mod 5, mod 7, and mod 11.

Original entry on oeis.org

1, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 113, 19, 29, 79, 157, 67, 167, 1, 173, 179, 181, 71, 193, 197, 31, 211, 389, 103, 83, 181, 233, 239, 241, 463, 59, 257, 263, 269, 271, 277, 281, 283, 1, 173, 131, 283, 311, 97, 53, 443, 331, 193, 107, 61, 257, 239, 1, 103, 277

Offset: 1

Hans Ruegg, Dec 01 2018

See sequence A322269 for further explanations. This sequence is related to A322269(5).
The sequence is periodic, repeating itself after phi(9240) terms. Its largest term is 1873, which is A322269(5). In order to satisfy the conditions, both f and b must be coprime to 9240. Otherwise, the product would be zero mod a prime <= 11.
The b(n) corresponding to each a(n) is A008365(n).
The first 28 entries are trivial: f=b, and then the product b*f naturally is a square modulo everything.

			The 30th number coprime to 9240 is 139. a(30) is 19, because 19 is the smallest prime by which we can multiply 139, so that the product (139*19 = 2641) is a square mod 8, and modulo all primes up to 11.

Hans Ruegg, Table of n, a(n) for n = 1..1920

Cf. A322269, A322271, A322272, A322273, A322275, A008365.

QresCode(n, nPrimes) = {
  code = bitand(n,7)>>1;
  for (j=2, nPrimes,
    x = Mod(n,prime(j));
    if (issquare(x), code += (1<A322271, sequence(3) returns A322272, ... sequence(6) returns A322275.

A322272 Smallest multiplication factors f, prime or 1, for all a (mod 120), coprime to 120, so that b*f is a nonzero square mod 8, mod 3, and mod 5.

Original entry on oeis.org

1, 7, 11, 13, 17, 19, 23, 29, 31, 13, 41, 43, 23, 1, 53, 11, 61, 43, 71, 73, 53, 31, 83, 41, 19, 73, 29, 7, 83, 61, 17, 71

Offset: 1

Hans Ruegg, Dec 01 2018

See sequence A322269 for further explanations. This sequence is related to A322269(3).
The sequence is periodic, repeating itself after phi(120) terms. Its largest term is 83, which is A322269(3). In order to satisfy the conditions, both f and b must be coprime to 120. Otherwise, the product would be zero mod a prime <= 5.
The b(n) corresponding to each a(n) is A007775(n).

			The 10th number coprime to 120 is 37. a(10) is 13, because 13 is the smallest prime by which we can multiply 37, so that the product (37*13 = 481) is a square mod 8, mod 3 and mod 5.

Cf. A322269, A322271, A322273, A322274, A322275, A007775.

QresCode(n, nPrimes) = {
  code = bitand(n,7)>>1;
  for (j=2, nPrimes,
    x = Mod(n,prime(j));
    if (issquare(x), code += (1<

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

Original entry on oeis.org

11, 11, 1, 1011, 110100, 111, 11011100, 11111100, 1011111100, 11110111100, 101111111100, 1111101111100, 11011111111100, 11111111111100, 11010011001011, 10011010011001011, 11011111111111100, 1011111111111111100, 11111011111111111100

Offset: 1

Hans Ruegg, Dec 01 2018

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 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.)
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)).

			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.)

This sequence is based on A322269.

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

QresCode(n, nPrimes) = {
  code = bitand(n,7)>>1;
  for (j=2, nPrimes,
    x = Mod(n,prime(j));
    if (issquare(x), code += (1<A322269, except that "code" is returned instead of "p".

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.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

A322271 Smallest multiplication factors f, prime or 1, for all b (mod 24), coprime to 24, so that b*f is a nonzero square mod 8 and mod 3.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

A322273 Smallest multiplication factors f, prime or 1, for all b (mod 840), coprime to 840 (= 4*7#), so that b*f is a nonzero square mod 8, mod 3, mod 5, and mod 7.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A322274 Smallest multiplication factors f, prime or 1, for all b (mod 9240), coprime to 9240 (= 4*11#), so that b*f is a square mod 8, mod 3, mod 5, mod 7, and mod 11.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A322272 Smallest multiplication factors f, prime or 1, for all a (mod 120), coprime to 120, so that b*f is a nonzero square mod 8, mod 3, and mod 5.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

A322273 Smallest multiplication factors f, prime or 1, for all b (mod 840), coprime to 840 (= 47#), so that bf is a nonzero square mod 8, mod 3, mod 5, and mod 7.

A322274 Smallest multiplication factors f, prime or 1, for all b (mod 9240), coprime to 9240 (= 411#), so that bf is a square mod 8, mod 3, mod 5, mod 7, and mod 11.