Introducing …. the Greedy Calvinosaurus Dinosaur

In this week's post, learn about Greatest Common Divisor.

Last week, we introduced several questions based on calculating the Greatest Common Divisor of several integers and polynomials. Using the Euclidean Algorithm is a standard approach to helping us to quickly calculate these values.

Judging from the comments in the solution discussions, here are some questions for you to ponder:

1) If \( n < 10 \), can \( \gcd (n, m ) > 10 \)?

2) What is the value of \( \gcd( -14, -21 ) \)?

3) Why does the Euclidean algorithm work? Specifically, why does \( \gcd(n,m) = \gcd(n, m+kn ) \) for any integers \(n, m, k \)?

For those who want a coding challenge:

Write code to calculate the GCD of 2 numbers, which ends in finitely many steps. You are not allowed to use conditions like “If n > 0, continue” or equivalent hacks.

No vote yet

24 votes

×

Problem Loading...

Note Loading...

Set Loading...

## Comments

Sort by:

TopNewestI generally programme in Pascal. Apart from the setting-up exercises (to ensure that \(a\) and \(b\) are positive and ordered), the function calls itself recursively as many times as the Euclidean algorithm is used in the calculation of the gcd.

Log in to reply

As I said, you are not allowed to use "if n \( > 0 \)" conditions (similarly for "while \(n>0\)"). You have hidden it within calling of the gcd function.

The main aspect of this problem is to figure out the number of steps which the Euclidean algorithm has to take.

Log in to reply

So you want to know about the time complexity of the Euclidean algorithm. Try some consecutive Fibonacci numbers.

Log in to reply

Log in to reply

Log in to reply

I hope these are right:

1) Yes, if \(n < -10\)

2) 7

Log in to reply

Yup.

Log in to reply

Hello Calvin! Will you post the answers to the 3 questions in the future? That would greatly help.

A few questions, how do you define gcd of negative numbers? Can you please give a few hints for the second question? In the first question, can n be negative?

Thanks!

Log in to reply

@Calvin What do you mean by " finite many steps"? Do you mean to write a code in the least amount of lines of code?

Log in to reply

It shouldn't have a phrase equivalent to "If \(n, m>0\), continue".

It can have a phrase "For i = 1 to \(\max(n,m) \)", though of course this is very inefficient.

Log in to reply

Is this one legit?

Log in to reply

Log in to reply

Log in to reply

Log in to reply

Log in to reply

If you fix this, the code is about optimal for speed, but it breaks the rules about no loops, like my first version did.

Log in to reply

Log in to reply

Alright. I'm working on a code right now...during class.

Log in to reply

So in Python, we can't use a while loop?

Log in to reply

Log in to reply

1) If \(n < 10\), then \(gcd(n, m)\) can be greater than \(10\). This is because if n can be negative too. Here's an example \(gcd(-20, 40) = 20\).

2) \(gcd(-14, -21) = 7\)

3) I'll post it later

Log in to reply

I'm not sure if this is allowed but it works.

astr = input("Type first number") bstr = input("Type second number") a = int(astr) b = int(bstr) while a < b or a > b: if a > b: a = a-b else: b = b-a if a == b: astr1 = str(a) print(astr1)

Log in to reply