How do I make Python choose the largest random value which fits the requirements?-CodePudding

So I'm trying to write a program that chooses the biggest irreducible proper fraction with the sum of the numerator and the denominator equal to n. Here's what I have so far:

import random


def fraction(n): 
    if n < 3 or n > 10 ** 12:
        error_message = 'n must lie in the range (3; 10^12)'
        print(error_message)
    while True: # cycle for repeated variable checking
        if n >= 3 or n <= 10 ** 12:
            b = random.randint(2, 100) # generating two random numbers a and b, where a is the nominator and b the denominator
            a = random.randint(2, 100) # the range is shortened for testing
        if a   b != n: # continue picking random ints until they fit
            continue
        if a   b == n:
            if a != b and a < b: # if a=b the fraction is reducible and doesn't fit, and if a>b it is improper and doesn't fit either
                print(str(a)   '/'   str(b)) # printing an appropriate ordinary fraction
            else:
                continue
        break


n = int(input('n: '))
fraction(n)

The difficulty is this: when I begin testing bigger n numbers like 12, the output is different and some fractions are less than others, while I only need the biggest one. Is there any way I can put an additional condidtion that would make Python choose such fraction?

CodePudding user response：

To find the biggest one you don't need random generation of numerator and denominator. Just loop numerator a downwards starting from (n - 1) // 2, make denominator b = n - a and if math.gcd(a, b) == 1 (read Greated Common Divisor) then we found largest irreducible proper fraction a / b.

It follows from the fact that any fraction can be reduced at most by greatest common divisor (GCD) of numerator and denominator. And if GCD is 1 then it is irreducible.

In my code if tuple (0, n) is returned it means there was no answer, in other words there is no solution for given n. You may also return None instead of return 0, n in last line.

Try it online!

import math

def fraction(n):
    for a in range((n - 1) // 2, -1, -1):
        b = n - a
        if math.gcd(a, b) == 1:
            return a, b
    return 0, n

# Doing some tests below

for i, n in enumerate(range(100)):
    f = fraction(n)
    print(f'n {n:>2} frac {f[0]:>2}/{f[1]:>2}  |  ', end = '')
    if (i   1) % 4 == 0:
        print()

Output:

n  0 frac  0/ 0  |  n  1 frac  0/ 1  |  n  2 frac  0/ 2  |  n  3 frac  1/ 2
n  4 frac  1/ 3  |  n  5 frac  2/ 3  |  n  6 frac  1/ 5  |  n  7 frac  3/ 4
n  8 frac  3/ 5  |  n  9 frac  4/ 5  |  n 10 frac  3/ 7  |  n 11 frac  5/ 6
n 12 frac  5/ 7  |  n 13 frac  6/ 7  |  n 14 frac  5/ 9  |  n 15 frac  7/ 8
n 16 frac  7/ 9  |  n 17 frac  8/ 9  |  n 18 frac  7/11  |  n 19 frac  9/10
n 20 frac  9/11  |  n 21 frac 10/11  |  n 22 frac  9/13  |  n 23 frac 11/12
n 24 frac 11/13  |  n 25 frac 12/13  |  n 26 frac 11/15  |  n 27 frac 13/14
n 28 frac 13/15  |  n 29 frac 14/15  |  n 30 frac 13/17  |  n 31 frac 15/16
n 32 frac 15/17  |  n 33 frac 16/17  |  n 34 frac 15/19  |  n 35 frac 17/18
n 36 frac 17/19  |  n 37 frac 18/19  |  n 38 frac 17/21  |  n 39 frac 19/20
n 40 frac 19/21  |  n 41 frac 20/21  |  n 42 frac 19/23  |  n 43 frac 21/22
n 44 frac 21/23  |  n 45 frac 22/23  |  n 46 frac 21/25  |  n 47 frac 23/24
n 48 frac 23/25  |  n 49 frac 24/25  |  n 50 frac 23/27  |  n 51 frac 25/26
n 52 frac 25/27  |  n 53 frac 26/27  |  n 54 frac 25/29  |  n 55 frac 27/28
n 56 frac 27/29  |  n 57 frac 28/29  |  n 58 frac 27/31  |  n 59 frac 29/30
n 60 frac 29/31  |  n 61 frac 30/31  |  n 62 frac 29/33  |  n 63 frac 31/32
n 64 frac 31/33  |  n 65 frac 32/33  |  n 66 frac 31/35  |  n 67 frac 33/34
n 68 frac 33/35  |  n 69 frac 34/35  |  n 70 frac 33/37  |  n 71 frac 35/36
n 72 frac 35/37  |  n 73 frac 36/37  |  n 74 frac 35/39  |  n 75 frac 37/38
n 76 frac 37/39  |  n 77 frac 38/39  |  n 78 frac 37/41  |  n 79 frac 39/40
n 80 frac 39/41  |  n 81 frac 40/41  |  n 82 frac 39/43  |  n 83 frac 41/42
n 84 frac 41/43  |  n 85 frac 42/43  |  n 86 frac 41/45  |  n 87 frac 43/44
n 88 frac 43/45  |  n 89 frac 44/45  |  n 90 frac 43/47  |  n 91 frac 45/46
n 92 frac 45/47  |  n 93 frac 46/47  |  n 94 frac 45/49  |  n 95 frac 47/48
n 96 frac 47/49  |  n 97 frac 48/49  |  n 98 frac 47/51  |  n 99 frac 49/50

You may also modify your variant a bit by remembering maximal a, filtering out results where a is less then current maximal or gcd(a, b) > 1. Then your randomized solution may also work in most cases if enough time is given, although of course it is slow.

Try your modified code below. It prints iteratively bigger and bigger fraction until it freezes for long time if bigger fraction can't be found.

Try it online!

import random, math

def fraction(n): 
    if n < 3 or n > 10 ** 12:
        error_message = 'n must lie in the range (3; 10^12)'
        print(error_message)
    amax = -1
    while True: # cycle for repeated variable checking
        if n >= 3 or n <= 10 ** 12:
            b = random.randint(1, n) # generating two random numbers a and b, where a is the nominator and b the denominator
            a = random.randint(1, n) # the range is shortened for testing
        if a   b != n: # continue picking random ints until they fit
            continue
        if a   b == n:
            if a != b and a < b and a > amax: # if a=b the fraction is reducible and doesn't fit, and if a>b it is improper and doesn't fit either
                if math.gcd(a, b) == 1:
                    print(str(a)   '/'   str(b)) # printing an appropriate ordinary fraction
                    amax = a
            else:
                continue

n = int(input('n: '))
fraction(n)

Output: