# Problem of the Month(August 2009)

This month we investigate three problems involving products.

1. Consider rectangular grids of digits where the product of the numbers in the rows is equal to the product of the numbers in the columns. Since leading 0's should not exist and trailing 0's are less interesting, we only allow positive digits. We also have excluded grids that contain multiple copies of the same factor. We call these multiplicative grids. Can you find some multiplicative grids?

What about other bases? What about non-rectangular grids? What if each entry in the grid is k digits?

2. Suppose k, m, and n are positive integers. If we group the integers 1 through mn into m groups of n and multiply the numbers in each group, how close can the sum of k of these products be to the sum of the other m-k products? For which k, m, and n can we achieve equality? If not, how close can we get?

3. For which integers n > 1 and m does the expression P = xn + xn-1 + . . . + x2 + x + m factor over the integers? What infinite families are there? Can you find any other polynomials of this form that factor over the integers without a linear factor, other than the ones below?

1. Here are the known small multiplicative grids:

 2 × 3```135 156 194 567 576 154 295 276 432 444 ```

 2 × 4```1485 1584 1768 2368 2376 1584 1485 2835 1743 1323 2496 2736 2835 3828 5767 2365 1281 1155 1798 3339 ```

 3 × 3```114 117 118 118 119 124 124 126 128 287 473 468 858 291 426 596 464 363 325 328 385 245 648 285 285 414 646 132 133 133 147 164 216 216 216 232 426 597 774 561 852 319 322 567 621 214 288 212 624 366 273 261 225 126 234 234 246 323 324 342 342 342 357 441 846 561 429 418 528 684 742 671 336 228 525 216 264 235 183 148 624 357 429 452 459 524 528 532 533 722 836 738 982 891 364 442 522 663 468 525 344 146 648 328 475 144 198 168 819 842 844 846 917 918 918 954 896 526 926 936 339 552 588 642 222 213 223 323 311 238 295 364 ```

 2 × 5```25758 27594 27783 34596 35856 14931 13794 11715 12138 14384 56576 58548 63984 83776 96558 14235 13612 11468 12798 16575 ```

 2 × 6``` 289836 117369 (Brian Trial) ```

 4 × 4``` 2424 5294 2448 2642 4433 8442 4466 4721 (Brian Trial) (Brian Trial) ```

