{1,2,...,n}的和能被 m 整除的 m 元子集

王守恩

TSC999 发表于 2021-8-1 18:21
2# 楼中的那个验证程序可以简化如下：

因为Scan函数可以直接扫描表。

被减数是用4楼验证程序计算的，减数是用公式②计算的，差好像有什么规律？
光凭前面2,3,4,6,8的规律，还是推不出9的规律来。
n=39,42,45,...还得来几项。
n=09:1-1=0
n=10:2-2=0
n=11:7-7=0
n=12:26-25=1
n=13:81-80=1
n=14:224-223=1
n=15:559-557=2
n=16:1274-1272=2
n=17:2704-2702=2
n=18:5408-5404=4
n=19:10270-10266=4
n=20:18668-18664=4
n=21:32668-32660=8
n=22:55278-55270=8
n=23:90808-90800=8
n=24:145292-145280=12
n=25:227011-226999=12
n=26:347186-347174=12
n=27:520779-520761=18
n=28:767454-767436=18
n=29:1112799-1112781=18
n=30:1589712-1589686=26
n=31:2240037-2240011=26
n=32:3116562-3116536=26
n=33:4285272-4285236=36
n=34:5827956-5827920=36
n=35:7845312-7845276=36
n=36:10460416-10460368=48
n=37:13822676-13822628=48
n=38:18112456-18112408=48
n=39:?-23546129=？
n=40:?-30382101=？
n=41:?-38927066=？
n=42:?-49543538=？
n=43:?-62658003=?
n=44:?-78770060=?
n=45:?-98462575=?
n=46:?-122412930=?
n=47:?-151405465=?
n=48:?-186345187=?
.....
如果用7楼的方法：就得看2704个“0”是怎么分布的，手工难。

王守恩

TSC999 发表于 2021-8-3 20:13
今天折腾出了 \(m=2、4、6、8 \) 的公式如下：\[
F(n,2)=C_n^2/2-\lfloor{n/2}\rfloor/2 \quad .......... ...

对10楼作点修改。
在 1～n 中任意取 9 个不同整数，使得这 9 个数之和能被 9 整除，有几种不同取法？

\(a(n)=(\frac{9\lfloor n/9\rfloor^3+5\lfloor n/9\rfloor\ \ }{27})(\lfloor\frac{(n+5)_{9}+1}{9}\rfloor+\lfloor\frac{(n+4)_{9}+1}{9}\rfloor+\lfloor\frac{(n+3)_{9}+1}{9}\rfloor)\)
\(+(\frac{9\lfloor n/9\rfloor^3-9\lfloor n/9\rfloor^2+8\lfloor n/9\rfloor\ \ }{27})(\lfloor\frac{(n+8)_{9}+1}{9}\rfloor+\lfloor\frac{(n+7)_{9}+1}{9}\rfloor+\lfloor\frac{(n+6)_{9}+1}{9}\rfloor)\)
\(+(\frac{9\lfloor n/9\rfloor^3+9\lfloor n/9\rfloor^2+8\lfloor n/9\rfloor\ \ }{27})(\lfloor\frac{(n+2)_{9}+1}{9}\rfloor+\lfloor\frac{(n+1)_{9}+1}{9}\rfloor+\lfloor\frac{(n)_{9}+1}{9}\rfloor)+\frac{n!/9}{9!(n-9)!}\)

{0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 7, 26, 81, 224, 559, 1274, 2704, 5408, 10270, 18668, 32668, 55278,
90808, 145292, 227011, 347186, 520779, 767454, 1112799, 1589712, 2240037, 3116562, 4285272,
5827956, 7845312, 10460416, 13822676, 18112456, 23546192, 30382164, 38927129, 49543618, 62658083,
78770140, 98462675, 122413030, 151405565, 186345310, 228272976, 278381650, 338034860, 408786310,...}
注：《整数序列在线百科全书(OEIS)》没有收录。

王守恩

王守恩 发表于 2021-8-8 18:00
对10楼作点修改。
在 1～n 中任意取 9 个不同整数，使得这 9 个数之和能被 9 整除，有几种不同取法？

...

在 1～n 中任意取 9 个不同整数，使得这 9 个数之和能被 9 整除，有几种不同取法？

Table[Count[Total/@Subsets[Range@n, {9}]/9, _Integer], {n, 1, 36}]

{0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 7, 26, 81, 224, 559, 1274, 2704, 5408, 10270, 18668, 32668, 55278,
90808, 145292, 227011, 347186, 520779, 767454, 1112799, 1589712, 2240037, 3116562, 4285272,
5827956, 7845312, 10460416, ..............}}

