A062803 -id:A062803 - cp's OEIS frontend

A062570 a(n) = phi(2*n).

1, 2, 2, 4, 4, 4, 6, 8, 6, 8, 10, 8, 12, 12, 8, 16, 16, 12, 18, 16, 12, 20, 22, 16, 20, 24, 18, 24, 28, 16, 30, 32, 20, 32, 24, 24, 36, 36, 24, 32, 40, 24, 42, 40, 24, 44, 46, 32, 42, 40, 32, 48, 52, 36, 40, 48, 36, 56, 58, 32, 60, 60, 36, 64, 48, 40, 66, 64, 44, 48, 70, 48, 72

Offset: 1

Jason Earls, Jul 03 2001

a(n) is also the number of non-congruent solutions to x^2 - y^2 == 1 (mod n). - Yuval Dekel (dekelyuval(AT)hotmail.com), Sep 21 2003
a(n) is the size of a square companion matrix of the minimal cyclotomic polynomial of (-1)^(1/n). - Eric Desbiaux, Dec 08 2015
a(n) is the degree of the (2n)-th cyclotomic field Q(zeta_(2n)). Note that Q(zeta_n) = Q(zeta_(2n)) for odd n. - Jianing Song, May 17 2021
The number of integers k from 1 to n such that gcd(n,k) is a power of 2. - Amiram Eldar, May 18 2025

T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, p. 28.

Antti Karttunen, Table of n, a(n) for n = 1..65537 (first 1000 terms from Vincenzo Librandi)
N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021 (Includes this sequence).
László Tóth, Counting solutions of quadratic congruences in several variables revisited, arXiv preprint arXiv:1404.4214 [math.NT], 2014.
László Tóth, Counting Solutions of Quadratic Congruences in Several Variables Revisited, J. Int. Seq. 17 (2014), Article 14.11.6.
Wikipedia, Ramanujan's sum.

Cf. A000010, A000034, A008683, A037225, A060968, A062803, A185199, A209229.
Column 1 of A129559, column 2 of A372673.
Row 1 of A379010.
Row sums of A129558 and of A129564.

[phi(2*n)$n=1..80]; # Muniru A Asiru, Mar 18 2019

Table[EulerPhi[2 n], {n, 80}] (* Vincenzo Librandi, Aug 23 2013 *)

PARI
```
a(n) = eulerphi(2*n)
```

from sympy import totient
def A062570(n): return totient(n) if n&1 else totient(n)<<1 # Chai Wah Wu, Aug 04 2024

[euler_phi(2*n) for n in range(1,74)] # Zerinvary Lajos, Jun 06 2009

a(n) = Sum_{d|n and d is odd} n/d*mu(d).
Multiplicative with a(2^e) = 2^e and a(p^e) = p^e-p^(e-1), p>2.
Dirichlet g.f.: zeta(s-1)/zeta(s)*2^s/(2^s-1). - Ralf Stephan, Jun 17 2007
a(n) = A000010(2*n).
a(n) = phi(n)*(1+((n+1) mod 2)). - Gary Detlefs, Jul 13 2011
a(n) = A173557(n)*b(n) where b(n) = 1, 2, 1, 4, 1, 2, 1, 8, 3, 2, 1, 4, 1, 2, ... is the multiplicative function defined by b(p^e) = p^(e-1) if p<>2 and b(2^e)=2^e. b(n) = n/A204455(n). - R. J. Mathar, Jul 02 2013
a(n) = -c_{2n}(n) where c_q(n) is Ramanujan's sum. - Michael Somos, Aug 23 2013
a(n) = A055034(2*n), for n >= 2. - Wolfdieter Lang, Nov 30 2013
O.g.f.: Sum_{n >= 1} mu(2*n-1)*x^(2*n-1)/(1 - x^(2*n-1))^2. - Peter Bala, Mar 17 2019
a(n) = A000010(4*n)/2, for n > = 1 (see Apostol, Theorem 2.5, (b), p. 28). - Wolfdieter Lang, Nov 17 2019
a(n) = n - Sum_{d|n, n/d odd, d < n} a(d). - Ilya Gutkovskiy, May 30 2020
Dirichlet convolution of A000010 and A209229. - Werner Schulte, Jan 17 2021
From Richard L. Ollerton, May 07 2021: (Start)
a(n) = Sum_{k=1..n} A209229(gcd(n,k)).
a(n) = Sum_{k=1..n} A209229(n/gcd(n,k))*phi(gcd(n,k))/phi(n/gcd(n,k)). (End)
Sum_{k=1..n} a(k) ~ c * n^2, where c = 4/Pi^2 = 0.405284... (A185199). - Amiram Eldar, Oct 22 2022
a(n) = A000034(n) * A000010(n). - Amiram Eldar, May 18 2025

