题目71：将最简真分数按照升序排列

欧拉计划 · 发表于 2015-11-5 16:21:08

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

Ordered fractions

Consider the fraction, n/d, where n and d are positive integers. If n<d and HCF(n,d)=1, it is called a reduced proper fraction.

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.

题目：

考虑分数 n/d, 其中 n 和 d 是正整数。如果 n<d 并且最大公约数 HCF(n,d)=1, 它被称作一个最简真分数。

如果我们将 d ≤ 8 的最简真分数按照大小的升序列出来，我们得到：

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 左边的第一个分数。

如果将 d ≤ 1,000,000 的真分数按照大小升序列出，3/7 左边第一个分数的分子是多少？

jerryxjr1220 · 发表于 2016-9-25 03:31:40

本帖最后由 jerryxjr1220 于 2017-10-12 10:42 编辑

i=428570, j=999997
[Finished in 0.1s]

most, mosti, mostj = 0,0,0

for j in range(1,1000001):
    i = j*3//7
    if i/j < 3/7:
        if most < i/j:
            most = i/j
            mosti = i
            mostj = j
print (f'i={mosti},j={mostj}')

愤怒的大头菇 · 发表于 2016-12-5 21:30:46

from fractions import Fraction
import math
def Prime(x):
    if x>1:
        if x==2:
            return True
        if x%2==0:
            return False
        for i in range(3,int(math.sqrt(x)+1),2):
            if x%i==0:
                return False
        return True
    return False
def Dig(x):
    list1=[]
    if Prime(x):
        list1.append(x)
    else:
        for i in range(2,int(math.sqrt(x)+1)):
            if x%i == 0:
                list1.extend([i,int(x/i)])
    return list1
def Hcf(x,y):
    if x!=y:
        if x==1:
            return True
        for each in Dig(y):
            if x%each == 0:
                return False
        return True
    
list2 = [Fraction(1,7),Fraction(2,7),Fraction(3,8)]
for i in range(4,428571):
    y = int(7*i/3)+1
    while True:
        if Hcf(i,y):
            list2.append(Fraction(i,y))
            break
        else:
            y += 1
list2.sort()
print(list2[-1])

结果：428570/999997
答案是428570

愤怒的大头菇 · 发表于 2016-12-5 21:31:45

一如既往得慢

芒果加黄桃 · 发表于 2017-1-24 16:30:05

# encoding:utf-8
# 最接近3/7的真分数   分母<1000000
from time import time
from math import sqrt
def getPrimes(n):
    primes = [True] * n
    primes[0], primes[1] = False, False
    for (i, prime) in enumerate(primes):
        if prime:
            for j in range(i * i, n, i): 
                primes[j] = False
    return [k for (k, v) in enumerate(primes) if v]
def findPrimeFactors(n, l_pr, s_pr):
    if n in s_pr:
        return [n]
    sqr_n = int(sqrt(n))
    result = list()
    for pr in l_pr:
        if n % pr == 0:
            result.append(pr)
            result.extend(findPrimeFactors(int(n / pr), l_pr, s_pr))
            break
        if pr > sqr_n:
            break
    return result
def euler071(N=1000000):
    l_primes = getPrimes(N)
    s_pr = set(l_primes)
    l_pr = [x for x in l_primes if x <= int(sqrt(N)) + 1]
    maxfz, maxfm = int(3 / 7 * N), N
    maxrt, a, b = 0, 0, 0
    for i in range(maxfz, 2, -1):
        for j in range(int(i * 7 / 3), maxfm):
            t = i / j
            if t < 3 / 7 :  # 满足题目条件
                if t > maxrt:  # 比已找到的更接近3/7
                    s_i = set(findPrimeFactors(i, l_pr, s_pr))
                    s_j = set(findPrimeFactors(j, l_pr, s_pr))
                    if not(s_i & s_j):  # 没有公共的质数因子
                        maxrt, a, b = t, i, j  
                else:
                    break          
    print(maxrt, a, b)
if __name__ == '__main__':
    start = time() 
    euler071()
    print('cost %.6f sec' % (time() - start))

0.42857128571385716 428570 999997
cost 1.133000 sec

najin · 发表于 2017-10-3 21:58:11

改写了一下，用的matlab，
成功解决
结果是
428570 999997

时间已过 0.053004 秒。
>>

永恒的蓝色梦想 · 发表于 2019-8-4 09:47:11

本帖最后由永恒的蓝色梦想于 2021-1-31 14:55 编辑

