login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

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

%I #24 Sep 16 2020 17:48:35

%S 0,0,0,0,3,1,10,6,15,15,36,15,55,45,55,55,105,66,136,91,136,153,210,

%T 120,231,231,253,231,351,231,406,325,406,435,465,351,595,561,595,496,

%U 741,561,820,703,741,861,990,703,1035,946,1081,1035,1275,1035,1275,1128,1378,1431,1596

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

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

%F 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

%e 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).

%e 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

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

%o (PARI) a(n) = binomial(n - numdiv(n), 2) \\ _David A. Corneth_, Sep 15 2020

%Y Cf. A000005, A049820.

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

%K nonn,easy

%O 1,5

%A _Wesley Ivan Hurt_, Sep 15 2020