Euler Project 挨个做- 之二 (Q51-Q78)

tree_new_bee

原帖由 〇〇 于 2011-1-9 21:06 发表
tnb真强，一天做那么多题。

前几道都有以前的题为基础， 很容易做。
只有最后一道是有难度的。

tree_new_bee

原帖由 tree_new_bee 于 2011-1-9 20:45 发表
Executed in 94.109 seconds

很幸运， 8319823这个结果是正确答案

既然上面分析了，两个质数应该尽可能接近， 并且尽可能大， 因此我们可以再做出一些假设：
SQRT(10^7) ~= 3162
因此，我们假设两个数的最小值为1000， 相应的另一个数则不超过10000.

把开始的质数表部分替换成：
with tp as (select column_value p from table(pkg_prim2.seive_numlist_nk(1E5)) where column_value>1000)

这样计算的时间可以大大缩小：

        P1         P2          N        PHI      RATIO
---------- ---------- ---------- ---------- ----------
      3557       2339    8319823    8313928 1.00070905

Executed in 5.625 seconds

tree_new_bee

更进一步的简化是： 直接从与sqrt(10^7)最接近的数开始找， 找到第一个就返回：
declare
  pl1 t_numlist;
  pl2 t_numlist;
   
j integer;
n integer;
phi integer;
begin
  pl1 := pkg_prim2.seive_numlist_nk(sqrt(1E7));
  pl2 := pkg_prim2.seive_numlist_nk(1e4);

  for i in reverse pl1.first .. pl1.last loop
    j:= pl1.last+1;
    while  j<pl2.last and pl1(i)*pl2(j)< 1E7 loop
        n:= pl1(i)*pl2(j);
        phi := (pl1(i)-1)*(pl2(j)-1);
       if TRANSLATE(n,'0123456789','0')||
       TRANSLATE(n,'1023456789','1')||
       TRANSLATE(n,'2013456789','2')||
       TRANSLATE(n,'3012456789','3')||
       TRANSLATE(n,'4012356789','4')||
       TRANSLATE(n,'5012346789','5')||
       TRANSLATE(n,'6012345789','6')||
       TRANSLATE(n,'7012345689','7')||
       TRANSLATE(n,'8012345679','8')||
       TRANSLATE(n,'9012345678','9')
       =
       TRANSLATE(phi,'0123456789','0')||
       TRANSLATE(phi,'1023456789','1')||
       TRANSLATE(phi,'2013456789','2')||
       TRANSLATE(phi,'3012456789','3')||
       TRANSLATE(phi,'4012356789','4')||
       TRANSLATE(phi,'5012346789','5')||
       TRANSLATE(phi,'6012345789','6')||
       TRANSLATE(phi,'7012345689','7')||
       TRANSLATE(phi,'8012345679','8')||
       TRANSLATE(phi,'9012345678','9')
       then
           dbms_output.put_line('n1:' ||pl1(i) || ' n2:' || pl2(j)|| ' n: ' || n || '  phi: ' ||  phi || ' n/phi:' || (n/phi));
           return;
        end if;
     j:=j+1;
     end loop;   
  end loop;
end;

n1:2339 n2:3557 n: 8319823  phi: 8313928 n/phi:1.00070905112481128054031740472133027854

PL/SQL procedure successfully completed

Executed in 1.047 seconds


这样快是很快， 可是有点撞大运的感觉， 虽说碰巧得到了正确答案， 但实际上循环过程中，极有可能先碰到一个i*j比较小的数符合条件。

既满足乘积最接近10^7, 又让两个数尽可能接近SQRT(10^7), 想不出什么更好的办法控制这个扩散的过程。

tree_new_bee

Q71 Listing reduced proper fractions in ascending order of size.

Consider the fraction, n/d, where n and d are positive integers. If n<d and HCF(n,d)=1, it is called a reduced proper fraction.

If we list the set of reduced proper fractions for d ≤ 8 in ascending order of size, we get:

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8

It can be seen that 2/5 is the fraction immediately to the left of 3/7.

By listing the set of reduced proper fractions for d ≤ 1,000,000 in ascending order of size, find the numerator of the fraction immediately to the left of 3/7.

tree_new_bee

这个题， 很容易做。 但要证明做法的正确性不容易。

在分母小于7的数里，2/5是最接近3/7的分数， 那么要继续逼近3/7, 只要在分子和分母同时不断的加入3和7就可以无限逼近3/7. 即5/12, 8/19, 11/26,....


with t as (select floor((1e6-5)/7) x  from dual )
,t1 as (select x, 2+3*x n, 5+7*x d, (2+3*x )/( 5+7*x ) m  from t)
select * from t1

         X          N          D          M
---------- ---------- ---------- ----------
    142856     428570     999997 0.42857128

Executed in 0.109 seconds


