DS

[（ヅ）]

不是Data Scientist，也不是屌丝

考虑非负整数，DS数, digit sum number，指的是一个数的某一位上数字，为其它位上数字之和

s(n)记为"至多n位数字的DS数"的和
s(1) = 0
s(2) = 495
s(3) = 63270
s(7) = 85499991450

问: s(2020) = ? mod 1e16

[YWY]

不是Data Scientist，也不是屌丝

考虑非负整数，DS数, digit sum number，指的是一个数的某一位上数字，为其它位上数字之和

s(n)记为"至多n位数字的DS数"的多少
s(1) = 1
s(2) = 10
s(3) = 63270
s(7) = 85499991450

问: s(2020) = ? mod 1e16

可能懂的人都懂，但我属于不懂的。单从你的描述，我看的是一头雾水。

[（ヅ）]

可能懂的人都懂，但我属于不懂的。单从你的描述，我看的是一头雾水。

S(1)=1, 1位的ds数只有0
s（2）=10，两位的只有11，22，。。。，99。再加上1位的0

如此反复

[YWY]

S(1)=1, 1位的ds数只有0
s（2）=10，两位的只有11，22，。。。，99。再加上1位的0

如此反复

谢，现在我至少看懂题了。

等大家的分析和解答。

[TheMatrix]

S(1)=1, 1位的ds数只有0
s（2）=10，两位的只有11，22，。。。，99。再加上1位的0

如此反复

那3位的怎么可能有那么多？

[（ヅ）]

那3位的怎么可能有那么多？

算嘛

[TheMatrix]

算嘛

3位总共才1000个数。

[（ヅ）]

3位总共才1000个数。

我光顾着抄题了

我想想

[（ヅ）]

3位总共才1000个数。

我修改了原题

-!-

[meiyoumajia]

把0看成（2020-1个0后跟着0）
把133看成（2020-3个0后跟着133）
。。。

考虑最基本的生成元素和24种类型（可能有漏）


“长度”是2
11 22 33 44 55 66 77 88 99 （所有”尾“的和是45。所有位的数之和就是其两倍是：90。在后面会被用。）

长度3
123 134 145 156 167 178 189 235 246 257 268 279 347 358 369 459 （2x110=220）
112 224 336 448 （2x20 = 40，在后面例子中被用）

长度4
1236 1247 1258 1269 1348 1359 2349
1124 1135 1146 1157 1168 1179 2237 2248 2259 1225 1337 1449 2338
1113 2226 3339

11114 22228 （2x12=24）
11125 11136 11147 11158 11169 22239 12227
11226 11338
11237 11248 11259 11349 12238 12249

111115
111126 111137 111148 111159 122229
111227 111339 112228

1111116
1111127 1111138 1111149
1111228
1111239
1112229

11111117
11111128 11111139
11111229

111111118
111111129

1111111119

把每个生成元素的一个个数依次全部放进
（2020-16位）【需要考虑的最后16位】

以224为例，把2 2 4放入到2020位中的3位中，其它位放置0
共产生n=2020*2019*2018/2！个2020位以内的数
从总体的求和上看，2 2 4均匀分布在每个位，平均每个数每个位对求和被“分配”（2+2+4）/2020
不考虑量级，n个数的每位上的数的总和：m=n*（2+2+4）/2020
最后16位总和：（10^15+10^14+...+1)*m = (10^16-1)/9*m
所在类的最后16位总和可通过把上面的（2+2+4）被40取代后得到。

依此类推。把所有的类型表达式加起来后再化简。把10^16尽量去掉”一些“。

很繁

[TheMatrix]

把0看成（2002-1个0后跟着0）
把133看成（2002-3个0后跟着133）
。。。

考虑最基本的生成元素和类型

11 22 33 44 55 66 77 88 99

123 134 145 156 167 178 189 235 246 257 268 279 347 358 369 459
112 224 336 448

。。。

1236 。。。1247 。。。2349
1124 。。。2237 。。。2259
1225 。。。2338
1113 2226 3339

11114 22228
11125 。。。22239
11226 11338
11237 。。。
。。。

。。。


把每个生成元素的一个个数依次全部放进
（2002-16位）【需要考虑的最后16位】

以224为例，把2 2 4放入到2002位中的3位中，其它位放置0
共产生n=2002*2001*2000/2！个2002位以内的数
从总体上看，2 2 4均匀分布在每个位，平均每个数每个位分配（2+2+4）/2002
n个数的最后16位：n*16*（2+2+4）/2002

依此类推

很繁

哦。对。这是Euler partition的问题。接下来就不知道了。

[san721]

不是Data Scientist，也不是屌丝

考虑非负整数，DS数, digit sum number，指的是一个数的某一位上数字，为其它位上数字之和

s(n)记为"至多n位数字的DS数"的和
s(1) = 0
s(2) = 495
s(3) = 63270
s(7) = 85499991450

问: s(2020) = ? mod 1e16

唉，写了半天以为发出去了，结果又没了。Anyway, 如果我题目理解得对的话，对n\geq 2，貌似

S(n)=1+n*{(n-1 choose 1)+(n choose 2)+…+(n+7 choose 9)}-9* (n choose 2).

这样的话，S(2020)也就二十多位。

[san721]

唉，写了半天以为发出去了，结果又没了。Anyway, 如果我题目理解得对的话，对n\geq 2，貌似

S(n)=1+n*{(n-1 choose 1)+(n choose 2)+…+(n+7 choose 9)}- 9*(n choose 2).

这样的话，S(2020)也就二十多位。

Let k be the largest digit. The number "1" in the expression counts the case k=0. When 1\leq k\leq 9，apart from the special case that you have two digits "k" and n-2 digits "0", there are n choices for the "k" digit, and (n+k-2 choose n-2) (or (n+k-2 choose k)) choices for a positive integer with number of digits \leq n-1 and sum of digits equal to k. Summing this over k and correcting the overcount (with that -9*(n choose 2)), we get the answer.

S(2020)=3,173,070,559,865,049,175,734,923,271. Modulo 10^16, one has 5,049,175,734,923,271.

[meiyoumajia]

哦。对。这是Euler partition的问题。接下来就不知道了。

我那后面有点错误，忘了考虑那16位的各个位的量级。
改了。

[YWY]

唉，写了半天以为发出去了，结果又没了。Anyway, 如果我题目理解得对的话，对n\geq 2，貌似

S(n)=1+n*{(n-1 choose 1)+(n choose 2)+…+(n+7 choose 9)}-9* (n choose 2).

这样的话，S(2020)也就二十多位。

Let k be the largest digit. The number "1" in the expression counts the case k=0. When 1\leq k\leq 9，apart from the special case that you have two digits "k" and n-2 digits "0", there are n choices for the "k" digit, and (n+k-2 choose n-2) (or (n+k-2 choose k)) choices for a positive integer with number of digits \leq n-1 and sum of digits equal to k. Summing this over k and correcting the overcount (with that -9*(n choose 2)), we get the answer.

S(2020)=3,173,070,559,865,049,175,734,923,271. Modulo 10^16, one has 5,049,175,734,923,271.

你这个S(n)公式算的是位数不超过n的DS数的个数。一楼楼主改题了，现在要的是位数不超过n的所有DS数的总和。

[YWY]

Let's agree that, for 1234, its 1st digit is 4, 2nd digit is 3, ..., 4th digit is 1, i-th digit is 0 for all i > 4.

Let N be a natural number. We only consider numbers with up to N digits (in base-10). We are not going to repeat this assumption.

Let A(i, k) denote the number/cardinality of those DS numbers whose i-th digit is k (so 0 < i < N+1 and k = 0, 1, ..., 9). Then the sum of all DS numbers is \sum_{i = 1}^N 10^{i-1}(\sum_{k = 0}^9 k A(i, k)). Mod 10^{16}, the answer is \sum_{i = 1}^{16} 10^{i-1}(\sum_{k = 0}^9 k A(i, k)), although this could still exceed 10^{16}; so we might need to mod 10^{16} again.

