三重内积的最小值

王守恩

northwolves 发表于 2025-9-19 21:04
01        2        3        4        5        6        7        8        09        10
10        6        4        8        5        3        7        2        01        09
09        7        8        3        4        5        2        6        10        01

鹦鹉学舌,  没学好。 离正确答案总是差1。

a(11)=1305,  1*11*10 + 2*7*9 + 3*5*8 + 4*6*5 + 5*9*3 + 6*3*6 + 7*4*4 + 8*8*2 + 9*2*7 + 10*1*11 + 11*10*1=1305, 正确答案=1304。
01,2,3,4,5,6,7,8,9,10,11,
11,7,5,6,9,3,4,8,2,01,10,
10,9,8,5,3,6,4,2,7,11,01,

a(12)=1782,  1*12*11 + 2*8*10 + 3*6*9 + 4*7*5 + 5*10*3 + 6*4*7 + 7*5*4 + 8*9*2 + 9*3*6 + 10*2*8 + 11*1*12 + 12*11*1=1782, 正确答案=1781。
01,02,3,4,05,6,7,8,9,10,11,12,
12,08,6,7,10,4,5,9,3,02,01,11,
11,10,9,5,03,7,4,2,6,08,12,01,

a(13)=2378,  1*13*12 + 2*8*11 + 3*7*10 + 4*11*4 + 5*5*8 + 6*6*5 + 7*9*3 + 8*4*6 + 9*3*7 + 10*10*2 + 11*2*9 + 12*1*13 + 13*12*1=2378, 正确答案=2377。
01,02,03,04,5,6,7,8,9,10,11,12,13,
13,08,07,11,5,6,9,4,3,10,02,01,12,
12,11,10,04,8,5,3,6,7,02,09,13,01,

a(14)=3112,  1*14*13 + 2*9*12 + 3*7*11 + 4*8*7 + 5*12*4 + 6*5*8 + 7*6*5 + 8*10*3 + 9*3*9 + 10*4*6 + 11*11*2 + 12*2*10 + 13*1*14 + 14*13*1] =3112, 正确答案=3111。
01,02,03,4,05,6,7,08,9,10,11,12,13,14,
14,09,07,8,12,5,6,10,3,04,11,02,01,13,
13,12,11,7,04,8,5,03,9,06,02,10,14,01,

王守恩

有个"更狠"的"角色",  可以冲到a(10000)。——A070893。——可惜答案不太"准"。—— 还不如 mathe —— 6#的公式。

1, 6, 19, 46, 94, 172, 290, 460, 695, 1010, 1421, 1946, 2604, 3416, 4404, 5592, 7005, 8670, 10615, 12870, 15466, 18436, 21814, 25636, 29939, 34762, 40145, 46130, 52760, 60080, 68136, 76976, 86649, 97206, ——A070893。

1, 6, 18, 44, 89, 162, 271, 428, 642, 0930, 1304, 1781, 2377, 3111, 4002, 5073, 6344, 7842, 09587, 11610, 13933, 16591, 19612, 23028, 26871, 31177, 35976, 41314, 47221, 53736, 60907, 68773, 77373, 86759, ——A070735—标准答案。

1, 6, 18, 44, 89, 161, 271, 427, 642, 0929, 1302, 1776, 2367, 3094, 3976, 5032, 6285, 7757, 09472, 11454, 13731, 16330, 19280, 22610, 26353, 30539, 35204, 40381, 46107, 52419, 59356, 66957, 75263, 84316, ——OEIS没有—mathe—6#公式。

Table[Ceiling[n*Power[n!^3, (n)^-1]], {n, 40}]

northwolves

1. s={{01,2,3,4,5,6,7,8,9,10,11,12},  {12,10,6,7,5,9,3,2,4,8,01,11}, {11,8,9,5,6,3,7,10,4,2,12,01}};Times@@s//Total

复制代码

王守恩

第1行 = r = 1, 2, 3, 4, 5, ... 。第2行 = s 。

第3行 = t:  r*s 的最大值 = 1,  r*s 的次大值 = 2,  r*s 的三大值 = 3, ... 。

给出第2行 = s 。——还是没找到规律。

1,
2, 1,
3, 1, 2,
4, 2, 1, 3,
5, 2, 3, 1, 4,
6, 3, 4, 2, 1, 5,
7, 3, 4, 5, 2, 1, 6,
8, 5, 3, 4, 6, 2, 1, 7,
9, 5, 4, 6, 7, 3, 2, 1, 8,
10,7, 4, 5, 6, 8, 3, 2, 1, 9,
11,7, 5, 8, 4, 6, 9, 3, 2, 1, 10,
12,8, 6, 7,10,4, 5, 9, 3, 2, 1, 11,

