A229964 Number of pairs of integers q1, q2 with 1 < q1 < q2 < n such that if we randomly pick an integer in {1, ..., n}, the event of being divisible by q1 is independent of being divisible by q2.

0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 3, 0, 3, 2, 1, 0, 4, 0, 5, 1, 3, 0, 8, 0, 4, 3, 4, 0, 10, 0, 7, 3, 5, 2, 9, 0, 6, 4, 9, 0, 13, 0, 12, 6, 6, 0, 16, 0, 9, 6, 9, 0, 14, 1, 12, 3, 8, 0, 25, 0, 12, 10, 11, 4, 17, 0, 12, 7, 17, 0, 25, 0, 14, 12, 14, 2, 21, 0, 21, 5

Offset: 1

Author

Eric M. Schmidt, Oct 04 2013

Keywords

• nonn

Examples

			If n = 12, then q1 = 2 and q2 = 5 satisfy the condition as the probability of an integer in {1, ..., 12} being divisible by 2 is 1/2, by 5 is 1/6, and by both 2 and 5 is 1/12.
		

Links

• Eric M. Schmidt, Table of n, a(n) for n = 1..1000
• Rosemary Sullivan and Neil Watling, Independent Divisibility Pairs on the Set of Integers from 1 to N, INTEGERS, Electronic J. of Combinatorial Number Theory, Vol. 13, Paper A65, 2013.

Crossrefs

The n such that a(n) = m for various m are given by: m=0, A166684; m=1, A229965; m=2, A082663; m=3, A229966; m=4, A229967.

Programs

Python

from math import lcm
from sympy import divisors
def A229964(n): return sum(1 for d in divisors(n,generator=True) for e in range(d+1,n) if 1Chai Wah Wu, Aug 09 2024

Sage

def A229964(n) : return sum(sum(dprob(q1, n) * dprob(q2, n) == dprob(lcm(q1,q2), n) for q2 in range(q1+1, n)) for q1 in n.divisors() if q1 not in [1,n])
def dprob(q, n) : return (n // q)/n