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

〇〇 · 发表于 2010-12-29 20:02

8 位01组合只有256。。
只要求质数表中与01组合中第一个1相同位置为0或1的，否则凑不齐8个

tree_new_bee · 发表于 2010-12-29 20:28

用上面的函数，写出下面的语句：
with t as (select column_value n from table(pkg_prim2.seive_numlist(1000000)) where column_value>100000)
,tt as (select t1.n n1, t2.n n2, f_q51_diff(t1.n, t2.n) diff
from t t1, t t2
where t1.n<t2.n and length(t1.n) = length(t2.n)
and f_q51_diff(t1.n, t2.n) is not null)
select n1,diff, count(*) from tt group by n1, diff having count(*) >= 7

不过，这个语句跑了半个多小时了，还没有结果。

〇〇 · 发表于 2010-12-29 20:51

可能还可以用model子句快速结束迭代，如果遇到3个不是质数的，因为不可能再拼出8个质数

tree_new_bee · 发表于 2010-12-29 20:54

原帖由〇〇于 2010-12-29 20:02 发表
8 位01组合只有256。。
只要求质数表中与01组合中第一个1相同位置为0或1的，否则凑不齐8个

正在尝试这个思路。

〇〇 · 发表于 2010-12-29 21:21

56003 56113 like '__00_' or '__11_'
56223-56993 like replace(replace('00110','1',x),'0','_'),x从2到9

[ 本帖最后由〇〇于 2010-12-29 21:23 编辑 ]

tree_new_bee · 发表于 2010-12-29 22:20

以下思路与OO上面的基本相似，只有一点有区别，不是在满足10模式基础上加相应的倍数。而是将所有符合某种10模式的数，都统一成0.
比如56113/56223, 因为符合00110的模式，所以统一到基数56003.
这样，只要查统一到某个基数的数的数量，就可以了。

with tp as (select column_value p from table(pkg_prim2.seive_numlist(1000000)) where column_value>10)
,b as(select level-1 l from dual connect by level<=2)
,tbstr as (select replace(sys_connect_by_path(l ,'/'),'/','') str from b connect by level<=6)
,t01 as (select str s01 from tbstr where instr(str,'0')>0 and instr(str,'1')>0 ) --order by length(str), str
,tbase as (select p, s01,
case substr(s01,1,1) when  '0' then substr(p,1,1) when '1' then '0' else null end
|| case substr(s01,2,1) when  '0' then substr(p,2,1) when '1' then '0' else null end
|| case substr(s01,3,1) when  '0' then substr(p,3,1) when '1' then '0' else null end
|| case substr(s01,4,1) when  '0' then substr(p,4,1) when '1' then '0' else null end
|| case substr(s01,5,1) when  '0' then substr(p,5,1) when '1' then '0' else null end
|| case substr(s01,6,1) when  '0' then substr(p,6,1) when '1' then '0' else null end
|| case substr(s01,7,1) when  '0' then substr(p,7,1) when '1' then '0' else null end
|| case substr(s01,8,1) when  '0' then substr(p,8,1) when '1' then '0' else null end p1,
case substr(s01,1,1) when  '0' then null when '1' then substr(p,1,1) else null end
|| case substr(s01,2,1) when  '0' then null when '1' then substr(p,2,1) else null end
|| case substr(s01,3,1) when  '0' then null when '1' then substr(p,3,1) else null end
|| case substr(s01,4,1) when  '0' then null when '1' then substr(p,4,1) else null end
|| case substr(s01,5,1) when  '0' then null when '1' then substr(p,5,1) else null end
|| case substr(s01,6,1) when  '0' then null when '1' then substr(p,6,1) else null end
|| case substr(s01,7,1) when  '0' then null when '1' then substr(p,7,1) else null end
|| case substr(s01,8,1) when  '0' then null when '1' then substr(p,8,1) else null end p2
  from tp, t01
where length(s01) = length(p) )
, tgroup as (select p1, s01, count(*) cnt from tbase where length(translate('0123456789', p2||'0123456789', p2))=1
group by p1, s01 having count(*)>=8)
--select  s01, p1, cnt from tgroup
select min(p) from tbase where length(translate('0123456789', p2||'0123456789', p2))=1 and (p1,s01) in (select p1,s01 from tgroup)

