A002618 -id:A002618 - cp's OEIS frontend

A011755 a(n) = Sum_{k=1..n} k*phi(k).

1, 3, 9, 17, 37, 49, 91, 123, 177, 217, 327, 375, 531, 615, 735, 863, 1135, 1243, 1585, 1745, 1997, 2217, 2723, 2915, 3415, 3727, 4213, 4549, 5361, 5601, 6531, 7043, 7703, 8247, 9087, 9519, 10851, 11535, 12471, 13111, 14751, 15255, 17061, 17941, 19021, 20033

Offset: 1

N. J. A. Sloane

nonn

a(n) = Sum_{(x,y): 1<=x<=y<=n, 1=gcd(x,y)} y. Sum_{(x,y): 1<=x<=y<=n, 1=gcd(x,y)} x = (a(n)+1)/2. - Vladeta Jovovic, Jan 02 2003

Equals row sums of triangle A110663. Example: a(4) = 17 = (6 + 5 + 4 + 2), where row 4 of triangle A110663 = (6, 5, 4, 2). - Gary W. Adamson, Jul 26 2008

Seiichi Manyama, Table of n, a(n) for n = 1..10000 (terms 1..2001 from Indranil Ghosh)

Partial sums of A002618.

Cf. A000010, A002088, A110663, A319087.

Accumulate[Table[k*EulerPhi[k], {k, 1, 50}]] (* Vaclav Kotesovec, Sep 10 2018 *)

a(n) = sum(k=1, n, k*eulerphi(k)); \\ Michel Marcus, Feb 13 2017

from sympy import totient
def A011755(n): return sum(k*totient(k) for k in range(1,n+1)) # Chai Wah Wu, Feb 21 2023

Asymptotically: a(n) ~ C*n^3 with C=0.20264.... - Benoit Cloitre, Jan 14 2002
Asymptotically: a(n) ~ (2/Pi^2)*n^3. - Vladeta Jovovic, Jan 02 2003
a(n) = Sum_{k=1..n} phi(k^2). - Vaclav Kotesovec, May 08 2024

A238533 Number of solutions to gcd(x^2 + y^2 + z^2 + t^2 + h^2, n) = 1 with x,y,z,t,h in [0,n-1].

Original entry on oeis.org

1, 16, 162, 512, 2500, 2592, 14406, 16384, 39366, 40000, 146410, 82944, 342732, 230496, 405000, 524288, 1336336, 629856, 2345778, 1280000, 2333772, 2342560, 6156502, 2654208, 7812500, 5483712, 9565938, 7375872, 19803868, 6480000, 27705630, 16777216, 23718420

Offset: 1

José María Grau Ribas, Feb 28 2014

Amiram Eldar, Table of n, a(n) for n = 1..10000
Param Parekh, Paavan Parekh, Sourav Deb, and Manish K. Gupta, On the Classification of Weierstrass Elliptic Curves over Z_n, arXiv:2310.11768 [cs.CR], 2023. See p. 9.

Cf. A079458, A227499, A238534.

Cf. n^k * a(n): A000010 (k=-4), A002618 (k=-3), A053191 (k=-2), A189393 (k=-1), A239442 (k=2), A239443 (k=4).

g[n_, 5] := g[n, 5] = Sum[If[GCD[x^2 + y^2 + z^2 + t^2 + h^2, n] == 1, 1, 0], {x, n}, {y, n}, {z, n}, {t, n}, {h, n}];Table[g[n,5] , {n, 1, 15}]
Table[n^4 * EulerPhi[n], {n, 1, 33}] (* Amiram Eldar, Dec 06 2020 *)

From Álvar Ibeas, Nov 24 2017: (Start)
a(n) = phi(n^5) = n^4 * phi(n), where phi=A000010.
Dirichlet g.f.: zeta(s - 5) / zeta(s - 4). The n-th term of the Dirichlet inverse is n^4 * A023900(n) = (-1)^omega(n) * a(n) / A003557(n), where omega = A001221.
(End)
Sum_{k=1..n} a(k) ~ n^6 / Pi^2. - Vaclav Kotesovec, Feb 02 2019
Sum_{n>=1} 1/a(n) = Product_{p prime} (1 + p/(p^6 - p^5 - p + 1)) = 1.07162935672651489627... - Amiram Eldar, Dec 06 2020

