If f(a,b) is the minimal number of squares needed for an aXb rectangle, an array plot of those values looks like the following, with gray levels for 1 to 13 squares, cyan for 14 squares, red for 15-18 squares, and yellow for 19+ squares. The anomalies are at 323 and 352. http://i.imgur.com/rmqWTkJ.jpg So I went ahead and calculated k = f(a + b, b) - f(a, b) for various fixed b values. Let g(b) be the position where the value of k is 1 and stays 1 for all subsequent values of a. To b=203, the values look like 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 6, 14, 4, 4, 4, 4, 20, 6, 16, 9, 20, 10, 10, 6, 14, 26, 27, 28, 10, 26, 24, 33, 32, 16, 24, 21, 39, 29, 32, 27, 31, 40, 17, 18, 39, 18, 19, 41, 28, 60, 30, 33, 44, 36, 52, 24, 78, 43, 55, 44, 34, 50, 51, 82, 47, 71, 65, 62, 63, 32, 62, 66, 70, 68, 80, 86, 77, 30, 98, 36, 63, 80, 53, 76, 106, 77, 79, 70, 82, 82, 64, 68, 116, 85, 42, 76, 96, 88, 81, 64, 72, 97, 119, 66, 94, 73, 120, 131, 87, 115, 90, 65, 103, 75, 78, 133, 155, 79, 106, 85, 109, 100, 116, 110, 67, 98, 154, 81, 101, 104, 163, 118, 93, 55, 141, 97, 134, 116, 123, 93, 162, 126, 124, 101, 123, 124, 131, 70, 139, 182, 135, 136, 159, 109, 202, 178, 153, 109, 108, 136, 195, 144, 120, 140, 182, 94, 159, 140, 122, 147, 154, 161, 142, 125, 153, 114, 172, 140, 139, 156, 196, 132, 163, 143, 148, 152, 142, 164, 183, 117, 169, 185, 126, 130, 151, 141, 159, 159, 175, 176. g(b)>b for 53, 60, 67, 69, 78, 79, 82, 88, 96, 106, 110, 111, 113, 119, 120, 130, 134, 138, 144, 153, 156, 158, 159, 164, 168, 184. For example, g(53) = 60, so f(59 + 53, 53) - f(59, 53) = 0 and values above 59 give 1. The following shows pictures of f(59 + 53, 53) and f(59, 53), each needing 11 squares. http://i.imgur.com/ORGV008.jpg The initial table of values looks like following, with b, h(b), g(b), and terms of f(a + b, b) - f(a, b) for a from 1 to g(b). 1,1,1,(1) 2,1,1,(1) 3,1,1,(1) 4,1,1,(1) 5,1,2,(0,1) 6,2,2,(-1,1) 7,1,2,(0,1) 8,2,2,(-1,1) 9,2,2,(-3,1) 10,2,3,(-4,0,1) 11,3,3,(-4,-1,1) 12,3,3,(-5,-1,1) 13,2,3,(-6,0,1) 14,2,6,(-7,0,0,1,0,1) 15,3,14,(-8,-1,0,0,1,1,0,0,1,1,1,1,0,1) 16,4,4,(-8,-1,-1,1) 17,4,4,(-9,-1,-1,1) 18,4,4,(-11,-3,-1,1) 19,4,4,(-10,-4,-1,1) 20,4,20,(-12,-4,-1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1) 21,3,6,(-13,-4,0,-1,0,1) 22,5,16,(-14,-4,-2,-1,0,1,0,1,0,1,1,1,1,1,0,1) 23,5,9,(-15,-5,-2,-1,1,1,1,-1,1) 24,5,20,(-16,-5,-1,-1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0,1) 25,4,10,(-17,-4,-1,0,0,0,1,1,0,1) 26,4,10,(-18,-6,-3,0,-1,1,0,1,-1,1) 27,4,6,(-19,-7,-3,0,-1,1) 28,4,14,(-19,-7,-4,0,-1,0,1,1,1,0,1,1,0,1) 29,6,26,(-20,-8,-4,-2,-1,0,0,0,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1) 30,6,27,(-22,-8,-4,-1,-1,0,0,0,1,1,1,1,0,0,1,0,0,1,1,1,1,1,0,1,1,0,1) 31,5,28,(-22,-8,-4,-3,0,1,0,-1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1) 32,7,10,(-23,-8,-3,-1,-2,-1,1,1,0,1) 33,7,26,(-24,-9,-4,-3,-1,-1,0,-1,1,0,1,1,1,1,1,1,0,1,1,1,1,1,1,1,0,1) 34,7,24,(-26,-9,-5,-1,-2,-1,0,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,0,1) An array plot of sign(f(a + b, b) - f(a, b)) looks like the following, with white=-1, gray=0, black=1. http://i.imgur.com/OgXibuB.jpg Let h(b) be the position where the value of k is non-negative for the first time. To b=300, the values look like 1, 1, 1, 1, 1, 2, 1, 2, 2, 2, 3, 3, 2, 2, 3, 4, 4, 4, 4, 4, 3, 5, 5, 5, 4, 4, 4, 4, 6, 6, 5, 7, 7, 7, 5, 5, 8, 8, 6, 8, 10, 6, 9, 10, 9, 10, 10, 10, 7, 8, 10, 8, 11, 8, 9, 8, 11, 12, 12, 12, 10, 10, 9, 13, 10, 14, 10, 11, 11, 10, 15, 10, 12, 16, 12, 13, 11, 12, 15, 16, 12, 17, 16, 12, 17, 18, 14, 17, 19, 18, 13, 19, 15, 19, 19, 20, 19, 14, 16, 16, 25, 20, 21, 16, 15, 22, 24, 15, 18, 18, 19, 16, 26, 22, 23, 24, 18, 24, 17, 24, 27, 20, 23, 20, 20, 18, 27, 26, 26, 20, 25, 28, 19, 20, 20, 22, 26, 22, 26, 20, 30, 30, 22, 20, 29, 24, 21, 29, 31, 24, 29, 26, 29, 22, 25, 24, 32, 30, 31, 32, 23, 24, 37, 34, 27, 32, 37, 24, 26, 34, 33, 36, 35, 28, 25, 34, 36, 38, 31, 25, 40, 26, 30, 38, 37, 30, 35, 38, 27, 31, 38, 39, 41, 37, 30, 28, 40, 32, 42, 32, 30, 49, 29, 33, 41, 42, 33, 32, 42, 30, 43, 44, 41, 37, 43, 30, 31, 36, 36, 36, 34, 38, 46, 32, 36, 43, 42, 39, 45, 46, 33, 48, 41, 36, 44, 48, 44, 34, 46, 47, 46, 49, 36, 40, 35, 46, 38, 40, 48, 40, 49, 35, 50, 51, 50, 52, 51, 52, 37, 40, 42, 49, 53, 51, 52, 38, 52, 40, 51, 40, 52, 44, 39, 52, 44, 44, 46, 52, 44, 40, 42, 57, 40, 60, 55, 44, 41, 40, 63, 58, 57, 48, 30, 42, 59, 58, 44, 61, 46, 48. If you plot those values, term g(293) = 30 is a very glaring outlier. f(30+ 293, 293) - f(30, 293) = 0, with both rectangles needing 17 squares. http://i.imgur.com/QZreuBf.jpg has a picture of the rectangles. As it happens, 293+30 = 323 ... the glaring outlier mentioned in the title. I didn't know it would pop up as an outlier again when I calculated the sequences. --Ed Pegg Jr On Tue, Jul 11, 2017 at 12:32 PM, Allan Wechsler <acwacw@gmail.com> wrote:
These are exactly the sort of anomalies that are most fascinating to me about this problem. For a given height, as the width increases, the rectangle eventually look like a ribbon, and it is difficult to believe that the optimal strategy isn't to just cut off square pieces from the end. I think my conjecture is just that *eventually* the anomalies have to give out and cutting off squares from the end starts to be the right first move.
The question is, how far do we have to go before we are sure we have entered this periodic regime? Suppose for a given height h, we find that from a width of, say, 7h up to 20h the behavior is completely periodic: all the (w,h) solutions are just (w-h,h) solutions juxtaposed with a square of side h. Is it now impossible that 20h + w' is an anomaly of the kind Ed displays in his image? Could anomalies of this kind continue popping up sporadically *forever? *(I mean, for a given h.)
On Tue, Jul 11, 2017 at 11:13 AM, Ed Pegg Jr <ed@mathpuzzle.com> wrote:
That's an interesting conjecture, Allan.
http://i.imgur.com/ohYcGCy.jpg gives some cases where things get weird in rectangle dissections. In these, f(k,n) - f(k,n-2k) = 0.
--Ed Pegg Jr
On Mon, Jul 10, 2017 at 9:11 PM, Allan Wechsler <acwacw@gmail.com> wrote:
I'm reading the data I gave with very little trouble off that triangle, so I must have been too terse or garbled something I said. I will try again.
I conjecture (and think it must be easy to prove) that, for all positive k,
f(k,n) - f(k,n-k) = 1
for all n greater than some threshold that depends on k.
This threshold itself forms a sequence g(k), and I'm wondering: what is known about g?
On Mon, Jul 10, 2017 at 9:09 PM, Ed Pegg Jr <ed@mathpuzzle.com> wrote:
Dear Allan,
https://oeis.org/A219158 -- doesn't resemble your data.
Values are completely known to f(380,380), with http://int-e.eu/~bf3/squares/ giving a look-up function.
--Ed Pegg Jr
On Mon, Jul 10, 2017 at 6:52 PM, Allan Wechsler <acwacw@gmail.com> wrote:
Ed, this must be old news. The number of squares required for an n-by-x rectangle, for a fixed n, regarded as a function of x, must eventually enter a pseudo-periodic regime, in which for all x > N, f(x+n) = f(x) +
Hence, if you know f(x) up through N, you know it for all x.
For n = 1, f(x) = x.
For n = 2, f(x) = 0,2, 1,3, 2,4 ...
For n = 3, I'm pretty sure f(x) = 0,3,3, 1,4,4, 2,5,5 ...
For what values of n is f(x) completely understood?
On Mon, Jul 10, 2017 at 4:46 PM, Ed Pegg Jr <ed@mathpuzzle.com> wrote:
I've written this up at the following link. So far the sequence of inexplicably difficult rectangle edges is 180, 323, 352.
https://math.stackexchange.com/questions/2354003/whats- special-about-323-and-squared-rectangles
On Mon, Jul 10, 2017 at 2:35 PM, Ed Pegg Jr <ed@mathpuzzle.com> wrote:
> The minimal number of squares for rectangles up to longest side 380 is > known. > > http://int-e.eu/~bf3/squares/view.html#319,323 needs a minimum of 18 > squares. > > f(323,319)=18, > f(323,293)=17, > f(323,317)=16, > f(323,283)=16, > f(323,281)=16, > > Those are all of the cases up to larger side 380 that need more than 15 > squares if the aspect ratio is less than 2. > For 15 squares, add the value 352 as hard. > > f(323,X)=15, with X in {256, 271, 277, 307, 313} > f(352,X)=15, with X in {283, 289, 293, 299, 307, 311, 317, 325, 329, 331, > 333, 343, 347, 349, 351} > > For rectangles needing 14 squares, more than half the values have larger > side 323 or 352. > > What is special about 323 (and 352) and squares? > > --Ed Pegg Jr > _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun