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

tree_new_bee

另一个方法， 是根据p(n)=n(3n-1)/2来求得:  p(n) + p(m) 和p(n)-p(m)
设d=n-m, 则：
p(n) + p(n-d) = n(3n-1)/2 +(n-d)(3*(n-d) - 1)/2 = 3*n^2 +1.5*d^2 -3nd -n + 0.5d
p(n) - p(n-d) =  n(3n-1)/2 - (n-d)(3*(n-d) - 1)/2 = 3nd - 1.5d^2 - 0.5d

上面两个结果要为整数，则d必须为奇数。


with tn as (select rownum n from dual connect by rownum<=3000)
,td as (select rownum*2-1 d from dual connect by rownum<=(3000+1)/2)
select n*(3*n-1)/2 pen2, (n-d)*(3*(n-d)-1)/2 pen1, n*(3*n-1)/2-(n-d)*(3*(n-d)-1)/2 PD
from tn, td
where d<n
and floor((sqrt(24*( 3*n*n + 1.5*d*d -3*n*d -n + 0.5*d   )+1)+1)/6)
=   (sqrt(24*(3*n*n + 1.5*d*d -3*n*d -n + 0.5*d)+1)+1)/6
and floor((sqrt(24*( 3*n*d -1.5*d*d -0.5*d )+1)+1)/6)
=   (sqrt(24*(3*n*d -1.5*d*d -0.5*d)+1)+1)/6

      PEN2       PEN1         PD
---------- ---------- ----------
   7042750    1560090    5482660

Executed in 17.703 seconds

时间差不多。 其实也正常， 只是公式有差别，但实质是相同的。

tree_new_bee

把d必须为奇数的条件加到#230的语句中， 效果倒是挺明显的：

with tpen as (select rownum n, rownum*(rownum*3-1)/2 pen from dual connect by rownum<=3000)
select t1.n n1, t1.pen pen1, t2.n n2, t2.pen pen2, t2.pen-t1.pen d  from tpen t1, tpen t2
where floor((sqrt(24*(t1.pen+t2.pen)+1)+1)/6) =   (sqrt(24*(t1.pen+t2.pen)+1)+1)/6
and floor((sqrt(24*(t2.pen-t1.pen)+1)+1)/6) =   (sqrt(24*(t2.pen-t1.pen)+1)+1)/6
and t1.pen < t2.pen
and mod(t2.n - t1.n,2) = 1

        N1       PEN1         N2       PEN2          D
---------- ---------- ---------- ---------- ----------
      1020    1560090       2167    7042750    5482660

Executed in 12.015 seconds

tree_new_bee

用plsql写了一段比较严密的解决方案， 用于确认找到的D就是最小的D：

create or replace procedure tempproc is
  i integer;
  j integer;
  k integer;
  D number :=1E30;
  kmj number;
  kpj number;
  function pent(n number) return number is
  begin
    return n*(3*n-1)/2;
  end;
  function ispent(x number) return boolean is
  begin
    return (floor((sqrt(24*x+1) + 1)/6) = (sqrt(24*x+1) + 1)/6 ) ;
  end;
begin
  k:=2;
  j:=1;
  while k  < (D-1)/3+1 loop -- pent(k)-pent(k-1)<D
     j:=k-1;
     while j>0 loop
         PRAGMA INLINE (pent, 'YES');
         kmj := pent(k)-pent(j);
         if kmj > D then exit; end if;

         PRAGMA INLINE (pent, 'YES');
         kpj := pent(k)+pent(j);

         PRAGMA INLINE (ispent, 'YES');
         if ispent(kmj) and ispent(kpj) then
           if kmj< D then D:=kmj; end if;
         end if;
         j:=j-2;
     end loop;   
     k:=k+1;
  end loop;
  dbms_output.put_line('the D is: '||D );
  dbms_output.put_line('the last k tested is:' || k );
  
end tempproc;

SQL> exec tempproc

the D is: 5482660
the last k tested is:1827554

PL/SQL procedure successfully completed

Executed in 27.531 seconds


严密的代价是plsql代码要跑27秒。

在该题目的帖子中， 似乎很少人提起这一点。 不知是所有人都忽略了， 还是说有什么方法能证明找到的第一个D就一定是最小的D?


如果，不加这个严密判断， 在找到第一个D时就退出， 这段代码只要运行3秒

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

newkid

原帖由 tree_new_bee 于 2010-12-27 14:48 发表


一直没找到MATERIALIZE hint的相关说明。 看字面含义似乎与result_cache差不多？

MATERIALIZE 是指把子查询结果当作临时表来访问，不再和外层查询结合进行变形，result_cache则是在第二次运行SQL的时候直接取结果。

tree_new_bee

原帖由 newkid 于 2010-12-28 06:25 发表


MATERIALIZE 是指把子查询结果当作临时表来访问，不再和外层查询结合进行变形，result_cache则是在第二次运行SQL的时候直接取结果。

谢谢， 明白了。

tree_new_bee

Q45  After 40755, what is the next triangle number that is also pentagonal and hexagonal?

Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:
Triangle                   T_(n)=n(n+1)/2                   1, 3, 6, 10, 15, ...
Pentagonal                   P_(n)=n(3n−1)/2                   1, 5, 12, 22, 35, ...
Hexagonal                   H_(n)=n(2n−1)                   1, 6, 15, 28, 45, ...

It can be verified that T_(285) = P_(165) = H_(143) = 40755.

Find the next triangle number that is also pentagonal and hexagonal.

tree_new_bee

做完44，再看45题太容易了。
注意一点： 六角数必然是三角数， 所以没有必要判断三角数。

为了避免猜测上限， 可以用connect by 或者递归with.

select max(rownum+144),
max(rownum+144)*(2*max(rownum+144)-1)
from dual --where CONNECT_BY_ISLEAF=1
connect by trunc((sqrt(24* (rownum+143)*(2*(rownum+143)-1)+1) + 1)/6 ) <>   (sqrt(24* (rownum+143)*(2*(rownum+143)-1)+1) + 1)/6

MAX(ROWNUM+144) MAX(ROWNUM+144)*(2*MAX(ROWNUM+
--------------- ------------------------------
          27693                     1533776805

Executed in 0.188 seconds



直接pass!

6666444

俺懒自己不想做，每天来看看楼主解题，果然NB啊．．．楼主辛苦了

tree_new_bee

原帖由 6666444 于 2010-12-28 11:05 发表
俺懒自己不想做，每天来看看楼主解题，果然NB啊．．．楼主辛苦了

看别人做100道，不如自己做1道。

tree_new_bee

Q46 What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?

It was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and twice a square.

9 = 7 + 2×1^(2)
15 = 7 + 2×2^(2)
21 = 3 + 2×3^(2)
25 = 7 + 2×3^(2)
27 = 19 + 2×2^(2)
33 = 31 + 2×1^(2)

It turns out that the conjecture was false.

What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?

[ 本帖最后由 tree_new_bee 于 2010-12-28 14:41 编辑 ]