VOOZH about

URL: https://oeis.org/A383470

⇱ A383470 - OEIS

login
A383470
Numbers k which are divisible by the number of squares mod k.
0
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,2
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.
EXAMPLE
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.
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 *)
PROG
(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
CROSSREFS
Cf. A000224.
Sequence in context: A171943 A225748 A358231 * A114064 A381731 A071118
KEYWORD
nonn
AUTHOR
Allan C. Wechsler, Apr 27 2025
STATUS
approved