其实我觉得这类题的证明很有意思。 这个貌似跟普通娃欧氏平几学到啥程度有一定异曲同工的地方。 这个问题可能不是欧几里德的问题,而是不同类型的 decision problem 的问题。 或者说,图灵说,所有的 problem 最终都归结为 decision problem。但是从不同的 decision problem 出发,这个实际能用的前景,好像也不太一样。当然理论数学物理 可能不关心这个。
:en, n个同余相加,或2个同余相减 :
t*l
39 楼
我想了想,我觉得这两个证明可以用来估计 upper bound of search space。所以还是 实用的。
:en, n个同余相加,或2个同余相减 :
t*l
40 楼
plus 这个似乎能导出 lower upper bound,就是改成遍历所有 0 1, 0 1 10 11 100 101 110 ... 总共 n + 1个,必然有两个同余,相减。
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.
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什么的
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
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.
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
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^2个整数10^k, 0: 必然存在n个同余数的10^k, : 这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)
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? :-)
另外我觉得立志做马工的,和立志做数学工作者的,这个对 decision problem 是不是 往 “欧几里德捉迷藏辅助线” 和 抽屉啥的 方向狠搞,我觉得也还是要看娃个性和将 来方向。 对于小马工而言,我觉得学 decision problem 最终可能还得让图灵机 work out problem。所以对于目测范围内只能回答 does it exist 的 decision problem,可能 还是等基本的学完再说不迟。当然题一样可以是大致差不多的问题,侧重点可以有所不 同。俺目前的看法。
不过另一方面,你说的也是,这两玩意儿其实都是穷举法,只不过其中一个是 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"。而这也可能就是牛顿比欧几里德牛鼻的地方。
或者这么说,it is a decision problem, but unable to help the "decision 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楼的思路更快?
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*d
62 楼
如何最快找到最小的M
【在 x***1 的大作中提到】 : 啥意思?另类高大上。
x*1
63 楼
谢谢。
【在 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