A000224 -id:A000224 - cp's OEIS frontend

A337868 Number of distinct residues of x^r (mod n), x=0..n-1, r=2, ..., n.

0, 2, 3, 3, 5, 6, 7, 6, 7, 10, 11, 9, 13, 14, 15, 11, 17, 14, 19, 15, 21, 22, 23, 17, 21, 26, 20, 21, 29, 30, 31, 21, 33, 34, 35, 21, 37, 38, 39, 28, 41, 42, 43, 33, 35, 46, 47, 32, 43, 42, 51, 39, 53, 40, 55, 39, 57, 58, 59, 45, 61, 62, 49, 41, 65, 66, 67, 51, 69, 70, 71

Offset: 1

José María Grau Ribas, Sep 27 2020

nonn

Sequence is submultiplicative: a(m*n) <= a(m) * a(n) for m,n coprime. - Charles R Greathouse IV, Dec 19 2022

For n > 1, this is the number of distinct residues of x^r (mod n) with r > 1, that is, the restriction r <= n is not needed. - Charles R Greathouse IV, Dec 22 2022

For number of k-th power residues mod n, see A000224 (k=2), A052273 (k=4), A052274 (k=5), A052275 (k=6), A085310 (k=7), A085311 (k=8), A085312 (k=9), A085313 (k=10), A085314 (k=12), A228849 (k=13).

T[n_] := Union@Mod[Flatten@Table[Range[n]^i, {i, 2, n}], n];
Table[Length[T@n], {n, 1, 144}]

a(n)=if(n==1, return(0)); my(s); for(k=0,n-1, my(x=Mod(k,n)); forprime(p=2,n, if(ispower(x,p), s++; break))); s\\ Charles R Greathouse IV, Dec 22 2022

For n > 1, a(n) >= A000010(n) + 1 as all invertible elements of Z/nZ are powers, as is 0. (Conjecture: equality holds exactly for A000430, the primes and squares of primes.) - Charles R Greathouse IV, Dec 23 2022

A226757 a(n) = number of distinct quadruples of squares modulo n.

Original entry on oeis.org

1, 16, 16, 16, 81, 256, 256, 81, 256, 1296, 1296, 256, 2401, 4096, 1296, 256, 6561, 4096, 10000, 1296, 4096, 20736, 20736, 1296, 14641, 38416, 14641, 4096, 50625, 20736, 65536, 2401, 20736, 104976, 20736, 4096, 130321, 160000, 38416, 6561, 194481, 65536

Offset: 1

José María Grau Ribas, Jun 16 2013

Cf. A000224, A068197.

a(n) = A000224(n)^4. - Andrew Howroyd, Aug 06 2018

Name corrected by Andrew Howroyd, Aug 06 2018

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

Original entry on oeis.org

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

Allan C. Wechsler, Apr 27 2025

nonn

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.

			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.

Cf. A000224.

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 *)

# 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

cp's OEIS Frontend

A337868 Number of distinct residues of x^r (mod n), x=0..n-1, r=2, ..., n.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

PARI

Formula

A226757 a(n) = number of distinct quadruples of squares modulo n.

Views

Author

Keywords

Crossrefs

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Python