# Expressing numbers as sum of two squares and two powers of 2

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!

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

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}\\$$

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

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);
}
}
}
}
}

• 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. – Bernardo Recamán Santos Dec 12 '17 at 14:05
• @BernardoRecamánSantos I'm not going to waste my team trying to find a solution for this. Considering the amount of answers as well – Beastly Gerbil Dec 12 '17 at 16:46