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

tree_new_bee

显然， n的最大值是9, 在左边的数num为1时， 得到1 2 3 4 5 6 7 8 9.

因为n>=2, 所以左边的数num不能超过4位。

这样，之后要在num =(1..9999)和n = (2..9)之间暴力就是了。

with tnum as (select rownum num from dual connect by rownum<=9999)
,tn as (select rownum n from dual connect by rownum <=9)
, t1 as (select num, n from tnum, tn  where n>1 and n*length(num) <=9  and n*(length(num)+1) >9)
, t2 as (
select t1.num, t1.n n, replace(sys_connect_by_path(num*tn.n,'/'),'/', '') prod
from t1, tn   start with tn.n = 1
connect by t1.num = prior t1.num and t1.n=prior t1.n and   tn.n = prior tn.n+1 and tn.n<=t1.n)
,t3 as (select * from t2 where length(prod)=9 and translate('123456789', '$'||prod, '$') is null)
select * from t3 where prod = (select max(prod) from t3)


       NUM          N PROD
---------- ---------- --------------------------------------------------------------------------------
      9327          2 932718654

Executed in 0.672 seconds

SQL>

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

〇〇

142857*1 ~6

tree_new_bee

原帖由 〇〇 于 2010-12-24 12:11 发表
142857*1 ~6

tree_new_bee

Q39  If p is the perimeter of a right angle triangle, {a, b, c}, which value, for p ≤ 1000, has the most solutions?

If p is the perimeter of a right angle triangle with integral length sides, {a,b,c}, there are exactly three solutions for p = 120.

{20,48,52}, {24,45,51}, {30,40,50}

For which value of p ≤ 1000, is the number of solutions maximised?


这个和Q9类似。
直接暴力没多少难度。

with targ as (select 1000 arg from dual)
,t as (select rownum n from targ connect by rownum<=arg/2)   --a/b/c都不超过500
,t1 as (select ta.n a, tb.n b, round(sqrt(ta.n*ta.n+tb.n*tb.n)) c , ta.n+tb.n+ round(sqrt(ta.n*ta.n+tb.n*tb.n)) p
from t ta, t tb where round(sqrt(ta.n*ta.n+tb.n*tb.n),8) =round(sqrt(ta.n*ta.n+tb.n*tb.n)))
,t2 as (select p, count(*) cnt from t1,targ
where a<=p/3 and b>=a and b<c and c>=p/3
and p < arg group by p)
select * from t2 where cnt = (select max(cnt) from t2)


         P        CNT
---------- ----------
       840          8

Executed in 0.704 seconds

tree_new_bee

Q40 Finding the nth digit of the fractional part of the irrational number.

An irrational decimal fraction is created by concatenating the positive integers:

0.123456789101112131415161718192021...

It can be seen that the 12^(th) digit of the fractional part is 1.

If d_(n) represents the n^(th) digit of the fractional part, find the value of the following expression.

d_(1) × d_(10) × d_(100) × d_(1000) × d_(10000) × d_(100000) × d_(1000000)

tree_new_bee

Q40用SQL一时想不清楚， 人肉反倒很轻松。

很明显：
d(1) = 1
d(10) = 1

对于d(100): 1位数字9个共9位
     2位数字需要(100-9)/2 = 45.5个, 向上取整46个，共92位 -
     也即需要第46+9=55个数， 55的的末位数字为第92+9=101个数字。 所以第100位是5(前面一个5)

d(1000): 1位数字9个共9位
      2位数字90个共180位
      3位数字需要(1000-189)= 811 /3 ceiling= 271个，共813位 -
     也即需要第9+90+271=370个数， 370的末位数字为第1002个数字，所以第1000个数字为3 ->3
....
同样的方法， 可以推出d(10000)= 7, d(100000) = 2, d(1000000) = 1

所以d(1)*d(10)*d(100)*d(1000) * d(10000) * d(100000) * d(1000000) = 1*1*5*3*7*2*1 = 210

tree_new_bee

根据上面的思路，写出的SQL:

单看这个估计很难明白， 要把我上贴的方法看明白，才能看懂这段sql.


with t as( select power(10,rownum+1) n from dual connect by rownum<=6-1)
--with t as (select 1000000 n from dual)
, t1 as (select rownum d from t connect by rownum<=10)
, t2 as (select n, ceil((n-sum(d*9*power(10, d-1)))/(length(n)-1)) + (n/10-1) n1,
ceil((n-sum(d*9*power(10, d-1)))/(length(n)-1))*(length(n)-1) + sum(d*9*power(10, d-1)) p
from t, t1 where d<=length(n)-2 group by n)
, t3 as (select n,n1, p, substr(n1, -(p-n)-1,1) d from t2)
--select * from t3
select power(10, sum(log(10,d))) from t3


POWER(10,SUM(LOG(10,D)))
------------------------
                     210

Executed in 0.078 seconds

newkid

递归做Q38:
with t(n,s,n1) AS (
SELECT 1,TO_CHAR(LEVEL),LEVEL FROM DUAL
WHERE LENGTH(TRANSLATE('123456789', '$'||LEVEL, '$'))=9-LENGTH(LEVEL)
CONNECT BY LEVEL<=9999  
UNION ALL
SELECT n+1,s||TO_CHAR(n1*(n+1)),n1 FROM t
WHERE n<9 AND TRANSLATE(s,'$'||TO_CHAR(n1*(n+1)),'$')=s
      AND LENGTH(TRANSLATE('123456789', '$'||n1*(n+1), '$'))=9-LENGTH(n1*(n+1))
)
SELECT * FROM (SELECT * FROM t ORDER BY TO_NUMBER(s) DESC) WHERE ROWNUM=1;

         N S                      N1
---------- ---------------------- ----------
         2 932718654              9327

tree_new_bee

Q41  What is the largest n-digit pandigital prime that exists?

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once. For example, 2143 is a 4-digit pandigital and is also prime.

What is the largest n-digit pandigital prime that exists?

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

tree_new_bee

这个稍稍分析一下，就可以大大缩小暴力的范围。
在n=1..9中， 只有n=1,4,7时， 1+2+..n的和才不会被3整除。(一个数的各位数字能被3整除，则这个数能被3整除)
所以这个全排列数，只能是1位，4位或者7位。
既然要找最大的， 只要7位的存在， 那么搜索7位的即可。

为避免每次做关于质数的题都去处理跟质数相关的问题， 我做这些题时全部用我的pkg_prim2的两个过程来处理：
取一定范围内的质数： 用pkg_prim2.seive_numlist(maxn), 取得maxn范围内的全部质数，放到一个table of number类型中。
判断一个数是否为质数： 用pkg_prim2.isprim(n)


SQL语句很简单：
select max(column_value) from table(pkg_prim2.seive_numlist(7654321)) where column_value >=1234567
and translate('1234567' , '$'||column_value, '$') is null

MAX(COLUMN_VALUE)
-----------------
          7652413

Executed in 14.578 seconds

不过， 也相当慢。