cp's OEIS Frontend

a(n) depends only on prime signature of n (cf. A025487). a(m) = a(n) iff m and n have the same prime signature, i.e., iff A046523(m) = A046523(n).

Because A046523 (the smallest representative of prime signature of n) and this sequence are functions of each other as A046523(n) = A181821(a(n)) and a(n) = a(A046523(n)), it implies that for all i, j: a(i) = a(j) <=> A046523(i) = A046523(j) <=> A101296(i) = A101296(j), i.e., that equivalence-class-wise this is equal to A101296, and furthermore, applying any function f on this sequence gives us a sequence b(n) = f(a(n)) whose equivalence class partitioning is equal to or coarser than that of A101296, i.e., b is then a sequence that depends only on the prime signature of n (the multiset of exponents of its prime factors), although not necessarily in a very intuitive way. - Antti Karttunen, Apr 28 2022

If n = Product p_i^a_i, d = Product p_i^c_i is a unitary divisor of n if each c_i is 0 or a_i.

Also the number of squarefree divisors of n. - Labos Elemer

Also number of divisors of the squarefree kernel of n: a(n) = A000005(A007947(n)). - Reinhard Zumkeller, Jul 19 2002

Also shadow transform of pronic numbers A002378.

For n >= 1 define an n X n (0,1) matrix A by A[i,j] = 1 if lcm(i,j) = n, A[i,j] = 0 if lcm(i,j) <> n for 1 <= i,j <= n. a(n) is the rank of A. - Yuval Dekel (dekelyuval(AT)hotmail.com), Aug 11 2003

a(n) is also the number of solutions to x^2 - x == 0 (mod n). - Yuval Dekel (dekelyuval(AT)hotmail.com), Sep 21 2003

a(n) is the number of squarefree divisors of n, but in general the set of unitary divisors of n is not the set of squarefree divisors (compare the rows of A077610 and A206778). - Jaroslav Krizek, May 04 2009

Row lengths of the triangles in A077610 and in A206778. - Reinhard Zumkeller, Feb 12 2012

a(n) is also the number of distinct residues of k^phi(n) (mod n), k=0..n-1. - Michel Lagneau, Nov 15 2012

a(n) is the number of irreducible fractions y/x that satisfy x*y=n (and gcd(x,y)=1), x and y positive integers. - Luc Rousseau, Jul 09 2017

a(n) is the number of (x,y) lattice points satisfying both x*y=n and (x,y) is visible from (0,0), x and y positive integers. - Luc Rousseau, Jul 10 2017

Conjecture: For any nonnegative integer k and positive integer n, the sum of the k-th powers of the unitary divisors of n is divisible by the sum of the k-th powers of the odd unitary divisors of n (note that this sequence lists the sum of the 0th powers of the unitary divisors of n). - Ivan N. Ianakiev, Feb 18 2018

a(n) is the number of one-digit numbers, k, when written in base n such that k and k^2 end in the same digit. - Matthew Scroggs, Jun 01 2018

Dirichlet convolution of A271102 and A000005. - Vaclav Kotesovec, Apr 08 2019

Conjecture: Let b(i; n), n > 0, be multiplicative sequences for some fixed integer i >= 0 with b(i; p^e) = (Sum_{k=1..i+1} A164652(i, k) * e^(k-1)) * (i+2) / (i!) for prime p and e > 0. Then we have Dirichlet generating functions: Sum_{n > 0} b(i; n) / n^s = (zeta(s))^(i+2) / zeta((i+2) * s). Examples for i=0 this sequence, for i=1 A226602, and for i=2 A286779. - Werner Schulte, Feb 17 2022

The smallest integer with 2^m unitary divisors, or equivalently, the smallest integer with 2^m squarefree divisors, is A002110(m). - Bernard Schott, Oct 04 2022

The primes become the powers of 2 (2 -> 1, 3 -> 2, 5 -> 4, 7 -> 8); the composite numbers are formed by taking the values for the factors in the increasing order, multiplying them by the consecutive powers of 2, and summing. See the Example section.

From Antti Karttunen, Jun 27 2014: (Start)

The odd bisection (containing even terms) halved gives A244153.

The even bisection (containing odd terms), when one is subtracted from each and halved, gives this sequence back.

(End)

Question: Are there any other solutions that would satisfy the recurrence r(1) = 0; and for n > 1, r(n) = Sum_{d|n, d>1} 2^A033265(r(d)), apart from simple variants 2^k * A156552(n)? See also A297112, A297113. - Antti Karttunen, Dec 30 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)

A perfect partition of n is one which contains just one partition of every number less than n when repeated parts are regarded as indistinguishable. Thus 1^n is a perfect partition for every n; and for n = 7, 4 1^3, 4 2 1, 2^3 1 and 1^7 are all perfect partitions. [Riordan]

Also number of ordered factorizations of n+1, see A074206.

Also number of gozinta chains from 1 to n (see A034776). - David W. Wilson

a(n) is the permanent of the n X n matrix with (i,j) entry = 1 if j|i+1 and = 0 otherwise. For n=3 the matrix is {{1, 1, 0}, {1, 0, 1}, {1, 1, 0}} with permanent = 2. - David Callan, Oct 19 2005

Appears to be the number of permutations that contribute to the determinant that gives the Moebius function. Verified up to a(9). - Mats Granvik, Sep 13 2008

Dirichlet inverse of A153881 (assuming offset 1). - Mats Granvik, Jan 03 2009

Equals row sums of triangle A176917. - Gary W. Adamson, Apr 28 2010

A partition is perfect iff it is complete (A126796) and knapsack (A108917). - Gus Wiseman, Jun 22 2016

a(n) is also the number of series-reduced planted achiral trees with n + 1 unlabeled leaves, where a rooted tree is series-reduced if all terminal subtrees have at least two branches, and achiral if all branches directly under any given node are equal. Also Moebius transform of A067824. - Gus Wiseman, Jul 13 2018

Coons and Borwein: "We give a new proof of Fatou's theorem: if an algebraic function has a power series expansion with bounded integer coefficients, then it must be a rational function. This result is applied to show that for any non-trivial completely multiplicative function from N to {-1,1}, the series sum_{n=1..infinity} f(n)z^n is transcendental over {Z}[z]; in particular, sum_{n=1..infinity} lambda(n)z^n is transcendental, where lambda is Liouville's function. The transcendence of sum_{n=1..infinity} mu(n)z^n is also proved." - Jonathan Vos Post, Jun 11 2008

Coons proves that a(n) is not k-automatic for any k > 2. - Jonathan Vos Post, Oct 22 2008

The Riemann hypothesis is equivalent to the statement that for every fixed epsilon > 0, lim_{n -> infinity} (a(1) + a(2) + ... + a(n))/n^(1/2 + epsilon) = 0 (Borwein et al., theorem 1.2). - Arkadiusz Wesolowski, Oct 08 2013

Shadow transform of the squares A000290. - Vladeta Jovovic, Aug 02 2002

Labos Elemer and Henry Bottomley independently proved that (2) and (3) define the same sequence. Bottomley also showed that (1) and (2) define the same sequence.

Proof that (2) = (3): Let max{gcd(d, n/d)} = K, then d = Kx, n/d = Ky so n = KKxy where xy is the squarefree part of n, otherwise K is not maximal. Observe also that g = gcd(K, xy) is not necessarily 1. Thus K is also the "maximal square-root factor" of n. - Labos Elemer, Jul 2000

We can write sqrt(n) = b*sqrt(c) where c is squarefree. Then b = A000188(n) is the "inner square root" of n, c = A007913(n) and b*c = A019554(n) = "outer square root" of n.

Rediscovered by the HR automatic theory formation program.

a(n) depends only on prime signature of n (cf. A025487, A046523). So a(24) = a(375) since 24 = 2^3*3 and 375 = 3*5^3 both have prime signature (3, 1).

First differences of A013936. Average value tends towards Pi^2/6 = 1.644934... (A013661, A013679). - Henry Bottomley, Aug 16 2001

We have a(n) = A159631(n) for all n < 125, but a(125) = 2 < 3 = A159631(125). - Steven Finch, Apr 22 2009

Number of 2-generated Abelian groups of order n, if n > 1. - Álvar Ibeas, Dec 22 2014 [In other words, number of order-n abelian groups with rank <= 2. Proof: let b(n) be such number. A finite abelian group is the inner direct product of all Sylow-p subgroups, so {b(n)} is multiplicative. Obviously b(p^e) = floor(e/2)+1 (corresponding to the groups C_(p^r) X C_(p^(e-r)) for 0 <= r <= floor(e/2)), hence b(n) = a(n) for all n. - Jianing Song, Nov 05 2022]

Number of ways of writing n = r*s such that r|s. - Eric M. Schmidt, Jan 08 2015

The number of divisors of the square root of the largest square dividing n. - Amiram Eldar, Jul 07 2020

The number of unordered factorizations of n into cubefree powers of primes (1, primes and squares of primes, A166684). - Amiram Eldar, Jun 12 2025

Intersection of A002808 and A005117: n > 1 such that A008966(n) * (1-A010051(n)) = 1. - Reinhard Zumkeller, Dec 19 2011

Inverse Moebius transform of A034444: Sum_{d|n} 2^omega(d), where omega(n) = A001221(n) is the number of distinct primes dividing n.

Number of elements in the set {(x,y): x|n, y|n, gcd(x,y)=1}.

Number of elements in the set {(x,y): lcm(x,y)=n}.

Also gives total number of positive integral solutions (x,y), order being taken into account, to the optical or parallel resistor equation 1/x + 1/y = 1/n. Indeed, writing the latter as X*Y=N, with X=x-n, Y=y-n, N=n^2, the one-to-one correspondence between solutions (X, Y) and (x, y) is obvious, so that clearly, the solution pairs (x, y) are tau(N)=tau(n^2) in number. - Lekraj Beedassy, May 31 2002

Number of ordered pairs of positive integers (a,c) such that n^2 - ac = 0. Therefore number of quadratic equations of the form ax^2 + 2nx + c = 0 where a,n,c are positive integers and each equation has two equal (rational) roots, -n/a. (If a and c are positive integers, but, instead, the coefficient of x is odd, it is impossible for the equation to have equal roots.) - Rick L. Shepherd, Jun 19 2005

Problem A1 on the 21st Putnam competition in 1960 (see John Scholes link) asked for the number of pairs of positive integers (x,y) such that xy/(x+y) = n: the answer is a(n); for n = 4, the a(4) = 5 solutions (x,y) are (5,20), (6,12), (8,8), (12,6), (20,5). - Bernard Schott, Feb 12 2023

Numbers k such that a(k)/d(k) is an integer are in A217584 and the corresponding quotients are in A339055. - Bernard Schott, Feb 15 2023