Project Euler Problem 276, 268, 347

〇〇

newkid 发表于 2012-1-8 11:54
#347, 相当于一个斜面 z=x*lg1+y*lg2, 找出正整数坐标(x,y)在这个面上的投影，其中最靠近天花板 z=log(n)的 ...

都没看懂，汗ing

〇〇

Problem 366
07 January 2012


Two players, Anton and Bernhard, are playing the following game.
There is one pile of n stones.
The first player may remove any positive number of stones, but not the whole pile.
Thereafter, each player may remove at most twice the number of stones his opponent took on the previous move.
The player who removes the last stone wins.

E.g. n=5
If the first player takes anything more than one stone the next player will be able to take all remaining stones.
If the first player takes one stone, leaving four, his opponent will take also one stone, leaving three stones.
The first player cannot take all three because he may take at most 2x1=2 stones. So let's say he takes also one stone, leaving 2. The second player can take the two remaining stones and wins.
So 5 is a losing position for the first player.
For some winning positions there is more than one possible move for the first player.
E.g. when n=17 the first player can remove one or four stones.

Let M(n) be the maximum number of stones the first player can take from a winning position at his first turn and M(n)=0 for a losing position.

E M(n) for n<=100 is 728.

Find E M(n) for n<=10^18. Give your answer modulo 10^8.

lastwinner

〇〇 发表于 2012-1-8 07:50
全都加上索引也没用，本来是个全表扫描操作
SQL> create index p2mp on p2(mp);

这个倒是，本来就是全扫
不过我觉得是你方法没用对，这个时候用pl/sql来处理更好，只要有能除尽的就第一时间可以判定了
268这个题的思路应该是用pl/sql这个工具去做，sql不能提前退出一些无用的循环，会浪费计算力

lastwinner

268我有个思路
1、10^16里，找出所有的素数
2、筛掉数字1、所有素数、所有单个素数的n次方，所有两个素数X、Y的power(X,n)*power(Y,m)，所有三个素数的power(X,n)*power(Y,m)*power(Z,o)。m、n、o均为大于等于1的正整数，并且结果不超过10^16
3、计算筛掉的数字有多少，相减即可得到满足条件的素数


若按〇〇的思路，四个素数相乘，再找倍数，则难以消除重复的数
newkid提及的对数法，能一定程度上简化计算量，但在达到临界点时，难以判断是否超出10^16，还需要再次做乘法去验算

〇〇

1、10^16里，找出所有的素数
不现实 http://tieba.baidu.com/f?kz=817417199

newkid

#347 用PLSQL效果还可以：
DECLARE
   TYPE t_num IS TABLE OF NUMBER;

   V_RESULT t_num:=t_num();
   I NUMBER DEFAULT 1;
   J NUMBER DEFAULT 0;
   lv_sum NUMBER :=0;
   
   lv_limit NUMBER := 1E7;
   
   lv_upper1 NUMBER := (SQRT(lv_limit/2)-1)/2;
   lv_upper2 NUMBER := CEIL(lv_limit/2/2-1);
   lv_step BINARY_INTEGER;
   
   TYPE t_prime IS RECORD (
        pn NUMBER,lg NUMBER
        );
   TYPE t_primes IS TABLE OF t_prime;
   lv_primes t_primes := t_primes();

   lv_lg number := LOG(10,lv_limit);
   
BEGIN
    v_result.EXTEND(lv_upper2);

    while i<lv_upper1 loop
          lv_step := i*2+1;
          j:=2*i*(i+1);
          while j<=lv_upper2 loop
                v_result.DELETE(j);
                j:=j+lv_step;
          end loop;
          i := v_result.NEXT(i);
    end loop;

   
    lv_primes.EXTEND;
    lv_primes(1).pn:=2;
    lv_primes(1).lg:=LOG(10,2);

    for j in 1 .. lv_upper2 loop
        if v_result.EXISTS(j) then
           lv_primes.EXTEND;
           lv_primes(lv_primes.COUNT).pn:=j*2+1;
           lv_primes(lv_primes.COUNT).lg:=LOG(10,j*2+1);
        end if;
    end loop;

    FOR i IN 1..lv_primes.COUNT LOOP
        EXIT WHEN lv_primes(i).lg + lv_primes(i+1).lg >lv_lg ;
        FOR j IN i+1..lv_primes.COUNT LOOP
            EXIT WHEN lv_primes(i).lg + lv_primes(j).lg >lv_lg ;
        
            SELECT lv_sum+MAX(POWER(lv_primes(i).pn,FLOOR(ROUND((lv_lg-LEVEL*lv_primes(j).lg)/lv_primes(i).lg,30)))*POWER(lv_primes(j).pn,LEVEL))
              INTO lv_sum
            FROM DUAL
            CONNECT BY LEVEL<=FLOOR((lv_lg-lv_primes(i).lg)/lv_primes(j).lg);
        
        END LOOP;
    END LOOP;

    DBMS_OUTPUT.PUT_LINE('sum='||lv_sum);
END;
/

sum=11109800204052

PL/SQL procedure successfully completed.

Elapsed: 00:01:28.33

上一帖我是试图将其图形化，结果变成故弄玄虚。其实就是求 x*lg1+y*lg2 <= log(N) 在(X,Y)为正整数时的最大值。

