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

tree_new_bee

这个题， 思路不难， 难的是效率。
思路：
n² + an + b 是质数，
n=0时，n² + an + b = b, 所以b一定是质数(也是正数)
n=1时，n² + an + b = a+b+1, 所以a+b+1一定是质数, 或者说a一定是两个质数的差减1
同时， n² + an + b 是质数，意味着n² + an + b>1
所以a+b+1>1, 也即a+b>0


先放一个能转， 但效率不高的版本。

with tab1 as ( select /*+ RESULT_CACHE  */  column_value prim from table(pkg_prim2.seive_numlist(2*200)))
, tb as (select prim b from tab1 where prim<=200)
, tquad as (select (prim-1-b) a, b b, prim b0
from tb, tab1
where abs(prim-1-b) <200)
--select * from tquad
, tn as (select rownum-1 n from dual connect by rownum<=80)
, tabn as (select a,b,n, row_number() over (partition by a, b order by n)-1 rn, (n*n+n*a+b) nab
from tquad, tn
where n*n+n*a + b> 1 and pkg_prim2.isprim(n*n+n*a + b)=0)
--select * from tabn where a=22 and b=2 and rn=n
select a,b, count(*) from tabn where rn=n group by a,b


         A          B        CNT
---------- ---------- ----------
       -25        197         53

Executed in 5.906 seconds

SQL>


pkg_prim2.seive_numlist是用筛法生成某数范围内的t_numlist.

a,b限定200以内用6秒。

换成1000的话：


         A          B        CNT
---------- ---------- ----------
       -61        971         71

Executed in 115.438 seconds


不错， 能出来结果就算成功。

tree_new_bee

用pl/sql来做， 对循环做些精细控制：
1.  题中已经告诉f(1,41)=40, 所以可以直接先判断n=40时n*n+n*a+b是否质数，把不满足的都忽略。
2. 题中告诉了已知的f(-79,1601)=80, 实际上隐含告诉我们在1000以内不会超过80。所以对n>80的情况可忽略。
充分利用上面两个条件，能大大减少循环次数。

3. 质数表用pkg_prim2.seive_indextable快速产生。



declare
  a integer;
  b integer;
  maxa integer;
  maxb integer;
  cnt integer;
  maxcnt integer;
  primtable pkg_prim2.tprimtable;
begin
  primtable := pkg_prim2.seive_indextable(86500); --max prim needed is 80*80 + 1000*80 + 1000
  maxcnt:=40;  
  b := primtable.first;
  while b<1000 and b is not null  loop
    for a in greatest(1-b, floor((1-1600-b)/40)) ..1000 loop
      if primtable.exists(a+b+1) and primtable.exists(40*40+40*a+b) then
        cnt:=2;
        for n in 2..80 loop
          if n*n+a*n+b < 2 or not primtable.exists(n*n+a*n+b) then exit; end if;
          cnt:=cnt+1;
        end loop;
        
        if cnt>maxcnt then maxcnt:=cnt; maxa:=a; maxb:=b; end if;
      end if;
    end loop;
    b:=primtable.next(b);
  end loop;
  
  dbms_output.put_line( 'maxa:' || maxa || ' maxb: '||maxb || ' maxcnt: ' || maxcnt || ' a*b is:' || maxa*maxb);
end ;

maxa:-61 maxb: 971 maxcnt: 71 a*b is:-59231

PL/SQL procedure successfully completed

Executed in 0.297 seconds

lastwinner

原帖由 tree_new_bee 于 10-12-19 14:55 发表
这个题， 思路不难， 难的是效率。
思路：
n&sup2; + an + b 是质数，
n=0时，n&sup2; + an + b = b, 所以b一定是质数(也是正数)
n=1时，n&sup2; + an + b = a+b+1, 所以a+b+1一定是质数, 或者说a一定是两个质数的差减1
同时， n&sup2; + an + b 是质数，意味着n&sup2; + an + b>1
所以a+b+1>1, 也即a+b>0

思路很好！
构建一张不超过
80^2+1000^80+1000
的质数表先，估计能提高运算速度

你132中的思路也提到了同样的思路，即【2. 题中告诉了已知的f(-79,1601)=80, 实际上隐含告诉我们在1000以内不会超过80。所以对n>80的情况可忽略。】


用递归with貌似能有效解决循环跳出，等高手们出招，嘿嘿

〇〇

原帖由 tree_new_bee 于 2010-12-19 12:01 发表


没看懂。
用调试工具跟踪半天，也没明白什么意思。

http://www.itpub.net/thread-1364272-8-1.html
80楼加了中文注释,核心就是1/n的循环节长度的99...999能被n整除

tree_new_bee

原帖由 〇〇 于 2010-12-20 08:39 发表

http://www.itpub.net/thread-1364272-8-1.html
80楼加了中文注释,核心就是1/n的循环节长度的99...999能被n整除

这下容易懂多了。

tree_new_bee

原帖由 lastwinner 于 2010-12-20 00:54 发表


