A345082 Number of elements of order n in R/Z X Z/2Z.

1, 3, 2, 4, 4, 6, 6, 8, 6, 12, 10, 8, 12, 18, 8, 16, 16, 18, 18, 16, 12, 30, 22, 16, 20, 36, 18, 24, 28, 24, 30, 32, 20, 48, 24, 24, 36, 54, 24, 32, 40, 36, 42, 40, 24, 66, 46, 32, 42, 60, 32, 48, 52, 54, 40, 48, 36, 84, 58, 32, 60, 90, 36, 64, 48, 60, 66, 64

Offset: 1

Author

Michel Marcus, Jul 30 2021

Keywords

• nonn
• easy
• mult

Comments

From Peter Bala, Dec 30 2023: (Start)

Denoted phi_2(n) in van der Kamp.

The number of solutions of the congruence x*y == 2 (mod n), 1 <= x, y <= n.

Can be regarded as a generalization of Euler's totient function phi(n) = Sum_{k = 1..n, gcd(k,n) = 1} gcd(k,n) since a(n) = Sum_{k = 1..n, gcd(k,n) divides 2} gcd(k,n). (End)

Links

• N. Anghel, Heron triangles with constant area and perimeter, Rev. Roumaine Math. Pures Appl. 65 (2020), 4, 403-422.
• Peter H. van der Kamp, On the Fourier transform of the greatest common divisor, arXiv:1201.3139 [math.NT], 2012.

Crossrefs

Cf. A000010, A088245.

Cf. A319998, A319997.

Programs

Maple

with(numtheory):
seq(add(d*phi(n/d), d in divisors(igcd(2, n))), n = 1..70); # Peter Bala, Dec 30 2023

Mathematica

Table[If[OddQ[n],EulerPhi[n],If[Mod[n,4]==0,2EulerPhi[n],2EulerPhi[n]+EulerPhi[n/2]]],{n,68}] (* Stefano Spezia, Jul 30 2021 *)

PARI

a(n) = if (n%2, eulerphi(n), if (n%4, 2*eulerphi(n) + eulerphi(n/2), 2*eulerphi(n)));

Python

from sympy import totient as phi
def a(n): return phi(n) if n%2 else 2*phi(n)+phi(n//2) if n%4 else 2*phi(n)
print([a(n) for n in range(1, 69)]) # Michael S. Branicky, Jul 30 2021

Formula

a(n) = phi(n) if n is odd; 2*phi(n) if n == 0 (mod 4); 2*phi(n) + phi(n/2) if n == 2 (mod 4).

From Ridouane Oudra, Oct 17 2021: (Start)

a(n) = A000010(n) + A319998(n);

a(n) = 2*A000010(n) - A319997(n);

a(n) = Sum_{j = 1..n} gcd(n,j)*cos(4*Pi*j/n). (End)

From Peter Bala, Dec 30 2023: (Start)

a(n) = Sum_{d divides gcd(2,n)} d*phi(n/d), where phi(n) = A000010(n) denotes Euler's totient function.

Sum_{d divides n} a(d) = 2*n for n even, else equals n (van der Kamp, equation 26).

Dirichlet g.f.: zeta(s-1)*(1 + 2^(1-s))/zeta(s).

The Lambert series Sum_{n >= 1} a(n)*x^n/(1 - x^n) = x*(1 + 4*x + x^2)/(1 - x^2)^2. See A022998.

Multiplicative with a(2) = 3, a(2^k) = 2^k for k >= 2 and a(p^k) = p*k - p^(k-1) for odd primes p.

If n divides m then a(n) divides 3*a(m). (End)

Sum_{k=1..n} a(k) ~ c * n^2, where c = 9/(2*Pi^2) = 0.455945... (A088245). - Amiram Eldar, Jan 18 2024