Asymptotics of the number of compositions whose summands are the divisors of a number?

(Edited because the n/2 in the exponent in my original sketch was wrong).

Here's what might correspond to a (very) sketchy explanation as to those fans:

What does a typical (unrestricted) composition of an integer look like? Since there are 2^{n-k} compositions of n beginning with k, the expectation of the first element of the composition is actually around 2, and more generally the probability the first number is k decays exponentially with k.

In other words, a toy model for such a composition would be to successively and independently choose integers a_i such that the probability each a_i is equal to k is 2^{-k}, and stop when we reach n. This is problematic in some ways (especially when our sum gets close to n), but this should only affect the last few terms. We fail if we encounter an integer that is not a divisor of n.

By the law of large numbers we need to succeed about n/e_n times, where e_n is the expected value of a_i once we condition on the composition consisting only of divisors of n. Each integer has the same fixed probability c_n of being a divisor (here c_n depends mainly on the small divisors of n, and my intuition is that e_n would be the same way). Making a bunch of unsubstantiated independence assumptions, we would expect the probability a random composition has only divisors to be c_n^{n/e_n}. The fans then correspond to n which share the same small divisors and have approximately equal c_n and e_n.


The number of compositions of n with all parts equal to 1 or 2, for example, is the (n+1)st Fibonacci number, which grows like φn where φ = (1+√5)/2.

The number of compositions of 2p for p a prime, where all parts are equal to 1, 2, p, or 2p, isn't all that much bigger. In particular I believe it has the same exponential growth rate. I suspect this is one of the lines you see.

Replacing 2 with any integer, you can do the same sort of thing; this is what causes your points to fall, for the most part, along straight lines.