|
| |
|
|
A001615
|
|
Dedekind psi function: n * Product_{p|n, p prime} (1 + 1/p).
(Formerly M2315 N0915)
|
|
302
|
|
|
|
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, 42, 36, 48, 30, 72, 32, 48, 48, 54, 48, 72, 38, 60, 56, 72, 42, 96, 44, 72, 72, 72, 48, 96, 56, 90, 72, 84, 54, 108, 72, 96, 80, 90, 60, 144, 62, 96, 96, 96, 84, 144, 68, 108, 96
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
Number of primitive sublattices of index n in generic 2-dimensional lattice; also index of Gamma_0(n) in SL_2(Z).
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.
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.
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
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].
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
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
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
The Riemann Hypothesis is also equivalent to another inequality, see the Sole and Planat link. - Thomas Ordowski, May 28 2017
An infinitary analog of this sequence is the sum of the infinitary divisors of n (see A049417). - Vladimir Shevelev, Apr 01 2014
Problem: are there composite numbers n such that n+1 divides psi(n)? - Thomas Ordowski, May 21 2017
The sum of divisors d of n such that n/d is squarefree. - Amiram Eldar, Jan 11 2019
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
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).
The total number of order-n subgroups of C_n X C_n is A000203(n). (End)
|
|
|
REFERENCES
|
Tom Apostol, Intro. to Analyt. Number Theory, page 71, Problem 11, where this is called phi_1(n).
David A. Cox, "Primes of the Form x^2 + n y^2", Wiley, 1989, p. 228.
R. Fricke, Die elliptischen Funktionen und ihre Anwendungen, Teubner, 1922, Vol. 2, see p. 220.
Richard K. Guy, Unsolved Problems in Number Theory, 3rd Edition, Springer, 2004. See Section B41, p. 147.
B. Schoeneberg, Elliptic Modular Functions, Springer-Verlag, NY, 1974, p. 79.
G. Shimura, Introduction to the Arithmetic Theory of Automorphic Functions, Princeton, 1971, see p. 25, Eq. (1).
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
|
LINKS
|
F. A. Lewis et al., Problem 4002, Amer. Math. Monthly, Vol. 49, No. 9, Nov. 1942, pp. 618-619.
|
|
|
FORMULA
|
Dirichlet g.f.: zeta(s) * zeta(s-1) / zeta(2*s). - Michael Somos, May 19 2000
a(n) = Sum_{d|n} mu(n/d)^2 * d. - Joerg Arndt, Jul 06 2011
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.
a(n) = (1/phi(n))*Sum_{d|n} mu(n/d)*d^(b-1), for b=3. (End)
a(n) = Sum_{k=1..n} 2^omega(gcd(n,k)).
a(n) = Sum_{k=1..n} 2^omega(n/gcd(n,k))*phi(gcd(n,k))/phi(n/gcd(n,k)). (End)
|
|
|
EXAMPLE
|
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.
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 + ...
|
|
|
MAPLE
|
|
|
|
MATHEMATICA
|
Join[{1}, Table[n Times@@(1+1/Transpose[FactorInteger[n]][[1]]), {n, 2, 100}]] (* T. D. Noe, Jun 11 2006 *)
Table[DirichletConvolve[j, MoebiusMu[j]^2, j, n], {n, 100}] (* Jan Mangaldan, Aug 22 2013 *)
a[ n_] := If[ n < 1, 0, n Sum[ MoebiusMu[ d]^2 / d, {d, Divisors @ n}]]; (* Michael Somos, Jan 10 2015 *)
Table[n*Product[1 + 1/p, {p, Select[Divisors[n], PrimeQ]}], {n, 1, 100}] (* Vaclav Kotesovec, May 08 2021 *)
|
|
|
PROG
|
(PARI) {a(n) = if( n<1, 0, direuler( p=2, n, (1 + X) / (1 - p*X)) [n])};
(PARI) {a(n) = if( n<1, 0, n * sumdiv( n, d, moebius(d)^2 / d))}; /* Michael Somos, Nov 10 2006 */
(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
(Haskell)
import Data.Ratio (numerator)
a001615 n = numerator (fromIntegral n * (product $
map ((+ 1) . recip . fromIntegral) $ a027748_row n))
(Sage) def A001615(n) : return n*mul(1+1/p for p in prime_divisors(n))
(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
(Python 3.8+)
from math import prod
from sympy import primefactors
plist = primefactors(n)
return n*prod(p+1 for p in plist)//prod(plist) # Chai Wah Wu, Jun 03 2021
|
|
|
CROSSREFS
|
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).
|
|
|
KEYWORD
|
nonn,easy,core,nice,mult
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
