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

tree_new_bee

Q25 What is the first term in the Fibonacci sequence to contain 1000 digits?

The Fibonacci sequence is defined by the recurrence relation:

    F_(n) = F_(n−1) + F_(n−2), where F_(1) = 1 and F_(2) = 1.

Hence the first 12 terms will be:

    F_(1) = 1
    F_(2) = 1
    F_(3) = 2
    F_(4) = 3
    F_(5) = 5
    F_(6) = 8
    F_(7) = 13
    F_(8) = 21
    F_(9) = 34
    F_(10) = 55
    F_(11) = 89
    F_(12) = 144

The 12th term, F_(12), is the first term to contain three digits.

tree_new_bee

Q25 初看似乎很难， 1000位的数字，早超出大数的限制了。 似乎不好处理。
但这个题比之前一些类似题好的地方在于， 不必关心一个数的具体每一位的数字， 也就不用担心精度问题。

这样， 只要把之前的菲波纳契算法，改成类似科学计数法来处理就行了。

WITH t(r,a,b,e) AS (
SELECT 1,0,1,0 FROM DUAL
UNION ALL
SELECT r+1
      ,case when a+b>=1 then b/10 else b end
      ,case when (a+b)>=1 then (a+b)/10 else a+b end
      ,case when (a+b)>=1 then e+1 else e end
  FROM t
WHERE e<1000
)
cycle a,b set iscycle to 'y' default 'n'
--select r,a,b,e from t
select max(r) from t


    MAX(R)
----------
      4782



中间表的输出示例：
         R          A          B          E
---------- ---------- ---------- ----------
         1          0          1          0
         2        0.1        0.1          1
         3        0.1        0.2          1
         4        0.2        0.3          1
         5        0.3        0.5          1
         6        0.5        0.8          1
         7       0.08       0.13          2
         8       0.13       0.21          2
         9       0.21       0.34          2
        10       0.34       0.55          2
        11       0.55       0.89          2
        12      0.089      0.144          3
...

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

tree_new_bee

Q26 Find the value of d < 1000 for which 1/d contains the longest recurring cycle.

A unit fraction contains 1 in the numerator. The decimal representation of the unit fractions with denominators 2 to 10 are given:

    ^(1)/_(2)        =         0.5
    ^(1)/_(3)        =         0.(3)
    ^(1)/_(4)        =         0.25
    ^(1)/_(5)        =         0.2
    ^(1)/_(6)        =         0.1(6)
    ^(1)/_(7)        =         0.(142857)
    ^(1)/_(8)        =         0.125
    ^(1)/_(9)        =         0.(1)
    ^(1)/_(10)        =         0.1

Where 0.1(6) means 0.166666..., and has a 1-digit recurring cycle. It can be seen that ^(1)/_(7) has a 6-digit recurring cycle.

Find the value of d < 1000 for which ^(1)/_(d) contains the longest recurring cycle in its decimal fraction part.

tree_new_bee

Q26 跟Q25反过来了。
这个题看着很简单：
以1/7为例：
1/7 = 0.(142857) = 0.142857 142857 .....
把它乘以10^6方后，即1/7 * 10^6 = 142857.142857 142857 ....
这样小数点后的余数与原来的小数相同。

两边相减， 就是(10^6-1) *1/7 = 142857
后面必然是个整数。

但是这个方法涉及到比较大的数以后， 就有精度问题和大数运算的问题了。

tree_new_bee

先弄个SQL放到这里，做记录。
到47就超出精度范围了， 基本没有实用性。

with targ as (select 20 arg from dual)
,t as (select rownum n from targ connect by rownum<=arg)
,t1 as (select * from t t1 where not exists (select 1 from t t2 where t2.n<10 and mod(power(10,t2.n),t1.n) = 0))
,t2 as (select t1.n n1, t2.n n2, 1/t1.n, 1000*(power(10, t2.n)-1)/(t1.n) , mod(power(10, t2.n)/t1.n,1)
from t1 t1, t t2
where   t2.n<100 and mod((power(10, t2.n)-1)/(t1.n),0.001) = 0
)
--select * from t2
select n1, min(n2) from t2  group by n1 order by n1


        N1    MIN(N2)
---------- ----------
         3          1
         6          1
         7          6
         9          1
        11          2
        12          1
        13          6
        14          6
        15          1
        17         16
        18          1
        19         18

12 rows selected

SQL>

tree_new_bee

