cp's OEIS Frontend

It may be that every trajectory under iteration of the map k -> A291784(k) which increases indefinitely will eventually merge with this sequence. This is certainly true for the terms 45 through 152 of A291788. - N. J. A. Sloane, Sep 24 2017

Primes and prime powers are fixed points under the map f(k) = (psi(k)+phi(k))/2. (If n = p^k, then psi(n) = p^k(1+1/p), phi(n) = p^k(1-1/p), and their average is p^k, so n is a fixed point under the map.)

Since f(n)>n if n is not a prime power, there can be no nontrivial cycles.

Wall (1985) observes that the trajectories of 45 and 50 are unbounded, so a(45) = a(50) = -1.

Also 48 and many more terms seem to have unbounded trajectories. - Hugo Pfoertner, Sep 03 2017.

Obviously any number in the trajectory of a number with unbounded trajectory (in particular that of 45, A291787) again has this property. A291788 is the union of all these. - M. F. Hasler, Sep 03 2017

Primes and prime powers are fixed points under the map f(k) = (psi(k)+phi(k))/2, so in that case we take a(n)=0. (If n = p^k, then psi(n) = p^k(1+1/p), phi(n) = p^k(1-1/p), and their average is p^k, so n is a fixed point under the map.)

Since f(n)>n if n is not a prime power, there can be no nontrivial cycles.

Wall (1985) observes that the trajectories of 45 and 50 are unbounded, so a(45) = a(50) = -1. See A291787, A291788.

See A291787 (where A291787(m) = 2*A291787(m-7) for m >= 35) for the trajectory of 45.

There is a similar proof that all the terms from 48 though 152 have a trajectory that merges with the trajectory of 45, and so doubles every 7 steps after a certain point. For example, the trajectory of 152 reaches 2^106*33 at step 390, is 2^107*33 at step 397, and thereafter doubles every 7 steps.- N. J. A. Sloane, Sep 24 2017

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 = consists of all vectors of the form mV + nW, (m,n integers). A sublattice S = 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>, and (which = ) 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 , 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 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 Mobius transform of this sequence is A063659. - Gary W. Adamson, May 23 2008

The inverse Mobius transform of this sequence is A060648. - Vladeta Jovovic, Apr 05 2009

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

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

From Jianing Song, Nov 05 2022: (Start)

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)