For what natural $n$ does there exist a cube composed of $n$ cubes and more

Not a complete answer, just my idea and thoughts on it so far.

Summary

In short, I have split the problem into $c\in\mathbb N$ subproblems. It seems your initial coefficients idea is equivalent to $c=0,1$ combined with $n=n_2+(n_1-1)$ lemma, so you are missing solutions when $c\ge 2$ is not reachable by the lemma.

This is not a complete answer. I will present an idea and I will use it to replicate finding solvable $n$ for $m\le 3$, and find nontrivial $n=49, 51, 54$ that you missed. These are indeed the only three "hard" cases for $m=3$. Having said that, solving this for general $m$ will likely remain an open problem.

I haven't found anything significant online except this 1997. paper Dissecting d-Cubes into Smaller d-Cubes which solves $m\le 2$ and conjectures $m=3$ solution (the problem that wasn't solved at the time was proving not-found small cases of $n$ can't be done). Paper also gives some bounds on $m=4,5$ and asymptotics for general $m$. The $m=3$ case is now claimed solved (the small not-found $n$ have been proven impossible) according to mathworld (linked in comments by pregunton). The larger cases $m\ge 4$ are an open problem as far as I know.

The $c\in\mathbb N$ subproblem idea

Lemma. First note that if $n_1,n_2$ are possible, then so is $n_1+(n_2-1)$.

Also notice that two smallest cubes we can dissect into are always $n=1,2^m$.

I wanted to do a computer search on fixed $m$ to prove and disprove solutions of $n$ up to some bound $n\le n_0$. If $n_0$ is large enough, it will be easy to show all $n\ge n_0$ are possible as well. The idea was to solve the given $m$ case computationally, but there is one (or two) problem(s) that needs to be resolved (if possible) before the idea can be efficient.

Now, my idea was to split every $m$ (dimension) case into countably many cases. That is, every dissection of a cube contains either one case of $c=0,1,2,3\dots$ many composite cubes (cubes made of unit cubes).

(When I say "cube", I think of "$m$-cube".)

That is, start with a $k$-side cube ($k^m$ many unit $m$-cubes). We will be combining those cubes into $a_1,\dots,a_c$ side cubes. This will reduce the number of cubes by $a_i^m-1,i=1,\dots,c$. The problem becomes to find all $n$ for which some $(a_1,\dots,a_c)$ dissection is possible, where $1\lt a_1,\dots,a_c\lt k$ at least, and let $k\gt 1$.

$$ n=k^m-\sum_{i=1}^c a_i^m+c $$

Considering these equations for all possible $(a_1,\dots,a_c)$, will give all possible $n$. Note that to solve some $m$, only finitely many $c$ (dissection) cases need to be considered ($c\lt n_0$).

But the problem is that for $c\ge 2$ not all $(a_1,\dots,a_c)$ are possible. We need additional conditions to secure that $a_1,\dots,a_c$ side $m$-cubes can indeed be packed into a $k$-side $m$-cube in some way.

For $c=2$ for example, if you put $a_1$ in the corner, we are left with $k-a_1$ room in all of the $m$ dimensions (directions) hence $a_2\le k-a_1$. But if you put it some distance away from all corners, we get $a_2\le k-a_1-j$ which can only be worse. Of course we want to leave the most space free for $a_2$ after placing $a_1$, hence for $c=2$ the only additional restriction is $a_1+a_2\le k$, regardless of $m$. At the end I mention we have similar conditions for $c\le 2^m$. But for larger $c$, I do not see obvious (simple) conditions.

By using $n_1+(n_2-1)$ lemma on $c\le 2$ we can reach some of the $c\gt2$ cases (without needing to think about packing conditions), but not all of them, and this is when we miss some of the solutions.

I will first consider $m=1,2,3$ examples and show how to use this idea to search for solvable $n$.

Solving $(m\le 3)$ using the idea

$(m=1)$

For completion, you can include $m=1$. That is, we have a segment.

Combining any number of unit segments yields a segment, hence all $n\in\mathbb N$ are possible. Here it was sufficient to consider $c=0$ (use only unit $1$-cubes), to show that all $n$ have at least one dissection.

