login
A337273
Number of distinct positive integer pairs, (s,t), such that s < t < n where neither s nor t divides n.
8
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
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
KEYWORD
nonn,easy
AUTHOR
Wesley Ivan Hurt, Sep 15 2020
STATUS
approved