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

tree_new_bee

Q32 Find the sum of all numbers that can be written as pandigital products.

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, the 5-digit number, 15234, is 1 through 5 pandigital.

The product 7254 is unusual, as the identity, 39 × 186 = 7254, containing multiplicand, multiplier, and product is 1 through 9 pandigital.

Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.
HINT: Some products can be obtained in more than one way so be sure to only include it once in your sum.

tree_new_bee

这个要稍稍人肉一下， 以便确定暴力的边界。
a*b=c, 共9位数字，假设a<=b<c
则共有以下组合
1+1=7
1+2 = 6
1+3 = 5
1+4 = 4
2+2 = 5
2+3 = 4
3+3 = 3
其中只有1+4 = 4 和2+3=4两个满足条件。


with t1 as (select rownum n from dual connect by rownum<=98)
, t2 as (select rownum+120 n from dual connect by rownum<=9876-120)
,t3 as (select t1.n, t2.n, t1.n*t2.n p from t1,t2
where ((length(t1.n)=1 and length(t2.n)=4) or (length(t1.n)=2 and length(t2.n)=3))
and length(t1.n||t2.n||t1.n*t2.n) = 9
and translate('123456789$' ,'$'||t1.n || t2.n || t1.n*t2.n, '$') = '$')
select sum(distinct p) from t3

SUM(DISTINCTP)
--------------
         45228

Executed in 2.984 seconds

tree_new_bee

在上面的基础上， 把1+4和2+3两种组合分别设置条件， 可使对条件的控制更精细一些：
1+4的情况下， 1位数不可能为1， 所以4位数不能超过5000
无论哪种组合， ab两数都不能个位为1/5因为1*x=x, 5*x=(0/5))

with t1 as (select rownum+1 n from dual connect by rownum<=9-1)
, t2 as (select rownum+11 n from dual connect by rownum<=98-11)
, t3 as (select rownum+122 n from dual connect by rownum<=987-120)
, t4 as (select rownum+1233 n from dual connect by rownum<=5000-1233)
,t6 as (select n1, n2, n1*n2 p from (select  ta.n n1, tb.n n2 from t1 ta,t4 tb
                      union all select  ta.n n1, tb.n n2 from t2 ta,t3 tb)
where mod(n1, 5)>0 and mod(n2,5)>0
and substr(n1,-1,1)<>'1' and substr(n2,-1,1) <> '1'
and n1*n2<10000
--and length(n1||n2||n1*n2) = 9
and translate('123456789$' ,'$'||n1 || n2 || n1*n2, '$') = '$')
select sum(distinct p) from t6

SUM(DISTINCTP)
--------------
         45228

Executed in 0.312 seconds

SQL>

这个结果令人满意。

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

tree_new_bee

Q33 Discover all the fractions with an unorthodox cancelling method.

The fraction ^(49)/_(98) is a curious fraction, as an inexperienced mathematician in attempting to simplify it may incorrectly believe that ^(49)/_(98) = ^(4)/_(8), which is correct, is obtained by cancelling the 9s.

We shall consider fractions like, ^(30)/_(50) = ^(3)/_(5), to be trivial examples.

There are exactly four non-trivial examples of this type of fraction, less than one in value, and containing two digits in the numerator and denominator.

If the product of these four fractions is given in its lowest common terms, find the value of the denominator.

tree_new_bee

这个题因为涉及到的数据量小， 即使不加任何人肉判断直接暴力，也没多少计算量。 为了有趣，还是要稍稍人肉一下。
已知条件： (10a+b)/(10b+c) = a/c,  a<c

上面的等式变化一下，可得：
10ac + bc = 10ab + ac
9ac + bc = 10ab

所以： b= 9ac/(10a-c)  因为a<c 所以b> 9ac/(10a-a) = 9ac/9a = c, 即b>c
因此数的大小关系为a<c<b



with t as (select rownum n from dual connect by rownum<=9)
,t1 as (select ta.n a, tb.n b, tc.n c, 10*ta.n+tb.n ab, 10*tb.n+tc.n bc from t ta, t tb ,t tc
where ta.n < tc.n and tc.n<tb.n
and 9*ta.n*tc.n +tb.n*tc.n = 10*ta.n * tb.n)
,t2 as (select round(power(10, sum(log(10, ab)))) sab, round(power(10, sum(log(10,bc)))) sbc from t1)
, gcd(a, b) as
(select sab , sbc  from t2
union all
select b,
mod(a,b)
from gcd where b>0
)
select sbc/a from gcd,t2 where b=0


     SBC/A
