挑数字

aimisiyou

从自然数中挑选K个数（可以重复选取）组成一个数组，使得其中不超过3个元素之和可以连续取到1~N，现已知N。求数组中元素个数最少且最大值最小的一个。

比如N=10，（1,2， 4 ，4），（1,2,2,6）和（1,2,3,7）都满足个数最少，但（1,2，4,4中最大值为4）。所以结果是（1,2,4,4）。
1=1
2=2
1+2=3
4=4
1+4=5
2+4=6
1+2+4=7
4+4=8
1+4+4=9
2+4+4=10

现在N=10000，求该数组。

northwolves

看看我的数据正确与否：
1        {1}
2        {1,1}
3        {1,2}
4        {1,1,2}
5        {1,2,2}
6        {1,2,3}
7        {1,2,4}
8        {1,2,3,3}
9        {1,2,3,4}
10        {1,2,4,4}
11        {1,2,4,5}
12        {1,2,4,6}
13        {1,2,4,7}
14        {1,2,4,8}
15        {1,2,3,6,6}
16        {1,2,3,6,7}
17        {1,2,3,6,8}
18        {1,2,3,6,9}
19        {1,2,3,6,10}
20        {1,2,3,6,11}
21        {1,2,3,6,12}
22        {1,2,4,7,13}
23        {1,2,4,7,14}
24        {1,2,3,6,10,11}
25        {1,2,3,6,10,12}
26        {1,2,3,7,11,12}
27        {1,2,3,7,11,13}
28        {1,2,3,7,11,14}
29        {1,2,4,8,13,14}
30        {1,2,3,6,10,17}
31        {1,2,3,6,10,18}
32        {1,2,3,6,10,19}
33        {1,2,3,6,10,20}

aimisiyou

northwolves 发表于 2023-12-4 12:42
看看我的数据正确与否：
1        {1}
2        {1,1}

怎么算出来的？

northwolves

aimisiyou 发表于 2023-12-4 13:23
怎么算出来的？

1. f[n_]:=Module[{x=Prepend[1]/@Union[Sort/@Tuples[Range[n/2+5],Floor[Log2[n]]]]},y=Select[x,Complement[Range@n,Union[Total/@(Subsets[#,3])]]=={}&];First@SortBy[y,Last]];Table[{n,f[n]},{n,20}]

复制代码

northwolves

未返回结果的项数加1即可

{{1,{1}},{2,{1,1}},{3,{1,2}},{4,{1,1,2}},{5,{1,2,2}},{6,{1,2,3}},{7,{1,2,4}},{8,{1,2,3,3}},{9,{1,2,3,4}},{10,{1,2,4,4}},{11,{1,2,4,5}},{12,{1,2,4,6}},{13,{1,2,4,7}},{14,{1,2,4,8}},{15,First[{}]},{16,{1,2,3,6,7}},{17,{1,2,3,6,8}},{18,{1,2,3,6,9}},{19,{1,2,3,6,10}},{20,{1,2,3,6,11}}}

northwolves

不知道是否最优解，但在n>15时， {1,2,3,6}，{1,2,3,7}， {1,2,4,7}, { {1,2,4,8}必出。

aimisiyou

一个大佬给出他的思路建议:
“一个思路，不一定正确，供参考。

分三步取数，假如N=100
第一步，取从1开始的连续自然数1-4，两两相加可以得到连续整数1-7；
第二步，增加自然数，从8开始，递增4+1，把两数相加所得的连续数段适当延长，增加8，可以使连续的数段延长至1-12，增加13、18，可以使连续的数段延长至1-22；
用1-4、8、13、18，求三个数的和，连续数中最大可得到35（4+13+18）；
第三步，从36开始，依次递增22+1，得到36、59、82，三数和可得连续数1-104，满足N=100，可将36-82分别减去4，得到：
1-4、8-18、32-78共10个数，最大值78。

如果第一步取1-3，两两相加可得到连续自然数1-5；
第二步，从6开始，依次递增3+1，取6、10、14，使得两数和所得连续数段延长至1-17；
1-3、6-14共6个数，求三数之和，连续数中最大可得到27（3+10+14）；
第三步，从28开始，按17+1递增，取数28、46、64、82、100，三数和可得连续数1-117，满足N=100，可将46-100四个数各减17，得到：
1-3、6-14、28、29-83，共11个数，最大值83。

如果第一步取1-5，第二步从10开始，依次取10、16、22三数，两数和可得连续数1-27；
第三步从44开始，递增27+1，取44、72、100，综合N=100，可取44、45、73：
1-5、10-22、44、45、73，共11个数，最小值73。”


他给出的一个答案：1-18（共18个）、36-340（递增19，共17个）、667-9642（递增359，共26个），总共61个，最大9642。

l4m2

我目前能做到60，感覺是最少了

1. S=[]
   
2. A=[0,0,
   
3. 1,2,3,4,5,6,7,8,9,10,
   
4. 11,12,13,14,15,16,17,18,19,20,
   
5. 21,42,64,86,108,130,152,174,196,218,
   
6. 240,262,284,306,328,350,372,394,416,438,
   
7. 460,920,1402,1884,2366,2848,3330,3812,4294,4776,
   
8. 5258,5740,6222,6704,7186,7668,8150,8632,9114,9519];
   
9. for(i in A)for(j in A)for(k in A)if(i<j&j<k)S[A[i]+A[j]+A[k]]=1;
   
10. for(i=1;i<=10000;++i)if(!S[i])console.log(i);

复制代码

northwolves

aimisiyou 发表于 2023-12-5 12:14
一个大佬给出他的思路建议:
“一个思路，不一定正确，供参考。

随机测试，n=100, {1, 2, 3, 6, 10, 17, 28, 40, 46, 52} 共10个数，最大值52满足条件。

northwolves

找到几组更小一些的：
\begin{array}{cccccccccc}
1 & 2 & 4 & 7 & 14 & 21 & 29 & 38 & 46 & 47 \\
1 & 2 & 4 & 7 & 14 & 21 & 30 & 38 & 46 & 48 \\
1 & 2 & 4 & 7 & 14 & 21 & 30 & 39 & 47 & 48 \\
1 & 2 & 4 & 7 & 14 & 21 & 30 & 40 & 46 & 48 \\
1 & 2 & 4 & 7 & 14 & 21 & 31 & 40 & 48 & 49 \\
1 & 2 & 3 & 6 & 12 & 19 & 29 & 36 & 43 & 51 \\
1 & 2 & 3 & 6 & 10 & 17 & 28 & 40 & 46 & 52 \\
\end{array}