So it suffices to find A(i, k). When the i-th digit is k, the largest digit of the DS number is at least k. Let A(i, k, s) denote the number/cardinality of DS numbers (up to N digits) whose i-th digit is k and the the largest digit is s (so k \leq s \leq 9). So A(i, k) = A(i, k, k) + ... + A(i, k, 9). So it suffices to find A(i, k, s). It is straightforward to see that A(i, k, s) is independent of i and A(i, k, k) = N - 1. More generally, when k \leq s, we see A(i, k, s) = (N - 1)[s-k+N-3 choose N-3] = (N - 1)[s-k+N-3 choose s-k] . So A(i, k) = (N - 1) \sum_{j = 0}^{9 - k}[j+N-3 choose j].

This may not be the cleverest way to compute it. But this is at least a way to do it.

[YWY]

So, after simplification, we get S(N) = \sum_{i = 1}^N 10^{i-1}(\sum_{k = 1}^9 k A(i, k)) and A(i, k) = (N - 1) \sum_{j = 0}^{9 - k}[j+N-3 choose j] = (N - 1)[7-k+N choose 9-k]. This should make the computation a bit easier.

Since A(i, k) is independent of i, we actually get S(N) = (\sum_{k = 1}^9 k A(i, k))(10^N - 1)/9.

[meiyoumajia]

用我之前叙述的方法算S(3)：：：：：：：：：：：：：：：

“长度”是2::::::
11 22 33 44 55 66 77 88 99 （所有”尾“的和是45。所有位的数之和就是其两倍是：90。在后面会被用。）

把每个生成元素的一个个数依次全部放进3个位中

以22为例，把2 2放入到3位中的2位中，其它位放置0
共产生n=3*2/2!=3 个3位以内的数
从总体的求和看，(2 2)均匀分布在每个位，平均每个数的每个位对求和被“分配” a= (2+2)/3
不考虑量级，n个数的每位上的数的总和：m=n*a
作为代表的此例总和：(10^2+10^1+1)*m
所在类的最后16位总和可通过把上面的（2+2）被90取代后得到所在类的总和：(3*2/2!) * 90/3 * 111



"长度"3:::::::
123 134 145 156 167 178 189 235 246 257 268 279 347 358 369 459 （2x110=220）
此类总和：3! * 220/3 * 111

112 224 336 448 （2x20 = 40）
此类总和: (3!/2!) * 40/3 * 111



把上面三项加起来就是
S(3) = 570*111 = 63270



楼主给出的S(7) = 85499991450 = 76950* 1111111
要算到“长度7”为止。太繁了，那我还是算了吧（就是不去算的意思：-）。

[YWY]

Let's agree that, for 1234, its 1st digit is 4, 2nd digit is 3, ..., 4th digit is 1, i-th digit is 0 for all i > 4.

Let N be a natural number. We only consider numbers with up to N digits (in base-10). We are not going to repeat this assumption.

Let A(i, k) denote the number/cardinality of those DS numbers whose i-th digit is k (so 0 < i < N+1 and k = 0, 1, ..., 9). Then the sum of all DS numbers is \sum_{i = 1}^N 10^{i-1}(\sum_{k = 0}^9 k A(i, k)). Mod 10^{16}, the answer is \sum_{i = 1}^{16} 10^{i-1}(\sum_{k = 0}^9 k A(i, k)), although this could still exceed 10^{16}; so we might need to mod 10^{16} again.

So it suffices to find A(i, k). When the i-th digit is k, the largest digit of the DS number is at least k. Let A(i, k, s) denote the number/cardinality of DS numbers (up to N digits) whose i-th digit is k and the the largest digit is s (so k \leq s \leq 9). So A(i, k) = A(i, k, k) + ... + A(i, k, 9). So it suffices to find A(i, k, s). It is straightforward to see that A(i, k, s) is independent of i and A(i, k, k) = N - 1. More generally, when k \leq s, we see A(i, k, s) = (N - 1)[s-k+N-3 choose N-3] = (N - 1)[s-k+N-3 choose s-k] . So A(i, k) = (N - 1) \sum_{j = 0}^{9 - k}[j+N-3 choose j].

This may not be the cleverest way to compute it. But this is at least a way to do it.

