Make a rectangle from a collection of (sliced) squares Inspired by Make a Rectangle from a Triangle.

Task

There is a famous formula on the sum of first \$n\$ squares:

$$
1^2 + 2^2 + \dots + n^2 = \frac{n(n+1)(2n+1)}{6}
$$

It is known that this number is composite for any \$n \ge 3\$.

Now, imagine a collection of row tiles (a tile of shape \$1 \times k\$ with the number \$k\$ written on each cell), and you have 1 copy of size-1 tile, 2 copies of size-2 tiles, ... and \$n\$ copies of size-\$n\$ tiles.

[1]  [2 2]  [2 2]  [3 3 3]  [3 3 3]  [3 3 3] ...


Then arrange them into a rectangle whose width and height are both \$ \ge 2\$. You can place each tile horizontally or vertically.

+-----+---+-+-+
|3 3 3|2 2|1|2|
+-----+---+-+ |
|3 3 3|3 3 3|2|
+-----+-----+-+


Output such a matrix if it exists. You don't need to indicate the boundaries; just output the resulting matrix of integers. Your program may do whatever you want if the solution doesn't exist.

I believe there exists a solution for any \$n \ge 3\$. Please let me know if you find a proof or counterexample!

Standard code-golf rules apply. The shortest code in bytes wins.

Examples

n = 3: (2x7 example)
3 3 3 3 3 3 1
3 3 3 2 2 2 2

n = 4: (3x10 example)
4 4 4 4 4 4 4 4 2 2
4 4 4 4 3 3 3 2 2 1
4 4 4 4 3 3 3 3 3 3

n = 5: (5x11 example)
5 5 5 5 5 4 4 4 3 3 3
5 5 5 5 5 4 4 4 3 3 1
5 5 5 5 5 4 4 4 3 3 2
5 5 5 5 5 4 4 4 3 3 2
5 5 5 5 5 4 4 4 4 2 2

n = 6: (7x13 example)
6 6 6 6 6 5 5 5 5 5 3 3 3
6 6 6 6 6 5 5 5 5 3 3 3 1
6 6 6 6 6 5 5 5 5 4 3 3 3
6 6 6 6 6 5 5 5 5 4 4 4 2
6 6 6 6 6 5 5 5 5 4 4 4 2
6 6 6 6 6 5 5 5 5 4 4 4 2
6 6 6 6 6 6 4 4 4 4 4 4 2
Python 2, 238 ... 186 bytes

-2 bytes thanks to @Arnauld!

-5 bytes thanks to @ovs!!

-6 bytes thanks to @Jonathan Allan!!



n=input()
p=w=~n*n*(~n-n)/6
e=range(n+1)
def f(a,b,c,d=[]):1&gt;a&gt;exit(c);1&gt;b&gt;f(a-1,w,c+[d]);g=n;exec"e[g]-=1;g&lt;=b&gt;-1&lt;e[g]&gt;f(a,b-g,c,d+[g]*g);e[g]+=1;g-=1;"*n
while 1:1&gt;p%w&gt;f(p/w,w,[]);w-=1


Try it online!

Notice that the above code only used horizontal tiles. To prove it's correct...



C++ (gcc), 4355 bytes

This code is an explicit construction using only horizontal tiles for \$n&gt;6\$. It can produce correct solutions (at least) up to \$n=99\$.



#include &lt;bits/stdc++.h&gt;
using namespace std;
void dim(int x,int&amp;p,int&amp;q)
{
&#9;int u[]={x,x+1,x+x+1},o=0;
&#9;while(u[o]%2) ++o; u[o]/=2;
&#9;o=0; while(u[o]%3) ++o; u[o]/=3;
&#9;sort(u,u+3);if(x%3==1)swap(u[0],u[1]);
&#9;p=u[0];q=u[1]*u[2];
}
int o[100][99999],c[99999],g[99999];
void brute(int n,int&amp; v,int&amp; u,bool t)
{
&#9;for(int i=1;i&lt;=n;++i) c[i]=i;
&#9;if(t)
&#9;{
&#9;&#9;u=n*(n+1)*(2*n+1)/6,v=2;
&#9;&#9;while(u%v) ++v;
&#9;&#9;if(n&gt;=5) v=u/v;
&#9;&#9;u/=v; c[2]-=n==6;
&#9;}
&#9;for(int i=1;i&lt;=v;++i)
&#9;{
&#9;&#9;int s=u,cnt=0;
&#9;&#9;for(int j=n;j&gt;=1;--j) while(s&gt;=j&amp;&amp;c[j])
&#9;&#9;{
&#9;&#9;&#9;s-=j, --c[j]; for(int k=j;k--;) o[i][++cnt]=j;
&#9;&#9;}
&#9;}
&#9;c[2]+=t&amp;&amp;n==6;
&#9;for(int i=u;i&gt;=u-1&amp;&amp;i;--i)
&#9;&#9;for(int j=1;j&lt;=v;++j) if(!o[j][i])
&#9;&#9;{
&#9;&#9;&#9;int x=0; while(!c[x]) ++x;
&#9;&#9;&#9;--c[x]; int l=x; --j;
&#9;&#9;&#9;while(l--) o[++j][i]=x;
&#9;&#9;}
}
int s0[99999],s1[99999];
//find a subset of a with sum b
//guaranteed b is half of a's sum
//guaranteed a is consecutive
pair&lt;vector&lt;int&gt;,vector&lt;int&gt;&gt; solve2(vector&lt;int&gt; a,int b)
{
&#9;if(!a.size()) return make_pair(a,a);
&#9;int w=0,s=0,as=a.size();
&#9;for(int i=0;i&lt;as;++i)
&#9;&#9;s0[i+1]=s0[i]+a[i],
&#9;&#9;s1[i+1]=s1[i]+a[as-1-i];
&#9;while(w&lt;a.size()&amp;&amp;s+a[w]&lt;=b)
&#9;&#9;s+=a[w++];
&#9;assert(w!=a.size()&amp;&amp;w&gt;0);
&#9;for(int l=0;l&lt;w;++l)
&#9;{
&#9;&#9;int r=w-1-l;
&#9;&#9;int p=s0[l]+s1[r];
&#9;&#9;if(p&gt;b) continue;
&#9;&#9;int q=b-p;
&#9;&#9;if(!(a[l]&lt;=q&amp;&amp;q&lt;=a[as-r-1]))
&#9;&#9;&#9;continue;
&#9;&#9;//first l, last r, q.
&#9;&#9;vector&lt;int&gt; A,B;
&#9;&#9;for(int j=0;j&lt;l;++j) A.push_back(a[j]);
&#9;&#9;A.push_back(q);
&#9;&#9;for(int j=as-r;j&lt;as;++j) A.push_back(a[j]);
&#9;&#9;for(int j=l;j&lt;as-r;++j)
&#9;&#9;{
&#9;&#9;&#9;if(a[j]==q) q=-1;
&#9;&#9;&#9;else B.push_back(a[j]);
&#9;&#9;}
&#9;&#9;return make_pair(A,B);
&#9;}
&#9;assert(0);
}
int main()
{
&#9;int n,p,q;
&#9;cin&gt;&gt;n;
&#9;assert(n&gt;=3);
&#9;if(n&lt;=6) brute(n,p,q,1);
&#9;else
&#9;{
&#9;&#9;if(n%3==1)
&#9;&#9;{
&#9;&#9;&#9;int x=n%3,pp,qq;
&#9;&#9;&#9;dim(x,p,q);
&#9;&#9;&#9;brute(x,p,q,0);
&#9;&#9;&#9;while(n!=x)
&#9;&#9;&#9;{
&#9;&#9;&#9;&#9;//x+1...x+3
&#9;&#9;&#9;&#9;int xx=x+3; dim(xx,pp,qq);
&#9;&#9;&#9;&#9;assert(pp-p==2&amp;&amp;qq-q==x*3+6);
&#9;&#9;&#9;&#9;for(int i=x+1;i&lt;=x+3;++i) c[i]=i;
&#9;&#9;&#9;&#9;int mr=x/6;
&#9;&#9;&#9;&#9;for(int i=1;i&lt;=p;++i)
&#9;&#9;&#9;&#9;{
&#9;&#9;&#9;&#9;&#9;int cnt=q;
&#9;&#9;&#9;&#9;&#9;vector&lt;int&gt; rv;
&#9;&#9;&#9;&#9;&#9;if(i&lt;=mr) rv=vector&lt;int&gt;{x+2,x+2,x+2};
&#9;&#9;&#9;&#9;&#9;else rv=vector&lt;int&gt;{x+1,x+2,x+3};
&#9;&#9;&#9;&#9;&#9;for(int j:rv)
&#9;&#9;&#9;&#9;&#9;{
&#9;&#9;&#9;&#9;&#9;&#9;assert(c[j]); --c[j];
&#9;&#9;&#9;&#9;&#9;&#9;for(int k=j;k--;) o[i][++cnt]=j;
&#9;&#9;&#9;&#9;&#9;}
&#9;&#9;&#9;&#9;}
&#9;&#9;&#9;&#9;vector&lt;int&gt; rv;
&#9;&#9;&#9;&#9;for(int i=x+1;i&lt;=x+3;++i)
&#9;&#9;&#9;&#9;&#9;for(int j=c[i];j;--j) rv.push_back(i);
&#9;&#9;&#9;&#9;pair&lt;vector&lt;int&gt;,vector&lt;int&gt;&gt; s=solve2(rv,qq);
&#9;&#9;&#9;&#9;for(int i=p+1;i&lt;=pp;++i)
&#9;&#9;&#9;&#9;{
&#9;&#9;&#9;&#9;&#9;int cnt=0;
&#9;&#9;&#9;&#9;&#9;for(auto j:(i==pp)?s.first:s.second)
&#9;&#9;&#9;&#9;&#9;{
&#9;&#9;&#9;&#9;&#9;&#9;assert(c[j]); --c[j];
&#9;&#9;&#9;&#9;&#9;&#9;for(int k=j;k--;) o[i][++cnt]=j;
&#9;&#9;&#9;&#9;&#9;}
&#9;&#9;&#9;&#9;}
&#9;&#9;&#9;&#9;p=pp; q=qq; x=xx;
&#9;&#9;&#9;}
&#9;&#9;}
&#9;&#9;else
&#9;&#9;{
&#9;&#9;&#9;int x=n%6,pp,qq;
&#9;&#9;&#9;dim(x,p,q);
&#9;&#9;&#9;brute(x,p,q,0);
&#9;&#9;&#9;while(n!=x)
&#9;&#9;&#9;{
&#9;&#9;&#9;&#9;int xx=x+6; dim(xx,pp,qq);
&#9;&#9;&#9;&#9;if(n%6==0)
&#9;&#9;&#9;&#9;&#9;assert(pp-p==1&amp;&amp;qq-q==24*x+90); //[1 2 3 4 5 6]*3+[2 3 5 5 6 6]
&#9;&#9;&#9;&#9;else if(n%6==2)
&#9;&#9;&#9;&#9;&#9;assert(pp-p==2&amp;&amp;qq-q==12*x+39); //[1 2 3 4 5 6]+[1 1 2 3 5 6]
&#9;&#9;&#9;&#9;else if(n%6==3)
&#9;&#9;&#9;&#9;&#9;assert(pp-p==2&amp;&amp;qq-q==12*x+45); //[1 2 3 4 5 6]+[1 2 4 5 6 6]
&#9;&#9;&#9;&#9;else if(n%6==5)
&#9;&#9;&#9;&#9;&#9;assert(pp-p==1&amp;&amp;qq-q==24*x+78); //[1 2 3 4 5 6]*3+[1 1 2 2 4 5]
&#9;&#9;&#9;&#9;else assert(0);
&#9;&#9;&#9;&#9;vector&lt;int&gt; uv;
&#9;&#9;&#9;&#9;if(n%6==0) uv=vector&lt;int&gt;{2,3,5,5,6,6};
&#9;&#9;&#9;&#9;else if(n%6==2) uv=vector&lt;int&gt;{1,1,2,3,5,6};
&#9;&#9;&#9;&#9;else if(n%6==3) uv=vector&lt;int&gt;{1,2,4,5,6,6};
&#9;&#9;&#9;&#9;else uv=vector&lt;int&gt;{1,1,2,2,4,5};
&#9;&#9;&#9;&#9;for(int j=1;j&lt;4/(pp-p);++j)
&#9;&#9;&#9;&#9;&#9;for(int k=1;k&lt;=6;++k) uv.push_back(k);
&#9;&#9;&#9;&#9;for(int i=x+1;i&lt;=x+6;++i) c[i]=i;
&#9;&#9;&#9;&#9;for(int i=1;i&lt;=p;++i)
&#9;&#9;&#9;&#9;{
&#9;&#9;&#9;&#9;&#9;int cnt=q;
&#9;&#9;&#9;&#9;&#9;for(auto j_:uv)
&#9;&#9;&#9;&#9;&#9;{
&#9;&#9;&#9;&#9;&#9;&#9;int j=j_+x;
&#9;&#9;&#9;&#9;&#9;&#9;assert(c[j]); --c[j];
&#9;&#9;&#9;&#9;&#9;&#9;for(int k=j;k--;) o[i][++cnt]=j;
&#9;&#9;&#9;&#9;&#9;}
&#9;&#9;&#9;&#9;}
&#9;&#9;&#9;&#9;vector&lt;int&gt; rv;
&#9;&#9;&#9;&#9;for(int i=x+1;i&lt;=x+6;++i)
&#9;&#9;&#9;&#9;&#9;for(int j=c[i];j;--j) rv.push_back(i);
&#9;&#9;&#9;&#9;if(pp-p==2)
&#9;&#9;&#9;&#9;{
&#9;&#9;&#9;&#9;&#9;pair&lt;vector&lt;int&gt;,vector&lt;int&gt;&gt; s=solve2(rv,qq);
&#9;&#9;&#9;&#9;&#9;for(int i=p+1;i&lt;=pp;++i)
&#9;&#9;&#9;&#9;&#9;{
&#9;&#9;&#9;&#9;&#9;&#9;int cnt=0;
&#9;&#9;&#9;&#9;&#9;&#9;for(auto j:(i==pp)?s.first:s.second)
&#9;&#9;&#9;&#9;&#9;&#9;{
&#9;&#9;&#9;&#9;&#9;&#9;&#9;assert(c[j]); --c[j];
&#9;&#9;&#9;&#9;&#9;&#9;&#9;for(int k=j;k--;) o[i][++cnt]=j;
&#9;&#9;&#9;&#9;&#9;&#9;}
&#9;&#9;&#9;&#9;&#9;}
&#9;&#9;&#9;&#9;}
&#9;&#9;&#9;&#9;else
&#9;&#9;&#9;&#9;{
&#9;&#9;&#9;&#9;&#9;int i=pp,cnt=0;
&#9;&#9;&#9;&#9;&#9;for(auto j:rv)
&#9;&#9;&#9;&#9;&#9;{
&#9;&#9;&#9;&#9;&#9;&#9;assert(c[j]); --c[j];
&#9;&#9;&#9;&#9;&#9;&#9;for(int k=j;k--;) o[i][++cnt]=j;
&#9;&#9;&#9;&#9;&#9;}
&#9;&#9;&#9;&#9;}
&#9;&#9;&#9;&#9;p=pp; q=qq; x=xx;
&#9;&#9;&#9;}
&#9;&#9;}
&#9;}
&#9;cerr&lt;&lt;p&lt;&lt;","&lt;&lt;q&lt;&lt;"\n";
&#9;for(int i=1;i&lt;=p;++i,cout&lt;&lt;"\n")
&#9;&#9;for(int j=1;j&lt;=q;++j)
&#9;&#9;&#9;cout&lt;&lt;setw(2)&lt;&lt;o[i][j]&lt;&lt;" ";
&#9;if(n&gt;6)
&#9;{
&#9;&#9;for(int i=1;i&lt;=n;++i) c[i]=i;
&#9;&#9;for(int i=1;i&lt;=p;++i)
&#9;&#9;&#9;for(int j=1;j&lt;=q;++j)
&#9;&#9;&#9;{
&#9;&#9;&#9;&#9;int u=o[i][j];
&#9;&#9;&#9;&#9;assert(u&gt;=1&amp;&amp;u&lt;=n);
&#9;&#9;&#9;&#9;for(int k=2;k&lt;=u;++k)
&#9;&#9;&#9;&#9;&#9;assert(o[i][++j]==u);
&#9;&#9;&#9;&#9;--c[u];
&#9;&#9;&#9;}
&#9;&#9;for(int i=1;i&lt;=n;++i) assert(!c[i]);
&#9;}
}


