cp's OEIS Frontend

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

%I A381769 #85 Jul 23 2025 10:05:19
%S A381769 0,0,0,0,3,12,25,49,81,121,182,272,380,506,676,900,1156,1444,1806,
%T A381769 2256,2756,3306,3969,4761,5625,6561,7656,8930,10302,11772,13456,15376,
%U A381769 17424,19600,22052,24806,27722,30800,34225,38025,42025,46225,50850,55932,61256,66822,72900,79524,86436,93636
%N A381769 a(n) is the area of the largest rectangle that can be formed from n sticks whose lengths are 1, 2, ..., n.
%C A381769 For k >= 0 and n = 8k, 8k+1, 8k+6, or 8k+7, a(n) is a square.
%C A381769 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.
%C A381769 The cases not covered are n = 2, 3, 4, and 5.
%C A381769 For n >= 5 the solutions follow a predictable pattern.
%C A381769 For n >= 5 and (n≡0 mod 4 or n≡3 mod 4) all sticks contribute to the rectangle.
%C A381769 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.
%C A381769 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.
%C A381769 From _M. F. Hasler_, Mar 10 2025: (Start)
%C A381769 Theorem 2: Let n = 8k + r > 4 with k = round(n/8), and let L = k*(n + r + 1) = k*(8k + 2r + 1). Then
%C A381769   a(n) = L^2 if -3 < r < 2 or else L*(L+1) if r = 2 or -3, or else (L+1)*(L+2).
%C A381769 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.
%C A381769 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).
%C A381769 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).
%C A381769 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).
%C A381769 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).
%C A381769 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.
%C A381769 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).
%C A381769 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.
%C A381769 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).
%C A381769 (End)
%H A381769 Daniel Mondot, <a href="/A381769/b381769.txt">Table of n, a(n) for n = 0..10000</a>
%H A381769 Daniel Mondot, <a href="/A381769/a381769.txt">Proof of Theorem 1.</a>
%e A381769 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.
%e A381769  _ _ _ _ _
%e A381769 |       |
%e A381769 |       |
%e A381769 |_ _ _ _|
%t A381769 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)]]];
%t A381769 Array[a381769, 50, 0] (* _Paolo Xausa_, Jul 23 2025, after _M. F. Hasler_ *)
%o A381769 (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)
%o A381769 apply(A381769, [0..55]) \\ _M. F. Hasler_, Mar 10 2025
%o A381769 (Python)
%o A381769 def A381769(n): k=(n+4)//8; r=n-k*8; k*=n+r+1; return(k if -4<r<3 else k+2)*(k if -3<r<2 else k+1)if n>4 else (n==4)*3 # _M. F. Hasler_, Mar 11 2025
%K A381769 nonn,easy,nice
%O A381769 0,5
%A A381769 _Ali Sada_ and _Daniel Mondot_, Mar 06 2025
%E A381769 Edited by _N. J. A. Sloane_, Mar 10 2025