A333976 Number of pairs of divisors of n, (d1,d2), such that d1 <= d2 and gcd(d1,d2) > 1.

0, 1, 1, 3, 1, 5, 1, 6, 3, 5, 1, 13, 1, 5, 5, 10, 1, 13, 1, 13, 5, 5, 1, 25, 3, 5, 6, 13, 1, 22, 1, 15, 5, 5, 5, 32, 1, 5, 5, 25, 1, 22, 1, 13, 13, 5, 1, 41, 3, 13, 5, 13, 1, 25, 5, 25, 5, 5, 1, 55, 1, 5, 13, 21, 5, 22, 1, 13, 5, 22, 1, 60, 1, 5, 13, 13, 5, 22, 1, 41, 10

Offset

1,4

Links

Robert Israel, Table of n, a(n) for n = 1..10000

Formula

a(n) = Sum_{d1|n, d2|n, d1<=d2} (1-[gcd(d1,d2) = 1]), where [ ] is the Iverson bracket.

a(n) = A184389(n) - A018892(n). - Robert Israel, Nov 14 2025

a(n) = (tau(n)^2-tau(n^2)+tau(n)-1)/2, where tau(n) = A000005(n). - Wesley Ivan Hurt, Dec 28 2025

Example

a(7) = 1; (7,7)
a(8) = 6; (2,2), (2,4), (2,8), (4,4), (4,8), (8,8)
a(9) = 3; (3,3), (3,9), (9,9)
a(10) = 5; (2,2), (2,10), (5,5), (5,10), (10,10)

Maple

f:= proc(n) local T, tn, t;
   T:= ifactors(n)[2][.., 2];
   tn:= mul(1+t, t=T);
   tn*(tn+1)/2 - (mul(2*t+1, t=T)+1)/2
end proc:
map(f, [$1..1000]); # Robert Israel, Nov 14 2025

Mathematica

Table[Sum[Sum[(1 - KroneckerDelta[GCD[i, k], 1]) (1 - Ceiling[n/k] + Floor[n/k]) (1 - Ceiling[n/i] + Floor[n/i]), {i, k}], {k, n}], {n, 100}]

Crossrefs

Cf. A000005 (tau), A018892, A184389, A275387 (same with d1<d2), A337298.

Sequence in context: A324896 A029652 A238952 * A129510 A225656 A087913

Adjacent sequences: A333973 A333974 A333975 * A333977 A333978 A333979

Keyword

nonn

Author

Wesley Ivan Hurt, Jan 01 2021

Status

approved