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,5

Links

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

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

Example

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.

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}]

Prog

(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

Crossrefs

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

Sequence in context: A341746 A097917 A116570 * A362625 A352015 A225503

Adjacent sequences: A335564 A335565 A335566 * A335568 A335569 A335570

Keyword

nonn,easy

Author

Wesley Ivan Hurt, Sep 14 2020

Status

approved