Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 2 down vote favorite

I have a set of integers $A = \{a:a > 0\}$ and an integer $k > 0$. I need to find $g$ of $A$, which is defined to be GCD of $A$ that is no greater than $k$. For example, if $A = \{20, 40, 60\}$ and $k = 10$, then $g$ should be $10$. Another example would be $A = \{36, 72, 90, 126\}$ and $k = 17$, in which case $g$ would be $9$.

Assume that there is already a function $f(a, b)$ that yields GCD of two positive integers $a$ and $b$. How would I go about writing an algorithm that finds $g$?

share|improve this question
Are you interested in efficient algorithms or would any algorithm do? For instance if $k$ is small, then a simple algorithm would be to find the gcd of the set of numbers, say $g$ and find the largest number less than $k$ that divides $g$. – user17762 Jan 9 at 20:11
@Marvis While the examples I gave are very simple, in practice, $k$ will be fairly large, about 300, and $A$ will consist of large integers, e.g. 2517, 3120. The cardinality of $A$, however, will be pretty small, no greater than 10. – Tom Tucker Jan 9 at 20:18
1  
I consider $k \approx 300$ to be small. Hence, probably the simple algorithm would suffice. To get gcd of $n$ numbers, you need to call $f(f(f(\ldots (f(x_1,x_2),x_3), \ldots),x_{n-1}),x_n)$ – user17762 Jan 9 at 20:22
@Marvis By finding the largest number less than k that divides g, are you suggesting trying to divide g by k, k - 1, k -2, etc?. Sorry - I'm a programmer with little math background. – Tom Tucker Jan 9 at 20:31
Yes. I guess that would be a good way to go about. Will that be computationally expensive? For small $k$, I don't think so. – user17762 Jan 9 at 20:32
show 3 more comments

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.