A262311 Number of ordered ways to write n = x^2 + y^2 + phi(z^2) (0 <= x <= y and z > 0) with y or z prime, where phi(.) is Euler's totient function given by A000010.

Original entry on oeis.org

0, 1, 1, 1, 1, 3, 2, 1, 1, 3, 3, 2, 1, 2, 2, 3, 2, 2, 3, 3, 3, 4, 1, 2, 2, 3, 3, 2, 1, 3, 3, 1, 2, 2, 2, 3, 4, 4, 1, 3, 2, 6, 3, 2, 4, 4, 3, 1, 3, 4, 5, 5, 3, 3, 3, 4, 4, 8, 4, 3, 5, 4, 2, 2, 3, 6, 6, 1, 2, 5, 3, 2, 4, 5, 2, 2, 2, 3, 3, 2, 3, 6, 3, 2, 3, 3, 4, 4, 3, 3, 4, 5, 4, 3, 3, 1, 4, 3, 2, 3

Offset: 1

Zhi-Wei Sun, Oct 01 2015

nonn

Conjecture: a(n) > 0 for all n > 1.
I have verified this for n up to 10^6, and found that a(n) = 1 for the following 67 values of n: 2, 3, 4, 5, 8, 9, 13, 23, 29, 32, 39, 48, 68, 96, 108, 140, 144, 215, 264, 268, 324, 328, 384, 396, 404, 460, 471, 476, 500, 503, 684, 716, 759, 764, 768, 788, 860, 908, 936, 1032, 1076, 1112, 1148, 1164, 1259, 1344, 1399, 1443, 1484, 1503, 1551, 1839, 1868, 2088, 2723, 2883, 3744, 4296, 5963, 6804, 8328, 9680, 10331, 11948, 21524, 39716, 94415. It seems that a(n) = 1 for no other values of n.
It is easy to see that all the numbers phi(n^2) = n*phi(n) (n = 1,2,3,...) are pairwise distinct.
See also A262781 for a similar conjecture.

			a(2) = 1 since 2 = 0^2 + 0^2 + phi(2^2) with 2 prime.
a(5) = 1 since 5 = 0^2 + 2^2 + phi(1^2) with 2 prime.
a(23) = 1 since 23 = 1^2 + 4^2 + phi(3^2) with 3 prime.
a(29) = 1 since 29 = 0^2 + 3^2 + phi(5^2) with 3 and 5 both prime.
a(48) = 1 since 48 = 2^2 + 2^2 + phi(10^2) with 2 prime.
a(96) = 1 since 96 = 3^2 + 9^2 + phi(3^2) with 3 prime.
a(140) = 1 since 140 = 7^2 + 7^2 + phi(7^2) with 7 prime.
a(471) = 1 since 471 = 0^2 + 19^2 + phi(11^2) with 19 and 11 both prime.
a(476) = 1 since 476 = 8^2 + 16^2 + phi(13^2) with 13 prime.
a(936) = 1 since 936 = 4^2 + 30^2 + phi(5^2) with 5 prime.
a(1112) = 1 since 1112 = 23^2 + 23^2 + phi(9^2) with 23 prime.
a(1839) = 1 since 1839 = 3^2 + 30^2 + phi(31^2) with 31 prime.
a(1868) = 1 since 1868 = 2^2 + 2^2 + phi(62^2) with 2 prime.
a(2088) = 1 since 2088 = 15^2 + 39^2 + phi(19^2) with 19 prime.
a(2723) = 1 since 2723 = 34^2 + 35^2 + phi(19^2) with 19 prime.
a(2883) = 1 since 2883 = 21^2 + 44^2 + phi(23^2) with 23 prime.
a(3744) = 1 since 3744 = 4^2 + 54^2 + phi(29^2) with 29 prime.
a(4296) = 1 since 4296 = 26^2 + 60^2 + phi(5^2) with 5 prime.
a(5963) = 1 since 5963 = 26^2 + 59^2 + phi(43^2) with 59 and 43 both prime.
a(6804) = 1 since 6804 = 40^2 + 72^2 + phi(5^2) with 5 prime.
a(8328) = 1 since 8328 = 1^2 + 39^2 + phi(83^2) with 83 prime.
a(9680) = 1 since 9680 = 68^2 + 70^2 + phi(13^2) with 13 prime.
a(10331) = 1 since 10331 = 17^2 + 100^2 + phi(7^2) with 7 prime.
a(11948) = 1 since 11948 = 5^2 + 109^2 + phi(7^2) with 109 and 7 both prime.
a(21524) = 1 since 21524 = 59^2 + 109^2 + phi(79^2) with 109 and 79 both prime.
a(39716) = 1 since 39716 = 5^2 + 17^2 + phi(199^2) with 17 and 199 both prime.
a(94415) = 1 since 94415 = 115^2 + 178^2 + phi(223^2) with 223 prime.

