A383470 Numbers k which are divisible by the number of squares mod k.

1, 2, 4, 12, 16, 24, 48, 60, 72, 112, 144, 168, 192, 224, 240, 360, 528, 576, 672, 720, 792, 1188, 1344, 1456, 2016, 2184, 2376, 2448, 2880, 3360, 4032, 4560, 4752, 5940, 6336, 6840, 7392, 8448, 8832, 10080, 11880, 13200, 13248, 15456, 16632, 17472, 19008, 19800

Offset: 1

Author

Allan C. Wechsler, Apr 27 2025

Keywords

• nonn

Comments

The number of quadratic residues modulo n is A000224; this is the list of numbers k for which k is an integer multiple of A000224(k).

Finding numbers of this sort is fairly easy, because A000224(k) is multiplicative, but enumerating them exhaustively is more of a challenge. Other larger examples are 2004480, 71513280 (found by Robert Israel, the smallest example divisible by 89), and 1517336658746346757423104.

Examples

			224 has exactly 28 quadratic residues, that is, A000224(224) = 28. And 224 is 8 * 28, so 224 is an element of this sequence. But 225 has 44 quadratic residues, and 225 is not a multiple of 44, so 225 is not an element of this sequence.
		

Crossrefs

Cf. A000224.

Programs

Mathematica

f[p_, e_] := Floor[p^(e + 1)/(2*p + 2)] + 1; f[2, e_] := Floor[2^e/6] + 2; q[1] = True; q[n_] := Divisible[n, Times @@ f @@@ FactorInteger[n]]; Select[Range[20000], q] (* Amiram Eldar, Apr 27 2025 *)

Python

# Without benefit of sympy:
from math import prod
def factor(n):
  result = []
  for d in two_and_odds():
    if n == 1:
      return result
    if d > n // d:
      return result + [(n, 1)]
    e = 0
    while n % d == 0:
      e += 1
      n = n // d
    if e > 0:
      result += [(d, e)]
def two_and_odds():
  yield 2
  k = 3
  while True:
    yield k
    k += 2
# From Chai Wah Wu at A000224
def s(n): return prod((p**(e+1)//((p+1)*(q:=1+(p==2)))>>1)+q for p, e in factor(n))
def main(n):
    count = 1
    for i in range(1,n):
        if i%s(i) == 0:
            print(f"{count} {i}")
            count += 1