思路很好！
构建一张不超过
80^2+1000^80+1000
的质数表先，估计能提高运算速度

你132中的思路也提到了同样的思路，即【2. 题中告诉了已知的f(-79,1601)=80, 实际上隐含告诉我们在1000以内不会超过80。所以对n>80的情况可忽略。】


用递归with貌似能有效解决循环跳出，等高手们出招，嘿嘿

递归with没问题， 但对于大质数表的访问效率还是麻烦(除非把质数表做成物理表，加上索引也许效率能高许多)， 所以还是一个一个单独去判断。



with tbigprim as ( select /*+ RESULT_CACHE  */  column_value prim from table(pkg_prim2.seive_numlist(2001)))
, tb as (select prim b from tbigprim where prim<=1000)
, tquad as (select (prim-1-b) a, b b, prim b0
from tb, tbigprim
where abs(prim-1-b) <1000
and prim-1-b > greatest(1-b, floor((1-1600-b)/40))
and 40*40+40*(prim-1-b)+b>1
and pkg_prim2.isprim(40*40+40*(prim-1-b)+b)=0
)
--select * from tquad
, tabn (a,b, n )as (
select a,b, 0 from tquad
union all
select
a,
b,
n+1
from tabn where n<81 and n*n+n*a + b>0 and pkg_prim2.isprim(n*n+n*a + b)=0)
select * from tabn where n = (select max(n) from tabn)


         A          B          N
---------- ---------- ----------
       -61        971         71

Executed in 2.891 seconds

tree_new_bee

原帖由 tree_new_bee 于 2010-12-20 10:03 发表


递归with没问题， 但对于大质数表的访问效率还是麻烦(除非把质数表做成物理表，加上索引也许效率能高许多)， 所以还是一个一个单独去判断。

把大质数表物理存储下来。

SQL> create table prim86500 as select column_value prim from table(pkg_prim2.seive_numlist(86500));

Table created
  
SQL> create unique index idx_prim86500 on prim86500(prim);

Index created

with tab1 as (select prim ab1 from prim86500 where prim<=2001)
,tb as (select prim b from prim86500 where prim<=1000)
, tquad as (select (ab1-1-b) a, b b, ab1 b0
from tb, tab1
where abs(ab1-1-b) <1000
and ab1-1-b > greatest(1-b, floor((1-1600-b)/40))
and 40*40+40*(ab1-1-b)+b>1
and exists (select 1 from prim86500 where prim = 40*40+40*(ab1-1-b)+b))
--select * from tquad
, tabn (a,b, n )as (
select a,b, 0 from tquad
union all
select
a,
b,
n+1
from tabn where n<81 and n*n+n*a + b>0 and
exists(select 1 from prim86500 where prim = n*n+n*a + b)
)
select * from tabn where n = (select max(n) from tabn)


         A          B          N
---------- ---------- ----------
       -61        971         71

Executed in 0.984 seconds

SQL>

tree_new_bee

Q28 What is the sum of both diagonals in a 1001 by 1001 spiral?

Starting with the number 1 and moving to the right in a clockwise direction a 5 by 5 spiral is formed as follows:

21 22 23 24 25
20  7  8  9 10
19  6  1  2 11
18 5  4  3 12
17 16 15 14 13

It can be verified that the sum of the numbers on the diagonals is 101.

What is the sum of the numbers on the diagonals in a 1001 by 1001 spiral formed in the same way?

tree_new_bee

这题，看着很吓人， 其实只要人肉找找规律， 很简单：

看右上角的那条线， 是第n个奇数的平方  (2n-1)^2
左上角的线,    是右上角线 - 2(n-1)
左下角的线， 是右上角线 - 4(n-1)
右下角的线， 是右上角线 - 6(n-1)

所以一圈的总和，就是4*(2n-1)^2 - 2(n-1) - 4(n-1) - 6(n-1) = 4*(2n-1)^2 - 12(n-1)


SQL> with t as (select rownum+1 n from dual connect by rownum<=(1001-1)/2)
  2  select sum(4*(2*n-1)*(2*n-1) - 12*(n-1)) + 1 from t
  3  /

SUM(4*(2*N-1)*(2*N-1)-12*(N-1)
------------------------------
                     669171001

Executed in 0.079 seconds

SQL>

tree_new_bee

Q29 How many distinct terms are in the sequence generated by ab for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?

Consider all integer combinations of a^(b) for 2 ≤ a ≤ 5 and 2 ≤ b ≤ 5:

    2^(2)=4, 2^(3)=8, 2^(4)=16, 2^(5)=32
    3^(2)=9, 3^(3)=27, 3^(4)=81, 3^(5)=243
    4^(2)=16, 4^(3)=64, 4^(4)=256, 4^(5)=1024
    5^(2)=25, 5^(3)=125, 5^(4)=625, 5^(5)=3125

If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:

4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125

How many distinct terms are in the sequence generated by a^(b) for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?

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