Corrected by Vladeta Jovovic, Dec 04 2002

A087786 a(n) = number of solutions to x^3 - y^3 == 0 (mod n).

Original entry on oeis.org

1, 2, 3, 6, 5, 6, 19, 20, 27, 10, 11, 18, 37, 38, 15, 40, 17, 54, 55, 30, 57, 22, 23, 60, 45, 74, 135, 114, 29, 30, 91, 112, 33, 34, 95, 162, 109, 110, 111, 100, 41, 114, 127, 66, 135, 46, 47, 120, 175, 90, 51, 222, 53, 270, 55, 380, 165, 58, 59, 90, 181, 182, 513, 352, 185

Offset: 1

Yuval Dekel (dekelyuval(AT)hotmail.com), Oct 06 2003

Andrew Howroyd, Table of n, a(n) for n = 1..10000

Cf. A046530, A087694, A062803.

a(n)={my(v=vector(n)); for(i=0, n-1, v[i^3%n + 1]++); sum(i=0, n-1, v[i+1]^2)} \\ Andrew Howroyd, Jul 17 2018

a(n)={my(f=factor(n)); prod(i=1, #f~, my(p=f[i,1], e=f[i,2]); p^(2*(2*e\3)) + sum(i=0, (e-1)\3, if(p%3==1 || (p==3&&3*iAndrew Howroyd, Jul 17 2018

Multiplicative with a(p^e) = p^(2*floor(2*e/3)) + Sum_{i=0..floor((e-1)/3)} k*(p-1)*p^(e+i-1) where k = 3 if (p = 3 and 3*i+1 = e) or (p mod 3 = 1) otherwise k = 1. - Andrew Howroyd, Jul 17 2018

More terms from John W. Layman, Oct 18 2003

A086933 Number of solutions to x^2 + y^2 = 0 mod n.

Original entry on oeis.org

1, 2, 1, 4, 9, 2, 1, 8, 9, 18, 1, 4, 25, 2, 9, 16, 33, 18, 1, 36, 1, 2, 1, 8, 65, 50, 9, 4, 57, 18, 1, 32, 1, 66, 9, 36, 73, 2, 25, 72, 81, 2, 1, 4, 81, 2, 1, 16, 49, 130, 33, 100, 105, 18, 9, 8, 1, 114, 1, 36, 121, 2, 9, 64, 225, 2, 1, 132, 1, 18, 1, 72, 145, 146, 65, 4, 1, 50, 1, 144, 81

Offset: 1

Yuval Dekel (dekelyuval(AT)hotmail.com), Sep 21 2003

Sum_{nSteven Finch, Feb 05 2007

Andrew Howroyd, Table of n, a(n) for n = 1..10000
S. R. Finch, Series involving arithmetric functions.
N. Gafurov, On the number of divisors of a quadratic form, Proc. Steklov Inst. Math. 200 (1993) 137-148.
L. Tóth, Counting solutions of quadratic congruences in several variables revisited, arXiv preprint arXiv:1404.4214 [math.NT], 2014.
L. Toth, Counting Solutions of Quadratic Congruences in Several Variables Revisited, J. Int. Seq. 17 (2014) # 14.11.6.
G. Yu, On the number of divisors of the quadratic form m^2+n^2, Canad. Math. Bull. 43 (2000) 239-256.

Cf. A062803.

a[n_] := a[n] = Module[{f, p, e}, f = FactorInteger[n]; Switch[f, {{2, }}, Return[n], {{, }}, {p, e} = f[[1]]; If[Mod[p, 4] == 3, Return[p^(e - Mod[e, 2])], Return[((p-1)*e+p)*p^(e-1)]], , Times @@ (a[#[[1]]^#[[2]]]& /@ f)]];
Array[a, 81] (* Jean-François Alcover, Aug 21 2018, after Vladeta Jovovic *)

ap(p,e)=if(p%4<2, ((p-1)*e+p)*p^(e-1), p^(e - e%2))
a(n)=my(o=valuation(n,2),f=factor(n>>o)); prod(i=1,#f~, ap(f[i,1],f[i,2]))<Charles R Greathouse IV, Dec 06 2016

Multiplicative with a(2^e)=2^e, a(p^e)=p^(e-(e mod 2)) if p mod 4=3, a(p^e)=((p-1)*e+p)*p^(e-1) if p mod 4<>3 and p<>2. - Vladeta Jovovic, Sep 22 2003
From Peter Bala, Mar 24 2019: (Start)
a(n) = n*Sum_{d|n, d odd} (-1)^((d-1)/2)*phi(d)/d.
O.g.f.: Sum_{n odd} (-1)^((n-1)/2)*phi(n)*x^n/(1 - x^n)^2. (End)

More terms from John W. Layman, Sep 22 2003

A088964 Number of solutions to x^2 == 2y^2 (mod n).

Original entry on oeis.org

1, 2, 1, 4, 1, 2, 13, 8, 9, 2, 1, 4, 1, 26, 1, 16, 33, 18, 1, 4, 13, 2, 45, 8, 25, 2, 9, 52, 1, 2, 61, 32, 1, 66, 13, 36, 1, 2, 1, 8, 81, 26, 1, 4, 9, 90, 93, 16, 133, 50, 33, 4, 1, 18, 1, 104, 1, 2, 1, 4, 1, 122, 117, 64, 1, 2, 1, 132, 45, 26

Offset: 1

Yuval Dekel (dekelyuval(AT)hotmail.com), Oct 28 2003

Andrew Howroyd, Table of n, a(n) for n = 1..10000
László Tóth, Counting Solutions of Quadratic Congruences in Several Variables Revisited, J. Int. Seq. 17 (2014), Article 14.11.6.

Cf. A087561, A062803, A196525, A328895.

A088964 := proc(n) local a,x,y ; a := 0 ; for x from 0 to n-1 do for y from 0 to n-1 do if (x^2-2*y^2) mod n = 0 then a := a+1 ; end if; end do; end do ; a ; end proc:
seq(A088964(n),n=1..70) ; # R. J. Mathar, Jan 07 2011

a[n_] := Product[{p, e} = pe; Which[p == 2, 2^e, Abs[Mod[p, 8] - 4] == 1, (p^2)^Quotient[e, 2], True, (p+e(p-1))p^(e-1)], {pe, FactorInteger[n]}];
Array[a, 100] (* Jean-François Alcover, Apr 08 2020, after Andrew Howroyd *)
f[2, e_] := 2^e; f[p_, e_] := If[MemberQ[{1, 7}, Mod[p, 8]], ((p-1)*e + p)*p^(e-1), p^(2*Floor[e/2])]; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Sep 20 2020 *)

a(n)={my(v=vector(n)); for(i=0, n-1, v[i^2%n + 1]++); sum(i=0, n-1, v[i+1]*v[2*i%n + 1])} \\ Andrew Howroyd, Jul 09 2018

a(n)={my(f=factor(n)); prod(i=1, #f~, my(p=f[i,1], e=f[i,2]); if(p==2, 2^e, if(abs(p%8-4)==1, (p^2)^(e\2), (p+e*(p-1))*p^(e-1))))} \\ Andrew Howroyd, Jul 09 2018

Multiplicative with a(2^e) = 2^e, a(p^e) = p^(2*floor(e/2)) for p mod 8 = +-3, a(p^e) = ((p-1)*e+p)*p^(e-1) for p mod 8 = +-1. - Andrew Howroyd, Jul 13 2018

Sum_{k=1..n} a(k) ~ c * n^2, where c = (64/Pi^4) * A328895 * A196525 = 0.35720726027165235652... . - Amiram Eldar, Nov 21 2023

A306271 a(n) is the smallest positive integer x such that x^2 mod n is a square, with x^2 >= n.

Original entry on oeis.org

1, 2, 2, 2, 3, 4, 5, 3, 3, 7, 8, 4, 10, 11, 4, 4, 13, 6, 15, 6, 5, 18, 19, 5, 5, 21, 6, 9, 24, 8, 26, 6, 7, 29, 6, 6, 31, 32, 8, 7, 35, 10, 37, 16, 7, 40, 41, 7, 7, 10, 10, 19, 46, 12, 8, 9, 14, 51, 52, 8, 54, 55, 8, 8, 9, 14, 59, 26, 16, 12, 63, 9, 65, 66, 10

Offset: 1

Daniel Suteu, Feb 01 2019

nonn

			For n = 10, a(10) = 7, which is the smallest positive integer x such that x^2 mod n is a square and that x^2 >= n. Here 7^2 mod 10 = 9 = 3^2.

Daniel Suteu, Table of n, a(n) for n = 1..10000
Wikipedia, Congruence of squares

Cf. A000290, A048152, A062803, A112045, A254328, A306257.

a:= proc(n) local k, t;
      for k do t:= irem(k^2, n);
        if issqr(t) and isqrt(t)<>k then break fi
      od; k
    end:
seq(a(n), n=1..100);  # Alois P. Heinz, Feb 01 2019

a[n_] := For[x = Sqrt[n]//Ceiling, True, x++, If[IntegerQ[Sqrt[PowerMod[x, 2, n]]], Return[x]]];
Array[a, 100] (* Jean-François Alcover, Nov 07 2020 *)

a(n) = for(k=sqrtint(n), oo, if(issquare(k^2 % n) && sqrtint(k^2 % n) != k, return(k)));

a(n^2) = n.

a(p) = p - floor(sqrt(p)), for prime p > 2.

A366561 Triangle read by rows: T(n,k) = Sum_{y=1..n} Sum_{x=1..n} [GCD(f(x,y), n) = k], where f(x,y) = x^2 - y^2.

Original entry on oeis.org

1, 2, 2, 4, 0, 5, 8, 0, 0, 8, 16, 0, 0, 0, 9, 8, 8, 10, 0, 0, 10, 36, 0, 0, 0, 0, 0, 13, 32, 0, 0, 8, 0, 0, 0, 24, 36, 0, 24, 0, 0, 0, 0, 0, 21, 32, 32, 0, 0, 18, 0, 0, 0, 0, 18, 100, 0, 0, 0, 0, 0, 0, 0, 0, 0, 21, 32, 0, 40, 32, 0, 0, 0, 0, 0, 0, 0, 40

Offset: 1

Mats Granvik, Oct 13 2023

Row n appears to have sum n^2. The number of nonzero terms in row n is A366563(n). Sum_{k=1..n} T(n,k)*A023900(k)/n = A366562(n).

			{
{1}, = 1^2
{2, 2}, = 2^2
{4, 0, 5}, = 3^2
{8, 0, 0, 8}, = 4^2
{16, 0, 0, 0, 9}, = 5^2
{8, 8, 10, 0, 0, 10}, = 6^2
{36, 0, 0, 0, 0, 0, 13}, = 7^2
{32, 0, 0, 8, 0, 0, 0, 24}, = 8^2
{36, 0, 24, 0, 0, 0, 0, 0, 21}, = 9^2
{32, 32, 0, 0, 18, 0, 0, 0, 0, 18}, = 10^2
{100, 0, 0, 0, 0, 0, 0, 0, 0, 0, 21}, = 11^2
{32, 0, 40, 32, 0, 0, 0, 0, 0, 0, 0, 40} = 12^2
}

Cf. A127649, A000290, A062803, A082953.

Cf. A000010, A054523.

nn = 12; f = x^2 - y^2; g[n_] := DivisorSum[n, MoebiusMu[#] # &]; Flatten[Table[Table[Sum[Sum[If[GCD[f, n] == k, 1, 0], {x, 1, n}], {y, 1, n}], {k, 1, n}], {n, 1, nn}]]

T(n,k) = sum(x=1, n, sum(y=1, n, gcd(x^2 - y^2, n) == k)); \\ Michel Marcus, Oct 14 2023

T(n,k) = Sum_{y=1..n} Sum_{x=1..n} [GCD(f(x,y), n) = k], where f(x,y) = x^2 - y^2.
Conjecture 1: T(n,n) = A062803(n).
Conjecture 2: T(n,1) = A082953(n).
Conjectures from Ridouane Oudra, Jun 17 2025: (Start)
T(n,k) = 0 iff k not divide n.
T(n,k) = phi(n/k)*Sum_{d|k} (k/d)*phi(d*n/k), for n odd and k|n.
T(n,k) = 2*(-1)^k*phi(n/k)*Sum_{d|k} (-1)^(k/d)*(k/d)*phi(d*n/k), for n even and k|n.
T(n,k) = gcd(n,2)*(-1)^k*phi(n/k)*Sum_{d|k} (-1)^(k/d)*(k/d)*phi(d*n/k), for all integers n and k|n.
More generally, for all integers n, k: T(n,k) = gcd(n,2)*(-1)^k*A054523(n,k)*Sum_{d|k} (-1)^(k/d)*(k/d)*A054523(d*n,k). (End)

A235872 Number of solutions to the equation x^2=0 in the ring of Gaussian integers modulo n.

Original entry on oeis.org

1, 2, 1, 4, 1, 2, 1, 8, 9, 2, 1, 4, 1, 2, 1, 16, 1, 18, 1, 4, 1, 2, 1, 8, 25, 2, 9, 4, 1, 2, 1, 32, 1, 2, 1, 36, 1, 2, 1, 8, 1, 2, 1, 4, 9, 2, 1, 16, 49, 50, 1, 4, 1, 18, 1, 8, 1, 2, 1, 4, 1, 2, 9, 64, 1, 2, 1, 4, 1, 2, 1, 72, 1, 2, 25, 4, 1, 2, 1, 16, 81, 2

Offset: 1

José María Grau Ribas, Apr 03 2014

Numbers of solutions to x^2 == y^2 (mod n), 2*x*y == 0 (mod n). - Andrew Howroyd, Aug 06 2018

Andrew Howroyd, Table of n, a(n) for n = 1..10000

Cf. A062803, A090699.

invoG[n_] := invoG[n] = Sum[If[Mod[(x + I y)^2, n] == 0, 1, 0], {x, 0, n - 1}, {y, 0, n - 1}]; Table[invoG[n], {n, 1, 104}]
f[p_, e_] := p^(2*Floor[e/2]); f[2, e_] := 2^e; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Nov 13 2022 *)

a(n)={sum(i=0, n-1, sum(j=0, n-1, (i^2 - j^2)%n == 0 && 2*i*j%n == 0))} \\ Andrew Howroyd, Aug 06 2018

a(n)={my(f=factor(n)); prod(i=1, #f~, my([p,e]=f[i,]); p^if(p==2, e, e - e%2))} \\ Andrew Howroyd, Aug 06 2018

Multiplicative with a(2^e) = 2^e, a(p^e) = p^(2*floor(e/2)). - Andrew Howroyd, Aug 06 2018

Sum_{k=1..n} a(k) ~ c * n^(3/2), where c = (2/21)*(3+sqrt(2))*zeta(3/2)/zeta(3) = 0.91363892007.... - Amiram Eldar, Nov 13 2022

cp's OEIS Frontend

A062570 a(n) = phi(2*n).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Sage

Formula

Extensions

A087786 a(n) = number of solutions to x^3 - y^3 == 0 (mod n).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

PARI

Formula

Extensions

A086933 Number of solutions to x^2 + y^2 = 0 mod n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A088964 Number of solutions to x^2 == 2y^2 (mod n).

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

A306271 a(n) is the smallest positive integer x such that x^2 mod n is a square, with x^2 >= n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A366561 Triangle read by rows: T(n,k) = Sum_{y=1..n} Sum_{x=1..n} [GCD(f(x,y), n) = k], where f(x,y) = x^2 - y^2.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Formula

A235872 Number of solutions to the equation x^2=0 in the ring of Gaussian integers modulo n.

Views

Author

Keywords

Comments