A381769 a(n) is the area of the largest rectangle that can be formed from n sticks whose lengths are 1, 2, ..., n.

0, 0, 0, 0, 3, 12, 25, 49, 81, 121, 182, 272, 380, 506, 676, 900, 1156, 1444, 1806, 2256, 2756, 3306, 3969, 4761, 5625, 6561, 7656, 8930, 10302, 11772, 13456, 15376, 17424, 19600, 22052, 24806, 27722, 30800, 34225, 38025, 42025, 46225, 50850, 55932, 61256, 66822, 72900, 79524, 86436, 93636

Offset: 0

Author

Ali Sada and Daniel Mondot, Mar 06 2025

Keywords

• nonn
• easy
• nice

Comments

For k >= 0 and n = 8k, 8k+1, 8k+6, or 8k+7, a(n) is a square.

For k >= 1 and n = 8k+2, 8k+3, 8k+4, or 8k+5 , a(n) is a rectangular number of the form m*(m+1) for some m.

The cases not covered are n = 2, 3, 4, and 5.

For n >= 5 the solutions follow a predictable pattern.

For n >= 5 and (n≡0 mod 4 or n≡3 mod 4) all sticks contribute to the rectangle.

For n >= 5 and (n≡1 mod 4 or n≡2 mod 4) there is portion of length 1 that does not contribute to the rectangle, as in the example below.

Theorem 1: For n >= 13, a(n) = (floor(sqrt(a(n-8)))+2*n-7)*(ceiling(sqrt(a(n-8)))+2*n-7). For proof see link.

From M. F. Hasler, Mar 10 2025: (Start)

Theorem 2: Let n = 8k + r > 4 with k = round(n/8), and let L = k*(n + r + 1) = k*(8k + 2r + 1). Then

a(n) = L^2 if -3 < r < 2 or else L*(L+1) if r = 2 or -3, or else (L+1)*(L+2).

Proof: If n = 8k, we can form 4 sets of equal sum by adding the numbers from n down to 1 one after the other to one of the sets that has the lowest sum. For example, put 8 through 5 into sets A, B, C, D, then 4 through 1 must go into D, C, B and finally A. That way, after every 8 additions, the sum of the elements of each set will be the same. The average number added is (n+1)/2, and each set receives 2*k numbers, so the common sum is L = k*(n+1) = k*(8k + 1), and we can form a square of area a(n) = L^2.

Similarly, if n = 8k + r with r < 8, we proceed in the same way, starting with n and doing k iterations of 8 "additions", the last of which is r+1, when {1, ..., r} remain. Thus, so far, the average of the added numbers is (n + r+1)/2, and the common sum is now L = k*(n + r+1) = k*(8k + 2r+1).

If r = 1, then there remains only {1}. This "unit stick" can be added to any set but won't help for making a larger square, so still a(n) = L^2, with L = k*(8k + 3).

If r = 2, there remains {1, 2}. Adding these to two distinct sets allows to make a rectangle of area a(n) = L*(L+1) where now L = k*(n + 3) = k*(8k + 5).

The reasoning also applies for r = -1: For example, when n = 7, the sets will be {7}, {6, 1}, {5, 2}, {4, 3}. We can actually imagine a 0 added in the last step, to explain the average value (n+0)/2 of the 2k numbers that each set receives, for a common sum of L = k*n. The four sets of equal sum L correspond to a square of area a(n) = L^2, L = k*n = k*(8k - 1).

Now consider r = -2, for example n = 6: The sets will be {6}, {5}, {4, 1}, {3, 2} when nothing is left. We see that three sets again have the usual sum L = k*(n - 1) = k*(8k - 3), and one set has a sum of L+1, which doesn't help to make a larger area: again, a(n) = L^2 in this case.

For n = 8k - 3, two sets will still have the usual sum L = k*(n - 2) = k*(8k - 5), but two sets will have a sum of L+1 and L+2, respectively. (For n = 5, we get {5}, {4}, {3}, {2+1}.) So we can make a rectangle of area a(n) = L(L+1).

For n = 8k - 4, if we distribute all numbers, we have one set with the usual sum L = k*(n-3) = k*(8k-7), but the others have a sum of L+1, L+2 and L+3, respectively. For n = 4, we have {4}, {3}, {2}, {1}, and the best we can make is a rectangle of area a(4) = 1*3 = 3. But if k > 1, we can rearrange the terms to get a larger area: When only {4, 3, 2, 1} remain, we exchange 5 and 6 and add 4, 3, 2, 1 in turn to the set with smallest sum. For example, {12, 5}, {11, 6}, {10, 7}, {9, 8} becomes {12, 6, 1}, {11, 5, 4}, {10, 7, 3}, {9, 8, 2} with sums 19, 20, 20, 19. This way we get an area of a(n) = (L+1)(L+2) for all k > 1.

For n = 8k + 3, after k iterations, the sets have the sum L = k*(n + 4) = k*(8k + 7), and {1, 2, 3} remains. For example, when n = 11, L = 11+4 = 10+5 = 9+6 = 8+7 = 15. If we exchange again 5 and 6 and distribute 1, 2 and 3 to the sets with sums L and L-1, we get two sets with sum L+1 and two with sum L+2. Thus, a(n) = (L+1)(L+2).

(End)

Examples

			For n = 5, the five sticks can be arranged to form a 4 X 3 rectangle, so a(5) = 12. Clockwise from top, the sticks have lengths 5, 3, 4, 2 + 1.
 _ _ _ _ _
|       |
|       |
|_ _ _ _|
		

Links

• Daniel Mondot, Table of n, a(n) for n = 0..10000
• Daniel Mondot, Proof of Theorem 1.

Programs

Mathematica

a381769[n_] := Which[n < 4, 0, n == 4, 3, True, Module[{k = Quotient[n+4, 8], r}, k *= n + (r = n - 8*k) + 1; Which[-3 < r < 2, k^2, r == 2 || r == -3, k*(k+1), True, (k+1)*(k+2)]]];
Array[a381769, 50, 0] (* Paolo Xausa, Jul 23 2025, after M. F. Hasler *)

PARI

A381769(n)=if(n>4, my(k=n\/8, r=n-k*8); ((r<-3||r>2)*2+k*=n+1+r)*(k+(r>1 || r<-2)), n==4, 3)
apply(A381769, [0..55]) \\ M. F. Hasler, Mar 10 2025

Python

def A381769(n): k=(n+4)//8; r=n-k*8; k*=n+r+1; return(k if -44 else (n==4)*3 # M. F. Hasler, Mar 11 2025

Extensions

Edited by N. J. A. Sloane, Mar 10 2025