A115000 -id:A115000 - cp's OEIS frontend

A007434 Jordan function J_2(n) (a generalization of phi(n)).

1, 3, 8, 12, 24, 24, 48, 48, 72, 72, 120, 96, 168, 144, 192, 192, 288, 216, 360, 288, 384, 360, 528, 384, 600, 504, 648, 576, 840, 576, 960, 768, 960, 864, 1152, 864, 1368, 1080, 1344, 1152, 1680, 1152, 1848, 1440, 1728, 1584, 2208, 1536

Offset: 1

N. J. A. Sloane

Number of points in the bicyclic group Z/mZ X Z/mZ whose order is exactly m. - George J. Schaeffer (gschaeff(AT)andrew.cmu.edu), Mar 14 2006
Number of irreducible fractions among {(u+v*i)/n : 1 <= u, v <= n} with i = sqrt(-1), where a fraction (u+v*i)/n is called irreducible if and only if gcd(u, v, n) = 1. - Reinhard Zumkeller, Aug 20 2005
The weight of the n-th polynomial for the analog of cyclotomic polynomials for elliptic divisibility sequences. That is, let the weight of b1 = 1, b2 = 3, b3 = 8, b4 = 12 and let e1 = b1, e2 = b2*b1, e3 = b3*b1, e4 = b2*b4*b1, e5 = (b2^4*b4 - b3^3)*b1 = b5*e1, and so on, be an elliptic divisibility sequence. Then weight of e2 = 4, e3 = 9, e4 = 16, e5 = 25, where weight of en is n^2 in general, while weight of bn is a(n). - Michael Somos, Aug 12 2008
J_2(n) divides J_{2k}(n). J_2(n) gives the number of 2-tuples (x1,x2), such that 1 <= x1, x2 <= n and gcd(x1, x2, n) = 1. - Enrique Pérez Herrero, Mar 05 2011
From Jianing Song, Apr 06 2019: (Start)
Let k be any quadratic field such that all prime factors of n are inert in k, O_k be the corresponding ring of integers and G(n) = (O_k/nO_k)* be the multiplicative group of integers in O_k modulo n, then a(n) is the number of elements in G(n). The exponent of G(n) is A306933(n). [Equivalently, G(p^e) can be defined as (Z_{p^2}/p^eZ_{p^2})*, where Z_{p^2} is the ring of integers of the field Q_{p^2} (with a unique maximal ideal pZ_{p^2}), and Q_{p^2} is the unique unramified quadratic extension of the p-adic field Q_p. For the group structure of G(p^e), see A306933. - Jianing Song, Jun 19 2025]
For n >= 5, a(n) is divisible by 24. (End)
The Del Centina article on page 106 mentions a formula by Halphen denoted by phi(n)T(n). - Michael Somos, Feb 05 2021

			a(4) = 12 because the divisors of 4 being 1, 2, 4, we find that phi(1)*phi(4/1)*(4/1) = 8, phi(2)*phi(4/2)*(4/2) = 2, phi(4)*phi(4/4)*(4/4) = 2 and 8 + 2 + 2 = 12.
G.f. = x + 3*x^2 + 8*x^3 + 12*x^4 + 24*x^5 + 24*x^6 + 48*x^7 + 48*x^8 + 72*x^9 + ...

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 199, #3.
A. Del Centina, Poncelet's porism: a long story of renewed discoveries, I, Hist. Exact Sci. (2016), v. 70, p. 106.
L. E. Dickson (1919, repr. 1971). History of the Theory of Numbers I. Chelsea. p. 147.
P. J. McCarthy, Introduction to Arithmetical Functions, Universitext, Springer, New York, NY, USA, 1986.
G. Pólya and G. Szegő, Problems and Theorems in Analysis I (Springer 1924, reprinted 1972), Part Eight, Chap. 1, Section 6, Problem 64.
M. Ram Murty (2001). Problems in Analytic Number Theory. Graduate Texts in Mathematics. 206. Springer-Verlag. p. 11.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 1..1000
Sukumar Das Adhikari and A. Sankaranarayanan, On an error term related to the Jordan totient function Jk(n), Journal of Number Theory Volume 34, Issue 2, February 1990, Pages 178-188.
Dorin Andrica and Mihai Piticari, On Some Extensions Of Jordan's Arithmetic Functions, Proceedings of the International Conference on Theory and Applications of Mathematics and Informatics - ICTAMI 2003, Alba Iulia.
E. Artal Bartolo, P. D. González Pérez, M. González Villa, and E. León-Cardenal, On a suspension formula for Denef-Loeser zeta functions, arXiv:2502.05022 [math.AG], 2025. See p. 19.
Theo Douvropoulos, Joel Brewster Lewis, and Alejandro H. Morales, Hurwitz numbers for reflection groups III: Uniform formulas, arXiv:2308.04751 [math.CO], 2023, see p. 32.
F. A. Lewis and others, Problem 4002, Amer. Math. Monthly, Vol. 49, No. 9, Nov. 1942, pp. 618-619.
H. Li and T. MacHenry, Permanents and Determinants, Weighted Isobaric Polynomials, and Integer Sequences, J. Int. Seq. 16 (2013) #13.3.5, example 38.
MathOverflow, Averages of euler-phi function and similar.
Carl-Fredrik Nyberg-Brodda, On congruence subgroups of SL_2(Z[1/p]) generated by two parabolic elements, arXiv:2312.11258 [math.GR], 2023.
Nittiya Pabhapote and Vichian Laohakosol, Combinatorial Aspects of the Generalized Euler's Totient, International Journal of Mathematics and Mathematical Sciences, Volume 2010 (2010), Article ID 648165, 15 p.
Wolfgang Schramm, The Fourier transform of functions of the greatest common divisor, Electronic Journal of Combinatorial Number Theory A50 (8(1)), 2008.
N. J. A. Sloane, Transforms.
S. Thajoddin and S. Vangipuram, A Note On Jordan's Totient Function, Indian J. Pure Appl. Math, 1988.
László Tóth, Multiplicative arithmetic functions of several variables: a survey, arXiv preprint arXiv:1310.7053 [math.NT], 2013.
Wikipedia, Jordan's totient function.
Index to divisibility sequences

Cf. A000056, A000290, A001065, A001615, A027750, A046970, A115000, A134675.
Cf. A059379 and A059380 (triangle of values of J_k(n)).
Cf. A000010 (J_1), this sequence (J_2), A059376 (J_3), A059377 (J_4), A059378 (J_5).
Cf. A002117, A088453, A301875, A301876, A321879 (partial sums).

a007434 n = sum $ zipWith3 (\x y z -> x * y * z)
                  tdivs (reverse tdivs) (reverse divs)
                  where divs = a027750_row n;  tdivs = map a000010 divs
-- Reinhard Zumkeller, Nov 24 2012

J := proc(n,k) local i,p,t1,t2; t1 := n^k; for p from 1 to n do if isprime(p) and n mod p = 0 then t1 := t1*(1-p^(-k)); fi; od; t1; end; # (with k = 2)
A007434 := proc(n)
    add(d^2*numtheory[mobius](n/d),d=numtheory[divisors](n)) ;
end proc: # R. J. Mathar, Nov 03 2015

jordanTotient[n_, k_:1] := DivisorSum[n, #^k*MoebiusMu[n/#] &] /; (n > 0) && IntegerQ[n]; Table[jordanTotient[n, 2], {n, 48}] (* Enrique Pérez Herrero, Sep 14 2010 *)
a[ n_] := If[ n < 1, 0, Sum[ d^2 MoebiusMu[ n/d], {d, Divisors @ n}]]; (* Michael Somos, Jan 11 2014 *)
a[ n_] := If[ n < 2, Boole[ n == 1], n^2 (Times @@ ((1 - 1/#[[1]]^2) & /@ FactorInteger @ n))]; (* Michael Somos, Jan 11 2014 *)
jordanTotient[n_Integer?Positive, r_:1] := DirichletConvolve[MoebiusMu[K], K^r, K, n]; Table[jordanTotient[n, 2], {n, 48}] (* Jan Mangaldan, Jun 03 2016 *)

{a(n) = if( n<1, 0, sumdiv(n, d, d^2 * moebius(n / d)))}; /* Michael Somos, Mar 20 2004 */

{a(n) = if( n<1, 0, direuler( p=2, n, (1 - X) / (1 - X*p^2))[n])}; /* Michael Somos, Jan 11 2014 */

seq(n) = dirmul(vector(n,k,k^2), vector(n,k,moebius(k)));
seq(48)  \\ Gheorghe Coserea, May 11 2016

jordan(n,k)=my(a=n^k);fordiv(n,i,if(isprime(i),a*=(1-1/(i^k))));a  \\ Roderick MacPhee, May 05 2017

from math import prod
from sympy import factorint
def A007434(n): return prod(p**(e-1<<1)*(p**2-1) for p, e in factorint(n).items()) # Chai Wah Wu, Jan 29 2024

Moebius transform of squares.
Multiplicative with a(p^e) = p^(2e) - p^(2e-2). - Vladeta Jovovic, Jul 26 2001
a(n) = Sum_{d|n} d^2 * mu(n/d). - Benoit Cloitre, Apr 05 2002
a(n) = n^2 * Product_{p|n} (1-1/p^2). - Tom Edgar, Jan 07 2015
a(n) = Sum_{d|n} phi(d)*phi(n/d)*n/d; Sum_{d|n} a(d) = n^2. - Reinhard Zumkeller, Aug 20 2005
Dirichlet generating function: zeta(s-2)/zeta(s). - Franklin T. Adams-Watters, Sep 11 2005
Dirichlet inverse of A046970. - Michael Somos, Jan 11 2014
a(n) = a(n^2)/n^2. - Enrique Pérez Herrero, Sep 14 2010
a(n) = A000010(n) * A001615(n).
If n > 1, then 1 > a(n)/n^2 > 1/zeta(2). - Enrique Pérez Herrero, Jul 14 2011
a(n) = Sum_{d|n} phi(n^2/d)*mu(d)^2. - Enrique Pérez Herrero, Jul 24 2012
a(n) = Sum_{k = 1..n} gcd(k, n)^2 * cos(2*Pi*k/n). - Enrique Pérez Herrero, Jan 18 2013
a(1) + a(2) + ... + a(n) ~ 1/(3*zeta(3))*n^3 + O(n^2). Lambert series Sum_{n >= 1} a(n)*x^n/(1 - x^n) = x*(1 + x)/(1 - x)^3. - Peter Bala, Dec 23 2013
n * a(n) = A000056(n). - Michael Somos, Mar 20 2004
a(n) = 24 * A115000(n) unless n < 5. - Michael Somos, Aug 12 2008
a(n) = A001065(n) - A134675(n). - Conjectured by John Mason and proved by Max Alekseyev, Jan 07 2015
a(n) = Sum_{k=1..n} gcd(n, k) * phi(gcd(n, k)), where phi(k) is the Euler totient function. - Daniel Suteu, Jun 15 2018
G.f.: Sum_{k>=1} mu(k)*x^k*(1 + x^k)/(1 - x^k)^3. - Ilya Gutkovskiy, Oct 24 2018
Sum_{k>=1} 1/a(k) = Product_{primes p} (1 + p^2/(p^2 - 1)^2) = 1.81078147612156295224312590448625180897250361794500723589001447178002894356... - Vaclav Kotesovec, Sep 19 2020
Limit_{n->oo} (1/n) * Sum_{k=1..n} a(k)/k^2 = 1/zeta(3) (A088453). - Amiram Eldar, Oct 12 2020
From Richard L. Ollerton, May 09 2021: (Start)
a(n) = Sum_{k=1..n} (n/gcd(n,k))^2*mu(gcd(n,k))/phi(n/gcd(n,k)).
a(n) = Sum_{k=1..n} gcd(n,k)^2*mu(n/gcd(n,k))/phi(n/gcd(n,k)).
a(n) = Sum_{k=1..n} n*phi(gcd(n,k))/gcd(n,k).
a(n) = Sum_{k=1..n} phi(n*gcd(n,k))*mu(n/gcd(n,k))^2.
a(n) = Sum_{k=1..n} phi(n^2/gcd(n,k))*mu(gcd(n,k))^2*phi(gcd(n,k))/phi(n/gcd(n,k)). (End)
a(n) = Sum_{k = 1..n} phi(gcd(n, k)^2) = Sum_{d divides n} phi(d^2)*phi(n/d). - Peter Bala, Jan 17 2024
a(n) = Sum_{1 <= i, j <= n, lcm(i, j) = n} phi(i)*phi(j). See Tóth, p. 14. - Peter Bala, Jan 29 2024
Conjecture: a(n) = lim_{k->oo} (n^(2*(k + 1)))/A001157(n^k). - Velin Yanev, Dec 04 2024

Thanks to Michael Somos for catching an error in this sequence.

A079612 Largest number m such that a^n == 1 (mod m) whenever a is coprime to m.

Original entry on oeis.org

2, 24, 2, 240, 2, 504, 2, 480, 2, 264, 2, 65520, 2, 24, 2, 16320, 2, 28728, 2, 13200, 2, 552, 2, 131040, 2, 24, 2, 6960, 2, 171864, 2, 32640, 2, 24, 2, 138181680, 2, 24, 2, 1082400, 2, 151704, 2, 5520, 2, 1128, 2, 4455360, 2, 264, 2, 12720, 2, 86184, 2, 13920

Offset: 1

N. J. A. Sloane, Jan 29 2003

nonn

a(m) divides the Jordan function J_m(n) for all n except when n is a prime dividing a(m) or m=2, n=4; it is the largest number dividing all but finitely many values of J_m(n). For m > 0, a(m) also divides Sum_{k=1}^n J_m(k) for n >= the largest exceptional value. - Franklin T. Adams-Watters, Dec 10 2005

The numbers m with this property are the divisors of a(n) that are not divisors of a(r) for r

R. C. Vaughan and T. D. Wooley, Waring's problem: a survey, pp. 285-324 of Surveys in Number Theory (Urbana, May 21, 2000), ed. M. A. Bennett et al., Peters, 2003. (The function K(n), see p. 303.)

Antti Karttunen, Table of n, a(n) for n = 1..16384
Shigeki Akiyama and Hajime Kaneko, Curious congruences on cyclotomic polynomials, arXiv:2204.11267 [math.NT], 2022. See Proposition 1 p. 5-6.
P. J. Cameron and D. A. Preece, Notes on primitive lambda-roots, 2009. See lambda*() in theorem 5.2 (b) p. 8.
Joris van der Hoeven and Grégoire Lecerf, Sparse polynomial interpolation. Exploring fast heuristic algorithms over finite fields, Simon Fraser University (BC Canada) / Institut Polytechnique de Paris (France, 2019) hal-02382117.
R. C. Vaughan and T. D. Wooley, Waring's problem: a survey, The function K(n), see p. 19.

Cf. A006863 (bisection except for initial term); A059379 (Jordan function).
Cf. A075180, A115000, A115001, A115002, A115003.
Cf. A143407, A143408, A185633, A322315.

a(n) = {if (n%2, 2, res = 1; forprime(p=2, n+1, if (!(n % (p-1)), t = valuation(n, p); if (p==2, if (t, res *= p^(t+2)), res *= p^(t+1)););); res;);} \\ Michel Marcus, May 12 2018

a(n) = 2 for n odd; for n even, a(n) = product of 2^(t+2) (where 2^t exactly divides n) and p^(t+1) (where p runs through all odd primes such that p-1 divides n and p^t exactly divides n).
From Antti Karttunen, Dec 19 2018: (Start)
a(n) = A185633(n)*(2-A000035(n)).
It also seems that for n > 1, a(n) = 2*A075180(n-1). (End)
We have 2*A075180(2n-1) = A006863(n) by definition, and A006863(n) = a(2n) by the comments in A006863. Hence a(n) = 2*A075180(n-1) for all even n. For all odd n > 1, we have a(n) = 2, which is also equal to 2*A075180(n-1). So the formula above is true. - Jianing Song, Apr 05 2021

Edited by Franklin T. Adams-Watters, Dec 10 2005
Definition corrected by T. D. Noe, Aug 13 2008
Rather arbitrary term a(0) removed by Max Alekseyev, May 27 2010

A029937 Genus of modular curve X_1(n).

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 2, 1, 1, 2, 5, 2, 7, 3, 5, 6, 12, 5, 12, 10, 13, 10, 22, 9, 26, 17, 21, 21, 25, 17, 40, 28, 33, 25, 51, 25, 57, 36, 41, 45, 70, 37, 69, 48, 65, 55, 92, 52, 81, 61, 85, 78, 117, 57, 126, 91, 97

Offset: 1

N. J. A. Sloane

Also the dimension of the space of cusp forms of weight two on Gamma1(n). [Steven Finch, Apr 03 2009]

F. Hirzebruch et al., Manifolds and Modular Forms, Vieweg, 2nd ed. 1994, p. 161.

T. D. Noe, Table of n, a(n) for n = 1..1000
S. R. Finch, Modular forms on SL_2(Z), December 28, 2005. [Cached copy, with permission of the author]
Chang Heon Kim, Ja Kyung Koo, On the genus of some modular curves of level N, Bull Austral. Math. Soc. 54 (1996) 291-297.
A. V. Sutherland, Torsion subgroups of elliptic curves over number fields, 2012. - From _N. J. A. Sloane_, Feb 03 2013

Cf. A001617, A029938. [Steven Finch, Apr 03 2009]

with(numtheory); A029937 := proc(n) local i,j; j := 1+(1/24)*phi(n)*A001615(n); for i in divisors(n) do j := j-(1/4)*phi(i)*phi(n/i) od; j; end;

a[n_ /; n<5] = 0; a[n_] := 1+Sum[d^2*MoebiusMu[n/d]/24 - EulerPhi[d]*EulerPhi[n/d]/4, {d, Divisors[n]}]; Table[a[n], {n, 1, 100}] (* Jean-François Alcover, Jan 13 2014 *)

A029935(n) = {
  my(f = factor(n), fsz = matsize(f)[1],
     g = prod(k=1, fsz, f[k,1]),
     h = prod(k=1, fsz, sqr(f[k,1]-1)*f[k,2] + sqr(f[k,1])-1));
  return(h*n\sqr(g));
};
a(n) = {
  if (n < 5, return(0));
  my(f = factor(n), fsz = matsize(f)[1],
     g = prod(k=1, fsz, f[k,1]),
     h = prod(k=1, fsz, sqr(f[k,1]) - 1));
  return(1 + sqr(n\g)*h/24 - A029935(n)/4);
};
vector(63, n, a(n))  \\ Gheorghe Coserea, Oct 23 2016

a(n) = 1 + A115000(n) - A029935(n)/4, n > 4. [Kim and Koo, Theorem 1]

A115001 Sum_{k=1}^n J_2(k)/24.

Original entry on oeis.org

1, 2, 3, 5, 7, 10, 13, 18, 22, 29, 35, 43, 51, 63, 72, 87, 99, 115, 130, 152, 168, 193, 214, 241, 265, 300, 324, 364, 396, 436, 472, 520, 556, 613, 658, 714, 762, 832, 880, 957, 1017, 1089, 1155, 1247, 1311, 1409

Offset: 4

Franklin T. Adams-Watters, Dec 10 2005

nonn

See A115000 for further information.

A115002 J_4(n)/240.

Original entry on oeis.org

5, 10, 16, 27, 39, 61, 80, 119, 150, 208, 256, 348, 405, 543, 624, 800, 915, 1166, 1280, 1625, 1785, 2187, 2400, 2947, 3120, 3848, 4096, 4880, 5220, 6240, 6480, 7809, 8145, 9520, 9984, 11774, 12000

Offset: 6

Franklin T. Adams-Watters, Dec 10 2005

nonn

See A115000 for further information.

A115003 Sum_{k=1}^n J_4(k)/240.

Original entry on oeis.org

4, 9, 19, 35, 62, 101, 162, 242, 361, 511, 719, 975, 1323, 1728, 2271, 2895, 3695, 4610, 5776, 7056, 8681, 10466, 12653, 15053, 18000, 21120, 24968, 29064, 33944, 39164, 45404, 51884, 59693, 67838

Offset: 5

Franklin T. Adams-Watters, Dec 10 2005

nonn

See A115000 for further information.

Showing 1-6 of 6 results.

cp's OEIS Frontend

A007434 Jordan function J_2(n) (a generalization of phi(n)).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

PARI

PARI

Python

Formula

Extensions

A079612 Largest number m such that a^n == 1 (mod m) whenever a is coprime to m.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

Formula

Extensions

A029937 Genus of modular curve X_1(n).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A115001 Sum_{k=1}^n J_2(k)/24.

Views

Author

Keywords

Comments

A115002 J_4(n)/240.

Views

Author

Keywords

Comments

A115003 Sum_{k=1}^n J_4(k)/240.

Views

Author

Keywords

Comments