So, after simplification, we get S(N) = \sum_{i = 1}^N 10^{i-1}(\sum_{k = 1}^9 k A(i, k)) and A(i, k) = (N - 1) \sum_{j = 0}^{9 - k}[j+N-3 choose j] = (N - 1)[7-k+N choose 9-k]. This should make the computation a bit easier.

Since A(i, k) is independent of i, we actually get S(N) = (\sum_{k = 1}^9 k A(i, k))(10^N - 1)/9.

上面两个帖子里，我没说推理思路，现在简单说一下：就是把所有不超过N位的DS数都放在那里，做加法时我分别考虑第i位的加法（不考虑进位啥的，就是数学相加）。就好比45加97，我把它想成(4+9)10 + (5+7)1。我上面两贴中的内容基本就是考虑在不超过N位的DS数的列表里，在第i位上数值k出现多少次。

[meiyoumajia]

还是算下去吧。练习counting和大整数的计算。：-）

S(n):::::::::

n位数11...11是共同因子。先只考虑所求作为它的倍数。
（这样在处理2002位情况时会减少整数计算overflow的机会。乘以此数可以这样做：把被乘数一次次每次向左/上进一位，移出的低位充0，共做n-1次shift得到的n-1个数全部加到原来数上即得到乘积。这与2进制的乘法相同。在这里n=16对2002位。溢出最低16位的都被剔掉。）


“长度”是2
11 22 33 44 55 66 77 88 99 （所有”尾“的和是45，在求和时被用。类型中有9个生成元素，在统计此类数的数目时用。标记:(45, 9)）
此类型每个位数的总和：
n(n-1)/2!* 2*45/n =
2(n-1)/2!* 45



长度3
112 224 336 448 (20, 4)
2(n-1)(n-2)/2! * 20

123 134 145 156 167 178 189 235 246 257 268 279 347 358 369 459 (110, 16)
2(n-1)(n-2)* 110



长度4
1113 2226 3339 (18, 3)
2(n-1)(n-2)(n-3)/3!* 18

1124 1135 1146 1157 1168 1179 1225 1337 1449 2237 2248 2259 2338 (92, 13)
2(n-1)(n-2)(n-3)/2!* 92

1236 1247 1258 1269 1348 1359 2349 (56, 7)
2(n-1)(n-2)(n-3)* 56



长度5
11114 22228 (12, 2)
2(n-1)(n-2)(n-3)(n-4)/4!* 12

11125 11136 11147 11158 11169 12227 22239 (51, 7)
2(n-1)(n-2)(n-3)(n-4)/3!* 51

11226 11338 (14, 2)
2(n-1)(n-2)(n-3)(n-4)/2!/2!* 14

11237 11248 11259 11349 12238 12249 12339 (59, 7)
2(n-1)(n-2)(n-3)(n-4)/2!* 59



长度6
111115 (5, 1)
2(n-1)(n-2)(n-3)(n-4)(n-5)/5!* 5

111126 111137 111148 111159 122229 (39, 5)
2(n-1)(n-2)(n-3)(n-4)(n-5)/4!* 39

111227 111339 112228 (24, 3)
2(n-1)(n-2)(n-3)(n-4)(n-5)/3!/2!* 24

111238 111249 (17, 2)
2(n-1)(n-2)(n-3)(n-4)(n-5)/3!* 17

112239 (9, 1)
2(n-1)(n-2)(n-3)(n-4)(n-5)/2!/2!* 9



长度7
1111116 (6, 1)
2(n-1)(n-2)(n-3)(n-4)(n-5)(n-6)/6!*6

1111127 1111138 1111149 (24, 3)
2(n-1)(n-2)(n-3)(n-4)(n-5)(n-6)/5!* 24

1111228 (8, 1)
2(n-1)(n-2)(n-3)(n-4)(n-5)(n-6)/4!/2! * 8

1111239 (9,1)
2(n-1)(n-2)(n-3)(n-4)(n-5)(n-6)/4! * 9

1112229 (9,1)
2(n-1)(n-2)(n-3)(n-4)(n-5)(n-6)/3!/3! * 9


这样得到S(7) 正好是楼主给出的85499991450