语句超级简单， 但要证明结果的正确性， 需要证明以下几点：
以下均设定x>0
假设1: (2+3x)/(5+7x) 介于2/5和3/7之间
假设2: 当x越大时， (2+3x)/(5+7x)越逼近3/7, 也就是说 对于y=x+1,  (2+3y)/(5+7y) > (2+3x)/(5+7x)
假设3: 上面的语句中没有考虑最大公约数的问题， 实际上是因为(2+3x)与(5+7x)是互质的， 这点也要证明。
假设4:  (2+3x)/(5+7x) 是当前范围内最逼近3/7的数， 也就是说不存在分母小于(5+7x) 的分数， 介于(2+3x)/(5+7x) 与3/7之间。

假设4我不会证明， 其它几点证明如下：

假设1：
因为2/5< 3/7
所以：
(2+3x)/(5+7x) = 1/5 * (10+15x) /(5+7x)>  1/5* (10+14x)/(5+7x) = 2/5
(2+3x)/(5+7x) = 1/7 * (14+21x)/(5+7x) < 1/7 * (15+21x)/(5+7x) = 3/7

假设2：
设y=x+1, 则
(2+3y)/(5+7y) = (2+3(x+1))/(5+7(x+1))  =  (5+3x)/(12+7x)

(5+3x)/(12+7x) ??  (2+3x)/(5+7x)
<==> (5+3x)(5+7x) ?? (2+3x)*(12+7x)
<==> 21xx + 50x + 25 ?? 21xx+50x + 24
<==>21xx + 50x + 25 > 21xx+50x + 24
因为x>1, 所以上面三个不等式符号一致， 因此(2+3y)/(5+7y) >  (2+3x)/(5+7x)


假设3：
对于(2+3x)/(5+7x)
假设有大于1的公因子f, f>1则可以设： 2+3x = k1*f,  (5+7x) = k2*f,   其中k1,k2都是正整数
两式可分别得出 x= (k1*f-2)/3 和x=(k2*f-5)/7
所以：   (k1*f-2)/3  = (k2*f-5)/7
=> 7k1f - 14 = 3k2f - 15
(3k2-7k1)f = 1
f= 1/(3k2-7k1)

因为k1,k2都是正整数， 所以1/(3k2-7k1)不可能是大于1的正整数。

因此， (2+3x)与(5+7x)互质

[ 本帖最后由 tree_new_bee 于 2011-1-10 00:29 编辑 ]

〇〇

71我的解法
http://www.itpub.net/thread-1364272-3-2.html

tree_new_bee

原帖由 〇〇 于 2011-1-10 06:03 发表
71我的解法
http://www.itpub.net/thread-1364272-3-2.html

newkid

第4点穷尽法：

设  428570/999997 <a/b < 3/7

   428570*b/999997 <a <3*b/7

对b循环1-999996:
SELECT *
  FROM (SELECT ROWNUM*428570/999997 low,ROWNUM*3/7 high FROM DUAL CONNECT BY ROWNUM<999997
       )
WHERE CEIL(low)+CASE WHEN CEIL(low)=low THEN 1 ELSE 0 END<=TRUNC(high) - CASE WHEN TRUNC(high) =high THEN 1 ELSE 0 END;

no rows selected

OO的方法说明什么？428571/999999=3/7

tree_new_bee

原帖由 newkid 于 2011-1-10 09:58 发表
第4点穷尽法：

穷尽法只能证实1000000以内这样的结果是正确的， 不能证明推广到任意数做法都是正确的。

对假设4可以用归纳法证明：
证明：(2+3x)/(5+7x) 是当前范围内最逼近3/7的数， 也就是说不存在分母小于(5+7x) 的分数， 介于(2+3x)/(5+7x) 与3/7之间。
显然： x=1时 (2+3x)/(5+7x) = 5/12 就是 分母在12内的最逼近3/7的数。

假设 n=x-1时结论正确， 即不存在a/b, b<5+7(x-1), 使得(2+3(x-1))/(5+7(x-1)) < a/b < 3/7
因此， b的取值范围只能是：
可能的分母:  7x-2, 7x-1, 7x, 7x+1, 7x+2, 7x+3, 7x+4, 7x+5
相应的a可能的取值范围是(这之外的已经显然不符合条件了)： 3x-1, 3x, 3x+1,3x+2

虽说繁琐， 但以上的所有组合，都可以分别证明，要么 a/b = 3/7, 要们a/b > 3/7, 要么 a/b < (2+3x)/(5+7x)

这样问题就算得到证明了。

tree_new_bee

Q72 How many elements would be contained in the set of reduced proper fractions for d ≤ 1,000,000?

Consider the fraction, n/d, where n and d are positive integers. If n<d and HCF(n,d)=1, it is called a reduced proper fraction.

If we list the set of reduced proper fractions for d ≤ 8 in ascending order of size, we get:

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8

It can be seen that there are 21 elements in this set.

How many elements would be contained in the set of reduced proper fractions for d ≤ 1,000,000?