----------
       100

Executed in 0.063 seconds

其实t1的结果出来后(就4个数： 16/64， 19/95， 26/65，49/98)， 肉眼就能一口说出答案了， 可是为了让sql说出答案，还整的挺麻烦， 又是连乘， 又是gcd的。

真是无趣啊， 赶紧pass.

本来还想优化优化，利用b= 9ac/(10a-c)，减少一次表的连接， 可是看这运行时间， 实在是不值得了。

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

tree_new_bee

Q34  Find the sum of all numbers which are equal to the sum of the factorial of their digits.

145 is a curious number, as 1! + 4! + 5! = 1 + 24 + 120 = 145.

Find the sum of all numbers which are equal to the sum of the factorial of their digits.

Note: as 1! = 1 and 2! = 2 are not sums they are not included.

tree_new_bee

这个题，不人肉是没法做的， 因为要暴力需要有边界， 不人肉不知道暴力的边界在哪里。

从大数着手， 9!= 362880 为6位
如果是6个9， 则6*9! = 2177280 为7位
7个9， 则7*9! = 2540160 为7位
8个9，则8*9! = 2903040为7位
即n>=8时， 各位数字的阶乘和达不到n位。

因此暴力的边界可以放到7个9,即9999999以内。


with t as (select rownum-1 n from dual connect by rownum<=9+1)
,tp as (select n, round(power(10,sum(log(10,n)) over(order by n))) p from t where n>0 union select 0,1 from dual)
select sum(to_number(t1.n||t2.n||t3.n||t4.n||t5.n||t6.n||t7.n))-3  --去除提示中要排除的1和2
from tp t1, tp t2, tp t3 ,tp t4, tp t5, tp t6, tp t7
where t1.p+t2.p+t3.p+t4.p + t5.p+t6.p + t7.p  
      - (7-length(ltrim(t1.n||t2.n||t3.n||t4.n||t5.n||t6.n||t7.n, '0')))  --前导为0的数不计算0的阶乘
= t1.n||t2.n||t3.n||t4.n||t5.n||t6.n || t7.n

SUM(TO_NUMBER(T1.N||T2.N||T3.N
------------------------------
                         40730

Executed in 104.328 seconds


运行了100多秒， 循环了近千万次， 最后除了题目中给的145外只找到了1个数(40585), 悲哀啊悲哀～～

tree_new_bee

上面忽略了一个重要信息， 就是既然确定为最多7位， 那么7位的最大数字为7*9! = 2540160
排除前两位>25的情况，可以减少75%的循环量。

with t as (select rownum-1 n from dual connect by rownum<=9+1)
,tp as (select  n, round(power(10,sum(log(10,n)) over(order by n))) p from t where n>0 union select 0,1 from dual)
select sum(to_number(t1.n||t2.n||t3.n||t4.n||t5.n||t6.n||t7.n))-3  --去除提示中要排除的1和2
from tp t1, tp t2, tp t3 ,tp t4, tp t5, tp t6, tp t7
where (t1.n<2 or (t1.n=2 and t2.n<6)) and
        t1.p+t2.p+t3.p+t4.p + t5.p+t6.p + t7.p  
      - (7-length(ltrim(t1.n||t2.n||t3.n||t4.n||t5.n||t6.n||t7.n, '0')))  --前导为0的数不计算0的阶乘
= t1.n||t2.n||t3.n||t4.n||t5.n||t6.n || t7.n

SUM(TO_NUMBER(T1.N||T2.N||T3.N
------------------------------
                         40730

Executed in 26.938 seconds


就这样了， 想不出更多的有效人肉策略了。

tree_new_bee

Q35 How many circular primes are there below one million?

The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.

There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.

How many circular primes are there below one million?

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

tree_new_bee

做完这道，睡觉去。

这道题的关键是要预先排除。 对于大于7的数，只要数中有245680，就肯定不满足要求。

排除下来，100万以内其实没多少个需要检查的了。


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

  COUNT(*)
----------
        55

Executed in 0.344 seconds