这里是36项。网友们：还可以再来几项吗？

王守恩

chyanog 发表于 2021-8-13 21:52
前45项
0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 7, 26, 81, 224, 559, 1274, 2704, 5408, 10270, 18668, 32 ...

谢谢 chyanog！
n=0——42没有问题。
n=43:99087232, n=44:312124391, n=45:1164273263,好像有问题。

先看11楼(11楼是12楼的依据)：
n=09:1-1=0
n=10:2-2=0
n=11:7-7=0
n=12:26-25=1
n=13:81-80=1
n=14:224-223=1
n=15:559-557=2
n=16:1274-1272=2
n=17:2704-2702=2
n=18:5408-5404=4
n=19:10270-10266=4
n=20:18668-18664=4
n=21:32668-32660=8
n=22:55278-55270=8
n=23:90808-90800=8
n=24:145292-145280=12
n=25:227011-226999=12
n=26:347186-347174=12
n=27:520779-520761=18
n=28:767454-767436=18
n=29:1112799-1112781=18
n=30:1589712-1589686=26
n=31:2240037-2240011=26
n=32:3116562-3116536=26
n=33:4285272-4285236=36
n=34:5827956-5827920=36
n=35:7845312-7845276=36
n=36:10460416-10460368=48
n=37:13822676-13822628=48
n=38:18112456-18112408=48
n=39:23546192-23546129=63
n=40:30382164-30382101=63
n=41:38927129-38927066=63
n=42:49543618-49543538=80
n=43:62658083-62658003=80
n=44:78770140-78770060=80
n=45:98462675-98462575=100
n=46:122413030-122412930=100
n=47:151405565-151405465=100
n=48:186345310-186345187=123
......
上面的规律是这样：减数是用公式②计算的，差好像有规律，倒出来的被减数好像是这样的？

可是n=43:99087232, n=44:312124391, n=45:1164273263,差好像没有规律？
n=43:99087232-62658003=?
n=44:312124391-78770060=?
n=45:1164273263-98462575=?

chyanog

王守恩 发表于 2021-8-14 08:00
谢谢 chyanog！
n=0——42没有问题。
n=43:99087232, n=44:312124391, n=45:1164273263,好像有问题。

从43开始是有点问题，换了个写法，速度也快了很多，前70项

0->0, 1->0, 2->0, 3->0, 4->0, 5->0, 6->0, 7->0, 8->0, 9->1, 10->2, 11->7, 12->26, 13->81, 14->224, 15->559, 16->1274, 17->2704, 18->5408, 19->10270, 20->18668, 21->32668, 22->55278, 23->90808, 24->145292, 25->227011, 26->347186, 27->520779, 28->767454, 29->1112799, 30->1589712, 31->2240037, 32->3116562, 33->4285272, 34->5827956, 35->7845312, 36->10460416, 37->13822676, 38->18112456, 39->23546192, 40->30382164, 41->38927129, 42->49543618, 43->62658083, 44->78770140, 45->98462675, 46->122413030, 47->151405565, 48->186345310, 49->228272976, 50->278381650, 51->338034860, 52->408786310, 53->492401660, 54->590881992, 55->706489302, 56->841774452, 57->999607161, 58->1183208436, 59->1396185915, 60->1642571664, 61->1926862869, 62->2254065954, 63->2629743613, 64->3060065246, 65->3551861398, 66->4112681618, 67->4750856298, 68->5475563138, 69->6296897608, 70->7225948016

耗时 62 s

1. //gcc -O2 main.cpp -fopenmp
   
2. #include <stdio.h>
   
3. #include <time.h>
   
4. 
   
5. #define I64 unsigned long long
   
6. #define FOR(I, S) for(int I = S; I < n; I++)
   
7. 
   
8. int main() {
   
9.     clock_t t1 = clock();
   
10.     for(int n = 0; n <= 70; n++){
    
11.         I64 count=0;
    
12.         #pragma omp parallel for schedule(dynamic) reduction(+:count)
    
13.         FOR(i1, 0)
    
14.         FOR(i2, i1+1)
    
15.         FOR(i3, i2+1)
    
16.         FOR(i4, i3+1)
    
17.         FOR(i5, i4+1)
    
18.         FOR(i6, i5+1)
    
19.         FOR(i7, i6+1)
    
20.         FOR(i8, i7+1)
    
21.         FOR(i9, i8+1)
    
22.         if( (i1 + i2 + i3 + i4 + i5 + i6 + i7 + i8 + i9) % 9 == 0)
    
23.             count++;
    
24.         printf("%d->%lld, ", n, count);
    
25.     }
    
26.     printf("\n%ld ms\n", clock() - t1);
    
27.     return 0;
    
28. }
    

