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

tree_new_bee

72，猛一看题目，以为是71的延续。
实际一看， 与71基本不相干。

说是找简化的真分数， 其实就是找小于一个数的互质的数的数目， 也就是69/70题里面的φ(n)
所以这道题是69/70的延续。

69耍花招，根本没计算φ，  70偷了点懒， 只计算了一小部分φ(n)。
这道题是玩不了花活了， 只能老老实实去逐个计算了。

为了避免对每个数进行质因数分解， 我用了类似筛法找质数的方法， 先生成所有质数的幂的列表， 然后对它们进行相乘。
对于多个乘法对应一个数的情况， 例如： 8即可看作一个8， 也可看作2*4
从phi(p^k)=(p-1)*p^(k-1), 可以看出，单个大幂次的数计算的结果总是大于拆成两部分后的计算结果， 因此我们只要去较大值就行。


循环只用了7层， 是因为在69题中已经看到：1000000以内的数最长的质数连乘，是2*...*17, 也就是只有7个数。


-- Created on 2011-1-10 by TNB
declare
  maxnum integer :=1000000;
  pl pkg_prim2.tprimtable;
  p integer;
  k integer;  
  nl1 pkg_prim2.tprimtable;
  nl2 pkg_prim2.tprimtable;
  sm integer;
  a integer;
  b integer;
  c integer;
  d integer;
  e integer;
  f integer;
  g integer;
  
begin
  pl:= pkg_prim2.seive_indextable(maxnum);

  p:=pl.first;
  while p is not null loop
    for k in 1 .. floor(log(p, maxnum)) loop
        nl1(power(p,k)) := (p-1)*power(p, k-1);         
    end loop;
    p := pl.next(p);
  end loop;
  nl1(1):=1;
  --dbms_output.put_line('nl1.count:' || nl1.count);
  a:=nl1.first;
  while a is not null loop
    b:=nl1.first;
    while b<a and a*b<=maxnum loop
      c:=nl1.first;
      while (c<b or (c=b and  b=1)) and a*b*c<=maxnum loop
        d:=nl1.first;
        while (d<c or (d=c and  c=1)) and a*b*c*d <=maxnum loop
          e:=nl1.first;
          while (e<d or (e=d and  d=1)) and a*b*c*d*e <=maxnum loop
            f:=nl1.first;
            while (f<e or (f=e and  e=1)) and a*b*c*d*e*f <=maxnum loop
              g:=nl1.first;
              while (g<f or (g=f and  f=1)) and a*b*c*d*e*f*g <=maxnum loop
                    if nl2.exists(a*b*c*d*e*f*g) then
                      nl2(a*b*c*d*e*f*g) := greatest(nl2(a*b*c*d*e*f*g), nl1(a)*nl1(b)*nl1(c)*nl1(d)*nl1(e)*nl1(f)*nl1(g));
                    else
                      nl2(a*b*c*d*e*f*g):=nl1(a)*nl1(b)*nl1(c)*nl1(d)*nl1(e)*nl1(f)*nl1(g);
                    end if;
                g:=nl1.next(g);   
              end loop;
              f:=nl1.next(f);   
            end loop;
            e:=nl1.next(e);   
          end loop;
          d:=nl1.next(d);   
        end loop;
        c:=nl1.next(c);   
      end loop;
      b:=nl1.next(b);   
    end loop;
    a:=nl1.next(a);   
  end loop;
                           
  sm:=0;
  for i in 2..maxnum loop
   sm := sm+nl2(i);
   --dbms_output.put_line(i || ': ' || nl2(i));
  end loop;
  dbms_output.put_line('sum:' || sm);
end;


sum:303963552391

PL/SQL procedure successfully completed

Executed in 13.812 seconds

性能还不错。 不像想象中的那么恐怖。

newkid

又得质因数分解？“牛肉优化器”隆隆启动吧！

newkid

呵呵，我还没写完你都竣工了。

tree_new_bee

与上面算法基本等价的sql:

