Hans Ruegg - cp's OEIS frontend

A322275 Smallest multiplication factors f, prime or 1, for all b (mod 120120), coprime to 120120 (= 413#), so that bf is a square mod 8, and modulo all primes up to 13.

1, 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, 137, 139, 149, 151, 157, 67, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 83, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 1, 293, 307, 311, 313, 317, 683, 331, 337, 107, 349, 353, 239, 1, 103, 277, 331, 47, 389

Offset: 1

Hans Ruegg, Dec 01 2018

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

			The 44th number coprime to 120120 is 227. a(44) is 83, because 83 is the smallest prime by which we can multiply 227, so that the product (227*83 = 18841) is a square mod 8, and modulo all primes up to 13.

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

Cf. A322269, A322271, A322272, A322273, A322274, A008366.

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(5) returns A322274.

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.

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.

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<

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.

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

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.

Original entry on oeis.org

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<

A214583 Numbers m such that for all k with gcd(m, k) = 1 and m > k^2, m - k^2 is prime.

Original entry on oeis.org

3, 4, 6, 8, 12, 14, 18, 20, 24, 30, 32, 38, 42, 48, 54, 60, 62, 68, 72, 80, 84, 90, 98, 108, 110, 132, 138, 140, 150, 180, 182, 198, 252, 318, 360, 398, 468, 570, 572, 930, 1722

Offset: 1

Hans Ruegg, Jul 21 2012

No further terms < 10^10.
This sequence is based on a remark in a paper distributed over the Internet (see the Leo Moser link) under the heading "Unsolved Problems and Conjectures" (page 84):
"Is 968 the largest number n such that for all k with (n, k) = 1 and n > k^2, n - k^2 is prime? (Erdős)"
The statement by Moser contains an error: 968 does NOT have this property (968-25*25 = 343 = 7*7*7), and the largest such number (1722) is larger than 968.
A224076(n) <= A064272(a(n)+1). - Reinhard Zumkeller, Mar 31 2013

			For example, the number 20 is part of this sequence because 20-1*1 = 19 (prime), and 20-3*3 = 11 (prime). Not considered are 20-2*2 and 20-4*4, because 2 and 4 are not relative primes to 20.

Leo Moser, An Introduction to the Theory of Numbers, The Trillia Group 2004, page 84.

Cf. A065428.
Cf. A057828, A000290, A010051.
Cf. A224075; subsequence of A008864.

a214583 n = a214583_list !! (n-1)
a214583_list = filter (p 3 1) [2..] where
   p i k2 x = x <= k2 || (gcd k2 x > 1 || a010051' (x - k2) == 1) &&
                         p (i + 2) (k2 + i) x
-- Reinhard Zumkeller, Mar 31 2013, Jul 22 2012

Reap[For[p = 2, p < 2000, p = NextPrime[p], n = p+1; q = True; k = 1; While[k*k < n, If[GCD[k, n] == 1, If[! PrimeQ[n - k^2], q = False; Break[]]]; k += 1]; If[q, Sow[n]]]] [[2, 1]] (* Jean-François Alcover, Oct 11 2013, after Joerg Arndt's Pari program *)
gQ[n_]:=AllTrue[n-#^2&/@Select[Range[Floor[Sqrt[n]]],CoprimeQ[ #, n]&], PrimeQ]; Select[Range[2000],gQ] (* The program uses the AllTrue function from Mathematica version 10 *) (* Harvey P. Dale, Dec 02 2018 *)

N=10^10;
default(primelimit,N);
{ forprime (p=2, N,
    n = p + 1;
    q = 1;
    k = 1;
    while ( k*k < n,
        if ( gcd(k,n)==1,
            if ( ! isprime(n-k^2),  q=0; break() );
        );
        k += 1;
    );
    if ( q, print1(n,", ") );
); }
/* Joerg Arndt, Jul 21 2012 */

cp's OEIS Frontend

User: Hans Ruegg

A322275 Smallest multiplication factors f, prime or 1, for all b (mod 120120), coprime to 120120 (= 4*13#), so that b*f is a square mod 8, and modulo all primes up to 13.

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

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

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

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

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

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

A214583 Numbers m such that for all k with gcd(m, k) = 1 and m > k^2, m - k^2 is prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

A322275 Smallest multiplication factors f, prime or 1, for all b (mod 120120), coprime to 120120 (= 413#), so that bf is a square mod 8, and modulo all primes up to 13.

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.

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.