A018892 Number of ways to write 1/n as a sum of exactly 2 unit fractions.

1, 2, 2, 3, 2, 5, 2, 4, 3, 5, 2, 8, 2, 5, 5, 5, 2, 8, 2, 8, 5, 5, 2, 11, 3, 5, 4, 8, 2, 14, 2, 6, 5, 5, 5, 13, 2, 5, 5, 11, 2, 14, 2, 8, 8, 5, 2, 14, 3, 8, 5, 8, 2, 11, 5, 11, 5, 5, 2, 23, 2, 5, 8, 7, 5, 14, 2, 8, 5, 14, 2, 18, 2, 5, 8, 8, 5, 14, 2, 14, 5, 5, 2, 23, 5, 5, 5, 11, 2, 23, 5, 8, 5, 5, 5, 17, 2, 8, 8

Offset: 1

Author

Robert G. Wilson v

Keywords

• nonn
• easy
• nice

Comments

Number of elements in the set {(x,y): x|n, y|n, x<=y, gcd(x,y)=1}. Number of divisors of n^2 less than or equal to n. - Vladeta Jovovic, May 03 2002

Equivalently, number of pairs (x,y) such that lcm(x,y)=n. - Benoit Cloitre, May 16 2002

Also, number of right triangles with an integer hypotenuse and height n. - Reinhard Zumkeller, Jul 10 2002

The triangles are to be considered as resting on their hypotenuse, with the height measured to the right angle. - Franklin T. Adams-Watters, Feb 19 2015

a(n) >= 2 for n>=2 because of the identities 1/n = 1/(2*n) + 1/(2*n) = 1/(n+1) + 1/(n*(n+1)). - Lekraj Beedassy, May 04 2004

a(n) is the number of divisors of n^2 that are <= n; e.g., a(12) counts these 8 divisors of 12: 1,2,3,4,6,8,9,12. - Clark Kimberling, Apr 21 2019

Examples

			n=1: 1/1 = 1/2 + 1/2.
n=2: 1/2 = 1/4 + 1/4 = 1/3 + 1/6.
n=3: 1/3 = 1/6 + 1/6 = 1/4 + 1/12.
		

References

• K. S. Brown, Posting to netnews group sci.math, Aug 17 1996.
• L. E. Dickson, History of The Theory of Numbers, Vol. 2 p. 690, Chelsea NY 1923.
• A. M. and I. M. Yaglom, Challenging Mathematical Problems With Elementary Solutions, Vol. 1, Dover, N.Y., 1987, pp. 8 and 60, Problem 19.

Links

• T. D. Noe, Table of n, a(n) for n = 1..10000
• Jorg Brown, Comparison of records in sigma(n)/phi(n) and A018892.
• Roger B. Eggleton, Problem 10501(a), American Mathematical Monthly, Vol. 105, No. 4, (1998), p. 372.
• Project Euler, Problem 379: Least common multiple count.

Crossrefs

Records: A126097, A126098.

Cf. A000010, A001221, A046079, A048691, A063647, A089233, A184389.

Cf. A001620, A082633, A013661, A201994, A306016.

Programs

Haskell

a018892 n = length [d | d <- [1..n], n^2 `mod` d == 0]
-- Reinhard Zumkeller, Jan 08 2012

Mathematica

f[j_, n_] := (Times @@ (j(Last /@ FactorInteger[n]) + 1) + j - 1)/j; Table[f[2, n], {n, 96}] (* Robert G. Wilson v, Aug 03 2005 *)
a[n_] := (DivisorSigma[0, n^2] + 1)/2; Table[a[n], {n, 1, 99}](* Jean-François Alcover, Dec 19 2011, after Vladeta Jovovic *)

PARI

A018892(n)=(numdiv(n^2)+1)/2 \\ M. F. Hasler, Dec 30 2007

PARI

A018892s(n)=local(t=divisors(n^2));vector((#t+1)/2,i,[n+t[i],n+n^2/t[i]]) /* show solutions */ \\ M. F. Hasler, Dec 30 2007

PARI

a(n)=sumdiv(n,d,sum(i=1,d,lcm(d,i)==n)) \\ Charles R Greathouse IV, Apr 08 2012

Python

from math import prod
from sympy import factorint
def A018892(n): return prod((a<<1)+1 for a in factorint(n).values())+1>>1 # Chai Wah Wu, Aug 20 2023

Formula

If n = (p1^a1)(p2^a2)...(pt^at), a(n) = ((2*a1 + 1)(2*a2 + 1) ... (2*at + 1) + 1)/2.

a(n) = (tau(n^2)+1)/2. - Vladeta Jovovic, May 03 2002

a(n) = A063647(n)+1 = A046079(2*n)+1. - Lekraj Beedassy, Dec 01 2003

a(n) = Sum_{d|n} phi(2^omega(d)), where phi is A000010 and omega is A001221. - Enrique Pérez Herrero, Apr 13 2012

a(n) = A000005(n) + A089233(n). - James Spahlinger, Feb 16 2016

a(n) = n + Sum_{i=1..n} sign(n^2 mod -i). - Wesley Ivan Hurt, Apr 07 2021

a(n) = Sum_{d|n} mu(n/d)*A184389(d). - Ridouane Oudra, Feb 22 2022

Sum_{k=1..n} a(k) ~ (n/(2*zeta(2)))*(log(n)^2/2 + log(n)*(3*gamma - 1) + 1 - 3*gamma + 3*gamma^2 - 3*gamma_1 + zeta(2) + (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, Oct 03 2024

Extensions

More terms from David W. Wilson, Sep 15 1996

First example corrected by Jason Orendorff (jason.orendorff(AT)gmail.com), Jan 02 2009

Incorrect Mathematica program deleted by N. J. A. Sloane, Jul 08 2009