给出正整数列 a1,a2,…,a18=2020 使得对 3≤k≤18 均有 1≤i＜j＜k 使得 ak=ai+aj

uk702

王守恩 发表于 2021-1-17 09:26
uk702！8楼我不会用。这串数会长得不快吧？
记 F(n)=1, 2, 3, 5, 8, 13, 21, 34, 55, ......   
记 S ...

没看懂。你说的“项数”是什么意思呢？指的是所有不同 an 的个数吗？比如说，n=5, an=3,4,5,6,7,8 这6个“项”吗？或者说由于 n=5 时，an 的最大值为 8（也就是 F(5) 的意思），而 F(4)=5，故满足 F(4)<an≤F(5)，也说是 an= 6，7，8 这3个项（这3项共6个解）？

你说的“最大解集的数量”应该跟我说的也不是同一个意思。

比如说  n=5, 以下是它的所有解：
n = 5, [1, 2, 3, 3, 3]
n = 5, [1, 2, 3, 3, 4]
n = 5, [1, 2, 3, 3, 5]
n = 5, [1, 2, 3, 3, 6]
n = 5, [1, 2, 3, 4, 3]
n = 5, [1, 2, 3, 4, 4]
n = 5, [1, 2, 3, 4, 5]
n = 5, [1, 2, 3, 4, 6]
n = 5, [1, 2, 3, 4, 7]
n = 5, [1, 2, 3, 5, 3]
n = 5, [1, 2, 3, 5, 4]
n = 5, [1, 2, 3, 5, 6]
n = 5, [1, 2, 3, 5, 5]
n = 5, [1, 2, 3, 5, 7]
n = 5, [1, 2, 3, 5, 8]

我说的“最大解集的数量”是指这 15 个解，让 an 取前 n-1个中两两相加的值，故 S(n)（计入重复）满足  S(n+1)=S(n)*(n-1)(n-2)/2 ，但这种算法存在不少的重复.，因此肯定是偏大的

而严格递增解是：
n = 5, [1, 2, 3, 4, 5]
n = 5, [1, 2, 3, 4, 6]
n = 5, [1, 2, 3, 4, 7]
n = 5, [1, 2, 3, 5, 6]
n = 5, [1, 2, 3, 5, 7]
n = 5, [1, 2, 3, 5, 8]
计 6 个。

王守恩

uk702 发表于 2021-1-17 09:59
没看懂。你说的“项数”是什么意思呢？指的是所有不同 an 的个数吗？比如说，n=5, an=3,4,5,6,7,8 这6 ...

01=1
02=1, 2
03=1, 2, 3
04=1, 2, 3, 4
05=1, 2, 3, 5
06=1, 2, 3, 4, 6
06=1, 2, 3, 5, 6
07=1, 2, 3, 4, 7
07=1, 2, 3, 5, 7
08=1, 2, 3, 5, 8
09=1, 2, 3, 4, 5, 9
09=1, 2, 3, 4, 6, 9
09=1, 2, 3, 4, 7, 9
09=1, 2, 3, 5, 6, 9
09=1, 2, 3, 5, 7, 9
09=1, 2, 3, 5, 8, 9
10=1, 2, 3, 4, 6, 10
10=1, 2, 3, 4, 7, 10
10=1, 2, 3, 5, 7, 10
10=1, 2, 3, 5, 8, 10
11=1, 2, 3, 4, 7, 11
11=1, 2, 3, 5, 6, 11
11=1, 2, 3, 5, 8, 11
12=1, 2, 3, 5, 7, 12
13=1, 2, 3, 5, 8, 13
14=1, 2, 3, 4, 5, 09, 14
14=1, 2, 3, 4, 6, 08, 14
14=1, 2, 3, 4, 6, 10, 14
14=1, 2, 3, 4, 7, 10, 14
14=1, 2, 3, 4, 7, 11, 14
14=1, 2, 3, 5, 6, 08, 14
14=1, 2, 3, 5, 6, 09, 14
14=1, 2, 3, 5, 6, 11, 14
14=1, 2, 3, 5, 7, 09, 14
14=1, 2, 3, 5, 7, 12, 14
14=1, 2, 3, 5, 8, 09, 14
14=1, 2, 3, 5, 8, 11, 14
14=1, 2, 3, 5, 8, 13, 14

您是对的，错误已改。
对！！！我就是这个意思。

uk702

