cp's OEIS Frontend

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

%I A383470 #13 Apr 28 2025 11:32:12
%S A383470 1,2,4,12,16,24,48,60,72,112,144,168,192,224,240,360,528,576,672,720,
%T A383470 792,1188,1344,1456,2016,2184,2376,2448,2880,3360,4032,4560,4752,5940,
%U A383470 6336,6840,7392,8448,8832,10080,11880,13200,13248,15456,16632,17472,19008,19800
%N A383470 Numbers k which are divisible by the number of squares mod k.
%C A383470 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).
%C A383470 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.
%e A383470 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.
%t A383470 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 *)
%o A383470 (Python)
%o A383470 # Without benefit of sympy:
%o A383470 from math import prod
%o A383470 def factor(n):
%o A383470   result = []
%o A383470   for d in two_and_odds():
%o A383470     if n == 1:
%o A383470       return result
%o A383470     if d > n // d:
%o A383470       return result + [(n, 1)]
%o A383470     e = 0
%o A383470     while n % d == 0:
%o A383470       e += 1
%o A383470       n = n // d
%o A383470     if e > 0:
%o A383470       result += [(d, e)]
%o A383470 def two_and_odds():
%o A383470   yield 2
%o A383470   k = 3
%o A383470   while True:
%o A383470     yield k
%o A383470     k += 2
%o A383470 # From Chai Wah Wu at A000224
%o A383470 def s(n): return prod((p**(e+1)//((p+1)*(q:=1+(p==2)))>>1)+q for p, e in factor(n))
%o A383470 def main(n):
%o A383470     count = 1
%o A383470     for i in range(1,n):
%o A383470         if i%s(i) == 0:
%o A383470             print(f"{count} {i}")
%o A383470             count += 1
%Y A383470 Cf. A000224.
%K A383470 nonn
%O A383470 1,2
%A A383470 _Allan C. Wechsler_, Apr 27 2025