# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/

Search: id:a001615
Showing 1-1 of 1

%I A001615 M2315 N0915 #282 Jan 28 2024 08:52:53
%S A001615 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 A001615 42,36,48,30,72,32,48,48,54,48,72,38,60,56,72,42,96,44,72,72,72,48,96,
%U A001615 56,90,72,84,54,108,72,96,80,90,60,144,62,96,96,96,84,144,68,108,96
%N A001615 Dedekind psi function: n * Product_{p|n, p prime} (1 + 1/p).
%C A001615 Number of primitive sublattices of index n in generic 2-dimensional lattice; also index of Gamma_0(n) in SL_2(Z).
%C A001615 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 A001615 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 A001615 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 A001615 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 A001615 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 A001615 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 A001615 The Mobius transform of this sequence is A063659. - _Gary W. Adamson_, May 23 2008
%C A001615 The inverse Mobius transform of this sequence is A060648. - _Vladeta Jovovic_, Apr 05 2009
%C A001615 The Dirichlet inverse of this sequence is A008836(n) * A048250(n). - _Álvar Ibeas_, Mar 18 2015
%C A001615 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 A001615 The Riemann Hypothesis is also equivalent to another inequality, see the Sole and Planat link. - _Thomas Ordowski_, May 28 2017
%C A001615 An infinitary analog of this sequence is the sum of the infinitary divisors of n (see A049417). - _Vladimir Shevelev_, Apr 01 2014
%C A001615 Problem: are there composite numbers n such that n+1 divides psi(n)? - _Thomas Ordowski_, May 21 2017
%C A001615 The sum of divisors d of n such that n/d is squarefree. - _Amiram Eldar_, Jan 11 2019
%C A001615 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 A001615 From _Jianing Song_, Nov 05 2022: (Start)
%C A001615 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 A001615 The total number of order-n subgroups of C_n X C_n is A000203(n). (End)
%D A001615 Tom Apostol, Intro. to Analyt. Number Theory, page 71, Problem 11, where this is called phi_1(n).
%D A001615 David A. Cox, "Primes of the Form x^2 + n y^2", Wiley, 1989, p. 228.
%D A001615 R. Fricke, Die elliptischen Funktionen und ihre Anwendungen, Teubner, 1922, Vol. 2, see p. 220.
%D A001615 Richard K. Guy, Unsolved Problems in Number Theory, 3rd Edition, Springer, 2004. See Section B41, p. 147.
%D A001615 B. Schoeneberg, Elliptic Modular Functions, Springer-Verlag, NY, 1974, p. 79.
%D A001615 G. Shimura, Introduction to the Arithmetic Theory of Automorphic Functions, Princeton, 1971, see p. 25, Eq. (1).
%D A001615 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A001615 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A001615 T. D. Noe and N. J. A. Sloane, <a href="/A001615/b001615.txt">Table of n, a(n) for n = 1..10000</a>
%H A001615 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 A001615 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 A001615 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 A001615 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 A001615 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 A001615 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 A001615 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 A001615 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 A001615 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/DedekindFunction.html">Dedekind Function</a>
%H A001615 Wikipedia, <a href="http://en.wikipedia.org/wiki/Dedekind_psi_function">Dedekind psi function</a>
%H A001615 <a href="/index/Cor#core">Index entries for "core" sequences</a>
%H A001615 <a href="/index/Su#sublatts">Index entries for sequences related to sublattices</a>
%F A001615 Dirichlet g.f.: zeta(s) * zeta(s-1) / zeta(2*s). - _Michael Somos_, May 19 2000
%F A001615 Multiplicative with a(p^e) = (p+1)*p^(e-1). - _David W. Wilson_, Aug 01 2001
%F A001615 a(n) = A003557(n)*A048250(n) = n*A000203(A007947(n))/A007947(n). - _Labos Elemer_, Dec 04 2001
%F A001615 a(n) = n*Sum_{d|n} mu(d)^2/d, Dirichlet convolution of A008966 and A000027. - _Benoit Cloitre_, Apr 07 2002
%F A001615 a(n) = Sum_{d|n} mu(n/d)^2 * d. - _Joerg Arndt_, Jul 06 2011
%F A001615 From _Enrique Pérez Herrero_, Aug 22 2010: (Start)
%F A001615 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 A001615 a(n) = (1/phi(n))*Sum_{d|n} mu(n/d)*d^(b-1), for b=3. (End)
%F A001615 a(n) = n / Sum_{d|n} mu(d)/a(d). - _Enrique Pérez Herrero_, Jun 06 2012
%F A001615 a(n^k)= n^(k-1) * a(n). - _Enrique Pérez Herrero_, Jan 05 2013
%F A001615 If n is squarefree, then a(n) = A049417(n) = A000203(n). - _Vladimir Shevelev_, Apr 01 2014
%F A001615 a(n) = Sum_{d^2 | n} mu(d) * A000203(n/d^2). - _Álvar Ibeas_, Dec 20 2014
%F A001615 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 A001615 G.f.: Sum_{k>=1} mu(k)^2*x^k/(1 - x^k)^2. - _Ilya Gutkovskiy_, Oct 25 2018
%F A001615 a(n) = Sum_{d|n} 2^omega(d) * phi(n/d), Dirichlet convolution of A034444 and A000010. - _Daniel Suteu_, Mar 09 2019
%F A001615 From _Richard L. Ollerton_, May 07 2021: (Start)
%F A001615 a(n) = Sum_{k=1..n} 2^omega(gcd(n,k)).
%F A001615 a(n) = Sum_{k=1..n} 2^omega(n/gcd(n,k))*phi(gcd(n,k))/phi(n/gcd(n,k)). (End)
%F A001615 a(n) = abs(A158523(n)) = A158523(n) * A008836(n). - _Enrique Pérez Herrero_, Nov 07 2022
%e A001615 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 A001615 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 A001615 := proc(n) n*mul((1+1/i[1]),i=ifactors(n)[2]) end; # _Mark van Hoeij_, Apr 18 2012
%t A001615 Join[{1}, Table[n Times@@(1+1/Transpose[FactorInteger[n]][[1]]), {n,2,100}]] (* _T. D. Noe_, Jun 11 2006 *)
%t A001615 Table[DirichletConvolve[j, MoebiusMu[j]^2, j, n], {n, 100}] (* _Jan Mangaldan_, Aug 22 2013 *)
%t A001615 a[ n_] := If[ n < 1, 0, n Sum[ MoebiusMu[ d]^2 / d, {d, Divisors @ n}]]; (* _Michael Somos_, Jan 10 2015 *)
%t A001615 Table[n*Product[1 + 1/p, {p, Select[Divisors[n], PrimeQ]}], {n, 1, 100}] (* _Vaclav Kotesovec_, May 08 2021 *)
%o A001615 (PARI) {a(n) = if( n<1, 0, direuler( p=2, n, (1 + X) / (1 - p*X)) [n])};
%o A001615 (PARI) {a(n) = if( n<1, 0, n * sumdiv( n, d, moebius(d)^2 / d))}; /* _Michael Somos_, Nov 10 2006 */
%o A001615 (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 A001615 (PARI) a(n) = n * sumdivmult(n, d, issquarefree(d)/d) \\ _Charles R Greathouse IV_, Sep 09 2014
%o A001615 (Haskell)
%o A001615 import Data.Ratio (numerator)
%o A001615 a001615 n = numerator (fromIntegral n * (product $
%o A001615             map ((+ 1) . recip . fromIntegral) $ a027748_row n))
%o A001615 -- _Reinhard Zumkeller_, Jun 03 2013, Apr 12 2012
%o A001615 (Sage) def A001615(n) : return n*mul(1+1/p for p in prime_divisors(n))
%o A001615 [A001615(n) for n in (1..69)] # _Peter Luschny_, Jun 10 2012
%o A001615 (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 A001615 (Python 3.8+)
%o A001615 from math import prod
%o A001615 from sympy import primefactors
%o A001615 def A001615(n):
%o A001615     plist = primefactors(n)
%o A001615     return n*prod(p+1 for p in plist)//prod(plist) # _Chai Wah Wu_, Jun 03 2021
%Y A001615 Other sequences that count lattices/sublattices: A000203 (with primitive condition removed), A003050 (hexagonal lattice instead), A003051, A054345, A160889, A160891.
%Y A001615 Cf. A002110, A027748, A124010, A019269.
%Y A001615 Cf. A301594.
%Y A001615 Cf. A063659 (Möbius transform), A082020 (average order), A156303 (Euler transform), A173290 (partial sums), A175836 (partial products), A203444 (range).
%Y A001615 Cf. A210523 (record values).
%Y A001615 Algebraic combinations with other core sequences: A000082, A033196, A175732, A291784, A344695.
%Y A001615 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 A001615 Cf. A082695 (Dgf at s=3), A339925 (Dgf at s=4).
%K A001615 nonn,easy,core,nice,mult
%O A001615 1,2
%A A001615 _N. J. A. Sloane_
%E A001615 More terms from _Olivier Gérard_, Aug 15 1997

# Content is available under The OEIS End-User License Agreement: http://oeis.org/LICENSE