Here are the small multiplicative grids in other small bases:

 Base 9 ```168 187 385 388 556 671 736 516 586 487 754 383 116 236 2772 4366 4378 5454 5676 8545 1124 1643 2855 1145 3122 1573 125 125 125 127 127 147 147 164 214 327 372 423 351 677 615 732 873 645 421 416 325 552 416 578 514 376 126 227 236 268 314 317 318 325 332 335 516 783 772 428 376 336 565 512 673 358 367 746 154 388 372 286 142 325 448 456 516 626 628 633 754 846 578 862 325 428 818 831 683 712 748 436 261 372 252 134 376 372 13488 13776 68468 11846 12655 25186 ```

 Base 8 ```156 167 174 252 455 536 671 322 537 264 124 334 272 114 3754 5574 7626 7746 2327 2563 1231 3257 114 117 124 127 127 146 214 237 242 531 273 423 352 674 617 347 713 613 142 512 266 564 416 522 223 375 166 245 322 347 364 423 635 713 724 744 733 416 671 776 572 454 221 733 743 356 144 536 421 162 432 174 145 266 37554 57646 67744 13414 27775 16214 ```

 Base 7 ```366 2256 2525 543 1452 1155 114 114 125 213 215 216 223 246 353 316 255 265 263 312 426 143 366 444 236 422 426 426 624 434 514 534 624 426 523 112 312 252 252 16665 22566 31365 16665 1133 1133 1146 1155 1155 1155 1155 1232 2336 2453 1363 2163 3212 3663 6144 1352 1146 1122 4116 2411 1642 2411 1163 1554 1234 1236 1236 1243 1254 1254 1263 1336 6655 1515 2334 1545 1445 3552 1232 2541 1322 4221 3115 3266 5223 2556 4431 3651 1344 1353 1353 1354 1364 1412 1425 1445 3256 2264 2634 3514 2432 1665 1232 2512 3114 3555 3225 3256 4653 1254 4452 4455 1451 1454 1515 1533 1544 1614 1615 1624 2464 2214 2532 3655 6312 4234 1122 1242 1636 5236 1526 2365 2226 1126 3355 4653 1626 1641 1661 1661 1663 2115 2145 2145 3634 2563 5544 5634 4662 1144 1161 1443 3115 1463 1361 1363 3564 1163 3222 3342 2163 2214 2214 2226 2256 2256 2265 2316 3413 1225 1452 5535 5156 5445 5244 1665 1331 1323 1426 1212 2556 2661 2464 3131 2332 2332 2332 2334 2354 2365 2442 2451 1152 1464 1515 1124 4233 5332 2352 1135 2655 2554 2262 5236 2541 3241 2334 3631 2525 2533 2552 2562 2655 2664 3153 3162 5522 2426 3142 2552 3131 3261 1611 1255 1521 3232 2442 3614 6561 6464 2266 2343 3234 3355 3362 3362 3414 3524 3531 3635 1242 4365 5311 5445 3155 3354 2163 4465 3516 3615 1215 1521 1323 2424 1463 4114 4235 4252 4326 4356 4424 4436 4521 4545 1545 3546 1416 6621 1131 6336 1532 3144 4356 1513 4566 2642 4532 2365 1212 5412 4631 4631 5142 5215 5351 5433 5445 5445 2214 2664 2655 1416 2264 4252 3131 3216 1553 1636 1133 1445 1551 1544 4133 4361 5522 5654 5663 6135 6135 6226 6321 6336 2525 2611 3531 3355 3432 4243 1215 2562 1521 6645 4612 1225 1135 1221 1266 4462 6415 6452 6531 6534 6633 1122 5526 2266 4642 2144 3355 1626 2134 2412 4521 ```

 Base 6 ```154 252 5424 132 235 514 252 154 1144 415 451 241 223 424 252 1135 1143 1155 1225 1232 1243 1243 1244 3352 1452 2443 4355 2352 1251 1544 2133 1525 2314 3313 1552 1254 3412 3441 3121 1342 1342 1441 1441 1512 1513 1544 1551 2452 4445 1254 2541 1344 1344 3543 4335 2124 1523 2512 1112 1443 2233 4233 1514 1552 2125 2244 2541 3143 3315 3344 3552 3552 1252 1412 3544 2124 1143 2152 3512 2453 2242 4425 1443 1324 3424 4514 2544 4334 4353 4515 5324 5424 5513 5532 1554 2132 5522 2421 2153 1315 1332 5424 4132 1144 2125 3525 2332 4222 ```

 Base 5 ```344 2433 413 422 23443 332 1314 224 322 13324 211 143 1124 1124 1224 1312 1314 1344 1433 1342 4343 2141 1443 1232 4144 1411 2141 1122 2123 1234 2334 3432 3441 1441 1442 1443 1443 2241 2244 2431 2442 2324 2421 3342 1314 4343 2142 1342 3234 3443 3343 2123 2442 1342 2442 3124 3212 3231 3322 3333 3342 4343 1441 1144 1141 3423 2134 2234 2244 2123 1312 1232 1111 3414 3234 3432 3441 4141 4422 4314 1444 1322 1434 1423 3423 1124 3234 ```

 Base 4 ```1122 1331 3212 22332 132322 1221 2223 1332 11112 112123 1123 1312 1222 23212 123312 (Philip Mason) (Philip Mason) ```

 Base 3 ``` 2212 1212 1221 (Philip Mason) ```

