ProjEuler[71]:把约简后的真分数升序排列

jimogsh

Consider the fraction, n/d, where n and d are positive integers. If n

If we list the set of reduced proper fractions for d ≤ 8 in ascending order of size, we get:

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8

It can be seen that 2/5 is the fraction immediately to the left of 3/7.

By listing the set of reduced proper fractions for d ≤ 1,000,000 in ascending order of size, find the numerator of the fraction immediately to the left of 3/7.

把约简后的真分数按升序排列，当分母不大于8时，排列为

1. 1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8

复制代码

我们说2/5是3/7“左边”的一个数字。
现在要求分母值不大于1000000,找出3/7“左边”的一个分数来。

jimogsh

其实原题要求的是找出3/7左边一个数的分子来就可以了。

1. Nearest[Select[Floor[3/7 #]/# & /@ Range[10^6] // Union, # != 3/7 &],
   
2.   3/7] // Timing

复制代码

ggggwhw

之所以你的程序运行时间长是因为你只是在写程序,却忘了[欧拉习题] 中的欧拉是个数学家,
我先说一个常识:你个富翁有不足3/7亿元(或者多于3/7亿元)钱,走进了人民公社,人民公社中每个人都有3/7亿元钱,富翁想建立一个更大的人民公社,就是吸收原来的公社成员加上自己,当然新的公社内部还是平均分配的原则,那么每加入一个人后,新的公社内部平均每人所拥有的钱就更接近3/7亿元了.换句话说,如果m/n≠3/7,那么(m+3)/(n+7)肯定要比m/n更接近3/7.很容易证明的.
于是我们在判断谁更接近3/7时无须令m/n中的n从1取到10^6,只需令n从10^6-6取到10^6即可.

1. In[7]:= Timing[
   
2. Max[Table[
   
3.    If[IntegerQ[3/7 n], (3/7 n - 1)/n, Floor[3/7 n]/n], {n,
   
4.     1000000 - 6, 1000000}]]]
   
5. 
   
6. Out[7]= {1.37694*10^-17, 428570/999997}

复制代码

或者不严密的做法:

1. In[8]:= Timing[
   
2. Max[Complement[
   
3.    Table[Floor[3/7 n ]/n, {n, 1000000 - 6, 1000000}], {3/7}]]]
   
4. 
   
5. Out[8]= {1.37694*10^-17, 428570/999997}

复制代码

如果要通用性的话还可以写成:

1. In[9]:= fenzi = 3;
   
2. fenmu = 10;
   
3. fanwei = 99999;
   
4. Timing[Max[
   
5.   Table[If[IntegerQ[fenzi/fenmu*n], (fenzi/fenmu*n - 1)/n,
   
6.     Floor[fenzi/fenmu*n]/n], {n, fanwei - fenmu + 1, fanwei}]]]
   
7. 
   
8. Out[12]= {1.37694*10^-17, 29999/99997}

复制代码

waynebuaa

这题最好是作为一个数学题来看待：
3/7>x/y，要使x/y尽可能的大，只需7x-3y=-1 ,进而有 (x,y)=(3t+2,7t+5)，取 7t+5最接近10^6就可以了........

jimogsh

3# ggggwhw 受教，感谢楼上两位。我确实没多想，只是按照题意写程序了，呵呵。

ggggwhw

我有了另外一个想法:
分子和分母均在10内的既约真分数从大往小排序后第20个数字是多少,
即:1≤m<n≤10,且m与n互质,

1. fanwei = 10;
   
2. weizhi = 20
   
3. arr = Sort[Union
   
4.    [Flatten[
   
5.     Table[m/n, {n, 2, fanwei}, {m, 1, n - 1}]]], Greater]
   
6. arr[[weizhi]]

复制代码

问题是当fanwei取到10000时,内存能存下arr吗?如果不能存下如何找到第weizhi=22222个数字呢?
还有其它方法找到这个数字吗?
我有一个用For循环实现的想法,但是For好像速度一直不高.但是For只对参数weizhi敏感,参数fanwei对其没有什么影响.