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

%I #92 Jan 18 2024 02:45:19

%S 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,

%T 18,24,28,24,30,32,20,48,24,24,36,54,24,32,40,36,42,40,24,66,46,32,42,

%U 60,32,48,52,54,40,48,36,84,58,32,60,90,36,64,48,60,66,64

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

%C From _Peter Bala_, Dec 30 2023: (Start)

%C Denoted phi_2(n) in van der Kamp.

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

%C 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)

%H N. Anghel, <a href="http://imar.ro/journals/Revue_Mathematique/pdfs/2020/4/2.pdf">Heron triangles with constant area and perimeter</a>, Rev. Roumaine Math. Pures Appl. 65 (2020), 4, 403-422.

%H Peter H. van der Kamp, <a href="https://arxiv.org/abs/1201.3139">On the Fourier transform of the greatest common divisor</a>, arXiv:1201.3139 [math.NT], 2012.

%F 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).

%F From _Ridouane Oudra_, Oct 17 2021: (Start)

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

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

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

%F From _Peter Bala_, Dec 30 2023: (Start)

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

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

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

%F 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.

%F 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.

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

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

%p with(numtheory):

%p seq(add(d*phi(n/d), d in divisors(igcd(2, n))), n = 1..70); # _Peter Bala_, Dec 30 2023

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

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

%o (Python)

%o from sympy import totient as phi

%o def a(n): return phi(n) if n%2 else 2*phi(n)+phi(n//2) if n%4 else 2*phi(n)

%o print([a(n) for n in range(1, 69)]) # _Michael S. Branicky_, Jul 30 2021

%Y Cf. A000010, A088245.

%Y Cf. A319998, A319997.

%K nonn,easy,mult

%O 1,2

%A _Michel Marcus_, Jul 30 2021