min_difference = 1
min_numerator = 0
three_div_seven = 3 / 7


for denominator in range(1000000, 0, -1):
    numerator = 3 * denominator // 7
    difference = three_div_seven - numerator / denominator

    if difference and difference < min_difference:
        min_difference = difference
        min_numerator = numerator


print(min_numerator)

debuggerzh · 发表于 2020-8-29 18:33:29

428570

Process returned 0 (0x0) execution time : 649.486 s
Press any key to continue.
效率极低……求指点

#include<algorithm>
#include<iostream>
#include<set>
using namespace std;

const int M = 1e5;
const double ub = 3.0/7;
int ct = 0;
bool prime[M];
int factor[M];
set<int> fac_n;

void euler_sieve(){
  prime[1] = false;
  for (int i = 2;i <= M;i++) prime[i] = true;

  for (int i = 2;i <= M;i++){
    if (prime[i]) factor[++ct] = i;
    for (int j = 1;j <= ct && i*factor[j] < M;j++){
      prime[i*factor[j]] = false;
      if (i % factor[j] == 0) break;
    }
  }
}

bool co_prime(int x,int y){//x < y
  if (x == 1) return true;
  if (prime[y]) return true;
  if (prime[x] && y % x)  return true;
  if (y == x*2 + 1) return true;

  for (set<int>::iterator it = fac_n.begin();it != fac_n.end();++it){
    if (y % *it == 0) return false;
  }
  return true;
}

void parse(int x,set<int> & s){
  for (int i = 1;x != 1;i++){
    int t = factor[i];
    while(x % t == 0) {s.insert(t); x /= t;}
  }
}

int main(){
  double lb = 1.0/3;
  int ans;
  euler_sieve();

  for (int d = 4;d <= M;d++){
    for (int n = 1;n < (d+1)/2;n++){
      double t = (double)n / d;
      if (lb < t && t < ub){
        fac_n.clear();
        parse(n,fac_n);
        if (co_prime(n,d) )  {lb = t; ans = n;}
      }
    }
  }
  cout << ans << endl;
  return 0;
}

永恒的蓝色梦想 · 发表于 2020-8-30 10:38:38

本帖最后由永恒的蓝色梦想于 2020-8-30 19:05 编辑

#include<iostream>
using namespace std;



int main() {
    ios::sync_with_stdio(false);

    long double min_difference = 1, difference;
    unsigned long long denominator, result = 0, numerator;


    for (denominator = 1; denominator <= 1000000; denominator++) {
        numerator = 3 * denominator / 7;
        difference = 3.0L / 7 - (long double)numerator / denominator;

        if (difference && difference < min_difference) {
            min_difference = difference;
            result = numerator;
        }
    }


    cout << result << endl;
    return 0;
}

debuggerzh · 发表于 2020-8-30 11:01:29

debuggerzh 发表于 2020-8-29 18:33
428570

Process returned 0 (0x0) execution time : 649.486 s

第6行应该是1e6，调试忘记改了

debuggerzh · 发表于 2020-8-30 11:26:50

永恒的蓝色梦想发表于 2019-8-4 09:47

感谢大神的思路！以下是改进版本：
428570

Process returned 0 (0x0) execution time : 0.248 s
Press any key to continue.
只枚举分母，计算最接近结果的分子，大大减少循环次数

#include<algorithm>
#include<iostream>
#include<set>
using namespace std;

const int M = 1e6;
const double ub = 3.0/7;
int ct = 0;
bool prime[M];
int factor[M];
set<int> fac_n;

void euler_sieve(){
  prime[1] = false;
  for (int i = 2;i <= M;i++) prime[i] = true;

  for (int i = 2;i <= M;i++){
    if (prime[i]) factor[++ct] = i;
    for (int j = 1;j <= ct && i*factor[j] < M;j++){
      prime[i*factor[j]] = false;
      if (i % factor[j] == 0) break;
    }
  }
}

bool co_prime(int x,int y){//x < y
  if (x == 1) return true;
  if (prime[y]) return true;
  if (prime[x] && y % x)  return true;
  if (y == x*2 + 1) return true;

  for (set<int>::iterator it = fac_n.begin();it != fac_n.end();++it){
    if (y % *it == 0) return false;
  }
  return true;
}

void parse(int x,set<int> & s){
  for (int i = 1; ;i++){
    int t = factor[i];
    while(x % t == 0) {s.insert(t); x /= t;}
    if (x == 1 || prime[x]) break;
  }
  if (prime[x]) s.insert(x);
}