Philip Mason also found some small multiplicative grids in bases 11, 12, 13, 14, 15, and 16.

Here are the multiplicative non-rectangular polyominoes with small area:

 Area 3```1 1 2 4 64 95 65 98 ```

 Area 4``` 1 1 288 448 147 156 159 168 189 945 2 2 3 3 4 2 24 28 37 93 96 28 48 48 15 48 1 2 3 4 8 448 664 476 495 246 168 195 264 495 567 4 3 2 4 4 1 1 1 3 288 378 784 798 ```

 Area 5```2 3 1764 4896 154 189 273 372 492 544 588 648 675 16 64 18 12 16 18 64 35 35 434 546 12 25 16 28 56 94 448 345 234 276 7896 9765 4 2 366 498 648 984 15 36 15 15 164 432 618 9 1 2 2 6 4 1 1 1 2 2 4 6 9 264 495 945 165 684 198 285 147 5 8 7 4 5 5 4 5 138 248 615 4 6 2 5 5 3 1 1 1 1 2 2 3 4 6 6 6 8 8 4 6 7 9 7 324 784 345 465 186 178 288 328 128 16 17 26 31 38 41 7 4 6 2 5 2 24 88 34 48 54 36 55 61 66 71 72 77 9 2 9 4 1 4 48 24 35 28 63 85 15 18 35 39 68 4 6 3 6 6 24 12 16 14 13 1 7 1 8 2 1 2 3 2 4 3 8 4 2 432 748 432 112 861 224 864 4 6 4 7 6 9 7 8 8 1 8 2 8 7 224 225 336 444 645 441 444 126 144 184 329 336 344 348 5 3 2 8 5 6 5 4 5 4 6 3 5 7 594 644 644 663 693 748 855 861 5 8 3 6 9 2 5 4 6 5 7 5 4 7 2 4 16 19 28 37 63 92 49 23 46 46 74 36 8 8 9 9 2 4 18 18 19 19 19 27 29 29 24 32 36 54 72 14 54 81 7 6 8 7 6 8 8 7 36 38 39 57 58 76 78 87 12 16 72 14 24 12 32 21 8 9 8 9 9 9 9 9 11 12 23 26 27 38 44 44 55 36 15 48 35 24 54 26 63 24 2 6 5 7 9 5 9 2 8 61 62 63 72 77 88 99 99 99 24 15 12 14 22 44 21 43 66 2 7 5 6 6 7 4 6 8 15 15 28 35 36 65 77 88 99 24 62 14 26 21 12 22 44 66 4 4 5 4 5 4 6 7 8 1 2 2 2 2 3 6 6 8 77 13 36 63 88 12 26 38 36 64 45 44 11 65 45 34 45 45 1 1 1 3 3 6 6 6 7 9 65 75 85 35 46 45 48 68 35 45 39 35 77 16 15 48 18 13 15 35 ```

Here are the small multiplicative grids when we allow some of the grid entries to be 2 digit numbers:

 2 × 2 ``` 1 3 1 3 1 6 1 9 2 4 2 7 3 9 4 1 33 25 38 64 66 4 99 5 49 8 77 56 99 75 16 64 4 9 8 3 12 4 16 6 19 9 21 7 24 9 49 9 99 8 33 32 49 96 66 64 99 95 77 75 99 96 99 98 ```

2. Here are the best known results. When the left hand side and right hand side differ, the difference is given in red.

n \ m23
1 2 ≈ 1 [1] 3 = 1 + 2
2 2⋅3 ≈ 1⋅4 [2] 4⋅5 = 1⋅2 + 3⋅6
3 1⋅5⋅6 ≈ 2⋅3⋅4 [6] 4⋅5⋅9 = 1⋅2⋅6 + 3⋅7⋅8
4 2⋅3⋅5⋅7 ≈ 1⋅4⋅6⋅8 [18] 4⋅5⋅8⋅12 ≈ 1⋅2⋅7⋅10 + 3⋅6⋅9⋅11 [2]
5 2⋅4⋅5⋅6⋅8 ≈ 1⋅3⋅7⋅9⋅10 [30] 4⋅5⋅10⋅11⋅15 = 1⋅2⋅6⋅8⋅13 + 3⋅7⋅9⋅12⋅14
6 2⋅4⋅5⋅6⋅9⋅10 ≈ 1⋅3⋅7⋅8⋅11⋅12 [576] 1⋅7⋅12⋅13⋅15⋅18 ≈ 2⋅4⋅8⋅10⋅14⋅16 + 3⋅5⋅6⋅9⋅11⋅17 [10]
(Berend van der Zwaag)
7 2⋅4⋅6⋅7⋅8⋅10⋅11 ≈ 1⋅3⋅5⋅9⋅12⋅13⋅14 [840] 2⋅4⋅8⋅16⋅17⋅18⋅20 ≈ 1⋅5⋅9⋅10⋅13⋅15⋅21 + 3⋅6⋅7⋅11⋅12⋅14⋅19 [18]
(Berend van der Zwaag)
8 2⋅4⋅6⋅8⋅9⋅10⋅11⋅12 ≈ 1⋅3⋅5⋅7⋅13⋅14⋅15⋅16 [24480] 3⋅6⋅9⋅12⋅15⋅17⋅18⋅23 = 1⋅2⋅8⋅10⋅13⋅16⋅20⋅24 + 4⋅5⋅7⋅11⋅14⋅19⋅21⋅22
(Berend van der Zwaag)
9 2⋅4⋅5⋅7⋅8⋅10⋅14⋅15⋅17 ≈ 1⋅3⋅6⋅9⋅11⋅12⋅13⋅16⋅18 [93696]
10 3⋅4⋅5⋅7⋅8⋅10⋅13⋅14⋅15⋅17 ≈ 1⋅2⋅6⋅9⋅11⋅12⋅16⋅18⋅19⋅20 [800640]
11 4⋅5⋅6⋅7⋅9⋅10⋅11⋅12⋅14⋅15⋅16 ≈ 1⋅2⋅3⋅8⋅13⋅17⋅18⋅19⋅20⋅21⋅22 [7983360]
12 3⋅5⋅6⋅7⋅8⋅10⋅12⋅14⋅16⋅17⋅18⋅19 ≈ 1⋅2⋅4⋅9⋅11⋅13⋅15⋅20⋅21⋅22⋅23⋅24 [65318400]
13 1⋅2⋅4⋅8⋅10⋅16⋅17⋅19⋅20⋅22⋅23⋅24⋅25 ≈ 3⋅5⋅6⋅7⋅9⋅11⋅12⋅13⋅14⋅15⋅18⋅21⋅26 [2286926400]