with t as (select column_value p from table(pkg_prim2.seive_numlist_nk(100000)))
,tpower as (select /*+ MATERIALIZE */ p, k, power(p,k) n, (p-1)*power(p,k-1) phi from t, (select rownum k from dual connect by rownum<=log(2,100000))
where power(p,k) <= 100000
union select 1,1,1,1 from dual)
,t2 as (select
t1.n n1, t2.n n2, t3.n n3, t4.n n4, t5.n n5, t6.n n6, t7.n n7,
t1.n*t2.n*t3.n*t4.n*t5.n*t6.n*t7.n n, t1.phi*t2.phi*t3.phi*t4.phi*t5.phi*t6.phi*t7.phi phi
from tpower t1, tpower t2, tpower t3,tpower t4, tpower t5, tpower t6, tpower t7
where t1.n>t2.n  
and t2.n<=100000/t1.n
and t3.n<=100000/(t1.n*t2.n)
and t4.n<=100000/(t1.n*t2.n*t3.n)
and t5.n<=100000/(t1.n*t2.n*t3.n*t4.n)
and t6.n<=100000/(t1.n*t2.n*t3.n*t4.n*t5.n)
and t7.n<=100000/(t1.n*t2.n*t3.n*t4.n*t5.n*t6.n)
and (t2.n>t3.n or (t2.n=1 and t3.n=1))
and (t3.n>t4.n or (t3.n=1 and t4.n=1))
and (t4.n>t5.n or (t4.n=1 and t5.n=1))
and (t5.n>t6.n or (t5.n=1 and t6.n=1))
and (t6.n>t7.n or (t6.n=1 and t7.n=1))
)
,t3 as (select n, max(phi) phi from t2 group by n)
--select * from t3
select count(*), sum(phi) from t3

  COUNT(*)   SUM(PHI)
---------- ----------
     99999 3039650753

Executed in 57.188 seconds

从算法上看不出与上面的plsql有什么区别， 但这个计算到100000就要近1分钟了， 不知问题出在哪儿。

tree_new_bee

原帖由 newkid 于 2011-1-10 23:23 发表
呵呵，我还没写完你都竣工了。

呵呵， 我是先做好了， 才往上抄的题目。

tree_new_bee

一个最初写出的比较精巧， 但很低效的版本， 扔掉可惜， 放到这里做个归档。

-- Created on 2011-1-10 by ADMINISTRATOR
declare
  maxnum integer :=100000;
  pl pkg_prim2.tprimtable;
  p integer;
  k integer;  
  nl1 pkg_prim2.tprimtable; -- 保存质数幂次列表
  nl2 pkg_prim2.tprimtable; -- 需要与nl1交叉相乘的数的列表
  nlnew pkg_prim2.tprimtable; -- 每次相乘后新增加的数的列表
  nlfinal pkg_prim2.tprimtable; -- 全部数的列表
  sm integer;
  halfmaxnum integer;
begin
  pl:= pkg_prim2.seive_indextable(maxnum);

  halfmaxnum:=0;
  p:=pl.first;
  while p is not null loop
    for k in 1 .. floor(log(p, maxnum)) loop
        nl1(power(p,k)) := (p-1)*power(p, k-1);         
        if power(p,k) <= maxnum/2 and power(p,k)>halfmaxnum
          then halfmaxnum := power(p,k);
        end if;         
    end loop;
    p := pl.next(p);
  end loop;
  dbms_output.put_line('nl1.count:' || nl1.count);

  nl2:=nl1;
  nlfinal:=nl1;
  for i in 1..6 loop  -- maxnum内最多可以有多少个质数相乘, -1。
    if i>1 then
      nl2:=nlnew;
      nlnew.delete;
    end if;
    p:= case when i=1 then halfmaxnum else nl2.last end;
    while  p is not null loop
      k := case when i=1 then nl1.prior(p) else halfmaxnum end;
      while k is not null loop
        if  p*k<=maxnum and not nlfinal.exists(p*k) then
          nlnew(p*k) := nl2(p)*nl1(k);
          nlfinal(p*k) := nlnew(p*k);
        end if;
        k := nl1.prior(k);
      end loop;
      p:=nl2.prior(p);
    end loop;
  end loop;
  sm:=0;
  for i in 2..maxnum loop
   sm := sm+nlfinal(i);
   --dbms_output.put_line(i || ': ' || nlfinal(i));
  end loop;
  dbms_output.put_line('sum:' || sm);