Zhi-Wei Sun, Table of n, a(n) for n = 1..10000

Cf. A000010, A000040, A000290, A001481, A002618, A262747, A262781.

SQ[n_]:=IntegerQ[Sqrt[n]]
f[n_]:=EulerPhi[n^2]
Do[r=0;Do[If[f[z]>n,Goto[aa]];Do[If[SQ[n-f[z]-x^2]&&(PrimeQ[z]||PrimeQ[Sqrt[n-f[z]-x^2]]),r=r+1],{x,0,Sqrt[(n-f[z])/2]}];Label[aa];Continue,{z,1,n}];Print[n," ",r];Continue,{n,1,100}]

A053650 Cototient function of n^2.

Original entry on oeis.org

0, 2, 3, 8, 5, 24, 7, 32, 27, 60, 11, 96, 13, 112, 105, 128, 17, 216, 19, 240, 189, 264, 23, 384, 125, 364, 243, 448, 29, 660, 31, 512, 429, 612, 385, 864, 37, 760, 585, 960, 41, 1260, 43, 1056, 945, 1104, 47, 1536, 343, 1500, 969, 1456, 53, 1944, 825, 1792, 1197

Offset: 1

Labos Elemer, Feb 18 2000

Seems to be invertible like n*Phi(n). Compare with A002618, A038040.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

Cf. A000005, A038040.

Cf. A001248, A002618, A053650, A053192, A053193, A036689, A229099.

List([1..60], n-> n*(n- Phi(n)) ); # G. C. Greubel, May 18 2019

a053650 = a051953 . a000290  -- Reinhard Zumkeller, Jan 21 2014

[n*(n-EulerPhi(n)): n in [1..60]]; // Vincenzo Librandi, Jul 27 2016

Table[n(n-EulerPhi[n]), {n, 60}] (* Michael De Vlieger, Jul 26 2016 *)

a(n) = n^2 - eulerphi(n^2) \\ Michel Marcus, Jul 27 2013

[n*(n - euler_phi(n)) for n in (1..60)] # G. C. Greubel, May 18 2019

a(n) = n*(n - phi(n)) = n^2 - n*phi(n) = Cototient(n^2) = A051953(A000290(n)).
a(n) = n^2 - A002618(n).
For p prime, Cototient(p)=1 and a(p)=p.
a(n) = n*cototient(n) = n*A051953(n). - Omar E. Pol, Nov 22 2012
Dirichlet g.f.: zeta(s-2)*(1 - 1/zeta(s-1)). - Ilya Gutkovskiy, Jul 26 2016
Sum_{k=1..n} a(k) ~ c * n^3 / 3, where c = 1 - 6/Pi^2 (A229099). - Amiram Eldar, Dec 15 2023

A047916 Triangular array read by rows: a(n,k) = phi(n/k)(n/k)^kk! if k|n else 0 (1<=k<=n).

Original entry on oeis.org

1, 2, 2, 6, 0, 6, 8, 8, 0, 24, 20, 0, 0, 0, 120, 12, 36, 48, 0, 0, 720, 42, 0, 0, 0, 0, 0, 5040, 32, 64, 0, 384, 0, 0, 0, 40320, 54, 0, 324, 0, 0, 0, 0, 0, 362880, 40, 200, 0, 0, 3840, 0, 0, 0, 0, 3628800, 110, 0, 0, 0, 0, 0, 0, 0, 0, 0, 39916800, 48, 144

