A217584 -id:A217584 - cp's OEIS frontend

A048691 a(n) = d(n^2), where d(k) = A000005(k) is the number of divisors of k.

1, 3, 3, 5, 3, 9, 3, 7, 5, 9, 3, 15, 3, 9, 9, 9, 3, 15, 3, 15, 9, 9, 3, 21, 5, 9, 7, 15, 3, 27, 3, 11, 9, 9, 9, 25, 3, 9, 9, 21, 3, 27, 3, 15, 15, 9, 3, 27, 5, 15, 9, 15, 3, 21, 9, 21, 9, 9, 3, 45, 3, 9, 15, 13, 9, 27, 3, 15, 9, 27, 3, 35, 3, 9, 15, 15, 9, 27, 3, 27

Offset: 1

David Johnson-Davies

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

A. M. Gleason et al., The William Lowell Putnam Mathematical Competitions, Problems & Solutions:1938-1960 Soln. to Prob. 1 1960, p. 516, MAA, 1980.
Ross Honsberger, More Mathematical Morsels, Morsel 43, pp. 232-3, DMA No. 10 MAA, 1991.
Loren C. Larson, Problem-Solving Through Problems, Prob. 3.3.7, p. 102, Springer 1983.
Alfred S. Posamentier and Charles T. Salkind, Challenging Problems in Algebra, Prob. 9-9 pp. 143 Dover NY, 1988.
D. O. Shklarsky et al., The USSR Olympiad Problem Book, Soln. to Prob. 123, pp. 28, 217-8, Dover NY.
Wacław Sierpiński, Elementary Theory of Numbers, pp. 71-2, Elsevier, North Holland, 1988.
James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, page 91.
Charles W. Trigg, Mathematical Quickies, Question 194, pp. 53, 168, Dover, 1985.

Enrique Pérez Herrero, Table of n, a(n) for n = 1..10000
Ovidiu Bagdasar, On Some Functions Involving the lcm and gcd of Integer Tuples.
Umberto Cerruti, Percorsi tra i numeri (in Italian), pages 3-4.
Daniele A. Gewurz and Francesca Merola, Sequences realized as Parker vectors of oligomorphic permutation groups, J. Integer Seq., Vol. 6 (2003), Article 03.1.6.
John Scholes, Problem A1 of 21st Putnam Competition 1960, 2002. [Wayback Machine link]
Wacław Sierpiński, Elementary Theory of Numbers, Warszawa 1964.
Index to sequences related to Olympiads and other Mathematical competitions.

Cf. A000005, A034444, Mobius transf. of A035116, A048785, A061391, A018805, A002088, A015614, A018892, A063647, A182139.
Partial sums give A061503.
For similar LCM sequences, see A070919, A070920, A070921.
Cf. A005408, A124010.
For the earliest occurrence of 2n-1 see A016017.
Cf. A001620, A082633, A217584, A339055.

a048691 = product . map (a005408 . fromIntegral) . a124010_row
-- Reinhard Zumkeller, Jul 12 2012

A048691[n_]:=DivisorSigma[0,n^2] (* Enrique Pérez Herrero, May 30 2010 *)
DivisorSigma[0,Range[80]^2] (* Harvey P. Dale, Apr 08 2015 *)

numlib::tau (n^2)$ n=1..90 // Zerinvary Lajos, May 13 2008

A048691(n)=prod(i=1,#n=factor(n)[,2],n[i]*2+1) /* or, of course, a(n)=numdiv(n^2) */ \\ M. F. Hasler, Dec 30 2007

for(n=1, 100, print1(direuler(p=2, n, (1 - X^2)/(1 - X)^3)[n], ", ")) \\ Vaclav Kotesovec, Aug 21 2021

[sigma(n**2, 0) for n in range(1, 81)] # Stefano Spezia, Jul 14 2025

a(n) = A000005(A000290(n)).
tau(n^2) = Sum_{d|n} mu(n/d)*tau(d)^2, where mu(n) = A008683(n), cf. A061391.
Multiplicative with a(p^e) = 2e+1. - Vladeta Jovovic, Jul 23 2001
Also a(n) = Sum_{d|n} (tau(d)*moebius(n/d)^2), Dirichlet convolution of A000005 and A008966. - Benoit Cloitre, Sep 08 2002
a(n) = A055205(n) + A000005(n). - Reinhard Zumkeller, Dec 08 2009
Dirichlet g.f.: (zeta(s))^3/zeta(2s). - R. J. Mathar, Feb 11 2011
a(n) = Sum_{d|n} 2^omega(d). Inverse Mobius transform of A034444. - Enrique Pérez Herrero, Apr 14 2012
G.f.: Sum_{k>=1} 2^omega(k)*x^k/(1 - x^k). - Ilya Gutkovskiy, Mar 10 2018
Sum_{k=1..n} a(k) ~ n*(6/Pi^2)*(log(n)^2/2 + log(n)*(3*gamma - 1) + 1 - 3*gamma + 3*gamma^2 - 3*gamma_1 + (2 - 6*gamma - 2*log(n))*zeta'(2)/zeta(2) + (2*zeta'(2)/zeta(2))^2 - 2*zeta''(2)/zeta(2)), where gamma is Euler's constant (A001620) and gamma_1 is the first Stieltjes constant (A082633). - Amiram Eldar, Jan 26 2023