按这个要求，写了 julia 程序进行计算，算到 k=12 之后就算不下去了，前 233 项的结果如下（注意数字并不连续，中间有些 n  无解，a17=2018 似乎就是无解），反正我是找不出规律来：
n = 4, k = 4, sols = 1
n = 5, k = 4, sols = 1
n = 6, k = 5, sols = 2
n = 7, k = 5, sols = 2
n = 8, k = 5, sols = 1
n = 9, k = 6, sols = 6
n = 10, k = 6, sols = 4
n = 11, k = 6, sols = 3
n = 12, k = 6, sols = 1
n = 13, k = 6, sols = 1
n = 14, k = 7, sols = 13
n = 15, k = 7, sols = 9
n = 16, k = 7, sols = 6
n = 17, k = 7, sols = 5
n = 18, k = 7, sols = 3
n = 19, k = 7, sols = 2
n = 21, k = 7, sols = 1
n = 22, k = 8, sols = 28
n = 23, k = 8, sols = 21
n = 24, k = 8, sols = 15
n = 25, k = 8, sols = 10
n = 26, k = 8, sols = 8
n = 27, k = 8, sols = 7
n = 28, k = 8, sols = 3
n = 29, k = 8, sols = 4
n = 30, k = 8, sols = 1
n = 31, k = 8, sols = 2
n = 34, k = 8, sols = 1
n = 35, k = 9, sols = 44
n = 36, k = 9, sols = 37
n = 37, k = 9, sols = 33
n = 38, k = 9, sols = 21
n = 39, k = 9, sols = 22
n = 40, k = 9, sols = 11
n = 41, k = 9, sols = 14
n = 42, k = 9, sols = 6
n = 43, k = 9, sols = 9
n = 44, k = 9, sols = 6
n = 45, k = 9, sols = 4
n = 46, k = 9, sols = 3
n = 47, k = 9, sols = 3
n = 49, k = 9, sols = 2
n = 50, k = 9, sols = 2
n = 55, k = 9, sols = 1
n = 56, k = 10, sols = 59
n = 57, k = 10, sols = 67
n = 58, k = 10, sols = 48
n = 59, k = 10, sols = 46
n = 60, k = 10, sols = 32
n = 61, k = 10, sols = 35
n = 62, k = 10, sols = 23
n = 63, k = 10, sols = 18
n = 64, k = 10, sols = 18
n = 65, k = 10, sols = 19
n = 66, k = 10, sols = 8
n = 67, k = 10, sols = 10
n = 68, k = 10, sols = 8
n = 69, k = 10, sols = 8
n = 70, k = 10, sols = 7
n = 71, k = 10, sols = 9
n = 73, k = 10, sols = 4
n = 74, k = 10, sols = 3
n = 75, k = 10, sols = 2
n = 76, k = 10, sols = 3
n = 79, k = 10, sols = 2
n = 80, k = 10, sols = 1
n = 81, k = 10, sols = 2
n = 89, k = 10, sols = 1
n = 90, k = 11, sols = 81
n = 91, k = 11, sols = 89
n = 92, k = 11, sols = 69
n = 93, k = 11, sols = 57
n = 94, k = 11, sols = 61
n = 95, k = 11, sols = 57
n = 96, k = 11, sols = 35
n = 97, k = 11, sols = 45
n = 98, k = 11, sols = 33
n = 99, k = 11, sols = 29
n = 100, k = 11, sols = 26
n = 101, k = 11, sols = 26
n = 102, k = 11, sols = 18
n = 103, k = 11, sols = 21
n = 104, k = 11, sols = 12
n = 105, k = 11, sols = 18
n = 106, k = 11, sols = 14
n = 107, k = 11, sols = 10
n = 108, k = 11, sols = 5
n = 109, k = 11, sols = 9
n = 110, k = 11, sols = 8
n = 111, k = 11, sols = 9
n = 112, k = 11, sols = 7
n = 113, k = 11, sols = 6
n = 114, k = 11, sols = 4
n = 115, k = 11, sols = 6
n = 116, k = 11, sols = 2
n = 117, k = 11, sols = 2
n = 118, k = 11, sols = 3
n = 119, k = 11, sols = 4
n = 120, k = 11, sols = 2
n = 121, k = 11, sols = 2
n = 123, k = 11, sols = 3
n = 128, k = 11, sols = 2
n = 129, k = 11, sols = 2
n = 131, k = 11, sols = 2
n = 144, k = 11, sols = 1
n = 145, k = 12, sols = 124
n = 146, k = 12, sols = 91
n = 147, k = 12, sols = 92
n = 148, k = 12, sols = 66
n = 149, k = 12, sols = 76
n = 150, k = 12, sols = 72
n = 151, k = 12, sols = 68
n = 152, k = 12, sols = 58
n = 153, k = 12, sols = 56
n = 154, k = 12, sols = 45
n = 155, k = 12, sols = 55
n = 156, k = 12, sols = 29
n = 157, k = 12, sols = 46
n = 158, k = 12, sols = 34
n = 159, k = 12, sols = 38
n = 160, k = 12, sols = 28
n = 161, k = 12, sols = 28
n = 162, k = 12, sols = 18
n = 163, k = 12, sols = 22
n = 164, k = 12, sols = 12
n = 165, k = 12, sols = 22
n = 166, k = 12, sols = 19
n = 167, k = 12, sols = 24
n = 168, k = 12, sols = 14
n = 169, k = 12, sols = 17
n = 170, k = 12, sols = 12
n = 171, k = 12, sols = 12
n = 172, k = 12, sols = 5
n = 173, k = 12, sols = 12
n = 174, k = 12, sols = 8
n = 175, k = 12, sols = 4
n = 176, k = 12, sols = 7
n = 177, k = 12, sols = 8
n = 178, k = 12, sols = 8
n = 179, k = 12, sols = 9
n = 180, k = 12, sols = 3
n = 181, k = 12, sols = 8
n = 183, k = 12, sols = 9
n = 184, k = 12, sols = 4
n = 185, k = 12, sols = 3
n = 186, k = 12, sols = 6
n = 187, k = 12, sols = 2
n = 188, k = 12, sols = 2
n = 191, k = 12, sols = 5
n = 192, k = 12, sols = 2
n = 193, k = 12, sols = 3
n = 194, k = 12, sols = 3
n = 196, k = 12, sols = 2
n = 199, k = 12, sols = 3
n = 207, k = 12, sols = 2
n = 208, k = 12, sols = 1
n = 209, k = 12, sols = 2
n = 212, k = 12, sols = 2
n = 233, k = 12, sols = 1


