OFFSET
1,3
COMMENTS
A proper divisor of t is a divisor d in the range 1 <= d < t.
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).
A set of pairs is maximal when no further pair could be added without repeating some t or some d.
A prime t has a single proper divisor 1, so at most one prime t can appear in a set.
EXAMPLE
For a(8) = 19, the possible t's 1..n are:
1 2 3 4 5 6 7 8
Their respective possible proper divisors d are:
1 1 1 1 1 1 1
2 2 2
3 4
The sets of (t,d) pairs are:
COUNT
{ (2,1) (4,2) (6,3) (8,4) } 1
{ (2,1) (6,2) (8,4) } 2
{ (2,1) (6,3) (8,2) } 3
{ (3,1) (4,2) (6,3) (8,4) } 4
{ (3,1) (6,2) (8,4) } 5
{ (3,1) (6,3) (8,2) } 6
{ (4,1) (6,2) (8,4) } 7
{ (4,1) (6,3) (8,2) } 8
{ (4,2) (5,1) (6,3) (8,4) } 9
{ (5,1) (6,2) (8,4) } 10
{ (5,1) (6,3) (8,2) } 11
{ (4,2) (6,1) (8,4) } 12
{ (4,1) (6,3) (8,4) } 13
{ (6,1) (8,2) } 14
{ (4,2) (6,3) (7,1) (8,4) } 15
{ (6,2) (7,1) (8,4) } 16
{ (6,3) (7,1) (8,2) } 17
{ (4,2) (6,3) (8,1) } 18
{ (6,2) (8,1) } 19
In set number 9, the pairs have d = 1, 2, 3, 4, which are all the possible proper divisors of 1..8.
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.
Set {(6,3),(8,1)} is not counted since it's not maximal (could have (4,2) included).
PROG
(Python)
from itertools import combinations
from networkx import empty_graph, find_cliques
from sympy import divisors
def A368349(n):
G=empty_graph((t, d) for t in range(2, n+1) for d in
divisors(t, generator=True, proper=True))
for x, y in combinations(G, 2):
if x[0]!=y[0] and x[1]!=y[1]: G.add_edge(x, y)
return sum(1 for c in find_cliques(G)) # Pontus von Brömssen, Jan 10 2024
CROSSREFS
KEYWORD
nonn
AUTHOR
Tamas Sandor Nagy, Dec 22 2023
EXTENSIONS
a(12)-a(40) from Pontus von Brömssen, Jan 10 2024
STATUS
approved