$(m=2)$

This was already solved as you already mentioned. For completion, lets see how my idea applies here.

(trivial cases): First, assume $n\ge2^2=4$ since $n=1,2^m$ are possible and $2,\dots,2^m-1$ are not.

Considering $c=0$, gives that all $n=k^2=(4),9,16,25\dots$ cubes are possible.

Considering $c=1$, $n=k^m-a_1^m+1$. Trying largest $a_1=k-1$ gives $k^2-(k-1)^2+1=2k$.

We obtained that all even numbers $n\ge 4$ are possible. Using the fact that $n_2=2^2=4$ is the smallest $2$-cube, and that we can combine cube dissections as $n_1+(n_2-1)$, we have that the smallest dissection increment is $(n_2-1)=3$. Hence, all $2k+3$ are also possible, giving all odd numbers $n\ge7$.

This leaves only nontrivial impossible case $n=5$, and all nontrivial possible cases are $n\ge 6$.

To solve $m=2$, all we used was the minimized $c=0,1$ cases and their combinations.

(It can be shown $n=5$ can't be obtained with $c\ge 2$ cases, so we are done.)

$(m=3)$

Generally, we assume $n\ge2^m$ since $n=1,2^m$ are possible and $2,\dots,2^m-1$ are not (trivial cases). The smallest dissection increment is hence $(n_2-1)=2^m-1$. In this case, we have it is $(2^3-1)=7$.

This case is solved as mentioned in the comments, so I will be going after reconstructing all claimed possible $n\le 54$ by applying a restricted search on $c$ cases. Combining those, it is easily shown all $n\ge 48$ are all possible.

$(3.1.)$ That is, we preform a solution search on $c=0,1$ for $n\le 54$, to obtain:

The $c=0$ gives $n=k^3=(8), 27, 64,\dots$

The $c=1,a_1=k-1$ gives $n=k^3-(k-1)^3+1= (8),20,38,62\dots$

The $c=1,a_1=k-2$ gives $n=k^3-(k-2)^3+1= (27),57,99\dots$

The $c=1,a_1=k-3$ or beyond gives $n\gt 54$.

Using $n_2=8$ on $(c=0,k=2)\to n_1=8$ we obtain $n=15,22,29,36,43,50,\dots$

Using $n_2=8$ on $(c=0,k=3)\to n_1=27$ we obtain $n=34,41,48,55,\dots$

Using $n_2=8$ on $(c=1,k-1=1,2)$ gives duplicates. On $(c=1,k=4)$ gives $n=45,52\dots$

Using $n_2=8$ on $(c=1,k-2=1)$ gives duplicates. On larger, gives $n\gt 54$.

We have now obtained all $n\le 54$ possible with inserting minimal $(n_2-1)$ into $c=0,1$, which are:

$$n=1, 8, 15, 20, 22, 27, 29, 34, 36, 38, 41, 43, 45, 48, 50, 52$$

We are missing $n=39,46,49,51,53,54$ to construct all claimed possible $n\le 54$.

The second smallest $(n_2-1)$ that we have (and is not a multiple of previous) is $(n_2-1)=(20-1)=19$.

Combining $19$ with $n\le 54$ we have so far yields additionally $n=39,46,53$ but not $n=49,51,54$.

Other such $(n_2-1)$ small enough are $26,33,37$, but they do not yield any additional $n\le 54$ solutions.

That is, $c=0,1$ (combined with $n_1,n_2$ lemma) gives all (claimed possible by mathworld and linked paper) $3$-cubes $n\le 54$ other than $n=49,51,54$.

$(3.2)$ We continue the $n=49,51,54$ solution search on $c= 2$ as follows:

For $c=2$ we have $n=k^3-(a_1^3+a_2^3)+2$ such that $a_1+a_2\le k$.

For $k=3$, we get $n=27-(a_1^3+a_2^3)+2\lt 49$.

For $k=4$ we get $n=64-(a_1^3+a_2^3)+2,(a_1,a_2)=(2,2)$, yielding $n=50$.

For $k\ge5$ we get $n\gt 54$.

And so on. Up to $c\le2^m=2^3=8$, we can verify there are no extra solutions. (Packing is possible if and only if we can pack the individual $m$-cubes in individual corners, which is a simple packing condition.) But for larger $c$, I do not see obvious simple packing conditions.

$(3.3)$ We continue the $n\le 54$ solution search on $c\gt 8$ as follows:

We need to search for $n=49,51,54$ in $c\gt 2^m$ cases, where I'm not sure about "if and only if" packing conditions, which makes this a problem now. (Each found $n$ with some $c$ equation needs to be proven a valid packing individually, if we do not know the "if and only if" conditions for that $c$).

To cut the story short, these three nontrivial ("hard") cases can be found as following dissections:

• $c=13,k=6$ has a dissection $n=6^3-(9\cdot2^3+4\cdot3^3)+13=49$. That is, $$(a_1,\dots,a_{13})=(2,2,2,2,2,2,2,2,2,3,3,3,3)$$ are composite cubes used.

• $c=10,k=6$ has a dissection $n=6^3-(5\cdot2^3+5\cdot3^3)+10=51$. That is, $$(a_1,\dots,a_{10})=(2,2,2,2,2,3,3,3,3,3)$$ are composite cubes used.

• $c=12,k=8$ has a dissection $n=8^3-(4\cdot2^3+2\cdot3^3+6\cdot4^3)+12=54$. That is, $$(a_1,\dots,a_{12})=(2,2,2,2,3,3,4,4,4,4,4,4)$$ are composite cubes used.

To show that these packings (dissections) are possible, we fit the composite cubes in steps:

Where $\color{green}{green}$, $\color{blue}{blue}$, $\color{purple }{purple }$ are cubes of side lengths $2,3,4$, and $\color{orange }{orange }$ cubes are unit cubes. The number in a colored cube is how many cubes are placed there (at the bottom). Numbers in gray areas in down left corners are height of that area. Final image is filled cube.

With all of this, we have obtained all possible $n\le 54$ cubes claimed in linked paper and linked mathworld article. From $n_1+(n_2-1)$ lemma and these solvable $n\le 54$ cubes, it follows that all $n\ge 48$ cubes are possible.

It remains to prove that the not-found $n\lt 48$ cubes are not possible, to fully solve $m=3$. The mathworld link claims this was done, but I haven't found an explicit proof. To prove this with my method, we need to examine relevant $c$ cases (at worst all $c\lt 48$), but this is a problem since I haven't yet found "if and only if" packing conditions for all those cases.

Applying the idea to $(m\ge 4)$

Given any $m$, we could right now implement this idea as an algorithm and find bounds on some $n^{*}$ such that all $n\ge n^{*}$ are possible. But we will be missing some of the small (not large enough) $n\lt n^{*}$ solutions if we search only $c=0,1,2$, for example..

To find them all and prove we are not missing any solutions up to some $n^{*}$, we first need to find the packing conditions for $c\in\mathbb N$ values in general.

That is, we have the following question to overcome:

Given $m$-cubes of integer side lengths $a_1,\dots,a_c$, determine if we can fit them inside $m$-cube of integer side length $k$ or not (such that the remaining empty space can be completely filled with unit cubes)?

Of course it is not hard to start looking for necessary conditions and sufficient conditions for special cases of $c$. For example if $c\le2^m$ then packing is possible if and only if $(\forall i\ne 1)(a_i\le k-a_1)$ where $a_1$ is the largest $m$-cube (place $\le2^m$ cubes into the $2^m$ corners of the $m$-cube). But in general I'm not sure how to verify that I have all sufficient conditions or not.

Alternatively, perhaps there are algorithms to answer the posed question in general, so we can run a search on all necessary $c\in\mathbb N$ and not miss any small solutions. I haven't looked into this yet so this is where my work stops for now.

The best asymptotic on $n^{*}$ (according to linked paper) that is known is $O((2m)^{m-1})$, so we will need to check quite a lot of $c$ cases and $(a_1,\dots,a_c)$ cases, unless we can optimize this idea.

The bounds that the linked paper provides are $n^{*}\le809,1891$ for $m=4,5$.

Not a complete answer, just my idea. If I missed something so far, let me know.