〇〇

newkid 发表于 2012-1-9 02:20
#347 用PLSQL效果还可以：
DECLARE
   TYPE t_num IS TABLE OF NUMBER;

nice，不在嵌套循环中访问表的说法看来也不绝对。。。

〇〇

〇〇 发表于 2012-1-8 21:40
1、10^16里，找出所有的素数
不现实 http://tieba.baidu.com/f?kz=817417199

素数定理描述素数的大致分布情况。
素数的出现规律一直困惑着数学家。一个个地看，素数在正整数中的出现没有什么规律。可是总体地看，素数的个数竟然有规可循。对正实数x，定义π(x)为不大于x的素数个数。数学家找到了一些函数来估计π(x)的增长。以下是第一个这样的估计。
其中ln x为x的自然对数。上式的意思是当x趋近∞，π(x)与x/ln x的比值趋近1。但这不表示它们的数值随着x增大而接近。
下面是对π(x)更好的估计：
，当x 趋近∞。 其中（对数积分），而关系式右边第二项是误差估计，详见大O符号。
下表比较了π(x)，x/ln x和Li(x)：

x	π(x)[1]	π(x) − x / ln x[2]	π(x) / (x / ln x)	li(x) − π(x)[3]	x / π(x)
10	4	−0.3	0.921	2.2	2.500
102	25	3.3	1.151	5.1	4.000
103	168	23	1.161	10	5.952
104	1,229	143	1.132	17	8.137
105	9,592	906	1.104	38	10.425
106	78,498	6,116	1.084	130	12.740
107	664,579	44,158	1.071	339	15.047
108	5,761,455	332,774	1.061	754	17.357
109	50,847,534	2,592,592	1.054	1,701	19.667
1010	455,052,511	20,758,029	1.048	3,104	21.975
1011	4,118,054,813	169,923,159	1.043	11,588	24.283
1012	37,607,912,018	1,416,705,193	1.039	38,263	26.590
1013	346,065,536,839	11,992,858,452	1.034	108,971	28.896
1014	3,204,941,750,802	102,838,308,636	1.033	314,890	31.202
1015	29,844,570,422,669	891,604,962,452	1.031	1,052,619	33.507
1016	279,238,341,033,925	7,804,289,844,393	1.029	3,214,632	35.812
1017	2,623,557,157,654,233	68,883,734,693,281	1.027	7,956,589	38.116
1018	24,739,954,287,740,860	612,483,070,893,536	1.025	21,949,555	40.420
1019	234,057,667,276,344,607	5,481,624,169,369,960	1.024	99,877,775	42.725
1020	2,220,819,602,560,918,840	49,347,193,044,659,701	1.023	222,744,644	45.028
1021	21,127,269,486,018,731,928	446,579,871,578,168,707	1.022	597,394,254	47.332
1022	201,467,286,689,315,906,290	4,060,704,006,019,620,994	1.021	1,932,355,208	49.636
1023	1,925,320,391,606,803,968,923	37,083,513,766,578,631,309	1.020	7,250,186,216	51.939

素数定理可以给出第n个素数p（n）的渐近估计：
它也给出从整数中抽到素数的概率。从不大于n的自然数随机选一个，它是素数的概率大约是1/ln n。
这定理的式子于1798年法国数学家勒让德提出。1896年法国数学家雅克·阿达马和比利时数学家Charles Jean de la Vallée-Poussin先后独立给出证明。证明用到了复分析，尤其是黎曼ζ函数。
因为黎曼ζ函数与π(x)关系密切，关于黎曼ζ函数的黎曼猜想对数论很重要。一旦猜想获证，便能大大改进素数定理误差的估计。1901年瑞典数学家Helge von Koch证明出，假设黎曼猜想成立，以上关系式误差项的估计可改进为
至于大O项的常数则还未知道。
[编辑] 初等证明素数定理有些初等证明只需用数论的方法。第一个初等证明于1949年由匈牙利数学家保罗·艾狄胥和挪威数学家阿特利·西尔伯格合作得出。
在此之前一些数学家不相信能找出不需借助艰深数学的初等证明。像英国数学家哈代便说过素数定理必须以复分析证明，显出定理结果的“深度”。他认为只用到实数不足以解决某些问题，必须引进复数来解决。这是凭感觉说出来的，觉得一些方法比别的更高等也更厉害，而素数定理的初等证明动摇了这论调。Selberg－艾狄胥的证明正好表示，看似初等的组合数学，威力也可以很大。 但是，有必要指出的是，虽然该初等证明只用到初等的办法，其难度甚至要比用到复分析的证明远为困难。

^ A006880 ^ A057835
• ^ A057752
  

lastwinner

〇〇 发表于 2012-1-9 16:58
素数定理描述素数的大致分布情况。
素数的出现规律一直困惑着数学家。一个个地看，素数在正整数中的出现 ...

你贴个来源链接吧，你转也没转全，图都哪儿去了？

newkid

〇〇 发表于 2012-1-9 02:49
nice，不在嵌套循环中访问表的说法看来也不绝对。。。

我也没访问表嘛？FROM DUAL CONNECT BY只是偷懒让SQL完成循环。
这道题和SQL可以说没有关系。