Additional comments from Vladeta Jovovic, Apr 29 2001

A179746 Numbers of the form p^4q^2r^2 where p, q, and r are distinct primes.

Original entry on oeis.org

3600, 7056, 8100, 15876, 17424, 19600, 22500, 24336, 39204, 41616, 48400, 51984, 54756, 67600, 76176, 86436, 93636, 94864, 99225, 115600, 116964, 121104, 122500, 132496, 138384, 144400, 171396, 197136, 211600, 226576, 240100, 242064, 245025

Offset: 1

Vladimir Joseph Stephan Orlovsky, Jul 25 2010

nonn

Numbers k such that tau(k^2)/tau(k) = 5 where tau(n) is the number of divisors of n (A000005). - Bernard Schott, Nov 27 2020

T. D. Noe, Table of n, a(n) for n = 1..1000
Will Nicholes, List of Prime Signatures
Index to sequences related to prime signature

Subsequence of A217584.

Cf. A189988 (tau(k^2)/tau(k) = 3).

f[n_]:=Sort[Last/@FactorInteger[n]]=={2,2,4}; Select[Range[200000],f]

list(lim)=my(v=List(),t1,t2);forprime(p=2, (lim\36)^(1/4), t1=p^4;forprime(q=2, sqrt(lim\t1), if(p==q, next);t2=t1*q^2;forprime(r=q+1, sqrt(lim\t2), if(p==r,next);listput(v,t2*r^2)))); vecsort(Vec(v)) \\ Charles R Greathouse IV, Jul 24 2011

