Project Euler解题汇总(更新至309在1楼)

lastwinner

问题12 What is the value of the first triangle number to have over five hundred divisors?
The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:

1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28
We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?


这个题可以和问题179一起做出，但用你的算法，感觉可以更快捷的逼近正确答案
9个不同的质因子构成的数，其因子总数是2^9=512>500
但2、3、5、7、11、13、17、19、23这9个数的乘积太大了
19*23比(2*3^2)*(2^3*3)还大了，用后者替换前者，则产生的数小了一点，并且因子数增多了不少：
2^5、3^4、5、7、11、13、17的因子数为(5+1)*(4+1)*(1+1)*(1+1)*(1+1)*(1+1)*(1+1)=960
2减少2个，3减少1个，这样形成的数是原来的1/12，其因子数是512（2^3、3^3、5、7、11、13、17）
此时若将17替换为2^4，则结果进一步减小，因子数还是512（2^7、3^3、5、7、11、13）
继续减小乘积，2减少1个，3减少1个，5增加一个，结果再度减小，因子数为512*(6+1)/(7+1)*(2+1)/(3+1)*(2+1)/(1+1)=504
(2^6、3^2、5^2、7、11、13)
再往下无法获得更小的还具有500个以上因子的数了
这个数是43243200

于是就从这个数开始找，找到第一满足条件的三角数为止
sqrt(43243200*2)>9299，故而依据连续自然数的公式S(n)=n*(n+1)/2，n从9300开始找即可

lastwinner

Problem 35
17 January 2003

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?

问题35：环绕质数
一个质数，各位数字围成一个有向圆圈，按顺序，无论从哪个数字开始，都能组成一个质数，那这个质数就是环绕质数。比如197、971和719就是这样一组环绕质数
100以内的环绕质数已知的有：2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79 和97共13个
问100万以内这样的环绕质数有多少个？

1、建个100万之内的质数表：
CREATE TABLE PRIME_1M(  PN  NUMBER);
insert/*+ Append*/ into prime_1M WITH t AS (
    SELECT 2*ROWNUM+1 rn FROM DUAL CONNECT BY ROWNUM <= (1000000)/2-1-1
    )
select pn from (
SELECT rn AS pn from t
MINUS
SELECT t1.rn * t2.rn  FROM t t1, t t2
WHERE t1.rn <= t2.rn AND t1.rn < 1000   AND t1.rn * t2.rn <1000000
UNION
SELECT 2 FROM DUAL)
/


2、求解
with c1 as (select pn from prime_1m where pn>100  and  pn=regexp_substr(pn, '[1379]*')), --包含024568的数肯定不可能是circular prime
l as (select rownum rn from dual connect by rownum<=6), --1M以内的质数，最长也就是6位了。除了自身外，最多还可能有5个不一样的circular prime
cc as (select pn,  substr(pn,rn+1)||substr(pn,1,rn) cpn from c1, l where rn<=length(pn)), --求出一个prime的所有circular prime
cc2 as (select pn, min(cpn) mincpn, count(distinct cpn) cpncntd, count(*) cpncnt from cc group by pn) --求出一个质数对应的最小circular prime
select mincpn, sum(count(*))over() from cc2 group by mincpn having count(*)=min(cpncntd) -- 其实和 max(cpncnt) 的值一样，我只是担心在环绕过程中出现重复的数字，这会导致最后计算结果有误，不过后来琢磨了一下，这种现象不应该出现，如果出现，那这个数字一定不是质数
/


MINCPN     SUM(COUNT(*))OVER()
---------- -------------------
113                         42
1193                        42
11939                       42
193939                      42
197                         42
199                         42
19937                       42
199933                      42
337                         42
3779                        42

10 rows selected.

这里只求出了100以上的，100以内的已经在题目中说过了
所以，最终结果是 42＋13＝55个环绕质数

[ 本帖最后由 lastwinner 于 2010-11-14 22:13 编辑 ]

〇〇

好整齐的积分
lastwinner
路边野花不要，踩！
世本冇谱，靠者多便有



精华贴数 19
个人空间 1050
技术积分 49999 (21)
社区积分 30000 (51)
注册日期 2002-11-27
论坛徽章:328

lastwinner

Problem 17
17 May 2002

If the numbers 1 to 5 are written out in words: one, two, three, four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.
If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?

NOTE: Do not count spaces or hyphens. For example, 342 (three hundred and forty-two) contains 23 letters and 115 (one hundred and fifteen) contains 20 letters. The use of "and" when writing out numbers is in compliance with British usage.


问题17：就是1～1000按英文表示后，总共有多少个字母，空格和连字符不要计算在内，比如342 (three hundred and forty-two) 包含23个字母， 115 (one hundred and fifteen) 包含20个字母.

这题要用sql来做，也就是最后当计算器来用了
还是上excel吧

