• Advertisement
Sign in to follow this  

Math riddle

This topic is 4150 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Ok, don't expect for something really difficult, and besides, its probably a known formula. int func (int k, int n) { if (n == k) return k; if (n > k) return func (k, n - k); return func (k - n, n); } (proof also required, not only guessing)

Share this post


Link to post
Share on other sites
Advertisement
The answer, old boy, is

func(int k, int n) = min(int k, int n)

How do we know this? Welllll.....

In the equality case, the function merely returns the value of k, since either one of the values is considered the 'minimum'.

In the case that n is larger than k, we recursively call func, decreasing n until it is equal to k, in which case we return k.

In the case that k is larger than n, we recursively call func, decreasing k until it is equal to n, in which case we return k (which n is now equal to).

Since we are recursively decreasing our parameters until we reach the smallest one and then returning, it is obvious to see that we are returning the minimum value of the pair.



Share this post


Link to post
Share on other sites
No, it's calculating the greatest common divisor. I don't have proof though, but I've seen it before.

Share this post


Link to post
Share on other sites
What are you smoking, man?? It IS the GCD! kloffy was indeed correct.
Julian Spillane, the first reply of yours is obciously incorrect because when you decrease a from b multiple times it doesn't mean that a == b eventually, it will most likely pass him. For example:
3, 10:
10-3 = 7
7-3 = 4
4-3 = 1
1 != 3

And about your second reply: I have no idea what you wrote, but I think you should refresh your addition skills.

Share this post


Link to post
Share on other sites
Alright, yes, it is the GCD.

Now...to prove it...

Let d = gcd(n,k)

In the case that n = k, we know that the gcd(k, k) = k by the properties of divisibility, so we're done.

In the case that n > k, we know that n does not divide k. There could, however, be the chance that k divides n, so we recursively subtract k from n in hopes that it is a multiple and that eventually we will reach equivalence. If we overshoot, we fall back to the case that k > n.

In the case that k > n, we know that k does not divide n. It could be that n divides k, and so we reduce it by k until we reach equivalence.

When the algorithm eventually reaches the point where n' | k' and k' | n', we know that we've found the gcd(n,k). This is true because d would be the largest number that divides both n and k.


Well, that wasn't a rigorous proof at all, but it's too early in the morning to do a formalization of that. Give me about an hour or so to wake my brain up. :p

Share this post


Link to post
Share on other sites
Alright, I was going to use Hoare logic as a program verification proof on the function using the assumptions that I made that to state that if k' = n', then k' is the gcd(k, n)...

but I can't for the life of me figure out the loop invariant.

:(

Share this post


Link to post
Share on other sites
What's so difficult about this?

gcd(a,b) = a              if a = b
gcd(a,b) = gcd(a,b-a) if a < b
gcd(a,b) = gcd(a-b,b) if a > b


Besides:

max(a,b) > max(a,b-a) > 0 if a < b
max(a,b) > max(a-b,b) > 0 if a > b


Therefore, by induction, the function is the gcd.


Share this post


Link to post
Share on other sites
Well what you wrote was hardly a formal inductive proof. It was merely writing in gcd relational equations what I expressed (well, I know it's obvious and I'm not saying you rewrote what I expressed, merely that they're equivalent statements). I mean, you could formalize it, but in that form it's not.

And yeah, I was wrong about the "min" statement...I had misread the problem. I thought it said n-1 and k-1, not n-k and k-n.

Share this post


Link to post
Share on other sites
Quote:
Original post by Julian Spillane
Well what you wrote was hardly a formal inductive proof.

All that's missing to turn it into a formal inductive proof is some cosmetic garnish. The crunch of the proof is right there, minus a spot of case analysis.

Regards
Admiral

Share this post


Link to post
Share on other sites
*SIGH*

Prove by induction on n = max(a,b) that gcd(a,b) = f(a,b) for each a > 0, b > 0.

As an induction hypothesis, assume that:
∀ a > 0, b > 0, max(a,b) < n => gcd(a,b) = f(a,b)

Let max(a,b) = n:
- if a = b, then gcd(a,b) = a = f(a,b)
- if 0 < a < b, then gcd(a,b) = gcd(a,b-a) = f(a,b-a) = f(a,b) (applying the induction hypothesis because max(a,b-a) < b = max(a,b) = n and b-a > 0)
- if 0 < b < a, then gcd(a,b) = gcd(a-b,b) = f(a-b,b) = f(a,b) (applying the induction hypothesis because max(a-b,b) < a = max(a,b) = n and a-b > 0)

Therefore, ∀ a > 0, b > 0, gcd(a,b) = f(a,b). QED.


We're using strong induction, so there are no special cases to be considered.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement