This site is supported by donations to The OEIS Foundation.



(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)

%I M2315 N0915

%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 denoted by psi(n) by Fricke. - _Michael Somos_, Nov 10 2006

%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

%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, 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, 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) = sum(d|n,mu(n/d)*d^(b-1)/phi(n)), 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

%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 *)

%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

%Y Cf. A003051, A003050, A054345, A000082, A033196, A000203, A063659, A160889, A160891, A173290, A082020, A027748, A124010, A019269, A175836.

%Y Cf. A156303, A301594.

%Y See also A291784.

%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 | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 16 19:49 EST 2019. Contains 320167 sequences. (Running on oeis4.)