A140773 Consider the products of all pairs of (not necessarily distinct) positive divisors of n. a(n) is the number of these products that divide n. a(n) also is the number of the products that are divisible by n.

1, 2, 2, 4, 2, 5, 2, 6, 4, 5, 2, 10, 2, 5, 5, 9, 2, 10, 2, 10, 5, 5, 2, 16, 4, 5, 6, 10, 2, 14, 2, 12, 5, 5, 5, 20, 2, 5, 5, 16, 2, 14, 2, 10, 10, 5, 2, 24, 4, 10, 5, 10, 2, 16, 5, 16, 5, 5, 2, 28, 2, 5, 10, 16, 5, 14, 2, 10, 5, 14, 2, 32, 2, 5, 10, 10, 5, 14, 2, 24, 9, 5, 2, 28, 5, 5, 5, 16, 2, 28, 5

Offset: 1

Author

Leroy Quet, May 29 2008

Keywords

• nonn

Comments

Number of 3D grids of n congruent boxes with two different edge lengths, in a box, modulo rotation (cf. A034836 for cubes instead of boxes and A007425 for boxes with three different edge lengths; cf. A000005 for the 2D case). - Manfred Boergens, Feb 25 2021

Number of distinct faces obtainable by arranging n unit cubes into a cuboid. - Chris W. Milson, Mar 14 2021

Examples

			The divisors of 20 are 1,2,4,5,10,20. There are 10 pairs of divisors whose product divides 20: 1*1=1, 1*2=2, 1*4=4, 1*5=5, 1*10=10, 1*20=20, 2*2=4, 2*5=10, 2*10=20, 4*5 = 20. Likewise, there are 10 products that are divisible by 20: 4*5=20, 2*10=20, 4*10=40, 10*10=100, 1*20=20, 2*20=40, 4*20=80, 5*20=100, 10*20=200, 20*20=400. So a(20) = 10.
		

Links

• Antti Karttunen, Table of n, a(n) for n = 1..10000
• Chris W. Milson, Constructing Cuboids
• Chris W. Milson, A faster algorithm for a(n)

Crossrefs

Cf. A140774.

Cf. A000005, A034836, A038548, A007425, A046951.

Cf. A369255 (parity), A369256 (positions of odd terms), A378213 (Dirichlet inverse).

Programs

Mathematica

(* first do *) Needs["Combinatorica`"] (* then *) f[n_] := Count[ n/Times @@@ Union[Sort /@ Tuples[Divisors@ n, 2]], Integer]; Array[f, 91] (* _Robert G. Wilson v, May 31 2008 *)
d=Divisors[n]; r=Length[d]; Sum[Ceiling[Length[Divisors[d[[j]]]]/2],{j,r}] (* Manfred Boergens, Feb 25 2021 *)

PARI

\\ Two implementations, after the two different interpretations given by the author of the sequence:
A140773v1(n) = { my(ds = divisors(n),s=0); for(i=1,#ds,for(j=i,#ds,if(!(n%(ds[i]*ds[j])),s=s+1))); s; }
A140773v2(n) = { my(ds = divisors(n),s=0); for(i=1,#ds,for(j=i,#ds,if(!((ds[i]*ds[j])%n),s=s+1))); s; }
\\ Antti Karttunen, May 19 2017

Python

# See C. W. Milson link.

Formula

a(n) = Sum_{m|n} A038548(m) = Sum_{m|n} ceiling(d(m)/2), where d(m) = number of divisors of m (A000005). - Manfred Boergens, Feb 25 2021

a(n) = Sum_{d|n} A135539(d,n/d). - Ridouane Oudra, Jul 10 2021

a(n) = (A007425(n) + A046951(n))/2. - Ridouane Oudra, Apr 10 2024

G.f.: Sum_{k>=1} Sum_{d|k} x^(k^2/d)/(1 - x^k). - Miles Wilson, Jun 12 2025

Extensions

Corrected and extended by Robert G. Wilson v, May 31 2008