end;


这个比上面的SQL还要慢， 计算5万要80秒。


问题在于， 算出乘法后，丢掉了乘数的信息， 使得后续的乘数进行循环时，没有好的手段限制循环次数。

tree_new_bee

Q73 How many fractions lie between 1/3 and 1/2 in a sorted set of reduced proper fractions?

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 3 fractions between 1/3 and 1/2.

How many fractions lie between 1/3 and 1/2 in the sorted set of reduced proper fractions for d ≤ 12,000?


前几道题做完了， 这道题无论是思路还是计算量都显得不太难了。

唯一不同之处是， 之前的几道题都只要计算互质的数的数目而已， 这道题因为限定了取值范围， 所以必须找到那些具体的互质的数。

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

tree_new_bee

简单的SQL, 直接调用自定义的GCD函数:

with t as (select rownum n from dual connect by rownum<=12000)
,t1 as (select  tn.n n, td.n d , tn.n/td.n frac from (select * from t where n<=6000) tn, t td
where  3*tn.n>td.n and 2*tn.n < td.n and not (tn.n>1 and mod(td.n, tn.n)=0)
and pkg_prim2.gcd(td.n, tn.n) =1
)
select count(*) from t1


  COUNT(*)
----------
   7295372

Executed in 216.609 seconds

SQL>

能用， 但很慢。

tree_new_bee

改成plsql, 能稍快些， 但快不到哪里去。

-- Created on 2011-1-11 by TNB
declare
  maxnum integer :=12000;
  pl pkg_prim2.tprimtable;
  sm integer:=0;
begin
  pl := pkg_prim2.seive_indextable_nk(maxnum);
  
  for i in 5 .. maxnum loop
      if pl.exists(i) then
        sm:= sm + floor(i/2-0.001) - ceil(i/3+0.001)+1;
      else
        for j in ceil(i/3+0.001) .. floor(i/2-0.001) loop
          if pl.exists(j) and mod(i,j)>0 then
            sm:=sm+1;
          else
           if pkg_prim2.gcd(i,j) = 1 then sm:=sm+1; end if;
          end if;  
        end loop;
      end if;
    end loop;
    dbms_output.put_line('total: '||sm);
end;

total: 7295372

PL/SQL procedure successfully completed

Executed in 84.656 seconds

估计要想高效率，还得是用什么数学方法才行。

tree_new_bee

在对连续数范围内进行计算时， 筛法真是个好东西。


-- Created on 2011-1-11 by TNB
declare
  i integer;
  j integer;
  maxnum integer :=12000;
  sm integer:=0;
  type typen1 is table of boolean index by pls_integer;
  type typen2 is table of typen1 index by pls_integer;
  frac typen2;
begin
  
  for i in 5 .. maxnum loop
    for j in ceil(i/3+0.001) .. floor(i/2-0.001) loop
        frac(i)(j) := true;
    end loop;
  end loop;
  i:=frac.first;
  while i<=maxnum/2 and i is not null loop
    j:=frac(i).first;
    while j is not null loop
      for k in 2..maxnum/i loop
        if frac.exists(i*k) then frac(i*k).delete(j*k); end if;
      end loop;
      j:=frac(i).next(j);
    end loop;
    i:=frac.next(i);
  end loop;
  sm:=0;
  i:=frac.first;
  while i is not null loop
    sm:=sm+frac(i).count;
    i:=frac.next(i);
  end loop;
  dbms_output.put_line('total: '||sm);
end;

total: 7295372

PL/SQL procedure successfully completed

Executed in 8.218 seconds

因为回避了大量的gcd和mod操作, 这个效率高多了。

[ 本帖最后由 tree_new_bee 于 2011-1-11 18:15 编辑 ]