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?


ANSWERS

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   2496   2736   2835   3828   5767
1584   1485   2835   1743   1323   2365   1281   1155   1798   3339

3 × 3
114   117   118   118   119   124   124   126   128   132   133
287   473   468   858   291   426   596   464   363   426   597
325   328   385   245   648   285   285   414   646   214   288

133   147   164   216   216   216   232   234   234   246   323
774   561   852   319   322   567   621   441   846   561   429
212   624   366   273   261   225   126   336   228   525   216

324   342   342   342   357   357   429   452   459   524   528
418   528   684   742   671   836   738   982   891   364   442
264   235   183   148   624   525   344   146   648   328   475

532   533   722   819   842   844   846   917   918   918   954
522   663   468   896   526   926   936   339   552   588   642
144   198   168   222   213   223   323   311   238   295   364    

2 × 5
25758   27594   27783   34596   35856   56576   58548   63984   83776   96558
14931   13794   11715   12138   14384   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   227   236   268   314
327   372   423   351   677   615   732   873   645   516   783   772   428
421   416   325   552   416   578   514   376   126   358   367   746   154

317   318   325   332   335   448   456   516   626   628   633   754   846
376   336   565   512   673   578   862   325   428   818   831   683   712
388   372   286   142   325   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   236   422   426   426   624
223   246   353   316   255   265   434   514   534   624   426
263   312   426   143   366   444   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:

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 infinite 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.