有一个正整数 A ，能被 19 整除，且各位数字之和是 2021 ，求 A 的最小值

myyour

有一个正整数A，能被19整除，且各位数字之和是2021，求A的最小值。

王守恩

(1)，A是1个225位数：224*9+1*5=223*9+1*8+1*6=2021
(2)，5在高位：不行
(3)，6在高位：6(99...99)8(99...99)，1+9+1+214=225

答案(3)是电脑出来的，手工能出来吗？

Table[Mod[\(7*10^{224} - 10^{224 - n} - 1\), 19], {n, 1, 10}]
{8, 12, 1, 17, 11, 18, 13, 3, 2, 0}

Table[\(7*10^{26} - 10^{26 - n} - 1\), {n, 0, 10}]
{599999999999999999999999999,
689999999999999999999999999,
698999999999999999999999999,
699899999999999999999999999,
699989999999999999999999999,
699998999999999999999999999,
699999899999999999999999999,
699999989999999999999999999,
699999998999999999999999999,
699999999899999999999999999,
699999999989999999999999999}

myyour

王守恩 发表于 2021-12-10 10:21
1，A是1个225位数：224*9+1*5=2021
2，5尽量在高位：(99...99)5(99...99)，16+1+208=225

谢谢王老师，怎么判断这个数能否被19整除啊？

lihp2020

列竖式 计算 1/19

1        *100/19=        5        余        5
5        *100/19=        26        余        6
6        *100/19=        31        余        11
11        *100/19=        57        余        17
17        *100/19=        89        余        9
9        *100/19=        47        余        7
7        *100/19=        36        余        16
16        *100/19=        84        余        4
4        *100/19=        21        余        1
1        *100/19=        5        余        5  （这个位置开始循环了）
5        *100/19=        26        余        6
6        *100/19=        31        余        11
11        *100/19=        57        余        17
17        *100/19=        89        余        9
9        *100/19=        47        余        7
7        *100/19=        36        余        16
16        *100/19=        84        余        4

可以得到 1/19 =0.052631578947368421  052631578947368421  052631578947368421 ...

所以 可得18个1 能被19整除
18个1= 9个1 * 10000000001
1000000001因式分解 验证 7 * 11 * 13 * 19 * 52579

2021 /9 =224  余 5
我们不考虑能被19 整除 最小的数就该是5后面224个9   由于 18个9 能被19整除
224/18=12余8
加入  a***c 能被19整除 那么a***c后跟n*18个9也能被整除
我们考虑  

5后面224个9  = 5后面8个9  后面在12*18个9  

由于后面12*18个9  一定能被19整除
5后面8个9 多半不能  (不用计算 直接猜测)
  5后面8个9 的一个9位数  数字和=5+8*9 =77
  
现在 找一个9位数 数字和=77 的最小数 能被19整除就好

我找到的是 789989999   
ps（如何寻找一个9位数 数字和=77 的最小数 能被19整除 后面介绍）
那么 就是789989999 后面跟上216个9  就是最小的数

lihp2020

上面结论考虑不周
我强行 保证 后面N*18个9  其实可以不 用
纯手算 流程
分析 由于前面分析了 18个9  能被19 整除

10^18-1 能被19整除
那么
abc（18个9）efg 和abcefg 相对19 同余
abc（18个9）efg≡abcefg(mod 19)


由于我们要分析 5（224个9） 除以 19 余多少？

5（224个9） ≡5（8个9）(mod19)
【
由于 这个流程都有 好的 N个连续9  我们 就计算一下 保存好

10^n-1 mod 19 分别是多少

10^1-1 mode 19 =9
10^2-1 mode 19 =4
10^3-1 mode 19 =11
10^4-1 mode 19 =5
10^5-1 mode 19 =2
10^6-1 mode 19 =10
10^7-1 mode 19 =14
10^8-1 mode 19 =16
10^9-1 mode 19 =17
10^10-1 mode 19 =8
10^11-1 mode 19 =13
10^12-1 mode 19 =6
10^13-1 mode 19 =12
10^14-1 mode 19 =15
10^15-1 mode 19 =7
10^16-1 mode 19 =3
10^17-1 mode 19 =1
10^18-1 mode 19 =0(开始循环)
10^19-1 mode 19 =9
10^20-1 mode 19 =4

其实 快捷计算 就是an =mod(an-1*10+9,19) 这样就能手动计算】

5（8个9）(mod19)  
查上表  10^8-1 mode 19 =16
5（8个9）= 5*(10^8-1) +5+ 10^8-1
5*16+5+16 mode 19= 6

不满足

所以要满足条件的数 大概长相 6(n个9)8(m个9)
先算6（224个9） 除以 19 余多少
6（224个9） ≡6（8个9）(mod19)
6（8个9） ≡(6*16+6+16)(mod19) =4

所以6（223个9）8 mod 19 =3 （减少了1）

把 8 移动到第K位  就是K位9 变成8  第1位 8变成9
相差 10^(K-1)-1
原来 余数是3  减去 10^(K-1)-1 能乘除
所以10^(K-1)-1 mode19 =3  查上表可得 k=17

所以 6(224个9） 把 第17位的9 改成8就能被17整除

而再往K再往上挪到 18 位 相差    10^18-1   这个数能被19整除
所以可以往上挪到 n*18位
(224-17)/18=11   11*18+17 =215

6(n个9)8(214个9）
1+n+1+214=245 解得n=9

6(9个9)8(214个9）

Nicolas2050

我就奇怪了，难道编程很难？

lihp2020

Nicolas2050 发表于 2021-12-10 18:07
我就奇怪了，难道编程很难？

我记得 很多 初中小学 就很多 大数 求余的问题 lg：判断  一个和大的数是否被13 17 11 整除  所以 按照小学初中的思路做

uk702

易知，数字和为 2021 的最小整数是 59....9，其中 9 的个数为 224，也就是 6*10^224-1。经检验，6*10^224-1 mod 19 = 6 非所求。

数字和为 2021 的第2小的整数是 689....9(223个) =7*10^224-10^223-1， 第3小的整数是 6989...9(222个）= 7*10^224-10^222-1，第4小的整数是 69989...9(221个）= 7*10^224-10^221-1，...，依次为 69...9(m个)89...9(n个）= 7*10^224-10^m-1，其中 m+n=223，m=223..0。

经计算， (7*10^224-10^214-1) % 19 = 0


(19:35) gp > 7*10^224-10^214-1
%62 = 699999999989999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
(19:36) gp > vecsum(digits(7*10^224-10^214-1))
%63 = 2021
(19:36) gp > (7*10^224-10^214-1)/19                                                                             
%64 = 3684210526263157894736842105263157894736842105263157894736842105263157894736842105263157894736842105263157
8947368421052631578947368421052631578947368421052631578947368421052631578947368421052631578947368421052631578947
368421                                                                                                         
(19:37) gp > %*19                                                                                               
%65 = 6999999999899999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
9999999                                                                                                         

王守恩

有一个正整数A，能被奇素数P(p<m)整除，且各位数字之和是9m+k(8≥k≥0)，求A的最小值。
给出电脑计算通解公式(参考2楼)。
Table[Mod[\((k+2)*10^{m} - 10^{m - n} - 1\), p], {n, 0, p}]
电脑显示0时，对应的n就是解，即：A=\((k+2)*10^{m} - 10^{m - n} - 1\)