Dale Taylor - cp's OEIS frontend

A273543 Numbers for which 9 is a nontrivial quadratic residue.

16, 18, 20, 24, 27, 28, 32, 35, 36, 40, 44, 45, 48, 52, 54, 55, 56, 60, 63, 64, 65, 68, 70, 72, 76, 77, 80, 81, 84, 85, 88, 90, 91, 92, 95, 96, 99, 100, 104, 105, 108, 110, 112, 115, 116, 117, 119, 120, 124, 126, 128, 130, 132, 133, 135, 136, 140, 143, 144, 145, 148, 152

Offset: 1

Dale Taylor, May 25 2016

nonn

Composite numbers greater than 9 may have additional solutions to x^2=9 (mod n) beyond the trivial 3^2 and (n-3)^2 solutions. Numbers may be squarefree, such as 35, 55, 65, 70.

			For 54, x^2 = 9 (mod 54) has nontrivial solutions 15, 21, 33, 39, and trivial solutions 3, 51. For 57 which is not in the list, x^2 = 9 (mod 57) has only the trivial solutions 3, 54.

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000

Select[Range[10, 230], Length@PowerModList[9, 1/2, #] > 2 &]

is(n)=for(k=4,n\2, if(k^2%n==9, return(1))); 0 \\ Charles R Greathouse IV, Jun 08 2016

is(n)=if(n<16, return(0)); my(v2=valuation(n,2), v3=valuation(n,3), k=n/2^v2/3^v3); if(v2<3 && v3<2, if(v2>1,k>1,!isprimepower(k)), 1) \\ Charles R Greathouse IV, Jun 08 2016

a(n) ~ n. More specifically, a(n) = n + 2n/log n + O(n/log^2 n). - Charles R Greathouse IV, Jun 08 2016

For n > 12, these are numbers not of the form k*p^e where k is in {1, 2, 3, 6}, p > 3 is prime, and e > 0. - Charles R Greathouse IV, Jun 08 2016

A273179 Numbers k for which 2 has exactly four square roots mod k.

Original entry on oeis.org

119, 161, 217, 238, 287, 322, 329, 391, 434, 497, 511, 527, 553, 574, 623, 658, 679, 697, 713, 721, 782, 791, 799, 833, 889, 943, 959, 994, 1022, 1054, 1057, 1081, 1106, 1127, 1169, 1207, 1241, 1246, 1271, 1337, 1343, 1351, 1358, 1393, 1394, 1426, 1442, 1457, 1513

Offset: 1

Dale Taylor, May 17 2016

nonn

Sequence is fairly regular; 437 numbers below 1000 have 4 square roots of 2 mod k; 4796 below 10^4; 47276 below 10^5; and 452172 below 10^6.

			2 has square roots 11, 45, 74, 108 mod 119; e.g., 11^2 == 2 (mod 119).

Subsequence of A057126 (Numbers n such that 2 is a square mod n).

Select[Range[3000], Length@PowerModList[2, 1/2, #] == 4 &]

A262264 Primes that are less than the square of their least positive primitive root.

Original entry on oeis.org

3, 7, 23, 191, 409

Offset: 1

Dale Taylor, Sep 17 2015

Alternatively, primes such that the least positive primitive root is greater than the square root of p.

Next term is greater than 10^9.

			The least primitive root of 23 is 5; 5^2 is greater than 23, so 23 is in the sequence.
The least primitive root of 409 is 21; 21^2 = 441 is greater than 409, so 409 is in the sequence.
41 is not in the sequence because its least primitive root is 6, and 6^2 < 41.

References and links at A001918.

Cf. A001918 (least positive primitive root of n-th prime).

Select[Prime[Range[1000]], PrimitiveRoot[#]^2 > # &]

/* the following assumes that znprimroot() returns the smallest primitive root */
forprime(p=2,10^9,my(g=znprimroot(p));if(lift(g)^2>p,print1(p,", "))); \\ Joerg Arndt, Sep 17 2015

from itertools import islice, count
from sympy import prime, primitive_root
def A262264_gen(): # generator of terms
    return filter(lambda p: p < primitive_root(p)**2,(prime(n) for n in count(1)))
A262264_list = list(islice(A262264_gen(),5)) # Chai Wah Wu, Sep 14 2022

cp's OEIS Frontend

User: Dale Taylor

A273543 Numbers for which 9 is a nontrivial quadratic residue.

Views

Author

Keywords

Comments

Examples

Links

Programs

Mathematica

PARI

PARI

Formula

A273179 Numbers k for which 2 has exactly four square roots mod k.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A262264 Primes that are less than the square of their least positive primitive root.

Views

Author

Keywords

Comments

Examples

References

Crossrefs

Programs

Mathematica

PARI

Python