Try it online!



How does the construction work?

It's an incremental construction. Consider \$n \bmod 6\$, we can have these values for height and width of rectangles:


\$n/6\times (n+1)(2n+1)~(n\bmod 6=0)\$
\$(2n+1)/3\times n(n+1)/2~(n\bmod 6=1)\$
\$(n+1)/3\times n(2n+1)/2~(n\bmod 6=2)\$
\$n/3\times (n+1)(2n+1)/2~(n\bmod 6=3)\$
\$(2n+1)/3\times (n+1)n/2~(n\bmod 6=4)\$
\$(n+1)/6\times n(2n+1)~(n\bmod 6=5)\$


(dimensions might be \$1\$ for \$n\leq 6\$ so these small cases are handled manually)

So the main idea of my construction is:


We construct rectangles with the heights and widths as in above list.
If \$n\bmod 3 \neq 1\$, construct the solution for \$n-6\$ recursively, add in \$n-5,n-4\cdots n\$. The height of the rectangle will only increase 1 or 2.
If \$n\bmod 3=1\$, construct the solution for \$n-3\$ recursively and add in \$n-2,n-1,n\$. The height of the rectangle will only increase 2.
We first carefully assign the new numbers to the added columns, and then put rest of the numbers into one or two added rows.


The rest of the job is some careful casework to pick the numbers. These details are left as an exercise to the readers (Be ready for some long and tedious casework!). If you complete all the details, this should become a formal proof for the existence of the solutions (and using only horizontal tiles!).