%I M0247 N0087 #71 Jul 06 2024 01:34:00
%S 1,2,2,3,2,4,2,4,4,4,2,6,2,4,4,6,2,8,2,6,4,4,2,8,6,4,6,6,2,8,2,8,4,4,
%T 4,12,2,4,4,8,2,8,2,6,8,4,2,12,8,12,4,6,2,12,4,8,4,4,2,12,2,4,8,12,4,
%U 8,2,6,4,8,2,16,2,4,12,6,4,8,2,12,12,4,2,12,4,4,4,8,2,16,4,6,4,4,4,16
%N Number of parabolic vertices of Gamma_0(n).
%C Number of inequivalent cusps of Gamma_0(n). - _Michael Somos_, May 08 2015
%D B. Schoeneberg, Elliptic Modular Functions, Springer-Verlag, NY, 1974, p. 102.
%D Goro Shimura, Introduction to the Arithmetic Theory of Automorphic Functions, Princeton, 1971, see p. 25, Eq. (4).
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Alois P. Heinz, <a href="/A001616/b001616.txt">Table of n, a(n) for n = 1..20000</a> (first 1000 terms from N. J. A. Sloane)
%H Harriet Fell, Morris Newman, and Edward Ordman, <a href="http://archive.org/details/jresv67Bn1p61">Tables of genera of groups of linear fractional transformations</a>, J. Res. Nat. Bur. Standards Sect. B 67B (1963), 61-68.
%H Steven R. Finch, <a href="/A000521/a000521_1.pdf">Modular forms on SL_2(Z)</a>, December 28, 2005. [Cached copy, with permission of the author]
%H Steven R. Finch, <a href="/A001616/a001616.pdf">Primitive Cusp Forms</a>, April 27, 2009. [Cached copy, with permission of the author]
%H László Tóth, <a href="http://arxiv.org/abs/1310.7053">Multiplicative arithmetic functions of several variables: a survey</a>, arXiv preprint arXiv:1310.7053 [math.NT], 2013-2014.
%F a(n) = Sum_{d|n} phi(gcd(d,n/d)), where phi() is Euler's totient function. - _Joerg Arndt_, Jul 17 2011
%F Multiplicative with a(p^e) = p^[e/2] + p^[(e-1)/2]. - _David W. Wilson_, Sep 01 2001
%e G.f. = x + 2*x^2 + 2*x^3 + 3*x^4 + 2*x^5 + 4*x^6 + 2*x^7 + 4*x^8 + 4*x^9 + ...
%p with(numtheory); nupara := proc (n) local b, d; b := 0; for d to n do if modp(n,d) = 0 then b := b+eval(phi(gcd(d,n/d))) fi od; b end: # _Gene Ward Smith_, May 22 2006
%t Table[ Plus@@Map[ EulerPhi[ GCD[ #1, n/#1 ] ]&, Select[ Range[ n ], (Mod[ n, #1 ]==0)& ] ], {n, 1, 100} ] (* _Olivier Gérard_, Aug 15 1997 *)
%t a[ n_] := If[ n < 1, 0, Sum[ EulerPhi[ GCD[ d, n/d]], {d, Divisors@n}]]; (* _Michael Somos_, May 08 2015 *)
%t f[p_, e_] := p^Floor[e/2] + p^Floor[(e-1)/2]; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* _Amiram Eldar_, Aug 28 2023 *)
%o (PARI) a(n)=sumdiv(n,d,eulerphi(gcd(d,n/d))); \\ _Joerg Arndt_, Jul 17 2011
%o (Haskell)
%o a001616 n = sum $ map a000010 $ zipWith gcd ds $ reverse ds
%o where ds = a027750_row n
%o -- _Reinhard Zumkeller_, Jun 23 2013
%o (Python)
%o from math import prod
%o from sympy import factorint
%o def A001616(n): return prod(p**(e>>1)+p**(e-1>>1) for p, e in factorint(n).items()) # _Chai Wah Wu_, Jul 05 2024
%Y Cf. A027750, A000010, A027748, A124010.
%K nonn,easy,nice,mult
%O 1,2
%A _N. J. A. Sloane_
%E More terms from _Olivier Gérard_, Aug 15 1997