论坛 › 编程擂台 › 用n个114514不能构造的最小正整数是多少？10^k(1<=k<= 8)最少要用几个？

Yi_Zhi_OIer 发表于 2026-2-4 09:21:58

用n个114514不能构造的最小正整数是多少？10^k(1<=k<= 8)最少要用几个？

如标题。用n个114514不能构造的最小正整数是多少？10^k(1<=k<= 8)最少要用几个114514？只能用四则运算。注意中间结果必须为整数

补充内容 (2026-2-5 22:13):
再探讨不用是整数的情况

Yi_Zhi_OIer 发表于 2026-2-4 12:42:50

n=1: 1
n=2: 2
n=3: 1
n=4: 4
n=5: 5
n=6: 6
n=7: 7
n=8: 10
n=9: 11
n=10: 14
n=11: 19
n=12: 22
n=13: 29
n=14: 38
n=15: 43

Yi_Zhi_OIer 发表于 2026-2-4 12:43:51

n=12: size=182018, missing=22, time=0.522732s
n=13: size=589705, missing=29, time=1.41918s
n=14: size=1938469, missing=38, time=6.78302s
n=15: size=6452950, missing=43, time=17.7465s
n=16: size=21726871, missing=58, time=56.0103s
FOUND 10^2 with n=17
n=17: size=73875870, missing=77, time=193.877s
n=18: size=253403807, missing=103, time=816.499s
疑似

northwolves 发表于 2026-2-4 15:26:59

$k=1,9个$

$k=2,17个$

Yi_Zhi_OIer 发表于 2026-2-5 07:40:59

k=2时4*5*5最优，17个
我们设m=a^b，求b(a+1)最小值。
b(a+1)=log m/log a * (a+1)
计算器给出a=3.5911最好
我们尽量拆成4和5？

Yi_Zhi_OIer 发表于 2026-2-5 07:44:20

不一定。
10=3*3+1
10=((x+x+x)/x*(x+x+x)+x)/x

Yi_Zhi_OIer 发表于 2026-2-5 07:50:44

我的c++程序跑到了n=18，但是结果不精确。我用的是int128

mathe 发表于 2026-2-5 11:35:41

int128也会越界，另外这个题目其实不限制整数，允许中间结果是分数，应该结论也是相同的，问题1验算到n=11都保持一致。对于问题2，n=3大概率还是26

mathe 发表于 2026-2-5 15:24:39

这个问题主要在于计算过程的中间结果状态太多了，无法全部记录。
我们可以试着只记录中间计算结果为不超过N的正整数，比如其中\(N=10^7\)时，可以得到
2:[ 2 3 4 5 6 7 8 9 10 11 ]
3:[ 1 3 4 5 6 7 8 9 10 11 ]
4:[ 4 5 6 7 8 9 10 11 12 13 ]
5:[ 5 6 7 8 9 10 11 12 13 14 ]
6:[ 6 7 8 9 10 11 12 13 14 15 ]
7:[ 7 8 9 10 11 12 13 14 15 16 ]
8:[ 10 11 12 13 14 15 16 17 18 19 ]
Reach 10 in level 9
9:[ 11 13 14 15 16 17 18 19 20 21 ]
10:[ 14 17 18 19 20 21 22 23 24 25 ]
11:[ 19 21 22 23 24 25 26 27 28 29 ]
12:[ 22 23 26 28 29 30 31 32 33 34 ]
13:[ 29 31 33 34 35 37 38 39 40 41 ]
14:[ 38 41 42 43 44 46 47 49 50 51 ]
15:[ 43 53 55 56 57 58 59 61 62 63 ]
16:[ 58 62 66 67 69 70 71 73 74 76 ]
Reach 100 in level 17
17:[ 77 83 86 87 88 89 91 92 93 94 ]
18:[ 89 97 101 103 106 107 109 110 113 114 ]
19:[ 103 113 121 127 129 131 133 134 137 139 ]
20:[ 131 137 139 149 151 154 157 161 163 166 ]
21:[ 167 173 178 194 197 199 202 203 206 209 ]
22:[ 173 206 211 223 227 229 233 251 253 254 ]
23:[ 262 263 274 277 278 281 283 293 298 302 ]
24:[ 331 346 347 349 353 367 373 379 389 393 ]
25:[ 439 446 454 457 461 463 466 473 491 502 ]
Reach 1000 in level 26
26:[ 523 547 557 562 569 571 607 614 622 631 ]
27:[ 643 653 692 743 746 758 761 786 787 789 ]
28:[ 787 823 878 967 982 989 991 993 1013 1046 ]
Reach 10000 in level 29
29:[ 1069 1114 1138 1211 1262 1283 1286 1289 1291 1310 ]
30:[ 1447 1451 1493 1571 1609 1654 1667 1703 1706 1707 ]
31:[ 2102 2167 2171 2191 2222 2266 2417 2510 2513 2567 ]
Reach 100000 in level 32
32:[ 3138 3311 3313 3421 3873 3932 3934 3990 3991 3997 ]
其中每行分别代表使用这么多个数，前10个无法到达的整数（中间结果不超过N).
如果修改N为\(10^8\),可以得到
2:[ 2 3 4 5 6 7 8 9 10 11 ]
3:[ 1 3 4 5 6 7 8 9 10 11 ]
4:[ 4 5 6 7 8 9 10 11 12 13 ]
5:[ 5 6 7 8 9 10 11 12 13 14 ]
6:[ 6 7 8 9 10 11 12 13 14 15 ]
7:[ 7 8 9 10 11 12 13 14 15 16 ]
8:[ 10 11 12 13 14 15 16 17 18 19 ]
Reach 10 in level 9
9:[ 11 13 14 15 16 17 18 19 20 21 ]
10:[ 14 17 18 19 20 21 22 23 24 25 ]
11:[ 19 21 22 23 24 25 26 27 28 29 ]
12:[ 22 23 26 28 29 30 31 32 33 34 ]
13:[ 29 31 33 34 35 37 38 39 40 41 ]
14:[ 38 41 42 43 44 46 47 49 50 51 ]
15:[ 43 53 55 56 57 58 59 61 62 63 ]
16:[ 58 62 66 67 69 70 71 73 74 76 ]
Reach 100 in level 17
17:[ 77 83 86 87 88 89 91 92 93 94 ]
18:[ 103 106 110 113 114 115 116 118 119 121 ]
19:[ 131 133 137 139 142 146 149 151 152 154 ]
20:[ 166 167 172 173 174 178 182 186 187 190 ]
21:[ 173 206 211 223 227 229 231 232 233 238 ]
22:[ 262 263 266 274 277 278 281 283 293 298 ]
23:[ 331 346 347 349 353 367 371 373 377 379 ]
24:[ 439 446 454 457 461 463 466 473 491 493 ]
25:[ 523 547 557 562 569 583 607 614 617 622 ]
Reach 1000 in level 26
26:[ 692 713 742 743 746 754 758 761 786 787 ]
27:[ 823 877 878 883 887 913 914 919 937 941 ]
28:[ 989 991 1013 1046 1049 1051 1069 1109 1114 1129 ]
Reach 10000 in level 29
29:[ 1289 1319 1321 1327 1373 1381 1423 1447 1451 1453 ]
30:[ 1493 1571 1667 1774 1879 1894 1949 1966 1967 1978 ]
31:[ 2102 2266 2417 2573 2578 2621 2623 2638 2647 2758 ]
Reach 100000 in level 32
32:[ 3138 3313 3421 3873 3932 3934 3991 3997 4279 4345 ]
Reach 1000000 in level 33
33:[ 6586 6899 6913 7491 7885 7887 7921 7978 8066 8526 ]
34:[ 11867 11887 17396 17743 20953 21938 24401 25733 25735 26806 ]
35:[ 53268 71028 77791 77793 87097 96771 102647 126401 132257 135467 ]
36:[ 282296 294833 295021 306821 311579 316193 323581 330235 331655 363503 ]