大海捞针——越来越难！后面尽可能用 ..., 3, 2, 1。

王守恩

五重内积 A260356：1, 12, 60, 214, 600, 1443, 3089, ——a(7)。——冰火两重天。

a(1)=1,  1×1×1×1×1=1,
1,
1,
1,
1,
1,

a(2)=12,  1×1×2×2×1+2×2×1×1×2=12,
1, 2,
1, 2,
2, 1,
2, 1,
1, 2,

a(3)=60,  1×2×2×3×2+2×3×3×1×1+3×1×1×2×3=60,
1, 2, 3,
2, 3, 1,
2, 3, 1,
3, 1, 2,
2, 1, 3,

a(4)=214,  1×1×3×4×4+2×2×2×2×3+3×3×1×3×2+4×4×4×1×1=214,
1, 2, 3, 4,
1, 2, 3, 4,
3, 2, 1, 4,
4, 2, 3, 1,
4, 3, 2, 1,

a(5)=600,  1×2×3×4×5+2×1×4×5×3+3×4×5×2×1+4×5×1×3×2+5×3×2×1×4=600,
1, 2, 3, 4, 5,
2, 1, 4, 5, 3,
3, 4, 5, 1, 2,
4, 5, 2, 3, 1,
5, 3, 1, 2, 4,

a(6)=1443,  1×1×6×6×6+2×2×4×4×4+3×3×3×3×3+4×6×1×2×5+5×5×2×5×1+6×4×5×1×2=1445,
1, 2, 3, 4, 5, 6,——第1行 = A1 = 1, 2, 3, 4, 5, ... 。
1, 2, 3, 6, 5, 4,——第2行 = A2——还没找到规律。
6, 4, 3, 1, 2, 5,——第3行 = A3——还没找到规律。
6, 4, 3, 2, 5, 1,——第4行 = A4——还没找到规律。
6, 4, 3, 5, 1, 2,——第5行 = A5——A1*A2*A3*A4的最大值 = 1,  A1*A2*A3*A4的次大值 = 2,  A1*A2*A3*A4的三大值 = 3, ... 。

a(7)=3089,  1×3×7×7×3+2×6×1×6×6+3×7×5×1×4+4×2×3×4×5+5×5×6×3×1+6×1×2×5×7+7×4×4×2×2=3091,
1, 2, 3, 4, 5, 6, 7,
3, 6, 7, 2, 5, 1, 4,
7, 1, 5, 3, 6, 2, 4,
7, 6, 1, 4, 3, 5, 2,
3, 6, 4, 5, 1, 7, 2,

OEIS——A260356—是这样一串数——1, 12, 60, 214, 600, 1443, 3089, ——没有了。

mathe —— 6# ——是这样一串数——1, 12, 60, 213, 600, 1443, 3089, 6048, 11041, 19050, 31367, 49658, 76029, 113089, 164031, 232710, 323725, 442510, 595431, 789881, 1034385, 1338715,

Table[Ceiling[n Power[n!^5, (n)^-1]], {n, 40}]

王守恩

A070735——Let r, s, t be three permutations of the set {1, 2, 3, ..., n}; a(n) = minimal value of Sum_{i=1..n} r(i)*s(i)*t(i).
例如：
a(1)=1,  1×1×1=1,
a(2)=6,  1×2×2+2×1×1=6,
r={1, 2},
s={2, 1},
t={2, 1}.

a(3)=18,  1×3×2+2×1×3+3×2×1=18,
r={1, 2, 3},
s={3, 1, 2},
t={2, 3, 1}.

a(4)=44,  1×4×3+2×2×2+3×1×4+4×3×1=44,
r={1, 2, 3, 4},
s={4, 2, 1, 3},
t={3, 2, 4, 1}.

a(5)=89,  1×5×3+2×2×4+3×3×2+4×1×5+5×4×1=89,
r={1, 2, 3, 4, 5},
s={5, 2, 3, 1, 4},
t={3, 4, 2, 5, 1}.

a(6)=162,  1×6×5+2×4×3+3×2×4+4×3×2+5×1×6+6×5×1=162,
r={1, 2, 3, 4, 5, 6},
s={6, 4, 2, 3, 1, 5},
t={5, 3, 4, 2, 6, 1}.

