%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