由此我们可以得到第一个问题的一个下界（前18项应该没有问题）
和第二个问题的上界（7，17，26，29，32，33）

mathe 发表于 2026-2-6 08:50:36

整数范围设置为\(10^{14}\)
2:[ 2 3 4 5 6 7 8 9 10 11 ]
3:[ 1 3 4 5 6 7 8 9 10 11 ]
4:[ 4 5 6 7 8 9 10 11 12 13 ]
5:[ 5 6 7 8 9 10 11 12 13 14 ]
6:[ 6 7 8 9 10 11 12 13 14 15 ]
7:[ 7 8 9 10 11 12 13 14 15 16 ]
8:[ 10 11 12 13 14 15 16 17 18 19 ]
Reach 10 in level 9
9:[ 11 13 14 15 16 17 18 19 20 21 ]
10:[ 14 17 18 19 20 21 22 23 24 25 ]
11:[ 19 21 22 23 24 25 26 27 28 29 ]
12:[ 22 23 26 28 29 30 31 32 33 34 ]
13:[ 29 31 33 34 35 37 38 39 40 41 ]
14:[ 38 41 42 43 44 46 47 49 50 51 ]
15:[ 43 53 55 56 57 58 59 61 62 63 ]
16:[ 58 62 66 67 69 70 71 73 74 76 ]
Reach 100 in level 17
17:[ 77 83 86 87 88 89 91 92 93 94 ]
18:[ 103 106 110 113 114 115 116 118 119 121 ]
19:[ 131 133 137 139 142 146 149 151 152 154 ]
20:[ 166 167 172 173 174 178 182 186 187 190 ]
21:[ 173 206 211 223 227 229 231 232 233 238 ]
22:[ 262 263 266 274 277 278 281 283 293 298 ]
23:[ 331 346 347 349 353 367 371 373 377 379 ]
24:[ 439 446 454 457 461 463 466 473 491 493 ]
25:[ 523 547 557 569 614 622 631 633 634 643 ]
Reach 1000 in level 26
26:[ 713 746 758 761 786 787 789 791 803 806 ]
Reach 10000 in level 27
27:[ 986 989 993 1013 1046 1047 1048 1049 1051 1067 ]
28:[ 1138 1289 1315 1318 1319 1327 1334 1379 1381 1382 ]

也就是说10000可以27个整数表示

查看完整版本: 用n个114514不能构造的最小正整数是多少？10^k(1<=k<= 8)最少要用几个？