a(7)=271,  1×7×5+2×5×4+3×2×6+4×3×3+5×4×2+6×1×7+7×6×1=271,
r={1, 2, 3, 4, 5, 6, 7},
s={7, 5, 2, 3, 4, 1, 6},
t={5, 4, 6, 3, 2, 7, 1}.

a(8)=428,  1×8×7+2×5×5+3×3×6+4×4×3+5×6×2+6×2×4+7×1×8+8×7×1=428,
r={1, 2, 3, 4, 5, 6, 7, 8},
s={8, 5, 3, 4, 6, 2, 1, 7},
t={7, 5, 6, 3, 2, 4, 8, 1}.

a(9)=642,  ——OEIS没有列出相应的 r, s, t。
......
前32项为 1, 6, 18, 44, 89, 162, 271, 428, 642, 930, 1304, 1781, 2377, 3111, 4002, 5073, 6344, 7842, 9587, 11610, 13933, 16591, 19612, 23028, 26871, 31177, 35976, 41314, 47221, 53736, 60907, 68773.

a(16)-a(19) from Hiroaki Yamanouchi, Aug 21 2015

a(20) onwards from Martin Fuller, Aug 06 2023

Martin Fuller, Table of n, a(n) for n = 1~204——记住Martin Fuller这个狠角色, 冲到a(204)。

想你了——Martin Fuller！

王守恩

题目(1)——A070735——Let r, s, t be three permutations of the set {1, 2, 3, ..., n}; a(n) = minimal value of Sum_{i=1..n} r(i)*s(i)*t(i).

题目(2)——给定3*n个数 {1,1,1,2,2,2,3,3,3,4,4,4,...,n,n,n},  分成 n 组,  每组3个数,  使得各组乘积的和最小。

题目(1),题目(2)——答案是一样的吗？

王守恩

A070735—— 1, 6, 18, 44, 89, 162, 271, 428, 642, 930, 1304, 1781, 2377, 3111, 4002, 5073, 6344, 7842, 9587, 11610, 13933, 16591, 19612, 23028, 26871, 31177, 35976, 41314, 47221, 53736, 60907, 68773.

