cp's OEIS Frontend

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.

%I A140773 #51 Jun 12 2025 18:49:00
%S A140773 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,
%T A140773 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,
%U A140773 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
%N 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.
%C A140773 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
%C A140773 Number of distinct faces obtainable by arranging n unit cubes into a cuboid. - _Chris W. Milson_, Mar 14 2021
%H A140773 Antti Karttunen, <a href="/A140773/b140773.txt">Table of n, a(n) for n = 1..10000</a>
%H A140773 Chris W. Milson, <a href="https://github.com/chrismilson/cuboid-areas">Constructing Cuboids</a>
%H A140773 Chris W. Milson, <a href="https://github.com/chrismilson/cuboid-areas/blob/e860c66ec6dfce910bafffe5ead15fa5548169cf/main.py#L49">A faster algorithm for a(n)</a>
%F A140773 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
%F A140773 a(n) = Sum_{d|n} A135539(d,n/d). - _Ridouane Oudra_, Jul 10 2021
%F A140773 a(n) = (A007425(n) + A046951(n))/2. - _Ridouane Oudra_, Apr 10 2024
%F A140773 G.f.: Sum_{k>=1} Sum_{d|k} x^(k^2/d)/(1 - x^k). - _Miles Wilson_, Jun 12 2025
%e A140773 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.
%t A140773 (* 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 *)
%t A140773 d=Divisors[n]; r=Length[d]; Sum[Ceiling[Length[Divisors[d[[j]]]]/2],{j,r}] (* _Manfred Boergens_, Feb 25 2021 *)
%o A140773 (PARI)
%o A140773 \\ Two implementations, after the two different interpretations given by the author of the sequence:
%o A140773 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; }
%o A140773 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; }
%o A140773 \\ _Antti Karttunen_, May 19 2017
%o A140773 (Python) # See C. W. Milson link.
%Y A140773 Cf. A140774.
%Y A140773 Cf. A000005, A034836, A038548, A007425, A046951.
%Y A140773 Cf. A369255 (parity), A369256 (positions of odd terms), A378213 (Dirichlet inverse).
%K A140773 nonn
%O A140773 1,2
%A A140773 _Leroy Quet_, May 29 2008
%E A140773 Corrected and extended by _Robert G. Wilson v_, May 31 2008