MIN(P)
----------
121313

Executed in 96 seconds

tree_new_bee · 发表于 2010-12-29 22:22

上面的语句，大概是做euler project以来，写的难度最大的语句了。

为了便于理解，解释一下语句中的几个重要view:
tp: 质数表
t01: 01串， 01串的最大长度可根据需要修改。
tbase: 将形如56223根据模式串00110分解成56003(基数)和 22(用于后续判断各位是否相同)
tgroup: 能按同一个模式串统一到同一个基数的数的数量。 having count(*) 可根据需要修改。

上面的语句中，tgroup的输出为：

P1 S01 COUNT(*)
020303 101010 8

基数020303按照模式101010，各位加1后，就是上面的答案：121313

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

newkid · 发表于 2010-12-29 23:53

方法挺好，大胆假设小心求证嘛，6位没找到就找8位。

tree_new_bee · 发表于 2010-12-30 00:46

改成PLSQL来实现。
不是用逐个数字来驱动，而是先生成模式，然后用模式来驱动。
循环用的数字只用于替换模式中的0.

declare
  i integer;
  len integer;
  k integer;
  cnt integer;
  firstnumber integer;
  sbase varchar2(10);
  primtable pkg_prim2.tprimtable;
begin
primtable:= pkg_prim2.seive_indextable(1000000);

for rc in (with b as(select level-1 b from dual connect by level<=2)
,tbstr as (select replace(sys_connect_by_path(b ,'/'),'/','') str from b connect by level<=8)
select str s01 from tbstr where instr(str,'0')>0 and instr(str,'1')>0 order by length(s01), s01) loop
   len := length(replace(rc.s01,'1',''));
   for i in power(10, len-1) .. power(10,len)-1 loop
      k:=1;
      sbase:='';
      for j in 1..length(rc.s01) loop
            if substr(rc.s01, j,1) = '0' then
            sbase:=sbase||substr(i, k,1);
            k:=k+1;
            else
               sbase:=sbase||'0';
            end if;

      end loop;
      cnt:=0;
      for m in 0..9 loop
         if length(sbase + rc.s01 * m)= length(rc.s01) and primtable.exists(sbase + rc.s01 * m) then
            if cnt=0 then firstnumber := sbase + rc.s01 * m; end if;
            cnt:=cnt+1;
            if cnt=8 then
               dbms_output.put_line( 's01:' || rc.s01 || ', i:' || to_char(i) || ', sbase:'||sbase || ', firstnumber:' || firstnumber);
               return;
            end if;
         end if;
      end loop;
   end loop;
end loop;
end;

s01:101010, i:233, sbase:020303, firstnumber:121313

PL/SQL procedure successfully completed

Executed in 11.422 seconds

newkid · 发表于 2010-12-30 03:02

用OO的素数表写SQL:

var n number;
exec :n:=1000000

with ta as
(select level*2+1 l from dual connect by level<=sqrt(:N)/2),
t1 as (select level*2+1 l from dual connect by level<=sqrt(:N)/3)
,p1k as(select l rn from ta --1000以内的质数
minus
select t1.l*t2.l from t1,t1 t2 where t1.l<=sqrt(sqrt(:N))
and t1.l<=t2.l and t1.l*t2.l<=:N
)
,t0 AS (
SELECT 6*ROWNUM+1 rn FROM DUAL CONNECT BY ROWNUM <= (:n)/6
union all
SELECT 6*ROWNUM+5 rn FROM DUAL CONNECT BY ROWNUM <= (:n)/6
)
,t as(SELECT rn from t0
         where mod(rn,5)<>0
         and mod(rn,7)<>0
         and mod(rn,11)<>0
         and mod(rn,13)<>0
         and mod(rn,17)<>0
         and mod(rn,19)<>0
         and mod(rn,23)<>0
         and mod(rn,29)<>0
         and rn<:n
)
,tnew as(SELECT rn from t
      MINUS
      SELECT /*+ USE_MERGE (t1 t2) */ t1.rn * t2.rn
         FROM p1k t1, t t2
      WHERE t1.rn <= t2.rn
            AND t1.rn BETWEEN 31 AND (SELECT SQRT(:n) FROM DUAL)
            AND t1.rn * t2.rn <:n and t2.rn<=:n/31
union select * from p1k where rn<31
union select 2 from dual
   )