1. Table[a = b = c = Range[n]; k = MinimalBy[DeleteDuplicates[Permutations[b]], Total[ReverseSort[a*#]*c] &] // First;
   
2. m = Total[ReverseSort[a*k]*c]; Print["n=", n, ": b=", k, " 和=", m], {n, 10}]

复制代码

n=1: b={1} 和=1
n=2: b={1,2} 和=6
n=3: b={2,3,1} 和=18
n=4: b={2,3,4,1} 和=44
n=5: b={3,4,2,5,1} 和=89
n=6: b={4,3,5,2,6,1} 和=162
n=7: b={5,4,6,3,2,7,1} 和=271
n=8: b={6,4,5,7,2,3,8,1} 和=428
n=9: b={8,5,4,6,7,3,2,9,1} 和=642
n=10: b={9,6,4,8,5,3,7,2,10,1} 和=930

1. Table[a = b = c = Range[2, n - 2]; k = MinimalBy[DeleteDuplicates[Permutations[b]], Total[ReverseSort[a*#]*c] &] // First;
   
2. m = Total[ReverseSort[a*k]*c] + 3 n (n - 1); Print["n=", n, ": b=", k, " 和=", m], {n, 8, 14}]

复制代码

n=8: b={4,5,6,2,3} 和=428
n=9: b={5,4,6,7,3,2} 和=642
n=10: b={6,4,8,5,3,7,2} 和=930
n=11: b={6,5,8,4,7,9,3,2} 和=1304
n=12: b={7,6,8,5,9,3,10,2,4} 和=1781
n=13: b={8,6,7,10,4,9,5,11,2,3} 和=2377
n=14: b={9,7,8,6,10,11,5,3,12,2,4} 和=3111

1. Table[a = b = c = Join[Range[3, n - 5], {n - 3}]; k = MinimalBy[DeleteDuplicates[Permutations[b]], Total[ReverseSort[a*#]*c] &] // First;
   
2. m = Total[ReverseSort[a*k]*c] + 3 (n) (n - 1) + 6 (n - 2) (n - 4); Print["n=", n, ": b=", k, " 和=", m], {n, 11, 17}]

复制代码

n=11: b={5,6,8,3,4} 和=1304
n=12: b={6,7,5,9,3,4} 和=1781
n=13: b={6,7,10,4,5,8,3} 和=2377
n=14: b={7,6,11,8,4,5,9,3} 和=3111
n=15: b={8,7,6,9,10,12,5,4,3} 和=4002
n=16: b={9,8,6,11,7,10,13,4,5,3} 和=5074
n=17: b={9,8,10,11,14,7,5,4,12,3,6} 和=6345

王守恩

题目(1)——A070735——Let r, s, t be three permutations of the set {1, 2, 3, ..., n}; a(n) = minimal value of Sum_{i=1..n} r(i)*s(i)*t(i).

题目(2)——给定3*n个数 {1,1,1,2,2,2,3,3,3,4,4,4,...,n,n,n},  分成 n 组,  每组3个数,  使得各组乘积的和最小。

题目(1),题目(2)——答案是一样的吗？

答:  题目(2)的答案还是——A070735。

王守恩

1. Table[a = b = c = Range[n, n + m]; k = MinimalBy[DeleteDuplicates[Permutations[b]], Total[ReverseSort[a*#]*c] &] // First; Total[ReverseSort[a*k]*c], {m, 0, 10}, {n, 30}]

复制代码

m=0: {1, 8, 27, 64, 125, 216, 343, 512, 729, 1000, 1331, 1728, 2197, 2744, 3375, 4096, 4913, 5832, 6859, 8000, 9261, 10648, 12167, 13824, 15625, 17576, 19683, 21952, 24389, 27000},
m=1: {6, 30, 84, 180, 330, 546, 840, 1224, 1710, 2310, 3036, 3900, 4914, 6090, 7440, 8976, 10710, 12654, 14820, 17220, 19866, 22770, 25944, 29400, 33150, 37206, 41580, 46284, 51330, 56730},
m=2: {18, 72, 180, 360, 630, 1008, 1512, 2160, 2970, 3960, 5148, 6552, 8190, 10080, 12240, 14688, 17442, 20520, 23940, 27720, 31878, 36432, 41400, 46800, 52650, 58968, 65772, 73080, 80910, 89280},
m=3: {44, 146, 332, 626, 1052, 1634, 2396, 3362, 4556, 6002, 7724, 9746, 12092, 14786, 17852, 21314, 25196, 29522, 34316, 39602, 45404, 51746, 58652, 66146, 74252, 82994, 92396, 102482, 113276, 124802},
m=4: {89, 260, 550, 990, 1610, 2440, 3510, 4850, 6490, 8460, 10790, 13510, 16650, 20240, 24310, 28890, 34010, 39700, 45990, 52910, 60490, 68760, 77750, 87490, 98010, 109340, 121510, 134550, 148490, 163360},
m=5: {162, 426, 852, 1476, 2334, 3462, 4896, 6672, 8826, 11394, 14412, 17916, 21942, 26526, 31704, 37512, 43986, 51162, 59076, 67764, 77262, 87606, 98832, 110976, 124074, 138162, 153276, 169452, 186726, 205134},
m=6: {271, 660, 1257, 2105, 3247, 4725, 6580, 8855, 11592, 14833, 18620, 22995, 28000, 33677, 40068, 47215, 55160, 63945, 73612, 84203, 95760, 108325, 121940, 136647, 152488, 169505, 187740, 207235, 228032, 250173},
m=7: {428, 974, 1781, 2897, 4373, 6257, 8597, 11441, 14837, 18833, 23477, 28817, 34901, 41777, 49493, 58097, 67637, 78161, 89717, 102353, 116117, 131057, 147221, 164657, 183413, 203537, 225077, 248081, 272597, 298673},
m=8: {642, 1385, 2442, 3876, 5742, 8093, 10984, 14468, 18600, 23434, 29024, 35424, 42687, 50868, 60021, 70200, 81459, 93852, 107433, 122256, 138375, 155844, 174717, 195048, 216891, 240300, 265329, 292032, 320463, 350676},
m=9: {930, 1909, 3265, 5069, 7383, 10264, 13774, 17974, 22924, 28684, 35314, 42874, 51424, 61024, 71734, 83614, 96724, 111124, 126874, 144034, 162664, 182824, 204574, 227974, 253084, 279964, 308674, 339274, 371824, 406384},

第1项= 1, 6, 18, 44, 89, 162, 271, 428, 642, 930, 1304, 1781, 2377, 3111, 4002, ——A070735。

上面的数字串可以有同一个通项公式——a(n) = 4*a(n-1) - 6*a(n-2) + 4*a(n-3) - a(n-4) 。