10
$\begingroup$

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.

$\endgroup$
4
+50
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.