Euler Project 挨个做- 之二 (Q51-Q78)

tree_new_bee · 发表于 2011-1-9 14:10

Q68 What is the maximum 16-digit string for a "magic" 5-gon ring?

Consider the following "magic" 3-gon ring, filled with the numbers 1 to 6, and each line adding to nine.

Working clockwise, and starting from the group of three with the numerically lowest external node (4,3,2 in this example), each solution can be described uniquely. For example, the above solution can be described by the set: 4,3,2; 6,2,1; 5,1,3.

It is possible to complete the ring with four different totals: 9, 10, 11, and 12. There are eight solutions in total.
Total Solution Set
9 4,2,3; 5,3,1; 6,1,2
9 4,3,2; 6,2,1; 5,1,3
10 2,3,5; 4,5,1; 6,1,3
10 2,5,3; 6,3,1; 4,1,5
11 1,4,6; 3,6,2; 5,2,4
11 1,6,4; 5,4,2; 3,2,6
12 1,5,6; 2,6,4; 3,4,5
12 1,6,5; 3,5,4; 2,4,6

By concatenating each group it is possible to form 9-digit strings; the maximum string for a 3-gon ring is 432621513.

Using the numbers 1 to 10, and depending on arrangements, it is possible to form 16- and 17-digit strings. What is the maximum 16-digit string for a "magic" 5-gon ring?

tree_new_bee · 发表于 2011-1-9 14:14

为了解题方便，给图中的位置进行编号：

然后堆条件就是了， 10个表的关联看起来很可怕，可是加上一堆条件后还是能很快就出来的。

with t as (select rownum n from dual connect by rownum<=10)
,t1 as (select t1.n+ t2.n+t6.n tot,
t6.n||t1.n||t2.n||t7.n||t2.n||t3.n||t8.n||t3.n||t4.n ||t9.n||t4.n||t5.n ||t10.n||t5.n||t1.n str,
t1.n, t2.n, t3.n, t4.n, t5.n,t6.n, t7.n, t8.n, t9.n, t10.n
from t t1, t t2, t t3, t t4, t t5, t t6,t t7, t t8, t t9, t t10
where t6.n<t7.n and t6.n<t8.n and t6.n<t9.n and t6.n<t10.n
and t1.n not in ( t2.n, t3.n, t4.n, t5.n,t6.n, t7.n, t8.n, t9.n, t10.n)
and t2.n not in ( t3.n, t4.n, t5.n,t6.n, t7.n, t8.n, t9.n, t10.n)
and t3.n not in ( t4.n, t5.n,t6.n, t7.n, t8.n, t9.n, t10.n)
and t4.n not in ( t5.n,t6.n, t7.n, t8.n, t9.n, t10.n)
and t5.n not in ( t6.n, t7.n, t8.n, t9.n, t10.n)
and t6.n not in ( t7.n, t8.n, t9.n, t10.n)
and t7.n not in ( t8.n, t9.n, t10.n)
and t8.n not in ( t9.n, t10.n)
and t9.n not in ( t10.n)
and t1.n+ t2.n+t6.n = t2.n+t3.n+t7.n
and t1.n+ t2.n+t6.n = t3.n+t4.n+t8.n
and t1.n+ t2.n+t6.n = t4.n+t5.n+t9.n
and t1.n+ t2.n+t6.n = t5.n+t1.n+t10.n
and length(t6.n||t1.n||t2.n||t7.n||t2.n||t3.n||t8.n||t3.n||t4.n ||t9.n||t4.n||t5.n ||t10.n||t5.n||t1.n ) = 16
)
select max(str) from t1

MAX(STR)
--------------------------------------------------------------------------------
6531031914842725

Executed in 16.359 seconds

tree_new_bee · 发表于 2011-1-9 14:29

取其中的16位串，在上面用了and length(t6.n||t1.n||t2.n||t7.n||t2.n||t3.n||t8.n||t3.n||t4.n ||t9.n||t4.n||t5.n ||t10.n||t5.n||t1.n ) = 16

其实用下面的方法更有效：
内圈的数字都会用两次。所以要使字串为16位，意为着10不能出现在内圈里。
因此可以把上面的条件改为：
and 10 not in ( t1.n, t2.n, t3.n, t4.n, t5.n)

这样修改后，时间为12秒，略快一些。

tree_new_bee · 发表于 2011-1-9 14:46

connect by 查询写起来简洁，但因为条件不容易控制，效率总是差些。