为了解决这个问题，在大数包里添加一个新成员pkg_bignum.bigrecip,
参数是分母(普通number)和要求的精度， 返回值是大精度字符串。

  function bigrecip(d1 number, prec number) return varchar2 is
    result varchar2(4000);
    a integer;
    b integer;
    p integer;
  begin
    if d1<=1 then return '1'; end if;
    a := 0; b:=1;
    result:='0.';
    p:=0;   
   while b>0 loop
       b:= b*10;
       a:= floor(b/d1);
       b:= mod(b, d1);      
       result:=result||a;
       p:=p+1;
       if p> prec then exit; end if;
    end loop;
    return result;
  end;


利用这个函数的结果，可以通过字符串比较的方式来做了。

with tpos as (select rownum pos from dual connect by rownum<=1000)
,t as (select /*+ RESULT_CACHE  */ pos n,  pkg_bignum.bigrecip(pos, 3900) str from tpos where mod(pos,2)>0 and mod(pos,5)>0)
,t1 as (select n, str, case when substr(str, 20) is null then 0 else pos end pos,
substr(str, 20, 2000) str1, substr(str, pos+20,2000) str2
from t, tpos  
where (substr(str, 20, 2000) = substr(str, pos+20,2000) ) or (substr(str, 20) is null)
)
--select * from t1
,t2 as (select n, min(pos) num  from t1 group by n)
select * from t2 where num = (select max(num) from t2)

         N        NUM
---------- ----------
       983        982

Executed in 28.484 seconds

SQL>


性能不太理想。 但这个题能做出来就已经很知足了。 本来已经准备跳过此题的。
好在题目要求的是1000以内， 要是范围再大点， SQL的Varchar2都负担不起了， 那就只能纯粹plsql了。

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

newkid

q26 OO有个精彩解法：
http://www.itpub.net/thread-1364272-8-1.html
Q24我也有个简单写法，奇怪的是答案有一位和你不同，等下周有空了好好检查一下。

tree_new_bee

原帖由 newkid 于 2010-12-19 11:05 发表
q26 OO有个精彩解法：
http://www.itpub.net/thread-1364272-8-1.html

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

tree_new_bee

看了一下问题贴中别人的写法，很多没看明白。
用excel观察了一下，才算找出规律：

比如对于17来说：

余数        商
1       
10        0
15        5
14        8
4        8
6        2
9        3
5        5
16        2
7        9
2        4
3        1
13        1
11        7
8        6
12        4
1        7
10        0
15        5
14        8
4        8
6        2
9        3
5        5
16        2
7        9

在循环小数部分， 商的部分可能会有重复， 但余数不可能重复（余数只要重复，必然意味着后续序列重复）

btw: 由这个可以得到一个推论： 任何数的倒数的循环长度，都不可能超过这个数本身。

用这个思路， 就变的容易多了。


with tnum as (select rownum num from dual connect by rownum<=1000)
--with tnum as (select 7 num from dual )
, t(r, n,a, path, len) as (
select 0, num, 1, cast (',' as varchar2(4000)), 0 from tnum where mod(num,2)>0 and mod(num,5)>0
union all
select
r+1,
n,
mod(10*a,n),
case when r< least(20,n)   then path else path||a||',' end,    --假设非循环部分不超过20位， 为了怕遗漏也可以再加大， 越大性能越差。
case when substr(path, 2,instr(path, ',',2)-2) = a
  then length(translate(path,',1234567890', ','))-1
  else 0 end
from t where r<n+20 and len = 0)
, tresult as (select  * from t where len>0 )
select n, len from tresult where len = (select max(len) from tresult)


         N        LEN
---------- ----------
       983        982

Executed in 1.375 seconds


同样的思路，改成plsql会更快。就不贴了。

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

tree_new_bee

Q27 Find a quadratic formula that produces the maximum number of primes for consecutive values of n.

Euler published the remarkable quadratic formula:

n² + n + 41

It turns out that the formula will produce 40 primes for the consecutive values n = 0 to 39. However, when n = 40, 40^(2) + 40 + 41 = 40(40 + 1) + 41 is divisible by 41, and certainly when n = 41, 41² + 41 + 41 is clearly divisible by 41.

Using computers, the incredible formula  n² − 79n + 1601 was discovered, which produces 80 primes for the consecutive values n = 0 to 79. The product of the coefficients, −79 and 1601, is −126479.

Considering quadratics of the form:

    n² + an + b, where |a| < 1000 and |b| < 1000

    where |n| is the modulus/absolute value of n
    e.g. |11| = 11 and |−4| = 4

Find the product of the coefficients, a and b, for the quadratic expression that produces the maximum number of primes for consecutive values of n, starting with n = 0.