100之内，1～9要出现9轮，只有在11～19范围内不出现。1000之内就总共出现9×10＝90轮，再加上百位前出现的100轮，总共是190轮
100之内，11～19仅出现1轮，1000之内就总共出现1×10＝10轮
100之内，20、30～90要出现10轮，1000之内就总共出现10×10＝100轮
hundred 从100～999都要出现，总共出现900次
one thousand 只出现一次
and 超过100才会出现，并且整百不会出现，于是总共出现891次

最终答案 21124

lastwinner

原帖由 〇〇 于 10-11-14 21:35 发表
好整齐的积分
lastwinner
路边野花不要，踩！
世本冇谱，靠者多便有



精华贴数 19
个人空间 1050
技术积分 49999 (21)
社区积分 30000 (51)
注册日期 2002-11-27
论坛徽章:328

49999，29999的贴图在这里 http://www.itpub.net/thread-1368065-1-1.html ，9楼

newkid

问题12, 因为500=5X5X5X2X2, 所以最多有5个质数因子，N=A^4*B^4*C^4*D*E

如果四个质数因子，则可能为 N=A^4*B^4*C^4*D^3, 或者N=A^4*B^4*C^9*D, 或者 N=A^24*B*4*C*D,

如果三个则......写起来挺多的。

X^2+X = 2*N 有整数解，则SQRT(2*N+0.25)-0.5 是整数。把质数分别代入以上公式看看能不能得到整数解。

newkid

问题11, 以前我看过这个：

SELECT initcap(to_char(to_timestamp(substr(lpad(abs(123456789), 9, '0'),
                                           1,
                                           3),
                                    'FF3'),
                       'FFSP') || ' ' ||
               to_char(to_timestamp('000' ||
                                    substr(lpad(abs(123456789), 9, '0'), 4),
                                    'FF9'),
                       'FFSP'))
  FROM dual;

--output
One Hundred Twenty-Three Million Four Hundred Fifty-Six Thousand Seven Hundred Eighty-Nine

经过一番TO_TIMESTAMP, TO_CHAR, 就能变成英文数字。但它没有AND.

lastwinner

原帖由 newkid 于 10-11-15 06:08 发表
问题12, 因为500=5X5X5X2X2, 所以最多有5个质数因子，N=A^4*B^4*C^4*D*E

如果四个质数因子，则可能为 N=A^4*B^4*C^4*D^3, 或者N=A^4*B^4*C^9*D, 或者 N=A^24*B*4*C*D,

如果三个则......写起来挺多的。

X^2+X = 2*N 有整数解，则SQRT(2*N+0.25)-0.5 是整数。把质数分别代入以上公式看看能不能得到整数解。

题目用词是over，也就是超过

原帖由 newkid 于 10-11-15 06:13 发表
问题11, 以前我看过这个：

SELECT initcap(to_char(to_timestamp(substr(lpad(abs(123456789), 9, '0'),
                                           1,
                                           3),
                                    'FF3'),
                       'FFSP') || ' ' ||
               to_char(to_timestamp('000' ||
                                    substr(lpad(abs(123456789), 9, '0'), 4),
                                    'FF9'),
                       'FFSP'))
  FROM dual;

--output
One Hundred Twenty-Three Million Four Hundred Fifty-Six Thousand Seven Hundred Eighty-Nine

经过一番TO_TIMESTAMP, TO_CHAR, 就能变成英文数字。但它没有AND.

以前开发版也有过，格式记得是跟 J 有关
搜了一下，搜到你看到的那个帖了 http://www.itpub.net/viewthread.php?tid=1020486
还有你回答别人的帖： http://www.itpub.net/viewthread. ... har%2B%27%27J%27%27
较早的出处在这里： http://www.itpub.net/419197.html


没有and其实没关系，这很容易处理的，用正则替换就可以了

〇〇

Problem 310
13 November 2010


Alice and Bob play the game Nim Square.
Nim Square is just like ordinary three-heap normal play Nim, but the players may only remove a square number of stones from a heap.
The number of stones in the three heaps is represented by the ordered triple (a,b,c).
If 0<=a<=b<=c<=29 then the number of losing positions for the next player is 1160.

Find the number of losing positions for the next player if 0<=a<=b<=c<=100 000.

〇〇

The classic game of Nim ( http://www.zhipingyou.com/qqsh/index.php?topic=146.0 ) is a two-player game defined as follows:

There are N piles of stones (usually 3 piles with 3, 5, and 7 stones). In each turn, the player can take any number (>= 1) of stones, but from one pile only. The player that gets the last stone wins the game.

The Square Nim is a variation in which you can only take a perfect square number of stones, such as 1, 4, 9, 16, .... Because 1 is allowed, the game will always end.

a) What is the winning move if the initial state is [2, 9] (Two piles with 2 and 9 stones)?
b) What is the winning move if the initial state is [3, 5, 7]?
c) What is the winning move if the initial state is [23, 25, 28]?

This game is another example of a whole class of games, which include the bowling game ( http://www.zhipingyou.com/qqsh/index.php?topic=215.0 , officially known as the game of kayles), that can be solved by the Nim based theory.