with t as (select rownum n from dual connect by rownum<=10)
,t1 as (select replace(sys_connect_by_path(to_char(n,'FM00'),'/'),'/','') str from t where level=10 connect by nocycle level<=10 and n <> prior n)
,t2 as (select substr(str, 1,2) n1, substr(str, 3,2) n2, substr(str, 5,2) n3, substr(str, 7,2) n4, substr(str, 9,2) n5,
substr(str, 11,2) n6, substr(str, 13,2) n7, substr(str, 15,2) n8, substr(str, 17,2) n9, substr(str, 19,2) n10
from t1）
select max((n6+0)||(n1+0)||(n2+0)||(n7+0)||(n2+0)||(n3+0)||(n8+0)||(n3+0)||(n4+0) ||(n9+0)||(n4+0)||(n5+0)||(n10+0)||(n5+0)||(n1+0)) str
from t2
where n6<n7 and n6<n8 and n6<n9 and n6<n10
and n6+n1+n2 = n7+n2+n3
and n6+n1+n2 = n8+n3+n4
and n6+n1+n2 = n9+n4+n5
and n6+n1+n2 = n10+n5+n1
and 10 not in (n1,n2,n3,n4,n5)

STR
--------------------------------------------------------------------------------
6531031914842725

Executed in 130.844 seconds

在connect 过程能够略加干预之处，是可以限制n7>n6，将connect by条件改为：
connect by nocycle level<=10 and n <> prior n and n>case when level=7 then prior n else 0 end )
可以使时间缩短到96秒。再进一步改善就想不出办法了。

[ 本帖最后由 tree_new_bee 于 2011-1-9 17:02 编辑 ]

tree_new_bee · 发表于 2011-1-9 17:17

Q69 Find the value of n ≤ 1,000,000 for which n/φ(n) is a maximum.

Euler's Totient function, φ(n) [sometimes called the phi function], is used to determine the number of numbers less than n which are relatively prime to n. For example, as 1, 2, 4, 5, 7, and 8, are all less than nine and relatively prime to nine, φ(9)=6.
n Relatively Prime φ(n) n/φ(n)
2 1 1 2
3 1,2 2 1.5
4 1,3 2 2
5 1,2,3,4 4 1.25
6 1,5 2 3
7 1,2,3,4,5,6 6 1.1666...
8 1,3,5,7 4 2
9 1,2,4,5,7,8 6 1.5
10 1,3,7,9 4 2.5

It can be seen that n=6 produces a maximum n/φ(n) for n ≤ 10.

Find the value of n ≤ 1,000,000 for which n/φ(n) is a maximum.

[ 本帖最后由 tree_new_bee 于 2011-1-9 17:42 编辑 ]

tree_new_bee · 发表于 2011-1-9 17:42

这题，不用试，凭感觉就知道一个一个去求互质数的数目是行不通的。
不说求一个数的互质数的数目本身就很复杂，即使是个相对简单的计算，循环100万次都是不太可能能接受的。

与21题一样，先在小范围数字内找规律，看看每次n/φ(n) 创新高的n是些什么数：

with t as (select rownum n from dual connect by rownum<=300)
,t1 as (select t1.n n1, t2.n n2 from t t1, t t2
where t2.n<t1.n
and not exists (select 1 from t t3 where t3.n>1 and mod(t1.n, t3.n) = 0 and mod(t2.n, t3.n)=0))
,t2 as (select n1, count(*) cnt , n1/count(*) ratio, max(n1/count(*)) over (order by n1) maxratio from t1 group by n1)
select min(n1), ratio from t2 where ratio = maxratio group by ratio order by ratio

MIN(N1)    RATIO
---------- ----------
      2       2
      6       3
      30    3.75
   210    4.375

Executed in 7.313 seconds

ok, 大概看出规律了： 6=2*3, 30=2*3*5, 210=2*3*5*7, 每个创新高的数字都是最小的几个连续质数的乘积。
虽然不知道如何证明这个规律是正确的(估计证明本身也超出了我的数学知识范围了)，但就这么用了。(做出来的答案先蒙一把，不对的话再想办法

)

另外，从300个数就要7秒来看，上面说的逐个计算行不通是肯定的。

with t as (select column_value n from table(pkg_prim2.seive_numlist_nk(100)))
,t1 as (select n, power(10,sum(log(10,n)) over(order by n)) p  from t )
select max(n), max(p) from t1 where p<=1000000

MAX(N)    MAX(P)
---------- ----------
      17    510510

Executed in 0.063 seconds

结果证明，答案是正确的。

tree_new_bee · 发表于 2011-1-9 19:46

Q70 Investigate values of n for which φ(n) is a permutation of n.

Euler's Totient function, φ(n) [sometimes called the phi function], is used to determine the number of positive numbers less than or equal to n which are relatively prime to n. For example, as 1, 2, 4, 5, 7, and 8, are all less than nine and relatively prime to nine, φ(9)=6.
The number 1 is considered to be relatively prime to every positive number, so φ(1)=1.

Interestingly, φ(87109)=79180, and it can be seen that 87109 is a permutation of 79180.

Find the value of n, 1 < n < 10^(7), for which φ(n) is a permutation of n and the ratio n/φ(n) produces a minimum.

tree_new_bee · 发表于 2011-1-9 20:20

不像69, 70不能那么投机取巧了。这次真的要计算φ(n)的具体数字了。
wiki上可以搜到φ(n)的计算方法：
http://zh.wikipedia.org/zh-cn/%E ... 9%E5%87%BD%E6%95%B0

简单的说，就是对于p^k,p是质数：  phi(p^k) = (p-1)*p^(k-1)
对于其它数： phi(m*n) = phi(m)*phi(n)

有了这个方法，虽说计算简单了，但因为每个数都要进行质因数分解，对于10^7来说，依然是无法容忍的。
因此，仍然需要做大量的人肉工作。

如果不考虑phi(n)是n的排列，只考虑n/phi(n)最小，也就是对于n来说phi(n)最大，那么显然n一定是质数，并且是10^7内最大的质数。这样n/phi(n) = n/(n-1)

但是， n与n-1肯定不会是互相排列。
但据此所以我们可以设想：要让n/phi(n)比较小，那么一定是质因数分解的因子数越少越好, 因此我们可以假设n为两个质数的乘积。

对于两个质数的积来说：分两种情况：
两个质数不同：则phi(p*q) = (p-1)*(q-1)
两个质数相同：则phi(p*p) = (p-1)*p
可以看出两个数p,q相差越小，则phi(p,q)越大，如果两个数相同，则更大。

所以可以先从两个相同质数(即质数的平方数)入手测试：

and       TRANSLATE(p*p,'0123456789','0')||
   TRANSLATE(p*p,'1023456789','1')||
   TRANSLATE(p*p,'2013456789','2')||
   TRANSLATE(p*p,'3012456789','3')||
   TRANSLATE(p*p,'4012356789','4')||
   TRANSLATE(p*p,'5012346789','5')||
   TRANSLATE(p*p,'6012345789','6')||
   TRANSLATE(p*p,'7012345689','7')||
   TRANSLATE(p*p,'8012345679','8')||
   TRANSLATE(p*p,'9012345678','9')
   =
   TRANSLATE(p*(p-1),'0123456789','0')||
   TRANSLATE(p*(p-1),'1023456789','1')||
   TRANSLATE(p*(p-1),'2013456789','2')||
   TRANSLATE(p*(p-1),'3012456789','3')||
   TRANSLATE(p*(p-1),'4012356789','4')||
   TRANSLATE(p*(p-1),'5012346789','5')||
   TRANSLATE(p*(p-1),'6012345789','6')||
   TRANSLATE(p*(p-1),'7012345689','7')||
   TRANSLATE(p*(p-1),'8012345679','8')||
   TRANSLATE(p*(p-1),'9012345678','9')

      P       N       PHI    RATIO
---------- ---------- ---------- ----------

Executed in 0.109 seconds

遗憾的是，这里没有找到符合n与phi(n)互为排列的情况。

tree_new_bee · 发表于 2011-1-9 20:45

因此，接下来要实验的是两个不同质数的乘积。

with tp as (select column_value p from table(pkg_prim2.seive_numlist_nk(5E6)))
,t1 as (select /*+ MATERIALIZE */ tp1.p p1, tp2.p p2, tp1.p*tp2.p n, (tp1.p-1)*(tp2.p-1) phi,
(tp1.p*tp2.p)/ ((tp1.p-1)*(tp2.p-1)) ratio
from tp tp1, tp tp2
where tp2.p < 1E7/tp1.p and tp2.p<tp1.p)
,t2 as (select /*+ MATERIALIZE */ p1,p2, n, phi,ratio
from t1
where  TRANSLATE(n,'0123456789','0')||
   TRANSLATE(n,'1023456789','1')||
   TRANSLATE(n,'2013456789','2')||
   TRANSLATE(n,'3012456789','3')||
   TRANSLATE(n,'4012356789','4')||
   TRANSLATE(n,'5012346789','5')||
   TRANSLATE(n,'6012345789','6')||
   TRANSLATE(n,'7012345689','7')||
   TRANSLATE(n,'8012345679','8')||
   TRANSLATE(n,'9012345678','9')
   =
   TRANSLATE(phi,'0123456789','0')||
   TRANSLATE(phi,'1023456789','1')||
   TRANSLATE(phi,'2013456789','2')||
   TRANSLATE(phi,'3012456789','3')||
   TRANSLATE(phi,'4012356789','4')||
   TRANSLATE(phi,'5012346789','5')||
   TRANSLATE(phi,'6012345789','6')||
   TRANSLATE(phi,'7012345689','7')||
   TRANSLATE(phi,'8012345679','8')||
   TRANSLATE(phi,'9012345678','9') )
select * from t2 where ratio = (select min(ratio) from t2)

      P1       P2       N       PHI    RATIO
---------- ---------- ---------- ---------- ----------
   3557    2339 8319823 8313928 1.00070905

Executed in 94.109 seconds

很幸运， 8319823这个结果是正确答案。乌拉～

〇〇 · 发表于 2011-1-9 21:06

tnb真强，一天做那么多题。