小学数学题# Parenting - 为人父母
s*j
1 楼
比较难, 小孩做不出来没关系, 大多数上完了大学的也做不出来的.
证明 任给一个自然数 n , 存在 n 的整倍数 M (非零),
M 只由 0 和 1 构成 (十进制).
比如说 n=25, M=100
n=7, M =111,111
证明 任给一个自然数 n , 存在 n 的整倍数 M (非零),
M 只由 0 和 1 构成 (十进制).
比如说 n=25, M=100
n=7, M =111,111
d*g
2 楼
不太难证明。
但话说:
1 1
2 10
3 111
4 100
5 10
6 1110
7 1001
8 1000
9 111111111
9很隔色的说。:）
27 - 1101111111
但话说:
1 1
2 10
3 111
4 100
5 10
6 1110
7 1001
8 1000
9 111111111
9很隔色的说。:）
27 - 1101111111
a*g
3 楼
有趣。想一想。
【在 s*****j 的大作中提到】
: 比较难, 小孩做不出来没关系, 大多数上完了大学的也做不出来的.
: 证明 任给一个自然数 n , 存在 n 的整倍数 M (非零),
: M 只由 0 和 1 构成 (十进制).
: 比如说 n=25, M=100
: n=7, M =111,111
【在 s*****j 的大作中提到】
: 比较难, 小孩做不出来没关系, 大多数上完了大学的也做不出来的.
: 证明 任给一个自然数 n , 存在 n 的整倍数 M (非零),
: M 只由 0 和 1 构成 (十进制).
: 比如说 n=25, M=100
: n=7, M =111,111
d*g
4 楼
我的世界就好像，
0 和 1 构成 的十进制数,
很空灵,
有很多破洞。
【在 s*****j 的大作中提到】
: 比较难, 小孩做不出来没关系, 大多数上完了大学的也做不出来的.
: 证明 任给一个自然数 n , 存在 n 的整倍数 M (非零),
: M 只由 0 和 1 构成 (十进制).
: 比如说 n=25, M=100
: n=7, M =111,111
0 和 1 构成 的十进制数,
很空灵,
有很多破洞。
【在 s*****j 的大作中提到】
: 比较难, 小孩做不出来没关系, 大多数上完了大学的也做不出来的.
: 证明 任给一个自然数 n , 存在 n 的整倍数 M (非零),
: M 只由 0 和 1 构成 (十进制).
: 比如说 n=25, M=100
: n=7, M =111,111
d*g
5 楼
1, 10, 漏走了９
11,100, 漏走了９0
101,110, 松一口气
111,1000 OOPS, 漏走了９00
不忍继续。。。
11,100, 漏走了９0
101,110, 松一口气
111,1000 OOPS, 漏走了９00
不忍继续。。。
t*l
6 楼
目测好像是类似进制转换的某种 pseudo inverse。
十进制转二进制是做除法，从高位开始，每次除一个固定的二。
这玩意儿是乘法，目测是不是试试从低位开始？当然每次可以乘不同的数？
先涂鸦到这里，过一会儿再看。
：
： 比较难, 小孩做不出来没关系, 大多数上完了大学的也做不出来的.
十进制转二进制是做除法，从高位开始，每次除一个固定的二。
这玩意儿是乘法，目测是不是试试从低位开始？当然每次可以乘不同的数？
先涂鸦到这里，过一会儿再看。
：
： 比较难, 小孩做不出来没关系, 大多数上完了大学的也做不出来的.
t*l
7 楼
9
9 * 9 = 81
81 * ?1 = ?01 或 ?11
(问号可以指代不同的数字)
... ...
难道又是体力活？
：1, 10, 漏走了９
：11,100, 漏走了９0
9 * 9 = 81
81 * ?1 = ?01 或 ?11
(问号可以指代不同的数字)
... ...
难道又是体力活？
：1, 10, 漏走了９
：11,100, 漏走了９0
t*l
8 楼
当然体力活也不能太不小心了，是 0 是 1 还要算，我改成待定好了。
：9
：
：9
：
t*l
9 楼
是 0 是 1 取决于奇偶性，但是要考虑移位进位一起看。所以比较费体力。
：当然体力活也不能太不小心了，是 0 是 1 还要算，我改成待定好了。
：
：当然体力活也不能太不小心了，是 0 是 1 还要算，我改成待定好了。
：
t*l
10 楼
然后就
* ?01 =
* ?001 =
* ?0001 =
当然有个问题是要证明不会死循环，应该不难，因为每次小于 * 10000000...
：是 0 是 1 取决于奇偶性，但是要考虑移位进位一起看。所以比较费体力。
：
* ?01 =
* ?001 =
* ?0001 =
当然有个问题是要证明不会死循环，应该不难，因为每次小于 * 10000000...
：是 0 是 1 取决于奇偶性，但是要考虑移位进位一起看。所以比较费体力。
：
t*l
11 楼
想了想，这有个问题好像是死循环，因为进位的存在，每次干掉一位但多出来一位。要
消灭这个问题才不死循环，得再想想。
：然后就
：
消灭这个问题才不死循环，得再想想。
：然后就
：
t*l
12 楼
基于 0 / 1 加 shift 的pattern generation 有困难的话，可以考虑基于 prime
factorization，用 prime 2 和 prime 5 会不会就能不死循环？
factorization，用 prime 2 和 prime 5 会不会就能不死循环？
t*l
13 楼
我自己把自己搞糊涂了，其实 pattern generation 的算法是可以的，但是不要累乘，
而是寻找高位在原来的数上乘就可以避免死循环。也就是：
9 * 9 = 81
9 * ?9 = ?01 或 ?11，取决于奇偶性（问号可以是不同的数字）
最终线性方程组总存在解。就可以了。剩下的电算。
而是寻找高位在原来的数上乘就可以避免死循环。也就是：
9 * 9 = 81
9 * ?9 = ?01 或 ?11，取决于奇偶性（问号可以是不同的数字）
最终线性方程组总存在解。就可以了。剩下的电算。
t*l
14 楼
我觉得你这个思考角度有个绊脚石就是，找到或者证明 cover 到一个连续范围内所有
primes，这陶天才也不一定行。。。当然，话说回来，如果是张老，那说不定就是人类
一大步。。。
所以 AMO 也有坏习惯的地方，就是老躲在 bunker 里不思进取。。。当然，话还是说
回来，出 bunker 的愣头青里，十个里九个是炮灰，当然还有一个可能就是伟人。。。
：1, 10, 漏走了９
：11,100, 漏走了９0
primes，这陶天才也不一定行。。。当然，话说回来，如果是张老，那说不定就是人类
一大步。。。
所以 AMO 也有坏习惯的地方，就是老躲在 bunker 里不思进取。。。当然，话还是说
回来，出 bunker 的愣头青里，十个里九个是炮灰，当然还有一个可能就是伟人。。。
：1, 10, 漏走了９
：11,100, 漏走了９0
x*1
15 楼
不知道这么证对不对，
对任何一个个位数，存在这么一个个位数，两者乘积的最后一位为1或0，比如9*9=81，
8*5=0，等等。
对任何一个个位数，存在这么一个个位数，两者乘积再加上任何数，其结果的最后一位
数为1或0，比如，9＊1+1=10，9*5+5=50，8*1+3=11，8*5+1=41，等等。
对任何一自然数，找一个数使乘积的最后一位为1或0，再找一个数，乘以这一自然数，
加上上次乘积的除了0或1 的数，使其结果的最后一位为0或1，做下去，直到第一位为1
为止。这些找到的数，从后向前排起来，就是所要求的数。
比如7，找一个3，再找一个数乘以7加上2为0或1，为4，再找一个数乘以7加上3为0或1
，这个数正好为1，于是，7*143=1001，
比如7，找一个3，再找一个7，麻烦了，还得找个8找5找1，结果为7＊1583=111，111.
【在 s*****j 的大作中提到】
: 比较难, 小孩做不出来没关系, 大多数上完了大学的也做不出来的.
: 证明 任给一个自然数 n , 存在 n 的整倍数 M (非零),
: M 只由 0 和 1 构成 (十进制).
: 比如说 n=25, M=100
: n=7, M =111,111
对任何一个个位数，存在这么一个个位数，两者乘积的最后一位为1或0，比如9*9=81，
8*5=0，等等。
对任何一个个位数，存在这么一个个位数，两者乘积再加上任何数，其结果的最后一位
数为1或0，比如，9＊1+1=10，9*5+5=50，8*1+3=11，8*5+1=41，等等。
对任何一自然数，找一个数使乘积的最后一位为1或0，再找一个数，乘以这一自然数，
加上上次乘积的除了0或1 的数，使其结果的最后一位为0或1，做下去，直到第一位为1
为止。这些找到的数，从后向前排起来，就是所要求的数。
比如7，找一个3，再找一个数乘以7加上2为0或1，为4，再找一个数乘以7加上3为0或1
，这个数正好为1，于是，7*143=1001，
比如7，找一个3，再找一个7，麻烦了，还得找个8找5找1，结果为7＊1583=111，111.
【在 s*****j 的大作中提到】
: 比较难, 小孩做不出来没关系, 大多数上完了大学的也做不出来的.
: 证明 任给一个自然数 n , 存在 n 的整倍数 M (非零),
: M 只由 0 和 1 构成 (十进制).
: 比如说 n=25, M=100
: n=7, M =111,111
t*l
16 楼
基本属实。。。之所以说基本，是因为具体证明细节是个体力活，细节我没仔细看，除
非有人开支票。
：不知道这么证对不对，
：
非有人开支票。
：不知道这么证对不对，
：
t*l
17 楼
这个算法如果 branch 成 binary tree，应该是保证最强，也就是找到最小的满足的数。
现在的问题是，能不能每次选 0 / 1 是当场做决定，在线性时间内找到最优解。（线
性时间是指对于 number of digits 而言)。
：不知道这么证对不对，
：
现在的问题是，能不能每次选 0 / 1 是当场做决定，在线性时间内找到最优解。（线
性时间是指对于 number of digits 而言)。
：不知道这么证对不对，
：
x*1
18 楼
例如17:
17*3=51
17*5+5=90
17*3+9=60
17*2+6=40
17*1+4=21
17*4+2=70
17*9+7=160
17*5+16=101
那么这个数就是59412353，可以验算，
所以17*59412353=1010010001
为1
1
【在 x***1 的大作中提到】
: 不知道这么证对不对，
: 对任何一个个位数，存在这么一个个位数，两者乘积的最后一位为1或0，比如9*9=81，
: 8*5=0，等等。
: 对任何一个个位数，存在这么一个个位数，两者乘积再加上任何数，其结果的最后一位
: 数为1或0，比如，9＊1+1=10，9*5+5=50，8*1+3=11，8*5+1=41，等等。
: 对任何一自然数，找一个数使乘积的最后一位为1或0，再找一个数，乘以这一自然数，
: 加上上次乘积的除了0或1 的数，使其结果的最后一位为0或1，做下去，直到第一位为1
: 为止。这些找到的数，从后向前排起来，就是所要求的数。
: 比如7，找一个3，再找一个数乘以7加上2为0或1，为4，再找一个数乘以7加上3为0或1
: ，这个数正好为1，于是，7*143=1001，
17*3=51
17*5+5=90
17*3+9=60
17*2+6=40
17*1+4=21
17*4+2=70
17*9+7=160
17*5+16=101
那么这个数就是59412353，可以验算，
所以17*59412353=1010010001
为1
1
【在 x***1 的大作中提到】
: 不知道这么证对不对，
: 对任何一个个位数，存在这么一个个位数，两者乘积的最后一位为1或0，比如9*9=81，
: 8*5=0，等等。
: 对任何一个个位数，存在这么一个个位数，两者乘积再加上任何数，其结果的最后一位
: 数为1或0，比如，9＊1+1=10，9*5+5=50，8*1+3=11，8*5+1=41，等等。
: 对任何一自然数，找一个数使乘积的最后一位为1或0，再找一个数，乘以这一自然数，
: 加上上次乘积的除了0或1 的数，使其结果的最后一位为0或1，做下去，直到第一位为1
: 为止。这些找到的数，从后向前排起来，就是所要求的数。
: 比如7，找一个3，再找一个数乘以7加上2为0或1，为4，再找一个数乘以7加上3为0或1
: ，这个数正好为1，于是，7*143=1001，
x*1
19 楼
不知道咋找，我只是觉得有意思。
数。
【在 t******l 的大作中提到】
: 这个算法如果 branch 成 binary tree，应该是保证最强，也就是找到最小的满足的数。
: 现在的问题是，能不能每次选 0 / 1 是当场做决定，在线性时间内找到最优解。（线
: 性时间是指对于 number of digits 而言)。
:
: ：不知道这么证对不对，
: ：
数。
【在 t******l 的大作中提到】
: 这个算法如果 branch 成 binary tree，应该是保证最强，也就是找到最小的满足的数。
: 现在的问题是，能不能每次选 0 / 1 是当场做决定，在线性时间内找到最优解。（线
: 性时间是指对于 number of digits 而言)。
:
: ：不知道这么证对不对，
: ：
t*l
20 楼
另外递归时能保证降低 subproblem 位数（保证每次生成一个 1 / 0，而新乘上的数字
最大为 9，只要选小的数，总会发生不进位的情况 ），这样最终降低到一位数问题。
而所有一位数问题都有解，这样就最终可解而不会死递归。
：不知道这么证对不对，
：
最大为 9，只要选小的数，总会发生不进位的情况 ），这样最终降低到一位数问题。
而所有一位数问题都有解，这样就最终可解而不会死递归。
：不知道这么证对不对，
：
t*l
21 楼
我的想法是用竖式做的，不过没打草稿。我看了你写的，我觉得得有空打个草稿证明不
会死循环。
：例如17:
：
会死循环。
：例如17:
：
x*1
22 楼
对5的倍数的数，除以5，再做。
为1
1
【在 x***1 的大作中提到】
: 不知道这么证对不对，
: 对任何一个个位数，存在这么一个个位数，两者乘积的最后一位为1或0，比如9*9=81，
: 8*5=0，等等。
: 对任何一个个位数，存在这么一个个位数，两者乘积再加上任何数，其结果的最后一位
: 数为1或0，比如，9＊1+1=10，9*5+5=50，8*1+3=11，8*5+1=41，等等。
: 对任何一自然数，找一个数使乘积的最后一位为1或0，再找一个数，乘以这一自然数，
: 加上上次乘积的除了0或1 的数，使其结果的最后一位为0或1，做下去，直到第一位为1
: 为止。这些找到的数，从后向前排起来，就是所要求的数。
: 比如7，找一个3，再找一个数乘以7加上2为0或1，为4，再找一个数乘以7加上3为0或1
: ，这个数正好为1，于是，7*143=1001，
为1
1
【在 x***1 的大作中提到】
: 不知道这么证对不对，
: 对任何一个个位数，存在这么一个个位数，两者乘积的最后一位为1或0，比如9*9=81，
: 8*5=0，等等。
: 对任何一个个位数，存在这么一个个位数，两者乘积再加上任何数，其结果的最后一位
: 数为1或0，比如，9＊1+1=10，9*5+5=50，8*1+3=11，8*5+1=41，等等。
: 对任何一自然数，找一个数使乘积的最后一位为1或0，再找一个数，乘以这一自然数，
: 加上上次乘积的除了0或1 的数，使其结果的最后一位为0或1，做下去，直到第一位为1
: 为止。这些找到的数，从后向前排起来，就是所要求的数。
: 比如7，找一个3，再找一个数乘以7加上2为0或1，为4，再找一个数乘以7加上3为0或1
: ，这个数正好为1，于是，7*143=1001，
x*1
23 楼
对，有死循环，但可以换另外一个数，就不循环。
【在 t******l 的大作中提到】
: 我的想法是用竖式做的，不过没打草稿。我看了你写的，我觉得得有空打个草稿证明不
: 会死循环。
:
: ：例如17:
: ：
【在 t******l 的大作中提到】
: 我的想法是用竖式做的，不过没打草稿。我看了你写的，我觉得得有空打个草稿证明不
: 会死循环。
:
: ：例如17:
: ：
t*l
24 楼
竖式做的意思，就是移位对准，延迟计算高位直到数据相关性发生，因此每次只计算一
位数字（解决必须的数据相关性之后）。一直 roll 到最高位，然后最高位试图解决成
1。
不过我刚才没注意到最高位总会有数字加进来，所以是个序列问题。得证明不会死循环。
等有草稿纸再说。
：我的想法是用竖式做的，不过没打草稿。我看了你写的，我觉得得有空打个草稿证明
不会死循环。
：
位数字（解决必须的数据相关性之后）。一直 roll 到最高位，然后最高位试图解决成
1。
不过我刚才没注意到最高位总会有数字加进来，所以是个序列问题。得证明不会死循环。
等有草稿纸再说。
：我的想法是用竖式做的，不过没打草稿。我看了你写的，我觉得得有空打个草稿证明
不会死循环。
：
p*s
25 楼
问了儿子，他说太简单了，不就是抽屉原理。。。
x*1
26 楼
啥叫抽屉原理？
【在 p**s 的大作中提到】
: 问了儿子，他说太简单了，不就是抽屉原理。。。
【在 p**s 的大作中提到】
: 问了儿子，他说太简单了，不就是抽屉原理。。。
t*l
27 楼
这题用抽屉原理是不是要反证法？
t*d
28 楼
任一整数10^k除以n的余数0<=R
这n个同余数的10^ki (1就是一个 n 的整倍数 M (非零),
M 只由 0 和 1 构成 (十进制).
就是一个抽屉原理题
这n个同余数的10^ki (1就是一个 n 的整倍数 M (非零),
M 只由 0 和 1 构成 (十进制).
就是一个抽屉原理题
t*d
29 楼
你儿子不错
【在 p**s 的大作中提到】
: 问了儿子，他说太简单了，不就是抽屉原理。。。
【在 p**s 的大作中提到】
: 问了儿子，他说太简单了，不就是抽屉原理。。。
t*l
30 楼
也可能是多少位数字，取不同 0 1 方式，能产生多少个不同的 pair 的成绩，大于某
一个范围内所有可能的 pair。这类想法。
：啥叫抽屉原理？
：【 在 plus (plus) 的大作中提到: 】
一个范围内所有可能的 pair。这类想法。
：啥叫抽屉原理？
：【 在 plus (plus) 的大作中提到: 】
t*l
31 楼
这类小学题马工做不出来倒是情有可原，数学系更擅长这类一些。
当然可能是给我自己找借口，不过确实大部分一般马工这类题确实不太行，图灵机的学
多了。
：任一整数10^k除以n的余数0<=R
当然可能是给我自己找借口，不过确实大部分一般马工这类题确实不太行，图灵机的学
多了。
：任一整数10^k除以n的余数0<=R
t*l
32 楼
另外我待会儿仔细看这个逻辑。
：任一整数10^k除以n的余数0<=R<n，
：考察n^2个整数10^k, 0<k<n^2,
：任一整数10^k除以n的余数0<=R<n，
：考察n^2个整数10^k, 0<k<n^2,
t*l
33 楼
但这个可能要证明。我得想想。
：对，有死循环，但可以换另外一个数，就不循环。
：【 在 timefall (时光崩塌) 的大作中提到: 】
：对，有死循环，但可以换另外一个数，就不循环。
：【 在 timefall (时光崩塌) 的大作中提到: 】
p*s
34 楼
1
11
111
1111
11111
111111
1111111
......
n+1个里，至少有两个除以n余数相同，这两个数相减
【在 x***1 的大作中提到】
: 啥叫抽屉原理？
11
111
1111
11111
111111
1111111
......
n+1个里，至少有两个除以n余数相同，这两个数相减
【在 x***1 的大作中提到】
: 啥叫抽屉原理？
x*1
35 楼
厉害，不是一个级别的。
【在 t*******d 的大作中提到】
: 任一整数10^k除以n的余数0<=R
: 这n个同余数的10^ki (1: 就是一个 n 的整倍数 M (非零),
: M 只由 0 和 1 构成 (十进制).
: 就是一个抽屉原理题
【在 t*******d 的大作中提到】
: 任一整数10^k除以n的余数0<=R
: 这n个同余数的10^ki (1: 就是一个 n 的整倍数 M (非零),
: M 只由 0 和 1 构成 (十进制).
: 就是一个抽屉原理题
x*1
36 楼
一样高富帅，好理解些。
【在 p**s 的大作中提到】
: 1
: 11
: 111
: 1111
: 11111
: 111111
: 1111111
: ......
: n+1个里，至少有两个除以n余数相同，这两个数相减
【在 p**s 的大作中提到】
: 1
: 11
: 111
: 1111
: 11111
: 111111
: 1111111
: ......
: n+1个里，至少有两个除以n余数相同，这两个数相减
t*d
37 楼
en, n个同余相加，或2个同余相减
【在 p**s 的大作中提到】
: 1
: 11
: 111
: 1111
: 11111
: 111111
: 1111111
: ......
: n+1个里，至少有两个除以n余数相同，这两个数相减
【在 p**s 的大作中提到】
: 1
: 11
: 111
: 1111
: 11111
: 111111
: 1111111
: ......
: n+1个里，至少有两个除以n余数相同，这两个数相减
t*l
38 楼
其实我觉得这类题的证明很有意思。
这个貌似跟普通娃欧氏平几学到啥程度有一定异曲同工的地方。
这个问题可能不是欧几里德的问题，而是不同类型的 decision problem 的问题。
或者说，图灵说，所有的 problem 最终都归结为 decision problem。但是从不同的
decision problem 出发，这个实际能用的前景，好像也不太一样。当然理论数学物理
可能不关心这个。
：en, n个同余相加，或2个同余相减
：
这个貌似跟普通娃欧氏平几学到啥程度有一定异曲同工的地方。
这个问题可能不是欧几里德的问题，而是不同类型的 decision problem 的问题。
或者说，图灵说，所有的 problem 最终都归结为 decision problem。但是从不同的
decision problem 出发，这个实际能用的前景，好像也不太一样。当然理论数学物理
可能不关心这个。
：en, n个同余相加，或2个同余相减
：
t*l
39 楼
我想了想，我觉得这两个证明可以用来估计 upper bound of search space。所以还是
实用的。
：en, n个同余相加，或2个同余相减
：
实用的。
：en, n个同余相加，或2个同余相减
：
t*l
40 楼
plus 这个似乎能导出 lower upper bound，就是改成遍历所有 0 1，
0
1
10
11
100
101
110
...
总共 n + 1个，必然有两个同余，相减。
：en, n个同余相加，或2个同余相减
：
0
1
10
11
100
101
110
...
总共 n + 1个，必然有两个同余，相减。
：en, n个同余相加，或2个同余相减
：
t*d
41 楼
10进制相减会出8,9什么的
【在 t******l 的大作中提到】
: plus 这个似乎能导出 lower upper bound，就是改成遍历所有 0 1，
: 0
: 1
: 10
: 11
: 100
: 101
: 110
: ...
: 总共 n + 1个，必然有两个同余，相减。
【在 t******l 的大作中提到】
: plus 这个似乎能导出 lower upper bound，就是改成遍历所有 0 1，
: 0
: 1
: 10
: 11
: 100
: 101
: 110
: ...
: 总共 n + 1个，必然有两个同余，相减。
t*l
42 楼
你是对的，只能一个两个都是 1 的相减。
：10进制相减会出8,9什么的
：
：10进制相减会出8,9什么的
：
t*l
43 楼
But I think there is a lower bound, do this way:
First, take all prime 2 and 5 out of the given number.
Then there will be an 111111...111 will be divisible to the new number
(do not have prime 2 or 5). And the length of digit of 1111....1111
won't be more than the given number.
I am not sure the above can be proved wo/ using pigeon hole though.
：10进制相减会出8,9什么的
【在 t******l 的大作中提到】
: 你是对的，只能一个两个都是 1 的相减。
:
: ：10进制相减会出8,9什么的
: ：
First, take all prime 2 and 5 out of the given number.
Then there will be an 111111...111 will be divisible to the new number
(do not have prime 2 or 5). And the length of digit of 1111....1111
won't be more than the given number.
I am not sure the above can be proved wo/ using pigeon hole though.
：10进制相减会出8,9什么的
【在 t******l 的大作中提到】
: 你是对的，只能一个两个都是 1 的相减。
:
: ：10进制相减会出8,9什么的
: ：
t*l
44 楼
我看懂这个了。
不过好像 plus 的证明更强一些，plus 是 bound 在 n+1 位数字，你这个是 bound 在
n^2 位数字。
：任一整数10^k除以n的余数0<=R<n，
：考察n^2个整数10^k, 0<k<n^2,
不过好像 plus 的证明更强一些，plus 是 bound 在 n+1 位数字，你这个是 bound 在
n^2 位数字。
：任一整数10^k除以n的余数0<=R<n，
：考察n^2个整数10^k, 0<k<n^2,
t*l
45 楼
OK I get the strongest generation algorithm based on that.
1st, take all prime 2 and prime 5 from the number, generate
a new number.
Then do this, I use 3 as 1st example:
octave:10> mod(1,3)
ans = 1
octave:11> mod(10,3)
ans = 1
octave:12> mod(100,3)
ans = 1
use combinatroics, get 111, done.
7 will be one next reply.
【在 t******l 的大作中提到】
: But I think there is a lower bound, do this way:
: First, take all prime 2 and 5 out of the given number.
: Then there will be an 111111...111 will be divisible to the new number
: (do not have prime 2 or 5). And the length of digit of 1111....1111
: won't be more than the given number.
: I am not sure the above can be proved wo/ using pigeon hole though.
:
: ：10进制相减会出8,9什么的
1st, take all prime 2 and prime 5 from the number, generate
a new number.
Then do this, I use 3 as 1st example:
octave:10> mod(1,3)
ans = 1
octave:11> mod(10,3)
ans = 1
octave:12> mod(100,3)
ans = 1
use combinatroics, get 111, done.
7 will be one next reply.
【在 t******l 的大作中提到】
: But I think there is a lower bound, do this way:
: First, take all prime 2 and 5 out of the given number.
: Then there will be an 111111...111 will be divisible to the new number
: (do not have prime 2 or 5). And the length of digit of 1111....1111
: won't be more than the given number.
: I am not sure the above can be proved wo/ using pigeon hole though.
:
: ：10进制相减会出8,9什么的
t*l
46 楼
Now this the example for number 7
octave:13> mod(1,7)
ans = 1
octave:14> mod(10,7)
ans = 3
octave:15> mod(100,7)
ans = 2
octave:16> mod(1000,7)
ans = 6
use combinatorics, get 1001, done.
【在 t******l 的大作中提到】
: OK I get the strongest generation algorithm based on that.
: 1st, take all prime 2 and prime 5 from the number, generate
: a new number.
: Then do this, I use 3 as 1st example:
: octave:10> mod(1,3)
: ans = 1
: octave:11> mod(10,3)
: ans = 1
: octave:12> mod(100,3)
: ans = 1
octave:13> mod(1,7)
ans = 1
octave:14> mod(10,7)
ans = 3
octave:15> mod(100,7)
ans = 2
octave:16> mod(1000,7)
ans = 6
use combinatorics, get 1001, done.
【在 t******l 的大作中提到】
: OK I get the strongest generation algorithm based on that.
: 1st, take all prime 2 and prime 5 from the number, generate
: a new number.
: Then do this, I use 3 as 1st example:
: octave:10> mod(1,3)
: ans = 1
: octave:11> mod(10,3)
: ans = 1
: octave:12> mod(100,3)
: ans = 1
t*l
47 楼
Now the example of number 13
octave:18> mod(1, 13)
ans = 1
octave:19> mod(10, 13)
ans = 10
octave:20> mod(100, 13)
ans = 9
octave:21> mod(1000, 13)
ans = 12
so 1001, done
【在 t******l 的大作中提到】
: Now this the example for number 7
: octave:13> mod(1,7)
: ans = 1
: octave:14> mod(10,7)
: ans = 3
: octave:15> mod(100,7)
: ans = 2
: octave:16> mod(1000,7)
: ans = 6
: use combinatorics, get 1001, done.
octave:18> mod(1, 13)
ans = 1
octave:19> mod(10, 13)
ans = 10
octave:20> mod(100, 13)
ans = 9
octave:21> mod(1000, 13)
ans = 12
so 1001, done
【在 t******l 的大作中提到】
: Now this the example for number 7
: octave:13> mod(1,7)
: ans = 1
: octave:14> mod(10,7)
: ans = 3
: octave:15> mod(100,7)
: ans = 2
: octave:16> mod(1000,7)
: ans = 6
: use combinatorics, get 1001, done.
t*l
48 楼
Now the example of number 17
octave:22> mod(1, 17)
ans = 1
octave:23> mod(10, 17)
ans = 10
octave:24> mod(100, 17)
ans = 15
octave:25> mod(1000, 17)
ans = 14
octave:26> mod(10000, 17)
ans = 4
octave:27> mod(100000, 17)
ans = 6
So 100011
【在 t******l 的大作中提到】
: Now the example of number 13
: octave:18> mod(1, 13)
: ans = 1
: octave:19> mod(10, 13)
: ans = 10
: octave:20> mod(100, 13)
: ans = 9
: octave:21> mod(1000, 13)
: ans = 12
: so 1001, done
octave:22> mod(1, 17)
ans = 1
octave:23> mod(10, 17)
ans = 10
octave:24> mod(100, 17)
ans = 15
octave:25> mod(1000, 17)
ans = 14
octave:26> mod(10000, 17)
ans = 4
octave:27> mod(100000, 17)
ans = 6
So 100011
【在 t******l 的大作中提到】
: Now the example of number 13
: octave:18> mod(1, 13)
: ans = 1
: octave:19> mod(10, 13)
: ans = 10
: octave:20> mod(100, 13)
: ans = 9
: octave:21> mod(1000, 13)
: ans = 12
: so 1001, done
t*l
49 楼
In the other hand, as my trials above. What I found is:
Though when apply pigeon hole, your proof seems not as strong
as "plus"'s brilliant "1111...11".
However, it seems your direction is more inline with fundamentals
of number theories / remainder pattern. And if we throw pigeon hole
away, your direction lead to the most optimal solution I think.
So blunt is another side of brilliant? :-)
【在 t*******d 的大作中提到】
: 任一整数10^k除以n的余数0<=R
: 这n个同余数的10^ki (1: 就是一个 n 的整倍数 M (非零),
: M 只由 0 和 1 构成 (十进制).
: 就是一个抽屉原理题
Though when apply pigeon hole, your proof seems not as strong
as "plus"'s brilliant "1111...11".
However, it seems your direction is more inline with fundamentals
of number theories / remainder pattern. And if we throw pigeon hole
away, your direction lead to the most optimal solution I think.
So blunt is another side of brilliant? :-)
【在 t*******d 的大作中提到】
: 任一整数10^k除以n的余数0<=R
: 这n个同余数的10^ki (1: 就是一个 n 的整倍数 M (非零),
: M 只由 0 和 1 构成 (十进制).
: 就是一个抽屉原理题
t*l
50 楼
also higher mod can be computed recursive up to avoid long computation
time, e.g.:
octave:30> mod (10 * mod(10000, 17) , 17)
ans = 6
octave:31> mod(100000, 17)
ans = 6
and can be further optimized.
Also I believe apply theory on top of the "remainder pattern",
it maybe able to derive the upper bound of the computation,
I mean, much lower than pigeon hole gave us.
【在 t******l 的大作中提到】
: Now the example of number 17
: octave:22> mod(1, 17)
: ans = 1
: octave:23> mod(10, 17)
: ans = 10
: octave:24> mod(100, 17)
: ans = 15
: octave:25> mod(1000, 17)
: ans = 14
: octave:26> mod(10000, 17)
time, e.g.:
octave:30> mod (10 * mod(10000, 17) , 17)
ans = 6
octave:31> mod(100000, 17)
ans = 6
and can be further optimized.
Also I believe apply theory on top of the "remainder pattern",
it maybe able to derive the upper bound of the computation,
I mean, much lower than pigeon hole gave us.
【在 t******l 的大作中提到】
: Now the example of number 17
: octave:22> mod(1, 17)
: ans = 1
: octave:23> mod(10, 17)
: ans = 10
: octave:24> mod(100, 17)
: ans = 15
: octave:25> mod(1000, 17)
: ans = 14
: octave:26> mod(10000, 17)
t*d
51 楼
赞，如果把问题改成如何最快找到最小的M？
【在 t******l 的大作中提到】
: In the other hand, as my trials above. What I found is:
: Though when apply pigeon hole, your proof seems not as strong
: as "plus"'s brilliant "1111...11".
: However, it seems your direction is more inline with fundamentals
: of number theories / remainder pattern. And if we throw pigeon hole
: away, your direction lead to the most optimal solution I think.
: So blunt is another side of brilliant? :-)
【在 t******l 的大作中提到】
: In the other hand, as my trials above. What I found is:
: Though when apply pigeon hole, your proof seems not as strong
: as "plus"'s brilliant "1111...11".
: However, it seems your direction is more inline with fundamentals
: of number theories / remainder pattern. And if we throw pigeon hole
: away, your direction lead to the most optimal solution I think.
: So blunt is another side of brilliant? :-)
t*l
52 楼
您水车回帖不看帖嘛，俺不是说了您老的办法适于发展屠龙刀，当然鸽子笼那块可能就
相对不那么重要。
其实这个问题倒是 inverse logic 的例子，如果先搞出被乘数不容易，那试试先搞出
乘积是不是容易点。
：赞，如果把问题改成如何最快找到最小的M？
：
相对不那么重要。
其实这个问题倒是 inverse logic 的例子，如果先搞出被乘数不容易，那试试先搞出
乘积是不是容易点。
：赞，如果把问题改成如何最快找到最小的M？
：
t*d
53 楼
貌似还是45~50楼的思路最快，
再加一个特点：
n-1之内必然出现同余，一旦出现同余就开始循环余数
【在 t******l 的大作中提到】
: 您水车回帖不看帖嘛，俺不是说了您老的办法适于发展屠龙刀，当然鸽子笼那块可能就
: 相对不那么重要。
: 其实这个问题倒是 inverse logic 的例子，如果先搞出被乘数不容易，那试试先搞出
: 乘积是不是容易点。
:
: ：赞，如果把问题改成如何最快找到最小的M？
: ：
再加一个特点：
n-1之内必然出现同余，一旦出现同余就开始循环余数
【在 t******l 的大作中提到】
: 您水车回帖不看帖嘛，俺不是说了您老的办法适于发展屠龙刀，当然鸽子笼那块可能就
: 相对不那么重要。
: 其实这个问题倒是 inverse logic 的例子，如果先搞出被乘数不容易，那试试先搞出
: 乘积是不是容易点。
:
: ：赞，如果把问题改成如何最快找到最小的M？
: ：
t*l
54 楼
另外我觉得立志做马工的，和立志做数学工作者的，这个对 decision problem 是不是
往 “欧几里德捉迷藏辅助线” 和 抽屉啥的 方向狠搞，我觉得也还是要看娃个性和将
来方向。
对于小马工而言，我觉得学 decision problem 最终可能还得让图灵机 work out
problem。所以对于目测范围内只能回答 does it exist 的 decision problem，可能
还是等基本的学完再说不迟。当然题一样可以是大致差不多的问题，侧重点可以有所不
同。俺目前的看法。
：赞，如果把问题改成如何最快找到最小的M？
：
往 “欧几里德捉迷藏辅助线” 和 抽屉啥的 方向狠搞，我觉得也还是要看娃个性和将
来方向。
对于小马工而言，我觉得学 decision problem 最终可能还得让图灵机 work out
problem。所以对于目测范围内只能回答 does it exist 的 decision problem，可能
还是等基本的学完再说不迟。当然题一样可以是大致差不多的问题，侧重点可以有所不
同。俺目前的看法。
：赞，如果把问题改成如何最快找到最小的M？
：
t*d
55 楼
如果从比n高一位挨个算101, 111, 1001, 1011, 1101, 1111....
一般会更慢，也许机算有可能比45~50楼的思路更快？
【在 t*******d 的大作中提到】
: 貌似还是45~50楼的思路最快，
: 再加一个特点：
: n-1之内必然出现同余，一旦出现同余就开始循环余数
一般会更慢，也许机算有可能比45~50楼的思路更快？
【在 t*******d 的大作中提到】
: 貌似还是45~50楼的思路最快，
: 再加一个特点：
: n-1之内必然出现同余，一旦出现同余就开始循环余数
t*l
56 楼
属实，同余循环看起来能证明计算时间保证封顶，以及何时封顶。
当然这是你们数学家的事儿。我们马工不证明的出货了，手册上备注一下如果三天出不
来，按 ctrl-C 即可。
：貌似还是45~50楼的思路最快，
：再加一个特点：
当然这是你们数学家的事儿。我们马工不证明的出货了，手册上备注一下如果三天出不
来，按 ctrl-C 即可。
：貌似还是45~50楼的思路最快，
：再加一个特点：
t*l
57 楼
肉算慢的话，电算一般也不会快。
而且电算一般尽可能 recursive up，v1.0 慢点，v2.0 可以不改算法框架，尽可能利
用 recursive up 的 partial result 来加速。
：如果从比n高一位挨个算101, 111, 1001, 1011, 1101, 1111
：一般会更慢，也许机算有可能比45~50楼的思路更快？
而且电算一般尽可能 recursive up，v1.0 慢点，v2.0 可以不改算法框架，尽可能利
用 recursive up 的 partial result 来加速。
：如果从比n高一位挨个算101, 111, 1001, 1011, 1101, 1111
：一般会更慢，也许机算有可能比45~50楼的思路更快？
t*l
58 楼
不过另一方面，你说的也是，这两玩意儿其实都是穷举法，只不过其中一个是
recursive 穷举法，更大限度利用 partial results 而已。但 Big O 其实还是一样的。
不过这有可能是抽屉原理，或者欧几里德捉迷藏辅助线的 nature：It is a decision
problem, but by nature it is not, and cannot convert to the decision of "
;search direction"。而这也可能就是牛顿比欧几里德牛鼻的地方。
：如果从比n高一位挨个算101, 111, 1001, 1011, 1101, 1111....
：一般会更慢，也许机算有可能比45~50楼的思路更快？
recursive 穷举法，更大限度利用 partial results 而已。但 Big O 其实还是一样的。
不过这有可能是抽屉原理，或者欧几里德捉迷藏辅助线的 nature：It is a decision
problem, but by nature it is not, and cannot convert to the decision of "
;search direction"。而这也可能就是牛顿比欧几里德牛鼻的地方。
：如果从比n高一位挨个算101, 111, 1001, 1011, 1101, 1111....
：一般会更慢，也许机算有可能比45~50楼的思路更快？
t*l
59 楼
或者这么说，it is a decision problem, but unable to help the "decision
of direction" problem。
：不过另一方面，你说的也是，这两玩意儿其实都是穷举法，只不过其中一个是
：recursive 穷举法，更大限度利用 partial results 而已。但 Big O 其实还是一样
的。
of direction" problem。
：不过另一方面，你说的也是，这两玩意儿其实都是穷举法，只不过其中一个是
：recursive 穷举法，更大限度利用 partial results 而已。但 Big O 其实还是一样
的。
t*d
60 楼
属实，数大的时候recursive 穷举法优势会比较明显
的。
decision
【在 t******l 的大作中提到】
: 不过另一方面，你说的也是，这两玩意儿其实都是穷举法，只不过其中一个是
: recursive 穷举法，更大限度利用 partial results 而已。但 Big O 其实还是一样的。
: 不过这有可能是抽屉原理，或者欧几里德捉迷藏辅助线的 nature：It is a decision
: problem, but by nature it is not, and cannot convert to the decision of "
: ;search direction"。而这也可能就是牛顿比欧几里德牛鼻的地方。
:
: ：如果从比n高一位挨个算101, 111, 1001, 1011, 1101, 1111....
: ：一般会更慢，也许机算有可能比45~50楼的思路更快？
的。
decision
【在 t******l 的大作中提到】
: 不过另一方面，你说的也是，这两玩意儿其实都是穷举法，只不过其中一个是
: recursive 穷举法，更大限度利用 partial results 而已。但 Big O 其实还是一样的。
: 不过这有可能是抽屉原理，或者欧几里德捉迷藏辅助线的 nature：It is a decision
: problem, but by nature it is not, and cannot convert to the decision of "
: ;search direction"。而这也可能就是牛顿比欧几里德牛鼻的地方。
:
: ：如果从比n高一位挨个算101, 111, 1001, 1011, 1101, 1111....
: ：一般会更慢，也许机算有可能比45~50楼的思路更快？
x*1
61 楼
啥意思？另类高大上。
【在 t******l 的大作中提到】
: OK I get the strongest generation algorithm based on that.
: 1st, take all prime 2 and prime 5 from the number, generate
: a new number.
: Then do this, I use 3 as 1st example:
: octave:10> mod(1,3)
: ans = 1
: octave:11> mod(10,3)
: ans = 1
: octave:12> mod(100,3)
: ans = 1
【在 t******l 的大作中提到】
: OK I get the strongest generation algorithm based on that.
: 1st, take all prime 2 and prime 5 from the number, generate
: a new number.
: Then do this, I use 3 as 1st example:
: octave:10> mod(1,3)
: ans = 1
: octave:11> mod(10,3)
: ans = 1
: octave:12> mod(100,3)
: ans = 1
t*d
62 楼
如何最快找到最小的M
【在 x***1 的大作中提到】
: 啥意思？另类高大上。
【在 x***1 的大作中提到】
: 啥意思？另类高大上。
x*1
63 楼
谢谢。
【在 t*******d 的大作中提到】
: 如何最快找到最小的M
【在 t*******d 的大作中提到】
: 如何最快找到最小的M
c*x
64 楼
赞算法，赞通解。
【在 t******l 的大作中提到】
: OK I get the strongest generation algorithm based on that.
: 1st, take all prime 2 and prime 5 from the number, generate
: a new number.
: Then do this, I use 3 as 1st example:
: octave:10> mod(1,3)
: ans = 1
: octave:11> mod(10,3)
: ans = 1
: octave:12> mod(100,3)
: ans = 1
相关阅读
出售家电用品，欢迎选购，不买也可以进来看看西温莎的小孩真有那么苦？8个月的准妈妈，请大家给推荐一款比较经济实惠的美国产宝宝奶粉呗？！请问米国顶级私校应该关注亚裔移民二代、三代的轨迹人往高处走，水往低处流有一位强势的母亲到底是好是坏？Kolpavok 请进，，3岁男孩特别爱登台演唱该如何帮他发展这方面的才能。老婆可以换，父母不可以换求购Kawai k500 Invoice反对同质化竞争都是放屁Re: San Jose半马 (转载)发个可爱的宝宝video孕前必做的那些事儿你做到了吗？育儿的一种方法求评理，让孩子学会独立处理问题有错吗？有儿才方知父母苦如果将来有一天我的两个孩子成精英了2岁宝宝PPD test阳性， 抽血阴性，医生让吃九个月的药