Jump to content
  • Advertisement
Sign in to follow this  
UriKiller

Math riddle

This topic is 4328 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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!