n \ m45
1 4 ≈ 1 + 2 + 3 [2]
1 + 4 = 2 + 3
5 ≈ 1 + 2 + 3 + 4 [5]
3 + 4 ≈ 1 + 2 + 5 [1]
2 5⋅8 = 1⋅6 + 2⋅3 + 4⋅7
3⋅8 + 4⋅5 = 1⋅2 + 6⋅7
8⋅10 = 1⋅3 + 2⋅9 + 4⋅6 + 5⋅7
1⋅9 + 6⋅10 = 2⋅4 + 3⋅7 + 5⋅8
3 7⋅8⋅11 = 1⋅3⋅12 + 2⋅4⋅5 + 6⋅9⋅10
2⋅5⋅6 + 8⋅9⋅11 = 1⋅3⋅4 + 7⋅10⋅12
9⋅12⋅15 = 1⋅4⋅6 + 2⋅3⋅11 + 5⋅7⋅14 + 8⋅10⋅13
2⋅3⋅11 + 5⋅14⋅15 = 1⋅8⋅9 + 4⋅12⋅13 + 6⋅7⋅10
4 6⋅8⋅9⋅12 = 1⋅11⋅14⋅16 + 2⋅3⋅10⋅15 + 4⋅5⋅7⋅13
1⋅9⋅13⋅16 + 3⋅8⋅11⋅12 = 2⋅4⋅7⋅15 + 5⋅6⋅10⋅14
10⋅12⋅14⋅19 = 1⋅3⋅4⋅7 + 2⋅13⋅17⋅18 + 5⋅8⋅11⋅15 + 6⋅9⋅16⋅20
2⋅4⋅18⋅19 + 9⋅10⋅13⋅16 = 1⋅6⋅8⋅14 + 3⋅7⋅12⋅17 + 5⋅11⋅15⋅20
5 3⋅11⋅13⋅14⋅16 = 1⋅4⋅17⋅18⋅19 + 2⋅5⋅7⋅15⋅20 + 6⋅8⋅9⋅10⋅12
1⋅2⋅13⋅18⋅20 + 6⋅8⋅11⋅14⋅15 = 3⋅4⋅10⋅12⋅17 + 5⋅7⋅9⋅16⋅19
11⋅13⋅14⋅24⋅25 = 1⋅3⋅5⋅16⋅23 + 2⋅4⋅7⋅9⋅15 + 6⋅10⋅17⋅18⋅21 + 8⋅12⋅19⋅20⋅22
5⋅9⋅14⋅17⋅25 + 6⋅10⋅15⋅19⋅22 = 1⋅2⋅3⋅11⋅23 + 4⋅12⋅18⋅20⋅21 + 7⋅8⋅13⋅16⋅24
6 2⋅8⋅13⋅21⋅23⋅24 = 1⋅7⋅9⋅14⋅16⋅20 + 3⋅4⋅17⋅18⋅19⋅22 + 5⋅6⋅10⋅11⋅12⋅15
1⋅7⋅11⋅12⋅21⋅24 + 2⋅9⋅13⋅16⋅17⋅23 = 3⋅4⋅14⋅15⋅20⋅22 + 5⋅6⋅8⋅10⋅18⋅19

n \ m67
1 6 ≈ 1 + 2 + 3 + 4 + 5 [9]
5 + 6 ≈ 1 + 2 + 3 + 4 [1]
1 + 3 + 6 ≈ 2 + 4 + 5 [1]
7 ≈ 1 + 2 + 3 + 4 + 5 + 6 [14]
6 + 7 ≈ 1 + 2 + 3 + 4 + 5 [2]
1 + 6 + 7 = 2 + 3 + 4 + 5
2 10⋅12 = 1⋅9 + 2⋅8 + 3⋅7 + 4⋅11 + 5⋅6
3⋅11 + 6⋅12 = 1⋅7 + 2⋅9 + 4⋅10 + 5⋅8
1⋅7 + 4⋅12 + 5⋅9 = 2⋅11 + 3⋅10 + 6⋅8
13⋅14 = 1⋅12 + 2⋅11 + 3⋅10 + 4⋅9 + 5⋅8 + 6⋅7
5⋅13 + 7⋅14 = 1⋅8 + 2⋅12 + 3⋅9 + 4⋅11 + 6⋅10
2⋅12 + 4⋅13 + 6⋅14 = 1⋅8 + 3⋅9 + 5⋅11 + 7⋅10
3 9⋅17⋅18 = 1⋅8⋅12 + 2⋅13⋅14 + 3⋅4⋅7 + 5⋅6⋅15 + 10⋅11⋅16
3⋅12⋅18 + 7⋅13⋅14 = 1⋅10⋅16 + 2⋅4⋅11 + 5⋅6⋅15 + 8⋅9⋅17
1⋅8⋅15 + 2⋅5⋅7 + 11⋅14⋅17 = 3⋅13⋅16 + 4⋅6⋅10 + 9⋅12⋅18
15⋅16⋅18 = 1⋅6⋅7 + 2⋅10⋅21 + 3⋅9⋅20 + 4⋅12⋅19 + 5⋅13⋅14 + 8⋅11⋅17
6⋅14⋅21 + 7⋅11⋅13 = 1⋅9⋅19 + 2⋅18⋅20 + 3⋅12⋅17 + 4⋅8⋅16 + 5⋅10⋅15
2⋅9⋅15 + 4⋅18⋅20 + 8⋅17⋅21 = 1⋅5⋅12 + 3⋅6⋅14 + 7⋅10⋅13 + 11⋅16⋅19
4 8⋅18⋅21⋅22 = 1⋅4⋅11⋅13 + 2⋅5⋅17⋅20 + 3⋅9⋅12⋅23 + 6⋅14⋅19⋅24 + 7⋅10⋅15⋅16
5⋅14⋅18⋅23 + 7⋅10⋅15⋅20 = 1⋅6⋅8⋅21 + 2⋅4⋅13⋅24 + 3⋅12⋅17⋅19 + 9⋅11⋅16⋅22
3⋅6⋅9⋅20 + 4⋅5⋅7⋅19 + 11⋅14⋅16⋅22 = 1⋅12⋅13⋅23 + 2⋅10⋅18⋅21 + 8⋅15⋅17⋅24

Bryce Herdt, noted that sometimes we can do better with mn consecutive positive integers if we don't use 1 through mn, such as 2⋅5⋅7 ≈ 3⋅4⋅6 [2] and 3⋅5⋅9⋅10 ≈ 4⋅6⋅7⋅8 [6].

3. Here is what is known about the factorability of P = xn + xn-1 + . . . + x2 + x + m:

When m = – (kn + kn-1 + . . . + k2 + k), then there is a linear factor (x – k) of P.

As special cases of this:

• When m = 0, then x is a factor of P.

• When m = –n, then (x – 1) is a factor of P.

• When n = 2 and m = –k(k + 1), then P factors as (x + k)(x – k + 1).

Also, when m = 1 and (n+1) is composite, P factors since P is a factor of xn+1 – 1.

Here are the known exceptional cases:

 x7 + x6 + x5 + x4 + x3 + x2 + x – 2 = (x3 + x – 1)(x4 + x3 + x + 2) x13 + x12 + x11 + . . . + x3 + x2 + x – 3 = (x3 + x2 – 1)(x10 + x8 + x7 + 2x5 + x3 + 2x2 – x + 3) x4 + x3 + x2 + x + 12 = (x2 + 3x + 4)(x2 – 2x + 3) x8 + x7 + x6 + x5 + x4 + x3 + x2 + x + 20 = (x4 – x3 + x2 – 3x + 4)(x4 + 2x3 + 2x2 + 4x + 5) x10 + x9 + x8 + . . . + x3 + x2 + x – 22 = (x2 + x + 2)(x8 – x6 + 2x5 + x4 – 4x3 + 3x2 + 6x – 11) x5 + x4 + x3 + x2 + x – 55 = (x2 – x + 5)(x3 + 2x3 – 2x – 11)

Victor Miller gave this analysis: Consider a monic polynomial to have unknown coefficients, and use long division to find a factor with degree k with constant remainder m. This gives k-1 equations in k unknowns, so there is some space curve that the coefficients satisfy. If this is of genus > 1, by Falting's Theorem it will have only a finite number of rational points on the curve. If this has genus 1, it might have an inifinite number of rational points, and if it has genus 0, it definitely does. He calculates the curve has genus 0 for n=4 and k=2, genus 1 for n=5 and k=2, genus 2 for n=6 and k=2, genus 4 for n=6 and k=3, genus 4 for n=7 and k=2, and genus 11 for n=7 and k=3.

If you can extend any of these results, please e-mail me. Click here to go back to Math Magic. Last updated 8/1/09.