PHI function to list relative primes

coprimemath-softwareprime numberstotient-function

I am using a website called dcode to input numbers into the PHI function, and then receive an output of numbers relatively prime with my input.

The website, unfortunately, limits output to just 500 relatively prime numbers. For my testing this is too low, preferably I would like a complete list.

Could anyone recommend a desktop software which does not have such limitations? It can be for either Windows or Linux. I know about Matlab, but was hoping there was already a program which does what I want, without me having to learn a new scripting language.

Best Answer

This is an easily solved problem, and doesn't require any sort of advanced tools. As Peter said, Euler's Totient is only for computing the number of coprimes for a given n. To actually calculate them, I guarantee that website is doing exactly what Peter suggested: checking the GCD of each possibility. That shouldn't take very long.

Here's a complete Python program to do that, for numbers passed as arguments to the script. (i.e. you'd call it like python3 coprimes.py 47 87 to list the coprimes for, separately, 47 and 87). It'll list the results, and then give the quantity and time required to produce them, for each argument in turn.

It's quite fast. I tried it with the value 4636436, which has 1987032 coprimes. It took my Linux machine 8 seconds to compute and list them all. And honestly, the time spent printing them to the terminal takes up roughly half of that time.

#!/usr/bin/python3
import sys
import time
from pprint import pprint
from math import gcd

def coprimes(n):
    return list([x for x in range(1, n) if gcd(x, n) == 1])

def main(args):
    for n in args:
        t1 = time.monotonic()
        cp = coprimes(int(n))
        pprint(cp, compact=True)
        t2 = time.monotonic()
        print(f"Found {len(cp)} coprimes for {n} in {(t2 - t1):.6f} seconds")
        if n is not args[-1]:
            print("\n")

if __name__ == "__main__":
    main(sys.argv[1:])

The output:

$ python3 coprimes.py 47 87
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22,
 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42,
 43, 44, 45, 46]
Found 46 coprimes for 47 in 0.000209 seconds


[1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 25, 26, 28, 31, 32,
 34, 35, 37, 38, 40, 41, 43, 44, 46, 47, 49, 50, 52, 53, 55, 56, 59, 61, 62, 64,
 65, 67, 68, 70, 71, 73, 74, 76, 77, 79, 80, 82, 83, 85, 86]
Found 56 coprimes for 87 in 0.000224 seconds
Related Question