login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001615 Dedekind psi function: n * Product_{p|n, p prime} (1 + 1/p).
(Formerly M2315 N0915)
299

%I M2315 N0915 #282 Jan 28 2024 08:52:53

%S 1,3,4,6,6,12,8,12,12,18,12,24,14,24,24,24,18,36,20,36,32,36,24,48,30,

%T 42,36,48,30,72,32,48,48,54,48,72,38,60,56,72,42,96,44,72,72,72,48,96,

%U 56,90,72,84,54,108,72,96,80,90,60,144,62,96,96,96,84,144,68,108,96

%N Dedekind psi function: n * Product_{p|n, p prime} (1 + 1/p).

%C Number of primitive sublattices of index n in generic 2-dimensional lattice; also index of Gamma_0(n) in SL_2(Z).

%C A generic 2-dimensional lattice L = <V,W> consists of all vectors of the form mV + nW, (m,n integers). A sublattice S = <aV+bW, cV+dW> has index |ad-bc| and is primitive if gcd(a,b,c,d) = 1. The generic lattice L has precisely a(2) = 3 sublattices of index 2, namely <2V,W>, <V,2W> and <V+W,2V> (which = <V+W,2W>) and so on for other indices.

%C The sublattices of index n are in 1-to-1 correspondence with matrices [a b; 0 d] with a>0, ad=n, b in [0..d-1]. The number of these is Sum_{d|n} = sigma(n), which is A000203. A sublattice is primitive if gcd(a,b,d) = 1; the number of these is n * product_{p|n} (1+1/p), which is the present sequence.

%C SL_2(Z) = Gamma is the group of all 2 X 2 matrices [a b; c d] where a,b,c,d are integers with ad-bc = 1 and Gamma_0(N) is usually defined as the subgroup of this for which N|c. But conceptually Gamma is best thought of as the group of (positive) automorphisms of a lattice <V,W>, its typical element taking V -> aV + bW, W -> cV + dW and then Gamma_0(N) can be defined as the subgroup consisting of the automorphisms that fix the sublattice <NV,W> of index N. - _J. H. Conway_, May 05 2001

%C Dedekind proved that if n = k_i*j_i for i in I represents all the ways to write n as a product, and e_i=gcd(k_i,j_i), then a(n)= sum(k_i / (e_i * phi(e_i)), i in I ) [cf. Dickson, History of the Theory of Numbers, Vol. 1, p. 123].

%C Also a(n)= number of cyclic subgroups of order n in an Abelian group of order n^2 and type (1,1) (Fricke). - _Len Smiley_, Dec 04 2001

%C The polynomial degree of the classical modular equation of degree n relating j(z) and j(nz) is psi(n) (Fricke). - _Michael Somos_, Nov 10 2006; clarified by _Katherine E. Stange_, Mar 11 2022

%C The Mobius transform of this sequence is A063659. - _Gary W. Adamson_, May 23 2008

%C The inverse Mobius transform of this sequence is A060648. - _Vladeta Jovovic_, Apr 05 2009

%C The Dirichlet inverse of this sequence is A008836(n) * A048250(n). - _Álvar Ibeas_, Mar 18 2015

%C The Riemann Hypothesis is true if and only if a(n)/n - e^gamma*log(log(n)) < 0 for any n > 30. - _Enrique Pérez Herrero_, Jul 12 2011

%C The Riemann Hypothesis is also equivalent to another inequality, see the Sole and Planat link. - _Thomas Ordowski_, May 28 2017

%C An infinitary analog of this sequence is the sum of the infinitary divisors of n (see A049417). - _Vladimir Shevelev_, Apr 01 2014

%C Problem: are there composite numbers n such that n+1 divides psi(n)? - _Thomas Ordowski_, May 21 2017

%C The sum of divisors d of n such that n/d is squarefree. - _Amiram Eldar_, Jan 11 2019

%C Psi(n)/n is a new maximum for each primorial (A002110) [proof in link: Patrick Sole and Michel Planat, Proposition 1 page 2]. - _Bernard Schott_, May 21 2020

%C From _Jianing Song_, Nov 05 2022: (Start)

%C a(n) is the number of subgroups of C_n X C_n that are isomorphic to C_n, where C_n is the cyclic group of order n. Proof: the number of elements of order n in C_n X C_n is A007434(n) (they are the elements of the form (a,b) in C_n X C_n where gcd(a,b,n) = 1), and each subgroup isomorphic to C_n contains phi(n) generators, so the number of such subgroups is A007434(n)/phi(n) = a(n).

%C The total number of order-n subgroups of C_n X C_n is A000203(n). (End)

%D Tom Apostol, Intro. to Analyt. Number Theory, page 71, Problem 11, where this is called phi_1(n).

%D David A. Cox, "Primes of the Form x^2 + n y^2", Wiley, 1989, p. 228.

%D R. Fricke, Die elliptischen Funktionen und ihre Anwendungen, Teubner, 1922, Vol. 2, see p. 220.

%D Richard K. Guy, Unsolved Problems in Number Theory, 3rd Edition, Springer, 2004. See Section B41, p. 147.

%D B. Schoeneberg, Elliptic Modular Functions, Springer-Verlag, NY, 1974, p. 79.

%D G. Shimura, Introduction to the Arithmetic Theory of Automorphic Functions, Princeton, 1971, see p. 25, Eq. (1).

%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 T. D. Noe and N. J. A. Sloane, <a href="/A001615/b001615.txt">Table of n, a(n) for n = 1..10000</a>

%H O. Bordelles and B. Cloitre, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL16/Bordelles/bord14.html">An Alternating Sum Involving the Reciprocal of Certain Multiplicative Functions</a>, J. Int. Seq. 16 (2013) #13.6.3.

%H Harriet Fell, Morris Newman, and Edward Ordman, <a href="http://dx.doi.org/10.6028/jres.067B.006">Tables of genera of groups of linear fractional transformations</a>, J. Res. Nat. Bur. Standards Sect. B 67B 1963 61-68.

%H M. Hampejs, N. Holighaus, L. Toth and C. Wiesmeyr, <a href="http://arxiv.org/abs/1211.1797">Representing and counting the subgroups of the group Z_m X Z_n</a>, arXiv:1211.1797 [math.GR], 2012.

%H W. Hürlimann, <a href="http://dx.doi.org/10.18642/jantaa_7100121599">Dedekind's arithmetic function and primitive four squares counting functions</a>, Journal of Algebra, Number Theory: Advances and Applications 14:2 (2015), 73-88.

%H F. A. Lewis et al., <a href="http://www.jstor.org/stable/2303350">Problem 4002</a>, Amer. Math. Monthly, Vol. 49, No. 9, Nov. 1942, pp. 618-619.

%H E. Pérez Herrero, <a href="http://psychedelic-geometry.blogspot.com.es/2012/06/recycling-hardy-wright.html">Recycling Hardy & Wright</a>, Average Order of Dedekind Psi Function, Psychedelic Geometry Blogspot.

%H Michel Planat, <a href="http://arxiv.org/abs/1010.3239">Riemann hypothesis from the Dedekind psi function</a>, arXiv:1010.3239 [math.GM], 2010.

%H Patrick Sole and Michel Planat, <a href="http://arxiv.org/abs/1011.1825">Extreme values of the Dedekind Psi function</a>, to appear in Journal of Combinatorics and Number Theory, arXiv:1011.1825 [math.NT], 2010-2011.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/DedekindFunction.html">Dedekind Function</a>

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Dedekind_psi_function">Dedekind psi function</a>

%H <a href="/index/Cor#core">Index entries for "core" sequences</a>

%H <a href="/index/Su#sublatts">Index entries for sequences related to sublattices</a>

%F Dirichlet g.f.: zeta(s) * zeta(s-1) / zeta(2*s). - _Michael Somos_, May 19 2000

%F Multiplicative with a(p^e) = (p+1)*p^(e-1). - _David W. Wilson_, Aug 01 2001

%F a(n) = A003557(n)*A048250(n) = n*A000203(A007947(n))/A007947(n). - _Labos Elemer_, Dec 04 2001

%F a(n) = n*Sum_{d|n} mu(d)^2/d, Dirichlet convolution of A008966 and A000027. - _Benoit Cloitre_, Apr 07 2002

%F a(n) = Sum_{d|n} mu(n/d)^2 * d. - _Joerg Arndt_, Jul 06 2011

%F From _Enrique Pérez Herrero_, Aug 22 2010: (Start)

%F a(n) = J_2(n)/J_1(n) = J_2(n)/phi(n) = A007434(n)/A000010(n), where J_k is the k-th Jordan Totient Function.

%F a(n) = (1/phi(n))*Sum_{d|n} mu(n/d)*d^(b-1), for b=3. (End)

%F a(n) = n / Sum_{d|n} mu(d)/a(d). - _Enrique Pérez Herrero_, Jun 06 2012

%F a(n^k)= n^(k-1) * a(n). - _Enrique Pérez Herrero_, Jan 05 2013

%F If n is squarefree, then a(n) = A049417(n) = A000203(n). - _Vladimir Shevelev_, Apr 01 2014

%F a(n) = Sum_{d^2 | n} mu(d) * A000203(n/d^2). - _Álvar Ibeas_, Dec 20 2014

%F The average order of a(n) is 15*n/Pi^2. - _Enrique Pérez Herrero_, Jan 14 2012. See Apostol. - _N. J. A. Sloane_, Sep 04 2017

%F G.f.: Sum_{k>=1} mu(k)^2*x^k/(1 - x^k)^2. - _Ilya Gutkovskiy_, Oct 25 2018

%F a(n) = Sum_{d|n} 2^omega(d) * phi(n/d), Dirichlet convolution of A034444 and A000010. - _Daniel Suteu_, Mar 09 2019

%F From _Richard L. Ollerton_, May 07 2021: (Start)

%F a(n) = Sum_{k=1..n} 2^omega(gcd(n,k)).

%F a(n) = Sum_{k=1..n} 2^omega(n/gcd(n,k))*phi(gcd(n,k))/phi(n/gcd(n,k)). (End)

%F a(n) = abs(A158523(n)) = A158523(n) * A008836(n). - _Enrique Pérez Herrero_, Nov 07 2022

%e Let L = <V,W> be a 2-dimensional lattice. The 6 primitive sublattices of index 4 are generated by <4V,W>, <V,4W>, <4V,W+-V>, <2V+W,2W>, <2V,2W+V>. Compare A000203.

%e G.f. = x + 3*x^2 + 4*x^3 + 6*x^4 + 6*x^5 + 12*x^6 + 8*x^7 + 12*x^8 + 12*x^9 + ...

%p A001615 := proc(n) n*mul((1+1/i[1]),i=ifactors(n)[2]) end; # _Mark van Hoeij_, Apr 18 2012

%t Join[{1}, Table[n Times@@(1+1/Transpose[FactorInteger[n]][[1]]), {n,2,100}]] (* _T. D. Noe_, Jun 11 2006 *)

%t Table[DirichletConvolve[j, MoebiusMu[j]^2, j, n], {n, 100}] (* _Jan Mangaldan_, Aug 22 2013 *)

%t a[ n_] := If[ n < 1, 0, n Sum[ MoebiusMu[ d]^2 / d, {d, Divisors @ n}]]; (* _Michael Somos_, Jan 10 2015 *)

%t Table[n*Product[1 + 1/p, {p, Select[Divisors[n], PrimeQ]}], {n, 1, 100}] (* _Vaclav Kotesovec_, May 08 2021 *)

%o (PARI) {a(n) = if( n<1, 0, direuler( p=2, n, (1 + X) / (1 - p*X)) [n])};

%o (PARI) {a(n) = if( n<1, 0, n * sumdiv( n, d, moebius(d)^2 / d))}; /* _Michael Somos_, Nov 10 2006 */

%o (PARI) a(n)=my(f=factor(n)); prod(i=1,#f~, f[i,1]^f[i,2] + f[i,1]^(f[i,2]-1)) \\ _Charles R Greathouse IV_, Aug 22 2013

%o (PARI) a(n) = n * sumdivmult(n, d, issquarefree(d)/d) \\ _Charles R Greathouse IV_, Sep 09 2014

%o (Haskell)

%o import Data.Ratio (numerator)

%o a001615 n = numerator (fromIntegral n * (product $

%o map ((+ 1) . recip . fromIntegral) $ a027748_row n))

%o -- _Reinhard Zumkeller_, Jun 03 2013, Apr 12 2012

%o (Sage) def A001615(n) : return n*mul(1+1/p for p in prime_divisors(n))

%o [A001615(n) for n in (1..69)] # _Peter Luschny_, Jun 10 2012

%o (Magma) m:=75; R<x>:=PowerSeriesRing(Integers(), m); Coefficients(R!( (&+[MoebiusMu(k)^2*x^k/(1-x^k)^2: k in [1..2*m]]) )); // _G. C. Greubel_, Nov 23 2018

%o (Python 3.8+)

%o from math import prod

%o from sympy import primefactors

%o def A001615(n):

%o plist = primefactors(n)

%o return n*prod(p+1 for p in plist)//prod(plist) # _Chai Wah Wu_, Jun 03 2021

%Y Other sequences that count lattices/sublattices: A000203 (with primitive condition removed), A003050 (hexagonal lattice instead), A003051, A054345, A160889, A160891.

%Y Cf. A002110, A027748, A124010, A019269.

%Y Cf. A301594.

%Y Cf. A063659 (Möbius transform), A082020 (average order), A156303 (Euler transform), A173290 (partial sums), A175836 (partial products), A203444 (range).

%Y Cf. A210523 (record values).

%Y Algebraic combinations with other core sequences: A000082, A033196, A175732, A291784, A344695.

%Y Sequences of the form n^k * Product_ {p|n, p prime} (1 + 1/p^k) for k=0..10: A034444 (k=0), this sequence (k=1), A065958 (k=2), A065959 (k=3), A065960 (k=4), A351300 (k=5), A351301 (k=6), A351302 (k=7), A351303 (k=8), A351304 (k=9), A351305 (k=10).

%Y Cf. A082695 (Dgf at s=3), A339925 (Dgf at s=4).

%K nonn,easy,core,nice,mult

%O 1,2

%A _N. J. A. Sloane_

%E More terms from _Olivier Gérard_, Aug 15 1997

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 08:22 EDT 2024. Contains 371236 sequences. (Running on oeis4.)