[seqfan] Divisor partitions

Robert Dougherty-Bliss robert.w.bliss at gmail.com
Thu Mar 26 16:05:55 CET 2020

Dear SeqFans,

If you choose 11 numbers from the set {1, 2, ..., 20}, then there is at
least one pair such that one number in the pair divides the other, i.e.,
we get a "divisor pair."

This is just the pigeonhole principle after noting that {1, 2, ..., 20}
can be partitioned into 10 parts such that any two numbers in the same
part form a divisor pair. I've been calling such partitions "divisor

Let a(n) be the total number of divisor partitions of [n] = {1, 2, ...,
n}, which begins as follows:

    1, 2, 3, 7, 9, 25, 30, 78, 138, 342, 386, 1307

a(n) does not seem to be in the OEIS, nor does the sequence "divisor
partitions of [n] into k parts" for most nice values of k. I've begun a
draft for a(n) at A333517.

I've failed to find recurrences for a(n) or the corresponding "into k
parts" sequence, and I don't yet have a way to compute a(n) for n larger
than about 25.

Does anyone have any insight into these sequences? Does something
related already appear in the OEIS?


More information about the SeqFan mailing list