参考代码：

1. #http://www.mathchina.com/bbs/forum.php?mod=viewthread&tid=2044556&amp;page=1&;extra=#pid2395817
   
2. a=[[1], [[1,2]], [[1,2,3]]]
   
3. 
   
4. # 求各 ai 严格递增的解
   
5. if true
   
6.         b = [[1,2,3]]
   
7.         fa = 3; fb = 5;
   
8.         for k=4:18
   
9.                         global b, fa, fb
   
10.                         result = []; t = 0;
    
11.                         for u=1:length(b)
    
12.                                         for i=1:length(b[u])-1
    
13.                                                         t1 = b[u][i]
    
14.                                                         for j=i+1:length(b[u])
    
15.                                                                         t2 = b[u][j]
    
16.                                                                         s = t1 + t2
    
17.                                                                         if s > b[u][end]
    
18.                                                                                         tp = copy(b[u]); tp = append!(tp, s)
    
19.                                                                                         append!(result, [tp])
    
20.                                                                         end   
    
21.                                                         end
    
22.                                         end
    
23.                         end
    
24.                         b=unique(result)
    
25.                         sort!(b, lt=(x, y)->isless(x[end], y[end]))
    
26.                         for j=1:length(b)
    
27.                                         if b[j][end] <= fa
    
28.                                                 continue
    
29.                                         end
    
30.                                        
    
31.                                         t += 1
    
32.                                         if j == length(b) || b[j][end] < b[j+1][end]
    
33.                                                         #println("k = $k, $(b[j])")
    
34.                                                         println("n = $(b[j][end]), k = $k, sols = $t")
    
35.                                                         t = 0
    
36.                                         else
    
37.                                                         #println("k = $k, $(b[j])")
    
38.                                         end   
    
39.                         end
    
40.                         fb, fa = fb + fa, fb
    
41.         end
    
42. end
    
43. 
    

复制代码

王守恩

uk702 发表于 2021-1-17 17:42
按这个要求，写了 julia 程序进行计算，算到 k=12 之后就算不下去了，前 233 项的结果如下（注意数字并不连 ...

a17=2018 似乎就是无解，a18=2018 共有 2612 个严格递增的解
冰火两重天！这题目还真是有点意思了。

王守恩

uk702 发表于 2021-1-17 17:42
按这个要求，写了 julia 程序进行计算，算到 k=12 之后就算不下去了，前 233 项的结果如下（注意数字并不连 ...

uk702！我们先往前走？