Offset: 1

N. J. A. Sloane

T(n,k) = A054523(n,k) * A010766(n,k)^A002260(n,k) * A166350(n,k). - Reinhard Zumkeller, Jan 20 2014

			1; 2,2; 6,0,6; 8,8,0,24; 20,0,0,0,120; 12,36,48,0,0,720; ...

J. E. A. Steggall, On the numbers of patterns which can be derived from certain elements, Mess. Math., 37 (1907), 56-61.

Reinhard Zumkeller, Rows n = 1..125 of triangle, flattened
C. L. Mallows and N. J. A. Sloane, Notes on A002618, A002619, etc.
N. J. A. Sloane, Notes on A002618, A002619, etc.
J. E. A. Steggall, On the numbers of patterns which can be derived from certain elements, Mess. Math., 37 (1907), 56-61.
J. E. A. Steggall, On the numbers of patterns which can be derived from certain elements, Mess. Math., 37 (1907), 56-61. [Annotated scanned copy. Note that the scanned pages are out of order]

A064649 gives the row sums.
Cf. A002618 (left edge), A000142 (right edge), A049820 (zeros per row), A000005 (nonzeros per row).
See also A247917, A047918, A047919.

import Data.List (zipWith4)
a047916 n k = a047916_tabl !! (n-1) !! (k-1)
a047916_row n = a047916_tabl !! (n-1)
a047916_tabl = zipWith4 (zipWith4 (\x u v w -> x * v ^ u * w))
               a054523_tabl a002260_tabl a010766_tabl a166350_tabl
-- Reinhard Zumkeller, Jan 20 2014

a[n_, k_] := If[Divisible[n, k], EulerPhi[n/k]*(n/k)^k*k!, 0]; Flatten[ Table[ a[n, k], {n, 1, 12}, {k, 1, n}]] (* Jean-François Alcover, May 04 2012 *)

a(n,k)=if(n%k, 0, eulerphi(n/k)*(n/k)^k*k!) \\ Charles R Greathouse IV, Feb 09 2017

A323333 The Euler phi function values of the powerful numbers, A000010(A001694(n)).

Original entry on oeis.org

1, 2, 4, 6, 8, 20, 18, 16, 12, 42, 32, 24, 54, 40, 36, 110, 100, 64, 48, 156, 84, 80, 72, 120, 162, 128, 96, 272, 108, 294, 342, 168, 160, 144, 252, 220, 200, 256, 506, 192, 500, 216, 360, 312, 486, 336, 320, 812, 288, 240, 930, 440, 324, 400, 512, 660, 600

Offset: 1

Amiram Eldar, Jan 11 2019

nonn

The sum of the reciprocals of all the terms of this sequence is Murata's constant Product_{p prime}(1 + 1/(p-1)^2) (A065485).

Sequence is injective: no value occurs more than once. - Amiram Eldar and Antti Karttunen, Sep 30 2019

Amiram Eldar, Table of n, a(n) for n = 1..10000
Eckford Cohen, A property of Dedekind's psi-function, Proceedings of the American Mathematical Society, Vol. 12, No. 6 (1961), p. 996.

Cf. A000010, A001694, A002618 (a subsequence), A065485, A082695, A112526, A323332.