复制代码

王守恩

chyanog 发表于 2021-8-14 11:21
从43开始是有点问题，换了个写法，速度也快了很多，前70项

耗时 62 s

谢谢chyanog！这里是33项。尊敬的chyanog：能再来几项？我就想找个感觉出来(趁热打铁)。

在 1～n 中任意取 10 个不同整数，使得这 10 个数之和能被 10 整除，有几种不同取法？

Table[Count[Total/@Subsets[Range@n, {10}]/10, _Integer], {n, 10, 33}]

{{0, 1, 6, 28, 98, 299, 796, 1940, 4364, 9226, 18452, 35248, 64620,  114362, 196048,
326800, 531048, 843503, 1312114, 2002804, 3004206, 4434921, 6450792, 9255672}}

这里是33项。尊敬的chyanog：能再来几项？

chyanog

王守恩 发表于 2021-8-14 12:37
谢谢chyanog！这里是33项。尊敬的chyanog：能再来几项？我就想找个感觉出来(趁热打铁)。

在 1～n 中任 ...

可以自己改代码运行

0->0, 1->0, 2->0, 3->0, 4->0, 5->0, 6->0, 7->0, 8->0, 9->0, 10->0, 11->1, 12->6, 13->28, 14->98, 15->299, 16->796, 17->1940, 18->4364, 19->9226, 20->18452, 21->35248, 22->64620, 23->114362, 24->196048, 25->326800, 26->531048, 27->843503, 28->1312114, 29->2002804, 30->3004206, 31->4434921, 32->6450792, 33->9255672, 34->13112200, 35->18357328, 36->25417836, 37->34832164, 38->47272220, 39->63573384, 40->84764512, 41->112108400, 42->147142272, 43->191731453, 44->248123054, 45->319016108, 46->407631690, 47->517803323, 48->654067352, 49->821778016, 50->1027222520, 51->1277765890, 52->1581995860, 53->1949903400, 54->2393063260, 55->2924856890, 56->3560695340, 57->4318292180, 58->5217936380, 59->6282823775, 60->7539388530

79 s

TSC999

非常感谢 chyanog 先生的数据。是用 C++写的吧？ 我没有多玩过这个基本语言。即使复制了您的程序代码估计我的电脑配置也不行。
根据 chyanog  提供的数据，可以得到  m = 9  时公式如下：\[
F (n, 9)=\frac{C_n^9}9+\lfloor{n/9}\rfloor^3+\frac{\lfloor{n/9}\rfloor}9\begin{cases}-9\lfloor{n/9}\rfloor+8&n≡0、1、2\pmod{9}\\
\ 5&n≡3、4、5\pmod{9} \\
\ 9\lfloor{n/9}\rfloor+8&n≡6、7、8\pmod{9}
\end{cases}
\] 用 mathematica 程序计算 \(n=1～70\) 结果如下，跟  chyanog 的数据一致。

1. s[n0_]:=Module[{n=n0, m=9},
   
2.                k=\[LeftFloor]n/m\[RightFloor]; r=Mod[n, m];
   
3.                Binomial[n,m]/m+k^3+k/9 Piecewise[{{-9k+8, r<=2}, {5, r<=5}, {9k+8, r<=8}}]]
   
4. Table[{n, s[n]}, {n, 9, 70}] // TableForm

复制代码

运行结果：
  9, 1
10, 2
11, 7
12, 26
13, 81
14, 224
15, 559
16, 1274
17, 2704
18, 5408
19, 10270
20, 18668
21, 32668
22, 55278
23, 90808
24, 145292
25, 227011
26, 347186
27, 520779
28, 767454
29, 1112799
30, 1589712
31, 2240037
32, 3116562
33, 4285272
34, 5827956
35, 7845312
36, 10460416
37, 13822676
38, 18112456
39, 23546192
40, 30382164
41, 38927129
42, 49543618
43, 62658083
44, 78770140
45, 98462675
46, 122413030
47, 151405565
48, 186345310
49, 228272976
50, 278381650
51, 338034860
52, 408786310
53, 492401660
54, 590881992
55, 706489302
56, 841774452
57, 999607161
58, 1183208436
59, 1396185915
60, 1642571664
61, 1926862869
62, 2254065954
63, 2629743613
64, 3060065246
65, 3551861398
66, 4112681618
67, 4750856298
68, 5475563138
69, 6296897608
70, 7225948016