正整数数列: a1, a2,…, an
其中 a1=1, a2=2, ak=ai+aj
在这里： 3≤k≤n， 1≤i＜j＜k
试证：当 6<n 时，an=Fn-1 无解。
Fn(兔子数列)=1, 2, 3, 5, 8, 13, 21, 34,....

uk702

既然兄弟热情依旧，我创建了 https:\/\/gitee.com/uk702/mathchina2044556 的 git 仓，以保存相关的代码和结果（这里只能贴<250k 的文件）。

为了方便讨论，我建议作如下的约定：

#### 约定
##### （普通）解
对于给定的 k，满足题目要求的任何一个数列。 \
如 k=3时，只有 [1,2,3] 这一个解，k=4时，有 [1,2,3,3]，[1,2,3,4]，[1,2,3,5] 共 3 个（普通）解。 \
\
同时，若对于指定的 n, 有满足条件的数列存在，则称这个数列是 n 的一个（普通）解，如 n=5 时，数列 [1,2,3,5] 是它的一个解，这时 k=4。

##### 严格递增解
满足 a1 < a2 < a3 < ... < ak 的解，也就是 ai 严格递增的解 \
如 k=4 时，严格递增解有 [1,2,3,4]，[1,2,3,5] 共 2 个解。 \

##### 兔子解
以 F(n) 表示兔子数列 1,2,3,5,8,13，... \
若某个严格递增解同时满足 F(k-1) < ak <= F(k)，则称这个解是兔子解。 \
如 k=4 时，由于F(4)=5，F(3)=3，故 [1,2,3,4]，[1,2,3,5] 这两个解都是兔子解。 \
而 k=5 时，由于F(5)=8，F(4)=5，故共有 [1,2,3,4,6]，[1,2,3,5,6]，[1,2,3,4,7]，[1,2,3,5,7]，[1,2,3,5,8] 这 5 个兔子解。

##### 增强兔子解
增强兔子解除了 ak 要满足 F(k-1) < ak ≤ F(k) 外，还要求对每个 i ≤ k，都满足  F(i-1) < ai ≤ F(i) \
比如说 n=9, k=6，严格递增解（也是兔子解）共有 6 个，为如下所示：\
k = 6, [1, 2, 3, 4, 5, 9] \
k = 6, [1, 2, 3, 4, 6, 9] \
k = 6, [1, 2, 3, 5, 6, 9] \
k = 6, [1, 2, 3, 4, 7, 9] \
k = 6, [1, 2, 3, 5, 7, 9] \
k = 6, [1, 2, 3, 5, 8, 9] \
\
但增强兔子解只有 5 个解，这是因为 [1, 2, 3, 4, 5, 9] 中的 5，不满足 F(4) = 5 < ai  ≤ F(5) = 8，所以它是一个兔子解，但不是增强兔子解。

### 文件
文件【严格递增解/allailefi.txt】保存了 k<35 （k=35 没有算完）所有增强兔子解。

王守恩

uk702 发表于 2021-1-18 11:00
既然兄弟热情依旧，我创建了 https:\/\/gitee.com/uk702/mathchina2044556 的 git 仓，以保存相关的代码和 ...

从宝贵的13楼，我们可以知道：
an(最后1项)=20(共7项), 33(共8项), 54(共9项), 88(共10项), 143(共11项), 232(共12项)是无解的。
我就是想再看看(15楼的意思) ：
376(共13项), 609(共14项), 986(共15项), 1596(共16项), 2583(共17项),...还是无解的吗？
我们先往前走一走，回头再来想为什么，会轻松些。

王守恩

uk702 发表于 2021-1-17 17:42
按这个要求，写了 julia 程序进行计算，算到 k=12 之后就算不下去了，前 233 项的结果如下（注意数字并不连 ...

n = 4, k = 4, sols = 1
uk702 发表于 2021-1-17 17:42
按这个要求，写了 julia 程序进行计算，算到 k=12 之后就算不下去了，前 233 项的结果如下（注意数字并不连 ...
谢谢uk702!!!
从宝贵的13楼，我们可以知道，至少有：
n = 32—33, k = 8,连续2项无解
n = 51—54, k = 9,连续4项无解
n = 82—88, k = 10,连续7项无解
n = 132—143, k = 11,连续12项无解
n = 213—232, k = 12,连续20项无解
n = 344—376, k = 13,连续33项无解
n = 556—609, k = 14,连续54项无解
n = 899—986, k = 15,连续88项无解

uk702

将兔子解扩展到 k≤18，由此推知 a17=2018 无解。

王守恩

kids20082008！题目挺绕人的，能提供些什么吗？谢谢！