三人同行七十稀
Tuesday October 24, 2006 by Jimmy.Lin
前阵子解答Frank的质数问题 。今晚突然想起了一个有意思的问题。
给你一个105之内的数，把除以3，5，7的余数告诉我，我可以算出这个是什么数 。
这个问题在我很小的时候，我伯父教过我的一首歌曲：
三人同行七十稀，
五树梅花廿一枝，
七子共党中秋月，
除百零五便得知。
几年过去了。还深深的印在在脑中。特别是那个廿一枝，当时我伯父还问我这个字怎么念来着。 我的一个兄弟不认识，我认识，那时候狂喜。今天到网上一找，发现跟网络版本有点差别，古人【明朝数学家程大位在他著的《算法统宗》（1593年）】是如下说法，不过差不多的拉，我伯父的版本似乎更顺口：
三人同行七十稀，
五树梅花廿一枝，
七子团圆月正半，
除百零五便得知。
我来解说一下我伯父的版本好了。
除数是3时，乘以70，
除数是5时，乘以21，
除数时7时，乘以15，
然后除以105，余数就是答案。
本质问题分析：
70是5与7的倍数，而用3除余1；
21是3与7的倍数，而用5除余1；
15是3与5的倍数，而用7除余1。
实际例子分析：
如果一个数除以3余1，除以5余4，除以7余5。
求这个最小数。
我们如果不用公式，按照正常的逻辑来解。
除以3余1，则数为3m ＋1（m为自然数）
除以5余4，把m的值代入
m ＝ 1 时，值4，正解
那么，能被3，5除的肯定有如下特征：
4 ＋ 3*5*p
现在我们要一个数除以7余5，设为7n ＋ 5
所以7n + 5 = 4 + 15p
7n + 1 = 15p
很显然最小数当然是p＝ 1，次数为19。
如果用公式则是：
70 * 1 ＋ 21 * 4 + 15 * 5 = 2 * 105 + 19
right ?
下面是信手抓来的plsql
??DECLARE
v_num NUMBER;
BEGIN
FOR i IN 1..105 LOOP
IF mod(i,3)=1 AND MOD = 4 AND MOD = 6 THEN
dbms_output.put_line(i);
END IF;
END LOOP;
EXCEPTION
WHEN OTHERS THEN
dbms_output.put_line(‘error’
|| SQLCODE
|| SQLERRM);
END; ??
其实我们可以拓展到互质的三数。
希望大家喜欢。
好累啊。要睡觉了。^_^