-5
$\begingroup$

It has been shown that the smallest integer, greater than 1, that cannot be represented as a sum of two squares and at most two powers of 2 is 535,903. Show how to express 535,902 as the sum of two squares and two powers of 2. Avoid a computer if you can!

$\endgroup$
  • 3
    $\begingroup$ This seems very tedious. $\endgroup$ – Deusovi Dec 12 '17 at 3:45
3
$\begingroup$

Avoid a computer if you can!

I can't.

.

Here's my code in Java. It only takes a few seconds to run, and it doesn't print out any answers that are simply rearrangements of the same sum. Also, it prints the sums already formatted in MathJax.

for(int a = 0; a * a <= 535902; a++) {
      for(int b = a; b * b <= 535902; b++) {
          for(int c = 1; c <= 535902; c *= 2) {
              for(int d = c; d <= 535902; d *= 2) {
                  if(a * a + b * b + c + d == 535902) {
                      System.out.print(a + "^2 + " + b + "^2 + 2^{" + 
                      (Math.round(Math.log(c) / Math.log(2))) + "} + 2^{" + (Math.round(Math.log(d) / Math.log(2))) + "}\\\\");
                  }
              }
          }
      }
  }

Here's every possible sum of two squares and two powers of two that evaluates to $535902$.

$$15^2 + 523^2 + 2^{2} + 2^{18}\\19^2 + 729^2 + 2^{2} + 2^{12}\\39^2 + 731^2 + 2^{2} + 2^{4}\\151^2 + 669^2 + 2^{2} + 2^{16}\\197^2 + 705^2 + 2^{2} + 2^{6}\\201^2 + 701^2 + 2^{2} + 2^{12}\\215^2 + 477^2 + 2^{2} + 2^{18}\\297^2 + 669^2 + 2^{2} + 2^{7}\\357^2 + 639^2 + 2^{2} + 2^{7}\\369^2 + 629^2 + 2^{2} + 2^{12}\\397^2 + 615^2 + 2^{2} + 2^{6}\\415^2 + 603^2 + 2^{2} + 2^{6}\\445^2 + 567^2 + 2^{2} + 2^{14}\\453^2 + 575^2 + 2^{2} + 2^{6}\\483^2 + 535^2 + 2^{2} + 2^{14}\\489^2 + 541^2 + 2^{2} + 2^{12}\\$$

$\endgroup$
  • $\begingroup$ +1 for "I can't" - exactly what I thought as well. $\endgroup$ – Wen1now Dec 12 '17 at 6:52
  • $\begingroup$ Can you provide the code? :) $\endgroup$ – Tweakimp Dec 12 '17 at 7:13
  • $\begingroup$ @Tweakimp I added the code $\endgroup$ – Riley Dec 12 '17 at 17:08
0
$\begingroup$

This code will answer any such problem in a jiffy. Takes a minute or so to run when you get to sums around 20 000 000. 'Try to answer this without a computer' yeah right. Estimate 8 hours to 8 days fiddling with pencil and paper, probably at least a few hours with a calculator. Less than five minutes writing a program. Same answer list as already given. I would have put this as a comment, but alas I am too disreputable. Everything defined as int.

maxsz = atoi(argv[1]);
maxlb2 = (int) (log(maxsz-4)/log(2));
maxsqrt = (int) sqrt(maxsz-4);
printf("Expressing %d as the sum of two squares and two powers of two\n", maxsz);

for (i=1;i<maxsqrt;i++)
{
    for (j=i;j<maxsqrt;j++)
    {
        for (k=0,k2=1;k<=maxlb2;k++,k2*=2)
        {
            for (l=k,l2=k2;l<=maxlb2;l++,l2*=2)
            {
                if ((i*i + j*j + k2 + l2) == maxsz)
                {                       
                    printf("%d^2 + %d^2 + 2^%d + 2^%d\n", i,j,k,l);
                }
            }
        }
    }
}
$\endgroup$
  • $\begingroup$ No, with a bit of ingenuity, and some basic number theory, you can find by hand at least one solution in less than an hour. $\endgroup$ – Bernardo Recamán Santos Dec 12 '17 at 14:05
  • $\begingroup$ @BernardoRecamánSantos I'm not going to waste my team trying to find a solution for this. Considering the amount of answers as well $\endgroup$ – Beastly Gerbil Dec 12 '17 at 16:46

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.