A337273 Number of distinct positive integer pairs, (s,t), such that s < t < n where neither s nor t divides n.

0, 0, 0, 0, 3, 1, 10, 6, 15, 15, 36, 15, 55, 45, 55, 55, 105, 66, 136, 91, 136, 153, 210, 120, 231, 231, 253, 231, 351, 231, 406, 325, 406, 435, 465, 351, 595, 561, 595, 496, 741, 561, 820, 703, 741, 861, 990, 703, 1035, 946, 1081, 1035, 1275, 1035, 1275, 1128, 1378, 1431, 1596

Offset

1,5

Links

Table of n, a(n) for n=1..59.

Formula

a(n) = Sum_{k=1..n} Sum_{i=1..k-1} (ceiling(n/k) - floor(n/k)) * (ceiling(n/i) - floor(n/i)).

a(n) = binomial(n - tau(n), 2) where tau(n) is the number of divisors of n (cf. A000005). - David A. Corneth, Sep 15 2020

Example

a(7) = 10; There are 5 positive integers less than 7 that do not divide 7, {2,3,4,5,6}. Given this set, there are 10 pairs of positive integers, (s,t), such that s < t < 7. They are (2,3), (2,4), (2,5), (2,6), (3,4), (3,5), (3,6), (4,5), (4,6) and (5,6).
a(8) = 6 as 8 has 4 divisors; 1, 2, 4 and 8 so 8-4 numbers below 8 are not divisors of 8. Indeed those numbers are 3, 5, 6, 7. As these are four numbers we can choose binomial(4, 2) = 6 pairs of distinct such numbers below 8 giving the term. - David A. Corneth, Sep 15 2020

Mathematica

Table[Sum[Sum[(Ceiling[n/k] - Floor[n/k]) (Ceiling[n/i] - Floor[n/i]), {i, k - 1}], {k, n}], {n, 80}]

Prog

(PARI) a(n) = binomial(n - numdiv(n), 2) \\ David A. Corneth, Sep 15 2020

Crossrefs

Cf. A000005, A049820.

Cf. A335567, A337588, A337679, A337680, A337681, A337682, A337683, A337684.

Sequence in context: A171568 A107056 A365962 * A116384 A117207 A046658

Adjacent sequences: A337270 A337271 A337272 * A337274 A337275 A337276

Keyword

nonn,easy

Author

Wesley Ivan Hurt, Sep 15 2020

Status

approved