EulerPhi /@ Join[{1}, Select[Range@ 1200, Min@ FactorInteger[#][[All, 2]] > 1 &]] (* after Harvey P. Dale at A001694 *)

lista(nn) = apply(x->eulerphi(x), select(x->ispowerful(x), vector(nn, k, k))); \\ Michel Marcus, Jan 11 2019

A047918 Triangular array read by rows: a(n,k) = Sum_{d|k} mu(d)*U(n,k/d) if k|n else 0, where U(n,k) = A047916(n,k) (1<=k<=n).

Original entry on oeis.org

1, 2, 0, 6, 0, 0, 8, 0, 0, 16, 20, 0, 0, 0, 100, 12, 24, 36, 0, 0, 648, 42, 0, 0, 0, 0, 0, 4998, 32, 32, 0, 320, 0, 0, 0, 39936, 54, 0, 270, 0, 0, 0, 0, 0, 362556, 40, 160, 0, 0, 3800, 0, 0, 0, 0, 3624800, 110, 0, 0, 0, 0, 0, 0, 0, 0, 0, 39916690, 48, 96

Offset: 1

N. J. A. Sloane

J. E. A. Steggall, On the numbers of patterns which can be derived from certain elements, Mess. Math., 37 (1907), 56-61.

Reinhard Zumkeller, Rows n = 1..125 of triangle, flattened
C. L. Mallows and N. J. A. Sloane, Notes on A002618, A002619, etc.
N. J. A. Sloane, Notes on A002618, A002619, etc.
J. E. A. Steggall, On the numbers of patterns which can be derived from certain elements, Mess. Math., 37 (1907), 56-61.
J. E. A. Steggall, On the numbers of patterns which can be derived from certain elements, Mess. Math., 37 (1907), 56-61. [Annotated scanned copy. Note that the scanned pages are out of order]

Cf. A008683, A027750, A225817.

a047918 n k = sum [a008683 (fromIntegral d) * a047916 n (k `div` d) |
                   mod n k == 0, d <- [1..k], mod k d == 0]
a047918_row n = map (a047918 n) [1..n]
a047918_tabl = map a047918_row [1..]
-- Reinhard Zumkeller, Mar 19 2014

U[n_, k_] := If[ Divisible[n, k], EulerPhi[n/k]*(n/k)^k*k!, 0]; a[n_, k_] := Sum[ If[ Divisible[n, k], MoebiusMu[d]*U[n, k/d], 0], {d, Divisors[k]}]; Flatten[ Table[ a[n, k], {n, 1, 12}, {k, 1, n}]] (* Jean-François Alcover, May 04 2012 *)

Offset corrected by Reinhard Zumkeller, Mar 19 2014

A053192 a(n) is the cototient of n^3.

Original entry on oeis.org

0, 4, 9, 32, 25, 144, 49, 256, 243, 600, 121, 1152, 169, 1568, 1575, 2048, 289, 3888, 361, 4800, 3969, 5808, 529, 9216, 3125, 9464, 6561, 12544, 841, 19800, 961, 16384, 14157, 20808, 13475, 31104, 1369, 28880, 22815, 38400, 1681, 52920, 1849, 46464

Offset: 1

Labos Elemer, Mar 02 2000

For n^k, n^k - EulerPhi(n^k) = n^(k-1)*(n-EulerPhi(n)), or cototient(n^k) = n^(k-1)*cototient(n). A similar relation holds for Euler totient function.

Vincenzo Librandi, Table of n, a(n) for n = 1..1000

Cf. A000010, A051953, A002618, A053650, A053191, A001248, A229099.

[n^3-EulerPhi(n^3): n in [1..44]]; // Vincenzo Librandi, Jul 28 2013

Table[(n^3 - EulerPhi[n^3]), {n, 1, 50}] (* Vincenzo Librandi, Jul 27 2013 *)

a(n) = n^3 - eulerphi(n^3) \\ Michel Marcus, Jul 26 2013

a(n) = n^2*Cototient(n) = A051953(n^3) = n^3 - EulerPhi(n^3) = Cototient(n^3).
a(prime(n)) = A051953(prime(n)^3) = A001248(n).
Sum_{k=1..n} a(k) ~ c * n^4 / 4, where c = 1 - 6/Pi^2 (A229099). - Amiram Eldar, Dec 15 2023

A058161 Number of labeled cyclic groups with a fixed identity.

Original entry on oeis.org

1, 1, 1, 3, 6, 60, 120, 1260, 6720, 90720, 362880, 9979200, 39916800, 1037836800, 10897286400, 163459296000, 1307674368000, 59281238016000, 355687428096000, 15205637551104000, 202741834014720000, 5109094217170944000, 51090942171709440000

Offset: 1

Christian G. Bower, Nov 14 2000

nonn

Degree of Lagrange resolvent of polynomial of n-th degree. Equals degree of symmetric group of order n divided by order of metacyclic group of order n. - Artur Jasinski, Jan 22 2008

			a(4)=3 because we have: <(1234)> = <(1432)>,  <(1243)> = <(1342)>,  <(1324)> = <(1423)>. - _Geoffrey Critzer_, Sep 07 2015

J. L. Lagrange, Oeuvres, Vol. III Paris 1869.

Index entries for sequences related to groups

a(n) = A000142(n-1)/A000010(n) = A034381(n)/n.
Cf. A058162, A058163.
Cf. A002618.

Table[n!/(n EulerPhi[n]), {n, 1, 20}] (* Artur Jasinski, Jan 22 2008 *)

a(n) = (n-1)!/phi(n).

a(n) = n!/A002618(n) - Artur Jasinski, Jan 22 2008

A082473 Numbers n such that n = phi(x)*core(x) for some x <= n, where phi(x) is the Euler totient function and core(x) the squarefree part of x.

Original entry on oeis.org

1, 2, 6, 8, 12, 20, 32, 40, 42, 48, 54, 84, 108, 110, 120, 128, 156, 160, 192, 220, 240, 252, 272, 312, 336, 342, 432, 486, 500, 504, 506, 512, 544, 640, 660, 684, 768, 812, 840, 880, 930, 936, 960, 972, 1000, 1012, 1080, 1248, 1320, 1332, 1344, 1624, 1632

Offset: 1

Benoit Cloitre, Apr 27 2003

nonn

Also numbers n such that n = y*phi(y) for a unique positive integer y (see A194507). - Franz Vrabec, Aug 27 2011

Sequence A002618 sorted into ascending order; also A327171 sorted into ascending order, with duplicate terms removed. Indices of nonzero terms in A327170 and in A327172. - Antti Karttunen, Sep 29 2019

József Sándor and Borislav Crstici, Handbook of Number theory II, Kluwer Academic Publishers, 2004, Chapter 3, p. 224.

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..1000 from Alois P. Heinz)
Walther Janous, Problem 6588, Advanced Problems, The American Mathematical Monthly, Vol. 95, No. 10 (1988), p. 963; How Often is n*phi(n) <= x^2?, Solution to Problem 6588, ibid., Vol. 98, No. 5 (1991), pp. 446-448.

Cf. A000010, A002618, A007913, A194507, A327170, A327171, A327172.

With[{nn = 1700}, TakeWhile[Union@ Array[EulerPhi[#] (Sqrt@ # /. (c_: 1) a_^(b_: 0) :> (c a^b)^2) &, nn], # <= nn &]] (* Michael De Vlieger, Sep 29 2019, after Bill Gosper at A007913 *)

isok(n) = {for (x=1, n, if (eulerphi(x)*core(x) == n, return (1));); return (0);} \\ Michel Marcus, Dec 04 2013

From Antti Karttunen, Sep 29 2019: (Start)
a(n) = A002618(A194507(n)).
A327172(a(n)) = A194507(n).
(End)
The number of terms not exceeding x is ~ c * sqrt(x), where c = Product_{p prime} (1 + 1/sqrt(p*(p-1)) - 1/p) = 1.3651304521... (Janous, 1988). - Amiram Eldar, Mar 10 2021

cp's OEIS Frontend

A011755 a(n) = Sum_{k=1..n} k*phi(k).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A238533 Number of solutions to gcd(x^2 + y^2 + z^2 + t^2 + h^2, n) = 1 with x,y,z,t,h in [0,n-1].

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A262311 Number of ordered ways to write n = x^2 + y^2 + phi(z^2) (0 <= x <= y and z > 0) with y or z prime, where phi(.) is Euler's totient function given by A000010.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A053650 Cototient function of n^2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

GAP

Haskell

Magma

Mathematica

PARI

Sage

Formula

A047916 Triangular array read by rows: a(n,k) = phi(n/k)*(n/k)^k*k! if k|n else 0 (1<=k<=n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

A323333 The Euler phi function values of the powerful numbers, A000010(A001694(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

A047918 Triangular array read by rows: a(n,k) = Sum_{d|k} mu(d)*U(n,k/d) if k|n else 0, where U(n,k) = A047916(n,k) (1<=k<=n).

Views

Author

Keywords

References

Links

Crossrefs

Programs

Haskell

Mathematica

A047916 Triangular array read by rows: a(n,k) = phi(n/k)(n/k)^kk! if k|n else 0 (1<=k<=n).