A349360 Number of positive integer pairs (s,t), with s,t <= n and s <= t such that either both s and t divide n or both do not.

1, 3, 4, 7, 9, 13, 18, 20, 27, 31, 48, 42, 69, 65, 76, 81, 123, 99, 156, 126, 163, 181, 234, 172, 259, 263, 286, 274, 381, 289, 438, 372, 445, 475, 506, 423, 633, 605, 640, 564, 783, 631, 864, 762, 801, 913, 1038, 796, 1087, 1011, 1138, 1102, 1329, 1117, 1336, 1212, 1441

Offset: 1

Author

Wesley Ivan Hurt, Nov 15 2021

Keywords

• nonn
• easy

Examples

			a(5) = 9; There are 9 positive integer pairs (s,t), with s <= t such that both s and t divide 5 or both do not. They are (1,1), (1,5), (2,2), (2,3), (2,4), (3,3), (3,4), (4,4), (5,5).
		

Links

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

Crossrefs

Cf. A000005, A184389, A335567.

Programs

Maple

a:= n-> add(add(`if`(irem(n, j)>0 xor irem(n, i)=0, 1, 0), i=1..j), j=1..n):
seq(a(n), n=1..57);  # Alois P. Heinz, Nov 15 2021

Mathematica

a[n_] := Module[{d = DivisorSigma[0, n]}, n*(n+1)/2 - d*(n-d)]; Array[a, 100] (* Amiram Eldar, Feb 04 2025 *)

PARI

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

Python

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

Formula

a(n) = A184389(n) + A335567(n). - Alois P. Heinz, Nov 15 2021

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

a(p) = (p^2 - 3*p + 8)/2 for primes p. - Wesley Ivan Hurt, Nov 28 2021