An upper bound for Summative Fission numbers

Question

I recently found OEIS entry A256504 and have been playing around with this sequence a bit. Its definition is:

For a positive integer $n$, find the greatest number of consecutive positive integers (at least 2) which add to $n$. For each of these do the same ... iterate to completion. $F(n)$ is then the total number of integers (including $n$ itself) defined.

And here is an example, $F(24) = 13$:

       24
       /|\
      / | \
     /  |  \
    7   8   9
   / \     /|\
  3   4   / | \
 / \     /  |  \
1   2   2   3   4
           / \
          1   2

Looking at the graph on OEIS these numbers seem to be growing roughly linearly, but I'm not sure how to establish a rigorous bound for it.

A few interesting things I've noticed while checking numbers up to $n = 6\cdot10^6$ (and a few around $10^7$):

• There only seems to be one number where $F(n) > n$: $F(11) = 12$
• There only seem to be five numbers where $F(n) = n$: $1$, $3$, $5$, $6$, $23$.

• It appears that the sequence is growing slightly sublinearly.

  After $10^6$, the largest ratio $F(n)/n$ I can find is $0.713924$ for $1110609$.
  After $2\cdot10^6$, it's $0.712693$ for $2097749$.
  After $5\cdot10^6$, it's $0.710524$ for $5570687$.
  After $10^7$, it's $0.709625$ for $10240519$.

So my question is: can an upper bound for the sequence's growth be established rigorously and how tight can we make it? If the maximum ratio $\max_{n>n_0}F(n)/n$ is actually decreasing as $n_0$ grows, does it approach a finite constant?

I suppose it might be helpful to have an upper bound on A109814.

Answer 1

This is a nice question. The fission diagram forms a tree, and the leaves of the tree must sum to $n$. By noting that $3$ is the smallest number that can be split, we see that there can be at most $n/3$ ones, and hence there are at most $\frac{2}{3}n$ leaves. Each vertex that is not the base point or a leaf must have degree at least $3$, that is each node that is not a leaf must split into at least two more nodes, so we can bound the total number of nodes by $$F(n)\leq \frac{2n}{3}+\frac{2n}{6}+\frac{2n}{12}+\frac{2n}{24}+\cdots =\frac{4n}{3}$$ which gives a linear upper bound on the number of nodes.