11
$\begingroup$

Four marathon runners, each identified with a positive whole number, sit around a table. Each of them notices that their own number has a common divisor with the number of the runner sitting on his right but none with the number of the runner sitting opposite.

If the sum of the four runner's numbers is 299, what are their numbers?

$\endgroup$
  • 3
    $\begingroup$ This kind of problem is very reminiscent of Project Euler. Except instead of 299 it'd be like 10000007. $\endgroup$ – qwr Apr 25 '18 at 3:08
11
$\begingroup$

The numbers are (in order)

$15, 63, 91, 130$

Of course, this order could be shifted left/right, and be reversed, and still be a valid order.

Explanation:

$15+63+91+130=299$
$\gcd(15, 63) = 3$
$\gcd(63, 91) = 7$
$\gcd(91, 130) = 13$
$\gcd(130, 15) = 5$
$\gcd(15, 91) = 1$
$\gcd(63, 130) = 1$

How did I come up with these numbers, you ask?

Yeah, I know you probably wanted me to have some clever number theory solution, but by the time anyone can figure that out my program's done running. I might add that there is only one possible solution, as the program only outputs the 8 possible transformations of the same solution. (Btw, yes I do know that my program is extremely far from optimal. But I got the answer now, so no point in optimizing it now)


#include < iostream >

using namespace std;

int gcd(int a, int b) {
  for (;;) {
      if (a == 0) return b;
      b %= a;
      if (b == 0) return a;
      a %= b;
  }
}

int main() {
  for(int a = 1; a < 299; a++) {
      for(int b = 1; b < 299; b++) {
          for(int c = 1; c < 299; c++) {
              for(int d = 1; d < 299; d++) {
                  if(a + b + c + d == 299 &&
                          gcd(a, b) != 1 && gcd(b, c) != 1 &&
                          gcd(c, d) != 1 && gcd(d, a) != 1 &&
                          gcd(a, c) == 1 && gcd(b, d) == 1) {
                      cout << a << " " << b << " " << c << " " << d << endl;
                  }
              }
          }
      }
  }
}

$\endgroup$
  • 1
    $\begingroup$ Nice answer, and nice brute-force approach (that's not a criticism). Also don't apologize for your program's apparent lack of optimization - it is far more readable and is directly relatable to the question, than some optimized version which might run milliseconds faster but is harder to comprehend. For example, you could use a number smaller than 299 as the loop limit, but that'll need some calculation in advance, and some explanation. $\endgroup$ – Phylyp Apr 25 '18 at 2:58
  • 2
    $\begingroup$ @Phylyp Actually I could've removed the innermost for loop and only checked $d=299-a-b-c$. Would've made the program about 300x faster. Other than that huge optimization, I probably agree with you. $\endgroup$ – Riley Apr 25 '18 at 3:10
  • $\begingroup$ More code review: gcd can be rewritten and since we're looking for one solution we can (probably) assume wlog $a \le b \le c \le d$. Then again there are many more optimizations (see my answer). $\endgroup$ – qwr Apr 25 '18 at 3:13
  • $\begingroup$ @qwr Yes, changing the lower bounds on those for loops would definitely be the next thing to do, if I optimized it. $\endgroup$ – Riley Apr 25 '18 at 3:18
  • $\begingroup$ @Riley - good point, the innermost loop's removal might make a change, but I don't think it's of the order of magnitude you expect: Even in its current form, 298 executions of the innermost loop will short-circuit out at the computationally trivial a+b+c+d part without going to the computationally expensive GCD calculation. So, a tad slower, but not 300x. It just goes to show your instinctive and first-cut program is the best for the job (since it's a one-use throwaway program as well). $\endgroup$ – Phylyp Apr 25 '18 at 4:21
3
$\begingroup$

Narrowing down Riley's test cases:

It's clear

each pair of neighbors shares a unique common divisor, otherwise we'd quickly run into common divisors from runners across from each other.

And

The first few primes are $2, 3, 5, 7, 11, 13$. Since the numbers add up to $299$, an odd number, we must have one or three even numbers. However, $2$ can't be a common factor between numbers because that would lead to two even numbers.

We check a few cases and we see

Riley's answer has common factors $(3, 5, 7, 13)$ with an extra factor of $2$ thrown in.

$\endgroup$
  • $\begingroup$ I thought that the extra factor was 3, not 2? $\endgroup$ – micsthepick Apr 25 '18 at 3:42
  • $\begingroup$ @micsthepick 63 has an extra factor of 3. 130 has an extra factor of 2. $\endgroup$ – Riley Apr 25 '18 at 3:57
  • 1
    $\begingroup$ Thanks for that reference to Project Euler, it's something I'd not heard of before! I can see how optimizations like yours will play an important role there. $\endgroup$ – Phylyp Apr 25 '18 at 4:38
  • 1
    $\begingroup$ @Phylyp it's an on-and-off obsession of mine. I've learned a lot. $\endgroup$ – qwr Apr 25 '18 at 5:05
0
$\begingroup$

So, I was curious about how much faster I could make the c++ from @Riley. Apparently about 1700 times faster (from 20.4s to 0.012s). And probably more if I had applied some memoization to gcd()

#include <iostream>
#include <stdlib.h>
using namespace std;
int gcd(int a, int b) {
  for (;;) {
    if (a == 0) return b; b %= a;
    if (b == 0) return a; a %= b;
  }
}
int main() {
  for(int a = 1;   a < 299;     a++) {
  for(int b = a+2; b < 299-a;   b++) { if(gcd(a,b)!=1){
  for(int c = b+2; c < 299-a-b; c++) { if(gcd(b,c)!=1 && gcd(a,c)==1){
  for(int d = c+2; d < 299-a-b; d++) {
    if( a+b+c+d==299 && gcd(c,d)!=1 && gcd(d,a)!=1 && gcd(b,d)==1 ){
      cout << a << " " << b << " " << c << " " << d << endl;
      exit(0);
    }
  }}}}}}
}
/*run: g++ puzzle.cpp && time ./a.out */

$\endgroup$
  • $\begingroup$ Try removing the loop with d, and just set d = 299-a-b-c; $\endgroup$ – Riley Apr 26 '18 at 21:25
  • $\begingroup$ Of course. And I did: Measuring time spent with gettimeofday() from <sys/time.h> before any other changes, median time of 999 runs was 7354µs. After replacing inner loop with d=299-a-b-c that went down to 6132µs. And then I added memoization into an array of gcd() and it went down to 2229 µs (0.002229 seconds). $\endgroup$ – Kjetil S. Apr 28 '18 at 10:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.