A244342 - OEIS

%I #27 Apr 08 2020 11:18:49

%S 1,2,6,8,12,12,18,32,30,24,30,48,36,36,72,96,48,60,54,96,108,60,66,

%T 192,100,72,126,144,84,144,90,256,180,96,216,240,108,108,216,384,120,

%U 216,126,240,360,132,138,576,210,200,288,288,156,252,360,576,324,168

%N a(n) = phi(n)*h(n) where phi() is the Euler totient function, A000010, and h() is A092089.

%C a(n) = Sum_{k=1..n} gcd(k^2-1, n) for those k that are coprime to n (see proof in link).

%C Multiplicative because both A000010 and A092089 are. - _Andrew Howroyd_, Jul 26 2018

%H Robert Israel, <a href="/A244342/b244342.txt">Table of n, a(n) for n = 1..10000</a>

%H László Tóth, <a href="http://www.seminariomatematico.polito.it/rendiconti/69-1/97.pdf">Menon's identity and arithmetical sums representing functions of several variables</a>, Rend. Sem. Mat. Univ. Politec. Torino, 69 (2011), 97-110 (see (36) in Corollary 15, p. 108); also on <a href="https://arxiv.org/abs/1103.5861">arXiv</a>, arXiv:1103.5861 [math.NT], 2011.

%p A244342:= proc(n) add(`if`(igcd(k,n)=1,igcd(k^2-1,n),0),k=1..n) end proc;

%p seq(A244342(i),i=1..1000); # _Robert Israel_, Jul 06 2014

%t h[n_] := Product[{p, e} = pe; Which[OddQ[p], 2 e + 1, p == 2 && e == 1, 2, True, 4 (e - 1)], {pe, FactorInteger[n]}]; h[1] = 1;

%t a[n_] := EulerPhi[n] h[n];

%t Array[a, 100] (* _Jean-François Alcover_, Apr 08 2020 *)

%o (PARI) a(n) = sum(j=1, n, gcd(j^2-1,n)*(gcd(j,n)==1));

%Y Cf. A000010, A062355, A092089.

%K nonn,mult

%O 1,2

%A _Michel Marcus_, Jun 26 2014