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