mathe

数值计算还是比较简单的。
我们假设在1～n中选择u个数字之和模M为h的数目为C[n][h]
将这u个数字每个减1，得到1～n-1中选择u个或u-1个数数字之和模M为(h-u)%M, 所以得出递推式
C(u,n,h)=C(u,n-1,h-u)+C(u-1,n-1,h-u)

对应C代码

1. #include <stdio.h>
   
2. 
   
3. #define M 9
   
4. #define N 200
   
5. long C[2][N][M];
   
6. 
   
7. int main()
   
8. {
   
9.     int i,h,n;
   
10.     int u=1,s=1;
    
11.     for(h=0;h<M;h++){
    
12.         for(n=1;n<N;n++){
    
13.             C[u&1][n][h]=n/M;
    
14.             if(h>=1&&h<=n%M)C[u&1][n][h]++;
    
15.         }
    
16.     }
    
17.     for(u=2;u<=M;u++){
    
18.         s+=u;s%=M;
    
19.         for(n=1;n<u;n++)for(h=0;h<M;h++)C[u&1][n][h]=0;
    
20.         for(n=u;n<N;n++){
    
21.             for(h=0;h<M;h++){
    
22.                 int v=h-u;if(v<0)v+=M;
    
23.                 C[u&1][n][h]=C[u&1][n-1][v]+C[(u-1)&1][n-1][v];
    
24.             }
    
25.         }
    
26.     }
    
27.     for(n=1;n<N;n++){
    
28.         printf("%ld\n",C[M&1][n][0]);
    
29.     }
    
30.     return 0;
    
31. }

复制代码

于是可以飞速计算得到M=9时结果为

1
2
7
26
81
224
559
1274
2704
5408
10270
18668
32668
55278
90808
145292
227011
347186
520779
767454
1112799
1589712
2240037
3116562
4285272
5827956
7845312
10460416
13822676
18112456
23546192
30382164
38927129
49543618
62658083
78770140
98462675
122413030
151405565
186345310
228272976
...
98722443868638
103499336313894
108480587793774
113673807421734
119086845870388
124727801726924
不过chyanog最后几项好像错了？

TSC999

根据 chyanog 在 17# 楼的数据，可以得到  m = 10  时公式如下：

\[F (n, 10)={C_n^{10}}/10+\lfloor{n/10}\rfloor(-625\lfloor{n/10}\rfloor^4+1250\lfloor{n/10}\rfloor^3-875\lfloor{n/10}\rfloor^2+442\lfloor{n/10}\rfloor-216)/240\rceil \quad\quad  \quad n≡0、1\quad (mod\enspace 10)  \]
\[F (n, 10)={C_n^{10}}/10+\lfloor{n/10}\rfloor(-625\lfloor{n/10}\rfloor^4+625\lfloor{n/10}\rfloor^3-125\lfloor{n/10}\rfloor^2+167\lfloor{n/10}\rfloor-186)/240\rceil \quad\quad  \quad n≡2、3\quad (mod\enspace 10)  \]
\[F (n, 10)={C_n^{10}}/10+\lfloor{n/10}\rfloor(-625\lfloor{n/10}\rfloor^4+125\lfloor{n/10}\rfloor^2+192\lfloor{n/10}\rfloor-196)/240\rceil \quad\quad  \quad n≡4\quad (mod\enspace 10)  \]
\[F (n, 10)={C_n^{10}}/10+\lfloor{n/10}\rfloor(-625\lfloor{n/10}\rfloor^4+125\lfloor{n/10}\rfloor^2+192\lfloor{n/10}\rfloor-4)/240\rceil \quad\quad  \quad n≡5\quad (mod\enspace 10)  \]
\[F (n, 10)={C_n^{10}}/10+\lfloor{n/10}\rfloor(-625\lfloor{n/10}\rfloor^4-625\lfloor{n/10}\rfloor^3-125\lfloor{n/10}\rfloor^2+217\lfloor{n/10}\rfloor+6)/240\rceil \quad\quad  \quad n≡6、7\quad (mod\enspace 10)  \]
\[F (n, 10)={C_n^{10}}/10+\lfloor{n/10}\rfloor(-625\lfloor{n/10}\rfloor^4-1250\lfloor{n/10}\rfloor^3-875\lfloor{n/10}\rfloor^2-58\lfloor{n/10}\rfloor-24)/240\rceil \quad\quad  \quad n≡8、9\quad (mod\enspace 10)  \]

用 mathematica 程序计算 \(n=1～60\) ，跟  chyanog 的数据一致。