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

〇〇

id中带new的弟兄都太厉害了

    SUM(S)
----------
    872187

已用时间:  00: 00: 00.04
SQL> 5
  5* CONNECT BY LEVEL<=3
SQL> c/3/4
  5* CONNECT BY LEVEL<=4
SQL> /

    SUM(S)
----------
2.6595E+11

已用时间:  00: 00: 00.14
SQL> col s1 for 99999999999999
SQL> 54
54* select sum(s) from t1
SQL> c/)/)s1
54* select sum(s)s1 from t1
SQL> /

             S1
---------------
   265952760521

已用时间:  00: 00: 00.14

tree_new_bee

Q37 Find the sum of all eleven primes that are both truncatable from left to right and right to left.

The number 3797 has an interesting property. Being prime itself, it is possible to continuously remove digits from left to right, and remain prime at each stage: 3797, 797, 97, and 7. Similarly we can work from right to left: 3797, 379, 37, and 3.

Find the sum of the only eleven primes that are both truncatable from left to right and right to left.

NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.


跟Q35差不多。
不过难点在于上边界的确定。

如果把题目中的"only eleven primes"当作已知条件还好些，至少有了个中止退出的办法。 否则还要有有效的办法来找边界。

tree_new_bee

想不出找边界的办法， 只好逐步试。
试到1000000， 得到了11个数。

实现很容易， 基本上把Q35稍稍修改就行。

with tprim as (select /*+ RESULT_CACHE */ column_value prim from table(pkg_prim2.seive_numlist(1000000))
where column_value>10 and  translate(substr(column_value,2), '$1379','$') is null
and substr(column_value,1,1) in ('2','3','5','7') and substr(column_value,-1,1) in ('3', '7')
)
--select * from tprim
,tpos as (select rownum pos from dual connect by rownum<=6)
select count(prim),sum(prim) from tprim where not exists
(select 1 from tpos where pos<length(prim)
and (pkg_prim2.isprim(substr(prim,pos+1)) >0
or pkg_prim2.isprim(substr(prim,1, pos))>0
))

COUNT(PRIM) SUM(PRIM)--SELECT*
----------- ------------------
         11             748317

Executed in 0.141 seconds


别说， 还挺快。

这11个数是：

      PRIM
----------
        23
        37
        53
        73
       313
       317
       373
       797
      3137
      3797
    739397

11 rows selected

newkid

怎么证明总共就只有11个？

〇〇

恐怕要先证明7位的不存在，然后。。。

tree_new_bee

原帖由 newkid 于 2010-12-23 23:11 发表
怎么证明总共就只有11个？

似乎应该从3的倍数的特性： 各位数字和为3的倍数 这一点入手。
也就是说： 一个由[2357]{1379}[37] 组成的更长的数字， 要么数字本身是三的倍数， 要么其中的一部分会是3的倍数。

但是如果中间的那串数字全是3，9组成的话， 上面的似乎没办法对付。

这种情况下，还要证明中间的数字串3，9不能无限添加。


想不太清楚，思路很乱。

tree_new_bee

原帖由 〇〇 于 2010-12-24 07:33 发表
恐怕要先证明7位的不存在，然后。。。

证明7位的不存在，容易， 因为我们可以实证。 但这对后面似乎没帮助。

因为5位也不存在，但6位的存在。

〇〇

原帖由 tree_new_bee 于 2010-12-23 12:41 发表
想不出找边界的办法， 只好逐步试。
试到1000000， 得到了11个数。

实现很容易， 基本上把Q35稍稍修改就行。

with tprim as (select /*+ RESULT_CACHE */ column_value prim from table(pkg_prim2.seive_numlist(1000000))
where column_value>10 and  translate(substr(column_value,2), '$1379','$') is null
and substr(column_value,1,1) in ('2','3','5','7') and substr(column_value,-1,1) in ('3', '7')
)
--select * from tprim
,tpos as (select rownum pos from dual connect by rownum0
))

COUNT(PRIM) SUM(PRIM)--SELECT*
----------- ------------------
         11             748317

Executed in 0.141 seconds


别说， 还挺快。

这11个数是：

      PRIM
----------
        23
        37
        53
        73
       313
       317
       373
       797
      3137
      3797
    739397

11 rows selected

我用你的思路改写的纯SQL,不知错在哪里
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
    )
,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
       ),
tprim as (select rn prim from tnew
where rn>10 and  translate(substr(rn,2), '$1379','$') is null
and substr(rn,1,1) in ('2','3','5','7') and substr(rn,-1,1) in ('3', '7')
)
--select * from tprim where
,tpos as (select rownum pos from dual connect by rownum<=6)
select count(*) from tprim
where not exists
(select 1 from p1k,tpos where pos<length(rn)
and (mod(substr(tprim.prim,pos+1),p1k.rn) =0
or mod(substr(tprim.prim,1, pos),p1k.rn)=0
))

/

NT(*)
-----
  135

tree_new_bee

原帖由 〇〇 于 2010-12-24 10:47 发表

我用你的思路改写的纯SQL,不知错在哪里

两个错的地方：
一是where pos<length(rn)， 这里的rn应为tprim.prim

二是后面的mod p1k.rn要排除掉等于p1k.rn.

修改后应为这样：
.....
select * from tprim
where not exists
(select 1 from p1k,tpos where pos<length(tprim.prim)
and ((mod(substr(tprim.prim,pos+1),p1k.rn) =0 and substr(tprim.prim,pos+1)>p1k.rn)
or (mod(substr(tprim.prim,1, pos),p1k.rn)=0 and substr(tprim.prim,1, pos)>p1k.rn)
))


这个纯sql在我这里要3.4秒， 应该说是非常快了。

tree_new_bee

Q38  What is the largest 1 to 9 pandigital that can be formed by multiplying a fixed number by 1, 2, 3, ... ?

Take the number 192 and multiply it by each of 1, 2, and 3:

    192 × 1 = 192
    192 × 2 = 384
    192 × 3 = 576

By concatenating each product we get the 1 to 9 pandigital, 192384576. We will call 192384576 the concatenated product of 192 and (1,2,3)

The same can be achieved by starting with 9 and multiplying by 1, 2, 3, 4, and 5, giving the pandigital, 918273645, which is the concatenated product of 9 and (1,2,3,4,5).

What is the largest 1 to 9 pandigital 9-digit number that can be formed as the concatenated product of an integer with (1,2, ... , n) where n > 1?