Euler Project 挨个做 - 之一(Q1-50)

tree_new_bee

今天一下子做了4道题， 虽说都不难， 歇一歇。
恰逢上个帖子是100楼， 庆贺一下。

lastwinner

NB真不是吹的，楼主太厉害了！

tree_new_bee

原帖由 lastwinner 于 2010-12-17 14:32 发表
NB真不是吹的，楼主太厉害了！

好多题的做法还有很大的改进余地， 大家一起努力把。

durexlollipop

nb

tree_new_bee

每次做完一道题， 都很希望能看到题目后面能有euler给出的文档。 每次看后都能有进一步的收获。
不过可惜的是很多题目都没有文档(也许是太简单了)

这次，文档中给出了通过一个数的质因数分解， 来得到因数和的方法。
在文档中只列出了代码， 具体的推导方法给出了链接： http://mathschallenge.net/index. ... ber/sum_of_divisors

简单的说，结论就是：
如果一个数的质因数分解是p^a，
则他的因数和(包括自身在内)是：  (p^(a+1) - 1)/(p-1)

根据相乘性 σ(a×b×...)=σ(a)×σ(b)×...：
对于质因数分解p^a * q^b *....
则他的因数和(包括自身在内)是： (p^(a+1) - 1)/(p-1)   * (q^(b+1) -1) /(q-1) * .....


链接中没有对可乘性进行证明，我来把这个证明补充一下：
设S=A*B,  A= p^m,  B=q^n, pq互质
则A的因数为：  1, p, p^2,.. ,p^m
B的因数为：     1, q, q^2,... , q^n
S的因数为：   1, p, p^2,.. ,p^m,  q, q^2,... , q^n, p*(q, q^2,.... q^n), p^2 * (q, q^2,... q^m) + .... P^m(q, q^2,...q^n)
因为pq互质, 所以上面的除1以外的所有因数都互不相等，
所以S的因数和
σ(S) = 1 + (σ(A)-1) + (σ(B)-1) + p*(σ(B)-1) + p^2* (σ(B)-1) + p^m* (σ(B)-1)
       = 1+  (σ(A)-1) + (1+p+p^2+... +P^n) * (σ(B)-1)
       = 1+  (σ(A)-1) +  (σ(A) * (σ(B)-1)
       = σ(A) + σ(A) * (σ(B)-1) = σ(A) * σ(B)

[ 本帖最后由 tree_new_bee 于 2010-12-17 22:55 编辑 ]

newkid

94楼的解法很巧妙，为NB哥喝彩！

tree_new_bee

Q21 根据提示改写后的plsql代码:
declare
  sm number;
  type tnumlist is table of number index by pls_integer;
  numlist tnumlist;
  
j number;
icopy number;
step number;
cnt number;
begin
  for i in 1..10000 loop
        cnt := 0;
        sm := 1;
        if bitand(i,1)= 0 then step:=1; else step:=2; end if; --奇数的质因子中不会有偶数，可以跳过偶数
        icopy := i;
        j := 2;
        while j*j<=icopy loop
            while  j<=icopy and mod(icopy,j) = 0 loop
               icopy := icopy/j;
               cnt:=cnt+1;
            end loop;
           if cnt>0 then sm := sm * (power(j,cnt+1)-1)/(j-1); end if;
           cnt:=0;
           if j=2 then j:=j+1; else j:=j+step; end if;
        end loop;
        if icopy>1 then sm:=sm*(icopy+1); end if;  --icopy+1 == (icopy^2-1)/(icopy-1)
        numlist(i) := sm-i;
  end loop;
  
   sm := 0;
  for i in 1 .. 10000 loop
    if numlist.exists(numlist(i)) then
      if i = numlist(numlist(i)) and i <> numlist(i) then
        sm := sm + i ;
      end if;
    end if;
  end loop;
  dbms_output.put_line('sum is: ' || sm);
end;
SQL> /

sum is: 31626

PL/SQL procedure successfully completed

Executed in 0.312 seconds

tree_new_bee

Q22 What is the total of all the name scores in the file of first names?
Using names.txt (right click and 'Save Link/Target As...'), a 46K text file containing over five-thousand first names, begin by sorting it into alphabetical order. Then working out the alphabetical value for each name, multiply this value by its alphabetical position in the list to obtain a name score.

For example, when the list is sorted into alphabetical order, COLIN, which is worth 3 + 15 + 12 + 9 + 14 = 53, is the 938th name in the list. So, COLIN would obtain a score of 938 × 53 = 49714.

What is the total of all the name scores in the file?


这个题目没难度， 正好用用很少用的oracle内的文件操作。
用external table 来读取。


create  table euler_names(
fname varchar2 (20)
)
ORGANIZATION EXTERNAL (
       TYPE ORACLE_LOADER
       DEFAULT DIRECTORY euler_dir
       ACCESS PARAMETERS
       (
         records delimited by ','
         badfile euler_dir:'euler%a_%p.bad'
         logfile euler_dir:'euler%a_%p.log'
         fields ENCLOSED BY '"'
         (fname)
       )
       LOCATION ('euler_names.txt')
);

with t0 as (select rownum n from dual connect by rownum<=20)
, t as (select fname, row_number() over (order by fname) rk from euler_names)
,t1 as (select fname, rk, sum(ASCII(substr(fname,n,1))-64) weight
from t,t0 where n<=length(fname)  group by fname, rk)
select sum(rk*weight) from t1


SUM(RK*WEIGHT)
--------------
     871198282

tree_new_bee

刚看到，另一个euler的帖子也打开了。
先去看看已做过的。 没做过的还是先不看了。

newkid

107楼的j:=j+step换成对质数表遍历怎么样？不过反正你才在100之内循环，不用那么麻烦了。