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
Examples
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
Links
- Amiram Eldar, Table of n, a(n) for n = 1..10000
Crossrefs
Programs
-
Mathematica
Table[Sum[Sum[(Ceiling[n/k] - Floor[n/k]) (Ceiling[n/i] - Floor[n/i]), {i, k - 1}], {k, n}], {n, 80}] a[n_] := Module[{m = n - DivisorSigma[0, n]}, m*(m-1)/2]; Array[a, 100] (* Amiram Eldar, Feb 04 2025 *) -
PARI
a(n) = binomial(n - numdiv(n), 2) \\ David A. Corneth, Sep 15 2020
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