数学研发论坛

 找回密码
 欢迎注册
楼主: TSC999

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

[复制链接]
发表于 2021-8-7 19:43:40 | 显示全部楼层
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”是怎么分布的,手工难。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-8-8 18:00:15 | 显示全部楼层
本帖最后由 王守恩 于 2021-8-8 18:07 编辑
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-13 17:59:02 | 显示全部楼层
本帖最后由 王守恩 于 2021-8-13 18:12 编辑
王守恩 发表于 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项。网友们:还可以再来几项吗?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-8-14 08:00:13 | 显示全部楼层
本帖最后由 王守恩 于 2021-8-14 08:09 编辑
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=?

点评

王守恩言之有理。因为 n=45 时如果是 1164273263,算出的 m=9 的公式系数非常大,有 9 位数。与 m=8 时相差甚远。  发表于 2021-8-14 09:42
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-8-14 11:21:27 | 显示全部楼层
本帖最后由 chyanog 于 2021-8-14 15:29 编辑
王守恩 发表于 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. #define I64 unsigned long long
  5. #define FOR(I, S) for(int I = S; I < n; I++)

  6. int main() {
  7.     clock_t t1 = clock();
  8.     for(int n = 0; n <= 70; n++){
  9.         I64 count=0;
  10.         #pragma omp parallel for schedule(dynamic) reduction(+:count)
  11.         FOR(i1, 0)
  12.         FOR(i2, i1+1)
  13.         FOR(i3, i2+1)
  14.         FOR(i4, i3+1)
  15.         FOR(i5, i4+1)
  16.         FOR(i6, i5+1)
  17.         FOR(i7, i6+1)
  18.         FOR(i8, i7+1)
  19.         FOR(i9, i8+1)
  20.         if( (i1 + i2 + i3 + i4 + i5 + i6 + i7 + i8 + i9) % 9 == 0)
  21.             count++;
  22.         printf("%d->%lld, ", n, count);
  23.     }
  24.     printf("\n%ld ms\n", clock() - t1);
  25.     return 0;
  26. }
复制代码

评分

参与人数 2威望 +11 金币 +11 贡献 +11 经验 +11 鲜花 +11 收起 理由
TSC999 + 2 + 2 + 2 + 2 + 2 很给力!
王守恩 + 9 + 9 + 9 + 9 + 9 谢谢大神!

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-8-14 12:37:06 | 显示全部楼层
本帖最后由 王守恩 于 2021-8-14 12:59 编辑
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:能再来几项?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-8-14 14:21:40 | 显示全部楼层
本帖最后由 chyanog 于 2021-8-14 14:25 编辑
王守恩 发表于 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

评分

参与人数 1威望 +9 金币 +9 贡献 +9 经验 +9 鲜花 +9 收起 理由
王守恩 + 9 + 9 + 9 + 9 + 9 非常感谢!答案正确!

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2021-8-14 16:37:48 | 显示全部楼层
非常感谢 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

点评

是C代码,但C++编译器也能编译,对电脑配置要求很低的  发表于 2021-8-15 12:43
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-8-14 16:44:22 | 显示全部楼层
数值计算还是比较简单的。
我们假设在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. #define M 9
  3. #define N 200
  4. long C[2][N][M];

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

于是可以飞速计算得到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最后几项好像错了?

点评

请举例子说明递推公式,我只会这样简单理解:18668(9,9,20)=10270(9,9,19)+8398(9,8,19)  发表于 2021-8-15 11:54
前面错误的数据是王守恩提供的?我看错了。是编译器区别,微软的是P64就是指针64位,long 32位。但是大部分主流编译器都是LP64,就是long和指针都是64位。  发表于 2021-8-15 10:04
请举例子说明递推公式 C(u,n,h) = C(u,n-1,h-u) + C(u-1,n-1,h-u),例如 M=9,u=9,n=20,式中三项各是多少?  发表于 2021-8-15 09:24
能改写为 mathematica 程序吗?  发表于 2021-8-14 22:05
你的代码应该是在Linux上运行的,long在64位Linux下与64位的windows不一致  发表于 2021-8-14 17:58

评分

参与人数 1威望 +9 金币 +9 贡献 +9 经验 +9 鲜花 +9 收起 理由
王守恩 + 9 + 9 + 9 + 9 + 9 n(199)=124727801726924

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2021-8-14 21:57:17 | 显示全部楼层
根据 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 的数据一致。

评分

参与人数 1威望 +3 金币 +3 贡献 +3 经验 +3 鲜花 +3 收起 理由
王守恩 + 3 + 3 + 3 + 3 + 3 公式正确!

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2022-6-28 13:52 , Processed in 0.099954 second(s), 16 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表