SELECT n2,MIN(rn),COUNT(*)
  FROM (
SELECT rn
   ,SYS_CONNECT_BY_PATH(DECODE(n,1,'*',SUBSTR(rn,LEVEL,1)),',') n2
   ,SYS_CONNECT_BY_PATH(DECODE(n,1,SUBSTR(rn,LEVEL,1)),',') n3
  FROM tnew,(SELECT 0 n FROM DUAL UNION ALL SELECT 1 FROM DUAL)
WHERE LEVEL=LENGTH(rn)
CONNECT BY NOCYCLE rn=PRIOR rn AND LEVEL<=LENGTH(rn) AND PRIOR DBMS_RANDOM.VALUE IS NOT NULL
)
WHERE LENGTH(TRANSLATE('0123456789',n3,','))=9
GROUP BY n2
HAVING COUNT(*)>=8;

N2
-------------------------------
MIN(RN) COUNT(*)
---------- ----------
,*,2,*,3,*,3
121313       8

Elapsed: 00:03:14.21

竟然花了三分多钟，可能因为CONNECT BY里面用到了DBMS_RANDOM. 改用递归WITH:

with ta as
(select level*2+1 l from dual connect by level<=sqrt(:N)/2),
t1 as (select level*2+1 l from dual connect by level<=sqrt(:N)/3)
,p1k as(select l rn from ta --1000以内的质数
minus
select t1.l*t2.l from t1,t1 t2 where t1.l<=sqrt(sqrt(:N))
and t1.l<=t2.l and t1.l*t2.l<=:N
)
,t0 AS (
SELECT 6*ROWNUM+1 rn FROM DUAL CONNECT BY ROWNUM <= (:n)/6
union all
SELECT 6*ROWNUM+5 rn FROM DUAL CONNECT BY ROWNUM <= (:n)/6
)
,t as(SELECT rn from t0
         where mod(rn,5)<>0
         and mod(rn,7)<>0
         and mod(rn,11)<>0
         and mod(rn,13)<>0
         and mod(rn,17)<>0
         and mod(rn,19)<>0
         and mod(rn,23)<>0
         and mod(rn,29)<>0
         and rn<:n
)
,tnew as(SELECT rn from t
      MINUS
      SELECT /*+ USE_MERGE (t1 t2) */ t1.rn * t2.rn
         FROM p1k t1, t t2
      WHERE t1.rn <= t2.rn
            AND t1.rn BETWEEN 31 AND (SELECT SQRT(:n) FROM DUAL)
            AND t1.rn * t2.rn <:n and t2.rn<=:n/31
union select * from p1k where rn<31
union select 2 from dual
   )
,w(rn,n2,n3,lvl) AS (
SELECT rn,CAST(DECODE(n,1,'*',SUBSTR(rn,1,1)) AS VARCHAR2(10)),CAST(DECODE(n,1,SUBSTR(rn,1,1)) AS VARCHAR2(1)),1
  FROM tnew,(SELECT 0 n FROM DUAL UNION ALL SELECT 1 FROM DUAL)
UNION ALL
SELECT rn,n2||DECODE(n,1,'*',SUBSTR(rn,lvl+1,1)),NVL(n3,DECODE(n,1,SUBSTR(rn,lvl+1,1))),lvl+1
  FROM w,(SELECT 0 n FROM DUAL UNION ALL SELECT 1 FROM DUAL)
WHERE lvl<LENGTH(rn) AND (n3 IS NULL OR n=0 OR n=1 AND SUBSTR(rn,lvl+1,1)=n3)
)
SELECT n2,MIN(rn),COUNT(*)
  FROM w
WHERE lvl=LENGTH(rn)
GROUP BY n2
HAVING COUNT(*)>=8;

N2                   MIN(RN) COUNT(*)
------------------ ---------- ----------
*2*3*3                121313       8

Elapsed: 00:01:09.24

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

浏览过的版块