cp's OEIS Frontend

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.

%I A229964 #21 Aug 09 2024 15:15:38
%S A229964 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,
%T A229964 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,
%U A229964 4,17,0,12,7,17,0,25,0,14,12,14,2,21,0,21,5
%N 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.
%H A229964 Eric M. Schmidt, <a href="/A229964/b229964.txt">Table of n, a(n) for n = 1..1000</a>
%H A229964 Rosemary Sullivan and Neil Watling, <a href="http://www.emis.de/journals/INTEGERS/papers/n65/n65.Abstract.html">Independent Divisibility Pairs on the Set of Integers from 1 to N</a>, INTEGERS, Electronic J. of Combinatorial Number Theory, Vol. 13, Paper A65, 2013.
%e A229964 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.
%o A229964 (Sage)
%o A229964 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])
%o A229964 def dprob(q, n) : return (n // q)/n
%o A229964 (Python)
%o A229964 from math import lcm
%o A229964 from sympy import divisors
%o A229964 def A229964(n): return sum(1 for d in divisors(n,generator=True) for e in range(d+1,n) if 1<d<n and (n//d)*(n//e)==n*(n//lcm(d,e))) # _Chai Wah Wu_, Aug 09 2024
%Y A229964 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.
%K A229964 nonn
%O A229964 1,12
%A A229964 _Eric M. Schmidt_, Oct 04 2013