login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

Number of maximal sets of pairs (t,d) where 2 <= t <= n, d is a proper divisor of t, no t is repeated, and no d is repeated.
1

%I #57 Jan 10 2024 23:54:51

%S 0,1,2,3,4,9,11,19,32,51,58,176,196,269,614,1206,1309,3364,3619,8415,

%T 18079,22330,23711,79058,117094,139277,219667,455621,477477,1544588,

%U 1613790,3362761,7019600,8036377,13732062,48156197,49976001,56250675,116602593,308750265

%N Number of maximal sets of pairs (t,d) where 2 <= t <= n, d is a proper divisor of t, no t is repeated, and no d is repeated.

%C A proper divisor of t is a divisor d in the range 1 <= d < t.

%C Each t in a set of pairs cannot repeat another t in the set, and each d in a set cannot repeat another d, but any t may equal any d (apart from within a pair).

%C A set of pairs is maximal when no further pair could be added without repeating some t or some d.

%C A prime t has a single proper divisor 1, so at most one prime t can appear in a set.

%e For a(8) = 19, the possible t's 1..n are:

%e 1 2 3 4 5 6 7 8

%e Their respective possible proper divisors d are:

%e 1 1 1 1 1 1 1

%e 2 2 2

%e 3 4

%e The sets of (t,d) pairs are:

%e COUNT

%e { (2,1) (4,2) (6,3) (8,4) } 1

%e { (2,1) (6,2) (8,4) } 2

%e { (2,1) (6,3) (8,2) } 3

%e { (3,1) (4,2) (6,3) (8,4) } 4

%e { (3,1) (6,2) (8,4) } 5

%e { (3,1) (6,3) (8,2) } 6

%e { (4,1) (6,2) (8,4) } 7

%e { (4,1) (6,3) (8,2) } 8

%e { (4,2) (5,1) (6,3) (8,4) } 9

%e { (5,1) (6,2) (8,4) } 10

%e { (5,1) (6,3) (8,2) } 11

%e { (4,2) (6,1) (8,4) } 12

%e { (4,1) (6,3) (8,4) } 13

%e { (6,1) (8,2) } 14

%e { (4,2) (6,3) (7,1) (8,4) } 15

%e { (6,2) (7,1) (8,4) } 16

%e { (6,3) (7,1) (8,2) } 17

%e { (4,2) (6,3) (8,1) } 18

%e { (6,2) (8,1) } 19

%e In set number 9, the pairs have d = 1, 2, 3, 4, which are all the possible proper divisors of 1..8.

%e In set number 19, there is no way to include another pair since the unused proper divisors 3 or 4 can only come from t=6 or t=8, and they are already used.

%e Set {(6,3),(8,1)} is not counted since it's not maximal (could have (4,2) included).

%o (Python)

%o from itertools import combinations

%o from networkx import empty_graph,find_cliques

%o from sympy import divisors

%o def A368349(n):

%o G=empty_graph((t,d) for t in range(2,n+1) for d in

%o divisors(t,generator=True,proper=True))

%o for x,y in combinations(G,2):

%o if x[0]!=y[0] and x[1]!=y[1]: G.add_edge(x,y)

%o return sum(1 for c in find_cliques(G)) # _Pontus von Brömssen_, Jan 10 2024

%Y Cf. A027751, A032741.

%K nonn

%O 1,3

%A _Tamas Sandor Nagy_, Dec 22 2023

%E a(12)-a(40) from _Pontus von Brömssen_, Jan 10 2024