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

tree_new_bee

上面的人肉结果，另一点可以利用的是： 最终的值因子数目an可能与计算结果中的an不同， 但含有那几个值因子是肯定的(2,3,5,7,11,13), 所以循环时可以只循环2*3*5*7*11*13的倍数。

with targ as (select 15000-5881 arg from dual)
,t1 as (select (13*(rownum+452)-1)*(13*(rownum+452))/2 n, rownum m from targ connect by rownum<=arg/13
union
select (13*(rownum+452))*(5*(rownum+452)+1)/2 n, rownum m from targ connect by rownum<=arg/13
)
,t11 as (select * from t1 where mod(n, 2*3*5*7*11*13)= 0 )
,t2 as (select rownum d from targ connect by rownum*rownum<=(arg+5881)*(arg+5881+1)/2 )
,t3 as (select m,n,count(*)*2 cnt from  t11, t2 where n>d*d and mod(n, d) = 0  group by m,n )
select 13*(m+452),n,cnt+decode(sqrt(n)-floor(sqrt(n)),0,1,0) from t3 outer where cnt> (select max(cnt) from t3 where n<outer.n )

13*(M+452)          N CNT+DECODE(SQRT(N)-FLOOR(SQRT(
---------- ---------- ------------------------------
     12376   76576500                            576

Executed in 10.172 seconds

循环时，以13为循环步骤， 是因为几个质因子不一定分配在n和n+1的哪个之中， 所以不能以多个值因子的乘积为步骤， 只能选取一个最大的质因子。

用SQL都已经如此满意了， 上面的PLSQL如果进行同样的优化， 估计效果更好。(plsql中那个求因数个数的部分更能受益于优化)

tree_new_bee

原帖由 tree_new_bee 于 2010-12-15 08:53 发表
用SQL都已经如此满意了， 上面的PLSQL如果进行同样的优化， 估计效果更好。(plsql中那个求因数个数的部分更能受益于优化)

declare
i number; j number;
tri number; tmptri number;
k number;
factors number;
cnt number;
prod number;
begin
  tri:=17297280;
  i:= tri/2/3/5/7/11/13;
  while 1=1 loop
        if sqrt(2*tri+0.25) - 0.5 > floor(sqrt(2*tri+0.25) - 0.5) then  --not a triangle number
           GOTO NEXT_LOOP;
        end if;

        factors:=2;
        prod := 1;
        tmptri := i;
        j := 2;
        cnt := 2;
        while j<=sqrt(i) loop
            while mod(tmptri,j) = 0 loop
               tmptri := tmptri/j;
               cnt:=cnt+1;
            end loop;
            prod := prod * cnt;
           if j>2 then j:=j+2; else j:=j+1; end if;
            if j in (2,3,5,7,11,13) then cnt:=2; else cnt:=1; end if;
        end loop;
        if prod> 500 then
           dbms_output.put_line('No: ' || to_char(sqrt(2*tri+0.25) - 0.5) || ' number '|| tri || ' has factors: '|| prod);
           exit;
        end if;     
        <<NEXT_LOOP>>
        tri := tri + 2*3*5*7*11*13;
        i:= tri/2/3/5/7/11/13;

  end loop;
end;


SQL> /

No: 12375 number 76576500 has factors: 576

PL/SQL procedure successfully completed

Executed in 0.016 seconds


这次，可以用瞬时来形容了。

tree_new_bee

Q13:         Find the first ten digits of the sum of one-hundred 50-digit numbers.
又一道对于SQL来说丝毫没有难度的问题。

Oracle 的Number类型，直接相加就没问题(当然也有危险， 因为只保留38位精度， 如果从和的第10位到38位以后出现连续9然后+1那样的雪崩式进位，也许会导致结果错误)。

最没风险的还是用大数运算方法。

with t as (
          select '37107287533902102798797998220837590246510135740250' n from dual
union all select '46376937677490009712648124896970078050417018260538' n from dual
union all select '74324986199524741059474233309513058123726617309629' n from dual
union all select '91942213363574161572522430563301811072406154908250' n from dual
union all select '23067588207539346171171980310421047513778063246676' n from dual
union all select '89261670696623633820136378418383684178734361726757' n from dual
union all select '28112879812849979408065481931592621691275889832738' n from dual
union all select '44274228917432520321923589422876796487670272189318' n from dual
union all select '47451445736001306439091167216856844588711603153276' n from dual
union all select '70386486105843025439939619828917593665686757934951' n from dual
union all select '62176457141856560629502157223196586755079324193331' n from dual
union all select '64906352462741904929101432445813822663347944758178' n from dual
union all select '92575867718337217661963751590579239728245598838407' n from dual
union all select '58203565325359399008402633568948830189458628227828' n from dual
union all select '80181199384826282014278194139940567587151170094390' n from dual
union all select '35398664372827112653829987240784473053190104293586' n from dual
union all select '86515506006295864861532075273371959191420517255829' n from dual
union all select '71693888707715466499115593487603532921714970056938' n from dual
union all select '54370070576826684624621495650076471787294438377604' n from dual
union all select '53282654108756828443191190634694037855217779295145' n from dual
union all select '36123272525000296071075082563815656710885258350721' n from dual
union all select '45876576172410976447339110607218265236877223636045' n from dual
union all select '17423706905851860660448207621209813287860733969412' n from dual
union all select '81142660418086830619328460811191061556940512689692' n from dual
union all select '51934325451728388641918047049293215058642563049483' n from dual
union all select '62467221648435076201727918039944693004732956340691' n from dual
union all select '15732444386908125794514089057706229429197107928209' n from dual
union all select '55037687525678773091862540744969844508330393682126' n from dual
union all select '18336384825330154686196124348767681297534375946515' n from dual
union all select '80386287592878490201521685554828717201219257766954' n from dual
union all select '78182833757993103614740356856449095527097864797581' n from dual
union all select '16726320100436897842553539920931837441497806860984' n from dual
union all select '48403098129077791799088218795327364475675590848030' n from dual
union all select '87086987551392711854517078544161852424320693150332' n from dual
union all select '59959406895756536782107074926966537676326235447210' n from dual
union all select '69793950679652694742597709739166693763042633987085' n from dual
union all select '41052684708299085211399427365734116182760315001271' n from dual
union all select '65378607361501080857009149939512557028198746004375' n from dual
union all select '35829035317434717326932123578154982629742552737307' n from dual
union all select '94953759765105305946966067683156574377167401875275' n from dual
union all select '88902802571733229619176668713819931811048770190271' n from dual
union all select '25267680276078003013678680992525463401061632866526' n from dual
union all select '36270218540497705585629946580636237993140746255962' n from dual
union all select '24074486908231174977792365466257246923322810917141' n from dual
union all select '91430288197103288597806669760892938638285025333403' n from dual
union all select '34413065578016127815921815005561868836468420090470' n from dual
union all select '23053081172816430487623791969842487255036638784583' n from dual
union all select '11487696932154902810424020138335124462181441773470' n from dual
union all select '63783299490636259666498587618221225225512486764533' n from dual
union all select '67720186971698544312419572409913959008952310058822' n from dual
union all select '95548255300263520781532296796249481641953868218774' n from dual
union all select '76085327132285723110424803456124867697064507995236' n from dual
union all select '37774242535411291684276865538926205024910326572967' n from dual
union all select '23701913275725675285653248258265463092207058596522' n from dual
union all select '29798860272258331913126375147341994889534765745501' n from dual
union all select '18495701454879288984856827726077713721403798879715' n from dual
union all select '38298203783031473527721580348144513491373226651381' n from dual
union all select '34829543829199918180278916522431027392251122869539' n from dual
union all select '40957953066405232632538044100059654939159879593635' n from dual
union all select '29746152185502371307642255121183693803580388584903' n from dual
union all select '41698116222072977186158236678424689157993532961922' n from dual
union all select '62467957194401269043877107275048102390895523597457' n from dual
union all select '23189706772547915061505504953922979530901129967519' n from dual
union all select '86188088225875314529584099251203829009407770775672' n from dual
union all select '11306739708304724483816533873502340845647058077308' n from dual
union all select '82959174767140363198008187129011875491310547126581' n from dual
union all select '97623331044818386269515456334926366572897563400500' n from dual
union all select '42846280183517070527831839425882145521227251250327' n from dual
union all select '55121603546981200581762165212827652751691296897789' n from dual
union all select '32238195734329339946437501907836945765883352399886' n from dual
union all select '75506164965184775180738168837861091527357929701337' n from dual
union all select '62177842752192623401942399639168044983993173312731' n from dual
union all select '32924185707147349566916674687634660915035914677504' n from dual
union all select '99518671430235219628894890102423325116913619626622' n from dual
union all select '73267460800591547471830798392868535206946944540724' n from dual
union all select '76841822524674417161514036427982273348055556214818' n from dual
union all select '97142617910342598647204516893989422179826088076852' n from dual
union all select '87783646182799346313767754307809363333018982642090' n from dual
union all select '10848802521674670883215120185883543223812876952786' n from dual
union all select '71329612474782464538636993009049310363619763878039' n from dual
union all select '62184073572399794223406235393808339651327408011116' n from dual
union all select '66627891981488087797941876876144230030984490851411' n from dual
union all select '60661826293682836764744779239180335110989069790714' n from dual
union all select '85786944089552990653640447425576083659976645795096' n from dual
union all select '66024396409905389607120198219976047599490197230297' n from dual
union all select '64913982680032973156037120041377903785566085089252' n from dual
union all select '16730939319872750275468906903707539413042652315011' n from dual
union all select '94809377245048795150954100921645863754710598436791' n from dual
union all select '78639167021187492431995700641917969777599028300699' n from dual
union all select '15368713711936614952811305876380278410754449733078' n from dual
union all select '40789923115535562561142322423255033685442488917353' n from dual
union all select '44889911501440648020369068063960672322193204149535' n from dual
union all select '41503128880339536053299340368006977710650566631954' n from dual
union all select '81234880673210146739058568557934581403627822703280' n from dual
union all select '82616570773948327592232845941706525094512325230608' n from dual
union all select '22918802058777319719839450180888072429661980811197' n from dual
union all select '77158542502016545090413245809786882778948721859617' n from dual
union all select '72107838435069186155435662884062257473692284509516' n from dual
union all select '20849603980134001723930671666823555245252804609722' n from dual
union all select '53503534226472524250874054075591789781264330331690' n from dual
)
, t50 as (select rownum pos from dual connect by rownum<=50)
, t2 as (select pos-1 pos, sum(substr(n, -pos, 1)) sm from t,t50 group by pos)
, recu (r, d, m, str) as(
select 0, 0, 0, cast ('' as varchar2(4000))  from dual
union all select
r+1,
sm,
trunc((m+sm)/10),
trunc((m+sm)/10) ||mod(m+sm,10) || substr(str,3)
from recu, t2 where r=pos )
select substr( str, 1,10) from recu where r = (select max(r) from recu)

SUBSTR(STR,1,10)
--------------------
5537376230

Executed in 0.516 seconds


为了适当提高性能， 可以考虑在第12位以后(100个数的和进位不雪崩的话只会影响到前面2位)，如果下一个数字不是9， 则终止。 具体懒得写了。

[ 本帖最后由 tree_new_bee 于 2010-12-15 19:18 编辑 ]

tree_new_bee

Q14: Find the longest sequence using a starting number under one million.

The following iterative sequence is defined for the set of positive integers:

n → n/2 (n is even)
n → 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?



这也是一道有意思，也有挑战的题。

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

tree_new_bee

先用递归with写一段比较直观的：

将所有数作为anchor， 从每个点往下找路径。

with t as (select rownum n from dual connect by rownum<=1000)
, chain(num, path, step) as (
select n, n, 1 from t
union all
select
num,
case when mod(path,2)=0 then path/2 else 3*path+1 end,
step+1
from chain where path>1
)
cycle path set iscycle to 'y' default 'n'
select * from chain where step =(select max(step) from chain)

SQL> /

       NUM       PATH       STEP ISCYCLE
---------- ---------- ---------- -------
       871          1        179 n

Executed in 9.797 seconds

性能非常差， 1000以内就要将近10秒了。

tree_new_bee

换一种方法做递归：
这次选择单一的Anchor节点， 往下找path , 结束后开始下个数。
因为整个过程中，不需要构造太大的集合，所以开销节省不少。

with chain(num, path, step) as (
select 1, 1, 1 from dual
union all
select
case when path=1 then num+1 else num end,
case when path=1 then num+1 when mod(path,2)=0 then path/2 else 3*path+1 end,
case when path=1 then 1 else step+1 end
from chain where num<1000
)
cycle num,path set iscycle to 'y' default 'n'
--select * from chain
select * from chain where step = (select max(step) from chain)

       NUM       PATH       STEP ISCYCLE
---------- ---------- ---------- -------
       871          1        179 n

Executed in 1.375 seconds

1000以内只要1秒多， 进步很大。 提高到10000试试：

       NUM       PATH       STEP ISCYCLE
---------- ---------- ---------- -------
      6171          1        262 n

Executed in 55.75 seconds

这下要将近1分钟了  ，还是不可接受，要知道离100万还早着呢。
只好改道走PL/SQL了

tree_new_bee

PL/SQL：

declare
  maxchain    number := 0;
  maxchainnum number := 0;
  icopy       number;
  icopy2      number;
  len         number;
begin
  for i in 1 .. 10000 loop
    icopy := i;
    len   := 1;
    while icopy > 1 loop
      if bitand(icopy, 1) = 0 then
        icopy := icopy / 2;
      else
        icopy := icopy * 3 + 1;
      end if;
      len := len + 1;
    end loop;
  
    if len > maxchain then
      maxchain    := len;
      maxchainnum := i;
    end if;
  
  end loop;
  dbms_output.put_line('number: ' || maxchainnum || ' chains: ' ||
                       maxchain);
end;


number: 6171 chains: 262

PL/SQL procedure successfully completed

Executed in 0.609 seconds

哈，又快了两个数量级。
换成100000试试：

number: 77031 chains: 351

PL/SQL procedure successfully completed

Executed in 7.046 seconds

可以试试100万了：

number: 837799 chains: 525

PL/SQL procedure successfully completed

Executed in 85 seconds

能得到结果， 但运行1分半， 怎么也算不上理想的结果。

tree_new_bee

现在增加一点人肉成分：
对于偶数，没什么好分析的。
来看奇数n：
奇数n的下一步是3n+1, 3n+1一定是偶数， 所以再下一步一定是(3n+1)/2
假设n=2k+1
则n的下两步是(3n+1)/2 = (3*(2k+1)+1)/2 = (6k+4)/2 = 3k+2
而3k+2 > 2k+1
这就意味着： 所有3n+2形式的数字，都处于它之前的某个奇数的路径上， 因此可以忽略。

忽略这些数，可以节省1/3的循环时间。


declare
  maxchain    number := 0;
  maxchainnum number := 0;
  icopy       number;
  icopy2      number;
  len         number;
  i           number;
begin
  for k in 0 .. 1000000/3-1 loop
    for j in 0..1 loop
      i:= 3*k+j;
      icopy := i;
      len   := 1;
      while icopy > 1 loop
        if bitand(icopy, 1) = 0 then
          icopy := icopy / 2;
        else
          icopy := icopy * 3 + 1;
        end if;
        len := len + 1;
      end loop;
   
      if len > maxchain then
        maxchain    := len;
        maxchainnum := i;
      end if;
    end loop;   
  end loop;
  dbms_output.put_line('number: ' || maxchainnum || ' chains: ' ||
                       maxchain);
end;


number: 837799 chains: 525

PL/SQL procedure successfully completed

Executed in 55.157 seconds

(85-55)/85 = 35%,  果然节省了1/3左右的时间。

tree_new_bee

由上一步的分析可以看出， 如果能把之前的路径经历过的数预先排除， 能节省大量的循环开销。
那么我们就分析过的路径都保存下来。下次到达这些地方就直接取之前的路径长度信息。

declare
  type tpathtable is table of number index by PLS_INTEGER;
  pathtable tpathtable;
  maxchain    number := 0;
  maxchainnum number := 0;
  icopy       number;
  len         number;
begin
  for i in 1 .. 1000000 loop
    if pathtable.exists(i) then
      null;
    else
      icopy := i;
      len   := 1;
      while icopy > 1 loop
        if icopy < 1000000 and pathtable.exists(icopy) and
           pathtable(icopy) > 0 then
          len := len + pathtable(icopy) - 1;
          exit;
        else
          null; --if icopy < 1000000 then pathtable(icopy) := 0; end if;
        end if;
        if bitand(icopy, 1) = 0 then
          icopy := icopy / 2;
        else
          icopy := icopy * 3 + 1;
        end if;
        len := len + 1;
      end loop;
   
      pathtable(i) := len;
   
      if len > maxchain then
        maxchain    := len;
        maxchainnum := i;
      end if;
    end if;
  end loop;
  dbms_output.put_line('number: ' || maxchainnum || ' chains: ' ||
                       maxchain);

/*  for i in 1 .. 100 loop
    dbms_output.put_line('number: ' || i || ' chains: ' || pathtable(i));
  end loop; */

end;

number: 837799 chains: 525

PL/SQL procedure successfully completed

Executed in 6.016 seconds


这个时间效率应该算是很满意了。
注意代码中有一段null, 本来是打算把走过的路都存下来(只记录曾经访问，不记录路径长度信息， 长度信息比较难获取)， 一个新的数如果在这些路径
上，则直接跳过。  不过似乎减少循环节省的时间比不过维护LIST的时间， 实际性能反倒差了一些。

如果这个地方能获得路径长度信息， 给以后获取长度时提供帮助， 那也许会有帮助。

newkid

NB哥盖楼真快。40楼的“23以后的质数肯定不再需要”这个结论怎么得出来的？前面的D(N)>500怎么能保证凑出三角数来？