int main(){
  double lb = 1.0/3;
  int ans;
  euler_sieve();

  for (int d = 4;d <= M;d++){
    int n = (int)(d*3 - 1) / 7;
      double t = (double)n / d;
      if (lb < t && t < ub){
        fac_n.clear();
        parse(n,fac_n);
        if (co_prime(n,d) )  {lb = t; ans = n;}
      }
  }
  cout << ans << endl;
  return 0;
}

永恒的蓝色梦想 · 发表于 2020-8-30 11:31:29

本帖最后由永恒的蓝色梦想于 2020-8-30 11:39 编辑

debuggerzh 发表于 2020-8-30 11:26
感谢大神的思路！以下是改进版本：
428570

并不需要判断质数。

guosl · 发表于 2021-3-21 12:11:55

本帖最后由 guosl 于 2022-1-11 19:52 编辑

/*
428570
0.161768
*/
#include <iostream>
#include <algorithm>
using namespace std;

int main(void)
{
  int n = 0, d = 1;
  for (int i = 2; i <= 1000000; ++i)
  {
    for (int j = (3 * i + 6) / 7; 999 * j >= 428 * i; --j)
    {
      if (7 * j >= 3 * i)
        continue;
      if (n*i < j*d)
      {
        n = j;
        d = i;
      }
    }
  }
  cout << n << endl;
  return 0;
}

guosl · 发表于 2022-1-11 20:53:01

本帖最后由 guosl 于 2022-1-12 08:20 编辑

这道题我们先从数学上来讨论一下：对m<n的真分数，我们有以下事实：
1. m/n>m/(n+1)
2. m/n>(m-1)/n
3. m/n>(m-1)/(n-1)
4. m/(n+1) > (m-1)/n , m/(n+1) > (m-1)/(n-1) ,(m-1)/(n-1)>(m-1)/n。总结就是： m/n>m/(n+1) > (m-1)/(n-1)>(m-1)/n，当m/n=3/7时。
在本题中3/7=428571/999999，那么我们可以通过分母加1，分子减1，或分子与分母同时减1，或分子分母同时加1来调整与3/7的距离。但这些调整都预示着分子就在428571的附件，分母就在999999的附近。
为了省却调整的不确定性，我们干脆就在分母d是999990~1000000之间枚举，而分子就是428560~3*d/7之间枚举。

/*
答案：428570
*/
#include <iostream>
using namespace std;

int gcd(int x, int y)
{
  if (y == 0)
    return x;
  int z = x % y;
  while (z != 0)
  {
    x = y;
    y = z;
    z = x % y;
  }
  return y;
}

int main(void)
{
  int n0 = 0, d0 = 1;
  for (int d = 999990; d <= 1000000; ++d)
  {
    for (int n = 428560; 7 * n < 3 * d; ++n)
    {
      long long l1 = n0, l2 = d0;
      l1 *= d;
      l2 *= n;
      if (l1 < l2)
      {
        n0 = n;
        d0 = d;
      }
    }
  }
  cout << n0 / gcd(n0, d0) << endl;
  return 0;
}

TLM · 发表于 2023-2-28 18:51:19

应该是测不到时间，毕竟连循环都没有

# 3/7约等于m/n
# 3n-7m=1 ==> 3/7=(m+1/7)/n
# 3n=7m+1 ==> 3n%7=1
# n%7=5
d=1000000
n=d//7*7+5
if n>d:
    n=n-7
m=(3*n-1)//7
print(m)

salt_eto · 发表于 2024-1-3 19:37:31

本题等效于寻找n/m,使得3/7-n/m最小
3/7-n/m＝(３m-7n)/7m
使得分子＝１，m尽可能大即可
时间：<0.001ms

int test71 (int n)
{
    for (int i = n; i >0; i--)
    {
        if(i * 3% 7==1)
        return i * 3/ 7;
    }
}

时空伴随者 · 发表于 2024-4-23 21:33:15

if __name__ == '__main__':
    import datetime, time

    print(datetime.datetime.now().strftime('%F %T'))
    start = time.time()
    N = 1000000
    m = (N - 5) // 7
    print(f'Problem 71 : {m * 3 + 2}, {m * 7 + 5}')
    print("用时 %.6f 秒" % (time.time() - start))

2024-04-23 21:32:18
Problem 71 : 428570, 999997
用时 0.000000 秒

账号		自动登录	找回密码
密码			立即注册

题目71：将最简真分数按照升序排列

马上注册，结交更多好友，享用更多功能^_^

评分