from math import isqrt
from sympy import primepi, primerange, integer_nthroot
def A179746(n):
    def bisection(f,kmin=0,kmax=1):
        while f(kmax) > kmax: kmax <<= 1
        kmin = kmax >> 1
        while kmax-kmin > 1:
            kmid = kmax+kmin>>1
            if f(kmid) <= kmid:
                kmax = kmid
            else:
                kmin = kmid
        return kmax
    def f(x): return n+x+sum((t:=primepi(s:=isqrt(y:=x//r**2)))+(t*(t-1)>>1)-sum(primepi(y//k) for k in primerange(1, s+1)) for r in primerange(isqrt(x)+1))+sum(primepi(x//p**3) for p in primerange(integer_nthroot(x,3)[0]+1))-primepi(integer_nthroot(x,4)[0])
    return bisection(f,n,n)**2 # Chai Wah Wu, Mar 27 2025

Sum_{n>=1} 1/a(n) = (P(2)^2*P(4) - P(4)^2)/2 - P(2)*P(6) + P(8) = 0.00125114..., where P is the prime zeta function. - Amiram Eldar, Jul 03 2022

a(n) = A085987(n)^2. - R. J. Mathar, May 05 2023

A339055 Values taken by d(k^2)/d(k) where d(k) is the number of divisors of k and when this ratio is an integer.

Original entry on oeis.org

1, 3, 3, 3, 3, 3, 3, 3, 3, 5, 3, 3, 3, 3, 5, 5, 3, 3, 3, 3, 3, 3, 5, 5, 5, 3, 3, 5, 3, 5, 3, 3, 3, 3, 3, 5, 5, 3, 3, 5, 5, 5, 3, 3, 3, 3, 5, 3, 3, 3, 5, 3, 3, 3, 5, 5, 5, 5, 3, 3, 3, 3, 3, 5, 5, 5, 5, 3, 3, 5, 3, 5, 5, 3, 3, 3, 3, 5, 3, 3, 3, 3, 5, 3, 5, 3, 5, 3, 5

Offset: 1

Bernard Schott, Nov 22 2020

nonn

This sequence was the subject of the 3rd problem, proposed by Belarus during the 39th International Mathematical Olympiad in 1998 at Taipei (Taiwan) [see the link IMO].
If the prime signature of k is (u_1, u_2, ... , u_q) then d(k^2)/d(k) = Product_{i=1..q} (2*u_i+1)/(u_i+1); now, by a fine induction, we prove that every positive odd integer is a product of fractions of type (2u+1)/(u+1). Hence, the set of possible integer values of the data coincides with the set of all positive odd integers [see Marcin E. Kuczma reference]. The smallest integers k such that d(k^2)/d(k) = n-th odd integer are in A339056.
a(1) = 1 then from a(2) to a(234) the ratio takes only the values 3 and 5.
a(n) = 3 for numbers k whose prime signature is (4, 2) and the smallest such integer is 144 = 2^4 * 3^2 corresponding to a(2) = 3.
a(n) = 5 for numbers k whose prime signature is (4, 2, 2) and the smallest such integer is 3600 = 2^4 * 3^2 * 5^2 corresponding to a(10) = 5.
a(n) = 9 for numbers k whose prime signature is (4, 4, 2, 2) and the smallest such integer is 1587600 = 2^4 * 3^4 * 5^2 * 7^2 corresponding to a(235) = 9.

			The 4th number k such that d(k^2)/d(k) is an integer is A217584(4) = 400, 400 has 15 divisors and 400^2 = 160000 has 45 divisors, so, a(4) = 45/15 = 3.

Marcin E. Kuczma, International Mathematical Olympiads, 1986-1999, The Mathematical Association of America, 2003, pages 134-135.

The IMO Compendium, Problem 3, 39th IMO 1998.
Index to sequences related to Olympiads.

Cf. A000005, A005408, A025487, A048691, A217584, A339056.

for n from 1 to 600 do
q:= tau(n^4)/tau(n^2);
if q = floor(q) then print(q); else fi; od:

Select[DivisorSigma[0, #^2]/DivisorSigma[0, #] & /@ Range[10^5], IntegerQ] (* Amiram Eldar, Nov 23 2020 *)

lista(nn) = {my(q); for (n=1, nn, if (denominator(q=numdiv(n^2)/numdiv(n)) == 1, print1(q, ", ")););}
lista(100000) \\ Michel Marcus, Nov 23 2020

a(n) = A000005(A217584(n)^2)/A000005(A217584(n)).

A339056 Smallest integer k such that d(k^2)/d(k) = 2n-1, where d(k) is the number of divisors of k.

Original entry on oeis.org

1, 144, 3600, 1511654400000000, 1587600, 13168189440000, 177844628505600000000, 192099600, 76839840000, 4757720360193884160000, 439167347942400000000, 5037669383908052497858560000000000, 32464832400, 811620810000, 831099709440000

Offset: 1

Bernard Schott, Nov 25 2020

nonn

This sequence is related to the 3rd problem of the 39th International Mathematical Olympiad in 1998 at Taipei (Taiwan) (see link IMO).
As the set of integer values of the ratio d(k^2)/d(k) is exactly the set of all positive odd integers (see Marcin E. Kuczma reference), there exists, for each odd number, a smallest number k for which d(k^2)/d(k) = 2n-1.
All terms are perfect squares and if a number k is such that d(k^2)/d(k) = m, then all numbers that have the same prime signature as k give the same ratio m (see examples below); nevertheless, numbers with other prime signatures can also give this same ratio m (see example a(4)).
More results found by Amiram Eldar:
a(16) > 3*10^46,
a(17) = 13194538987069440000,
a(18) = 74219281802265600000000,
a(19) = 31164973305898534502400000000000000,
a(20) = 440046121805632742400000000,
a(21) = 439167347942400000000,
a(22) > 3*10^46.

			All numbers k with prime signature = [4, 2] give a ratio d(k^2)/d(k) = (9*5)/(5*3) = 3, and the smallest one is a(2) = 2^4*3^2 = 144.
All numbers k with prime signature = [4, 2, 2] give a ratio d(k^2)/d(k) = (9*5*5)/(5*3*3) = 5, and the smallest one is a(3) = 2^4*3^2*5^2 = 3600.
All numbers k with prime signature = [16, 10, 8] or [24, 12, 6] or [38, 10, 6] give the same ratio d(k^2)/d(k) = (33*21*17)/(17*11*9) = (49*25*13)/(25*13*7) = (77*21*13)/(39*11*7) = 7, but the smallest one is a(4) = 1511654400000000 = 2^16*3^10*5^8 < 2^24*3^12*5^6 < 2^38*3^10*5^6.
The successive prime signatures of the first ten terms are [], [4, 2], [4, 2, 2], [16, 10, 8], [4, 4, 2, 2], [16, 8, 4, 2], [16, 10, 8, 6], [4, 4, 2, 2, 2], [8, 4, 4, 2, 2], [28, 14, 4, 2, 2].

Marcin E. Kuczma, International Mathematical Olympiads, 1986-1999, The Mathematical Association of America, 2003, pages 134-135.

The IMO Compendium, Problem 3, 39th IMO 1998.
39th International Mathematical Olympiad, Problems and solutions, Taiwan, July 1998.
Index to sequences related to Olympiads.

Cf. A000005, A025487, A048691, A339055.

Subsequence of A217584.

isok(k, n) = numdiv(k^2)/numdiv(k) == n;
a(n) = my(k=1, m=2*n-1); while (!isok(k^2, m), k++); k^2; \\ Michel Marcus, Nov 26 2020

a(12) corrected by Amiram Eldar, Nov 26 2020

cp's OEIS Frontend

A333969 Squares of terms are the intersection of A025487 and A217584.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A048691 a(n) = d(n^2), where d(k) = A000005(k) is the number of divisors of k.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Mathematica

MuPAD

PARI

PARI

Sage

Formula

Extensions

A179746 Numbers of the form p^4*q^2*r^2 where p, q, and r are distinct primes.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A339055 Values taken by d(k^2)/d(k) where d(k) is the number of divisors of k and when this ratio is an integer.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A339056 Smallest integer k such that d(k^2)/d(k) = 2n-1, where d(k) is the number of divisors of k.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

PARI

Extensions

A179746 Numbers of the form p^4q^2r^2 where p, q, and r are distinct primes.