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

0, 0, 1, 1, 6, 3, 15, 10, 21, 21, 45, 21, 66, 55, 66, 66, 120, 78, 153, 105, 153, 171, 231, 136, 253, 253, 276, 253, 378, 253, 435, 351, 435, 465, 496, 378, 630, 595, 630, 528, 780, 595, 861, 741, 780, 903, 1035, 741, 1081, 990, 1128, 1081, 1326, 1081, 1326, 1176, 1431

Offset: 1

Author

Wesley Ivan Hurt, Sep 14 2020

Keywords

• nonn
• easy

Examples

			a(7) = 15; There are 5 positive integers less than 7 that do not divide 7, {2,3,4,5,6}. From this list, there are 15 ordered pairs, (s,t), such that s <= t < 7. They are (2,2), (2,3), (2,4), (2,5), (2,6), (3,3), (3,4), (3,5), (3,6), (4,4), (4,5), (4,6), (5,5), (5,6) and (6,6). So a(7) = 15.
		

Links

• Amiram Eldar, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A000005, A000217, A049820, A337273, A337588, A337679, A337680, A337681, A337682, A337683, A337684.

Programs

Maple

a:= n-> (t-> t*(t+1)/2)(n-numtheory[tau](n)):
seq(a(n), n=1..60);  # Alois P. Heinz, Nov 19 2021

Mathematica

Table[Sum[Sum[(Ceiling[n/k] - Floor[n/k]) (Ceiling[n/i] - Floor[n/i]), {i, k}], {k, n}], {n, 100}]
a[n_] := Module[{m = n - DivisorSigma[0, n]}, m*(m+1)/2]; Array[a, 100] (* Amiram Eldar, Feb 03 2025 *)

PARI

a(n) = {my(m = n - numdiv(n)); m*(m+1)/2;} \\ Amiram Eldar, Feb 03 2025

Python

from sympy import divisor_count
def A335567(n):
    m = divisor_count(n)
    return (n-m)*(n-m+1)//2 # Chai Wah Wu, Nov 19 2021

Formula

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

a(n) = (n-A000005(n))*(n-A000005(n)+1)/2. - Chai Wah Wu, Nov 19 2021

a(n) = A000217(A049820(n)). - Alois P. Heinz, Nov 19 2021

a(p) = (p-1)*(p-2)/2 for primes p. - Wesley Ivan Hurt, Nov 28 2021