A268631 Number of ordered pairs (a,b) of positive integers less than n with the property that n divides ab.

0, 0, 0, 1, 0, 4, 0, 5, 4, 8, 0, 17, 0, 12, 16, 17, 0, 28, 0, 33, 24, 20, 0, 53, 16, 24, 28, 49, 0, 76, 0, 49, 40, 32, 48, 97, 0, 36, 48, 101, 0, 112, 0, 81, 100, 44, 0, 145, 36, 96, 64, 97, 0, 136, 80, 149, 72, 56, 0, 241, 0, 60, 148, 129, 96, 184, 0, 129, 88, 212

Offset: 1

Author

Matthew McMullen, Feb 09 2016

Keywords

• nonn

Comments

a(n)=0 iff n is prime or 1. a(n) is odd iff n is a multiple of 4.

Examples

			For n=10 the a(10)=8 ordered pairs are (2,5), (5,2), (4,5), (5,4), (5,6), (6,5), (5,8), and (8,5).
		

Links

• Antti Karttunen, Table of n, a(n) for n = 1..20000

Crossrefs

Cf. A006579.

Programs

Mathematica

a[n_] := Sum[Sum[1, {i, Divisors[n*k]}] - 2*Sum[1, {i, TakeWhile[Divisors[n*k], # <= k &]}], {k, 1, n - 1}]

PARI

a(n) = sum(k=1, n-1, sumdiv(n*k, d, (d > k) && (d < n))); \\ Michel Marcus, Feb 09 2016

Python

from math import prod
from sympy import factorint
def A268631(n): return 1 - 2*n + prod(p**(e-1)*((p-1)*e+p) for p, e in factorint(n).items()) # Chai Wah Wu, May 15 2022

Formula

a(n) = Sum_{k=1..n-1} (number of divisors of nk that are between k and n, exclusive).

a(n) = Sum_{k=1..n-1} (number of divisors of nk - 2*(number of divisors of nk that are <= k)).

a(n) = A006579(n) - (n-1). - Michel Marcus, Feb 09 2016

a(p^k) = (p(k-1)-k)*p^(k-1)+1 for prime p. - Chai Wah Wu, May 15 2022