Recursively calculating the GCDs of a sets members

Vote count:

0

We have a set of positive integers.

We create a new set by calculating the greatest common divisor of all possible pairs of integers from this set.

We redo the above step until only one member remains in the set.

Is there an O(1) method to calculate how many new sets this process creates and whether the member in the last set will be 1?

Some python code that demonstrates what the process I described.

from itertools import combinations
from fractions import gcd
import random

def gen_new_set(a):
    count = 0
    while len(a) != 0:
       print str(count)+':\t'+str(len(a))+'\t'+str(a)
       a = set(gcd(x[0], x[1]) for x in combinations(a,2))  
       count += 1

if __name__ == '__main__':
    a = set( random.sample(range(1,40), 10))
    gen_new_set(a)

asked 1 min ago

AmV

6

Recursively calculating the GCDs of a sets members