A039302 -id:A039302 - cp's OEIS frontend

A000224 Number of squares mod n.

1, 2, 2, 2, 3, 4, 4, 3, 4, 6, 6, 4, 7, 8, 6, 4, 9, 8, 10, 6, 8, 12, 12, 6, 11, 14, 11, 8, 15, 12, 16, 7, 12, 18, 12, 8, 19, 20, 14, 9, 21, 16, 22, 12, 12, 24, 24, 8, 22, 22, 18, 14, 27, 22, 18, 12, 20, 30, 30, 12, 31, 32, 16, 12, 21, 24, 34, 18, 24, 24, 36, 12

Offset: 1

N. J. A. Sloane

For any n > 2, there are quadratic nonresidues mod n, so a(n) < n. - Charles R Greathouse IV, Oct 28 2022
Conjecture: n^2 == 1 (mod a(n)*(a(n)-1)) if and only if n is an odd prime. - Thomas Ordowski, Apr 13 2025
This conjecture holds at least up to n = 10^8. - Michel Marcus, Apr 13 2025

			The sequence of squares (A000290) modulo 10 reads 0, 1, 4, 9, 6, 5, 6, 9, 4, 1, 0, 1, 4, 9, 6, 5, 6, 9, 4, 1,... and this reduced sequence contains a(10) = 6 different values, {0,1,4,5,6,9}. - _R. J. Mathar_, Oct 10 2014

T. D. Noe, Table of n, a(n) for n = 1..10000
Imanuel Chen and Michael Z. Spivey, Integral Generalized Binomial Coefficients of Multiplicative Functions, Preprint 2015; Summer Research Paper 238, Univ. Puget.
Steven R. Finch and Pascal Sebah, Squares and Cubes Modulo n, arXiv:math/0604465 [math.NT], 2006-2016.
Shuguang Li, On the number of elements with maximal order in the multiplicative group modulo n, Acta Arithm. 86 (2) (1998) 113, see proof of theorem 2.1.
Param Parekh, Paavan Parekh, Sourav Deb, and Manish K. Gupta, On the Classification of Weierstrass Elliptic Curves over Z_n, arXiv:2310.11768 [cs.CR], 2023. See p. 6.
E. J. F. Primrose, The number of quadratic residues mod m, Math. Gaz. v. 61 (1977) n. 415, 60-61.
Walter D. Stangl, Counting Squares in Z_n, Math. Mag. 69 (1996) 285-289.

Cf. A095972, A046530 (cubic residues), A052273 (4th powers), A052274 (5th powers), A052275 (6th powers), A085310 (7th powers), A085311 (8th powers), A085312 (9th powers), A085313 (10th powers), A085314 (11th powers), A228849 (12th powers).

a000224 n = product $ zipWith f (a027748_row n) (a124010_row n) where
   f 2 e = 2 ^ e `div` 6 + 2
   f p e = p ^ (e + 1) `div` (2 * p + 2) + 1
-- Reinhard Zumkeller, Aug 01 2012

A000224 := proc(m)
    {seq( modp(b^2,m),b=0..m-1) };
    nops(%) ;
end proc: # Emeric Deutsch
# 2nd implementation
A000224 := proc(n)
    local a,ifs,f,p,e,c ;
    a := 1 ;
    ifs := ifactors(n)[2] ;
    for f in ifs do
        p := op(1,f) ;
        e := op(2,f) ;
        if p = 2 then
            if type(e,'odd') then
                a := a*(2^(e-1)+5)/3 ;
            else
                a := a*(2^(e-1)+4)/3 ;
            end if;
        else
            if type(e,'odd') then
                c := 2*p+1 ;
            else
                c := p+2 ;
            end if;
            a := a*(p^(e+1)+c)/2/(p+1) ;
        end if;
    end do:
    a ;
end proc: # R. J. Mathar, Oct 10 2014

Length[Union[#]]& /@ Table[Mod[k^2, n], {n, 65}, {k, n}] (* Jean-François Alcover, Aug 30 2011 *)
a[2] = 2; a[n_] := a[n] = Switch[fi = FactorInteger[n], {{, 1}}, (fi[[1, 1]] + 1)/2, {{2, }}, 3/2 + 2^fi[[1, 2]]/6 + (-1)^(fi[[1, 2]]+1)/6, {{, }}, {p, k} = fi[[1]]; 3/4 + (p-1)*(-1)^(k+1)/(4*(p+1)) + p^(k+1)/(2*(p+1)), , Times @@ Table[ a[Power @@ f], {f, fi}]]; Table[a[n], {n, 1, 100}] (* _Jean-François Alcover, Mar 09 2015 *)

a(n) = local(v,i); v = vector(n,i,0); for(i=0, floor(n/2),v[i^2%n+1] = 1); sum(i=1,n,v[i]) \\ Franklin T. Adams-Watters, Nov 05 2006

a(n)=my(f=factor(n));prod(i=1,#f[,1],if(f[i,1]==2,2^f[1,2]\6+2,f[i,1]^(f[i,2]+1)\(2*f[i,1]+2)+1)) \\ Charles R Greathouse IV, Jul 15 2011

from math import prod
from sympy import factorint
def A000224(n): return prod((p**(e+1)//((p+1)*(q:=1+(p==2)))>>1)+q for p, e in factorint(n).items()) # Chai Wah Wu, Oct 07 2024

a(n) = A105612(n) + 1.
Multiplicative with a(p^e) = floor(p^e/6) + 2 if p = 2; floor(p^(e+1)/(2p + 2)) + 1 if p > 2. - David W. Wilson, Aug 01 2001
a(2^n) = A023105(n). a(3^n) = A039300(n). a(5^n) = A039302(n). a(7^n) = A039304(n). - R. J. Mathar, Sep 28 2017
Sum_{k=1..n} a(k) ~ c * n^2/sqrt(log(n)), where c = (17/(32*sqrt(Pi))) * Product_{p prime} (1 - (p^2+2)/(2*(p^2+1)*(p+1))) * (1-1/p)^(-1/2) = 0.37672933209687137604... (Finch and Sebah, 2006). - Amiram Eldar, Oct 18 2022
If p is an odd prime, then a(p) = (p + 1)/2. - Thomas Ordowski, Apr 09 2025

A039306 Number of distinct quadratic residues mod 9^n.

Original entry on oeis.org

1, 4, 31, 274, 2461, 22144, 199291, 1793614, 16142521, 145282684, 1307544151, 11767897354, 105911076181, 953199685624, 8578797170611, 77209174535494, 694882570819441, 6253943137374964, 56285488236374671, 506569394127372034

Offset: 0

David W. Wilson

Number of distinct n-digit suffixes of base 9 squares.
From Danny Rorabaugh, Dec 15 2015: (Start)
Construct the word y_n as follows: y_0 = a; y_{n+1} is three concatenated copies of y_n, except that the middle copy is written with letters not used in y_n. For example:
y_0 = a;
y_1 = aba;
y_2 = abacdcaba;
y_3 = abacdcabaefeghgefeabacdcaba.
a(n) is the number of nonempty subwords of y_n that occur as a subword exactly once.
Let s(n, k) be the number of subwords of y_n that occur exactly 2^k times. One can show that s(n, 0) = a(n) using s(n+1, k+1) = s(n, k) + s(n, k+1), binomial(3^n+1, 2) = Sum_{k=0..n) s(n, k)*2^k, and the formulas for a(n) below.
(End)

			From _Danny Rorabaugh_, Dec 15 2015: (Start)
The squares of the numbers 0..8 are [0, 1, 4, 9, 16, 25, 36, 49, 64]. Modulo 9, these are [0, 1, 4, 0, 7, 7, 0, 4, 1]. Thus there are a(1) = 4 distinct quadratic residues module 9^1 = 9: 0, 1, 4, and 7.
There are a(2) = 31 subwords of y_2 = abacdcaba which occur in y_2 exactly once: [abac, abacd, abacdc, abacdca, abacdcab, abacdcaba, bac, bacd, bacdc, bacdca, bacdcab, bacdcaba, ac, acd, acdc, acdca, acdcab, acdcaba, cd, cdc, cdca, cdcab, cdcaba, d, dc, dca, dcab, dcaba, ca, cab, caba].
(End)

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (10,-9).

Quadratic residues modulo k^n: A023105 (k=2), A039300 (k=3), A039301 (k=4), A039302 (k=5), A039303 (k=6), A039304 (k=7), A039305 (k=8), this sequence (k=9), A000993 (k=10).

I:=[1, 4, 31]; [n le 3 select I[n] else 9*Self(n-1)+Self(n-2)-9*Self(n-3): n in [1..30]]; // Vincenzo Librandi, Apr 22 2012

CoefficientList[Series[(1-6*x)/((1-x)*(1-9*x)),{x,0,30}],x] (* Vincenzo Librandi, Apr 22 2012 *)

a(n) = floor((9^n+3)*3/8).
G.f.: (1-6*x)/((1-x)*(1-9*x)). - _Colin Barker, Mar 14 2012
a(n) = 9*a(n-1) +a(n-2) -9*a(n-3). - Vincenzo Librandi, Apr 22 2012
a(n) = (5+3^(2n+1))/8 = a(n-1) + 3^(2n-1). - Danny Rorabaugh, Dec 15 2015

A368415 Array read by ascending antidiagonals. A(n, k) = floor((n^k + 3)(n/(2n + 2))).

Original entry on oeis.org

1, 1, 1, 2, 2, 1, 2, 4, 3, 1, 3, 7, 11, 6, 1, 3, 11, 26, 31, 11, 1, 4, 16, 53, 103, 92, 22, 1, 4, 22, 93, 261, 410, 274, 43, 1, 5, 29, 151, 556, 1303, 1639, 821, 86, 1, 5, 37, 228, 1051, 3333, 6511, 6554, 2461, 171, 1, 6, 46, 329, 1821, 7354, 19996, 32553, 26215, 7382, 342, 1, 6, 56, 455, 2953

Offset: 1

Thomas Scheuerle, Dec 23 2023

Let p be an odd prime number, then A(p, k) is the number of distinct quadratic residues mod p^k. Let m = p1^k1^*p2^k2*..*pz^kz with p1..pz odd primes, then A(p1, k1)*A(p2, k2)*..*A(pz, kz) is the number of distinct quadratic residues mod m. For 2^t*m is floor((2^t+10)*(1/6))*A(p1, k1)*A(p2, k2)*..*A(pz, kz) the number of distinct quadratic residues mod 2^t*m.

			The array A(n, k) begins:
1,  1,   1,    1,     1,      1,       1,        1,         1,          1
1,  2,   3,    6,    11,     22,      43,       86,       171,        342
2,  4,  11,   31,    92,    274,     821,     2461,      7382,      22144
2,  7,  26,  103,   410,   1639,    6554,    26215,    104858,     419431
3, 11,  53,  261,  1303,   6511,   32553,   162761,    813803,    4069011
3, 16,  93,  556,  3333,  19996,  119973,   719836,   4319013,   25914076
4, 22, 151, 1051,  7354,  51472,  360301,  2522101,  17654704,  123582922
4, 29, 228, 1821, 14564, 116509,  932068,  7456541,  59652324,  477218589
5, 37, 323, 2953, 26573, 239149, 2152337, 19371025, 174339221, 1569052981
5, 46, 455, 4546, 45455, 454546, 4545455, 45454546, 454545455, 4545454546

Cf. A000124, A005578, A039300, A039302, A039304, A172241, A363773.

PARI
```
A(n, k) = (n^(k+1)+n*3)\(2*n+2)
```

A(n, k) = n*A(n, k-1) + A(n, k-2) - n*A(n, k-3), for k > 2 and A(n, 0) = 1.
A(1, k) = 1.
A(2, k) = A005578(k).
A(3, k) = A039300(k).
A(4, k) = A363773(k).
A(5, k) = A039302(k).
A(7, k) = A039304(k).
A(8, k) = A172241(k+1)+1.
A(n, 2) = A000124(n-1), for n > 0.

cp's OEIS Frontend

A000224 Number of squares mod n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Python

Formula

A039306 Number of distinct quadratic residues mod 9^n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

Formula

A368415 Array read by ascending antidiagonals. A(n, k) = floor((n^k + 3)(n/(2n + 2))).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

cp's OEIS Frontend

A000224 Number of squares mod n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Python

Formula

A039306 Number of distinct quadratic residues mod 9^n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

Formula

A368415 Array read by ascending antidiagonals. A(n, k) = floor((n^k + 3)*(n/(2*n + 2))).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

A368415 Array read by ascending antidiagonals. A(n, k) = floor((n^k + 3)(n/(2n + 2))).