<< problem 347 - Largest integer divisible by two primes | Langton's ant - problem 349 >> |

# Problem 348: Sum of a square and a cube

(see projecteuler.net/problem=348)

Many numbers can be expressed as the sum of a square and a cube. Some of them in more than one way.

Consider the palindromic numbers that can be expressed as the sum of a square and a cube, both greater than 1, in exactly 4 different ways.

For example, 5229225 is a palindromic number and it can be expressed in exactly 4 different ways:

2285^2 + 20^3

2223^2 + 66^3

1810^2 + 125^3

1197^2 + 156^3

Find the sum of the five smallest such palindromic numbers.

# My Algorithm

My `SquareCube`

objects are simple `struct`

s that store the `value`

of a `square`

and a `cube`

.

It contains two comparison functions: `operator==`

returns true when two objects are equal (obviously ...).

However, `operator<`

returns the "wrong" result: I flipped true, if the current object is *bigger* than the parameter.

The reason behind my weird logic is that I use the `std::priority_queue`

is returns always the largest object.

By flipping `operator<`

I can modifiy it to returns the smallest object.

I create all numbers which can be expressed as the sum of square and a cube in ascending order.

Initially an object `SquareCube`

which represents 2^2 + 3^2 is stored in a `std::priority_queue`

.

Whenever I take an object from the `top`

of the queue, I add two objects (square+1)^2 + cube^3 and square^2 + (cube+1)^3.

And whenever I can pick exactly four objects in a row with the same value, then I check whether they are palindromes.

## Alternative Approaches

A much simpler alternative is to create a huge array (about 10^9 entries) which contains only zeros.

Then generate all pairs (square,cube) and increment `myarray[square*square + cube*cube*cube]`

.

Look for the 5 smallest indices where `myerray[] = 5`

.

Remember that this approach needs about 1 GByte of memory. My solution needs less than 5 MByte.

## Note

Many numbers will occur twice in the queue, e.g. when I pick 35 = 3^2 + 3^3 from the queue then it was inserted after

picking 16 = 3^2 + 2^3 and after picking 31 = 2^2 + 3^3. I can easily spot those duplicates with my overloaded `operator==`

.

# My code

… was written in C++11 and can be compiled with G++, Clang++, Visual C++. You can download it, too.

#include <iostream>
#include <vector>
#include <queue>
#include <string>
// represent a number where "value = square^2 + cube^3"

struct SquareCube
{
// create a new object made of a square and a cube
SquareCube(unsigned int square_, unsigned int cube_)
: square(square_), cube(cube_),
value(cube_*(unsigned long long)cube_*cube_ + square_*(unsigned long long)square_)
{ }
// compare two objects (for std::priority_queue)
bool operator<(const SquareCube& other) const
{
if (value != other.value)
return value > other.value; // deliberately switched the sign => min-heap
return cube > other.cube;
}
bool operator==(const SquareCube& other) const
{
return value == other.value && cube == other.cube;
}
unsigned int square;
unsigned int cube;
// equal to square^2 + cube^3
unsigned int value;
};
int main()
{
// find the first 5 numbers
unsigned int maxFound = 5;
std::cin >> maxFound;
// all cubes and squares must be greater than 1
std::priority_queue<SquareCube> todo;
todo.push(SquareCube(2, 2));
// find first 5
unsigned int numFound = 0;
// and their sum
unsigned int sum = 0;
while (numFound < maxFound)
{
// start a new value
auto current = todo.top();
// add its "successors"
todo.emplace(current.square + 1, current.cube);
todo.emplace(current.square, current.cube + 1);
while (todo.top() == current)
todo.pop();
// count all combinations of squares and cube with the same value
unsigned int numSame = 1;
while (todo.top().value == current.value)
{
numSame++;
auto same = todo.top();
// same value, remove it and add its successors
while (todo.top() == same)
todo.pop();
todo.emplace(same.square + 1, same.cube);
todo.emplace(same.square, same.cube + 1);
}
// exactly four combinations ?
if (numSame == 4)
{
// palindrome ?
unsigned int reverse = 0;
auto reduce = current.value;
while (reduce > 0)
{
reverse *= 10;
reverse += reduce % 10;
reduce /= 10;
}
// yes, a match
if (current.value == reverse)
{
numFound++;
sum += current.value;
}
}
}
std::cout << sum << std::endl;
return 0;
}

This solution contains 14 empty lines, 15 comments and 4 preprocessor commands.

# Interactive test

You can submit your own input to my program and it will be instantly processed at my server:

This is equivalent to`echo 1 | ./348`

Output:

*Note:* the original problem's input `5`

__cannot__ be entered

because just copying results is a soft skill reserved for idiots.

*(this interactive test is still under development, computations will be aborted after one second)*

# Benchmark

The correct solution to the original Project Euler problem was found in 5.6 seconds on a Intel® Core™ i7-2600K CPU @ 3.40GHz.

(compiled for x86_64 / Linux, GCC flags: `-O3 -march=native -fno-exceptions -fno-rtti -std=c++11 -DORIGINAL`

)

See here for a comparison of all solutions.

**Note:** interactive tests run on a weaker (=slower) computer. Some interactive tests are compiled without `-DORIGINAL`

.

# Changelog

July 23, 2017 submitted solution

July 23, 2017 added comments

# Difficulty

Project Euler ranks this problem at **25%** (out of 100%).

# Links

projecteuler.net/thread=348 - **the** best forum on the subject (*note:* you have to submit the correct solution first)

# Heatmap

green problems solve the original Project Euler problem and have a perfect score of 100% at Hackerrank, too.

yellow problems score less than 100% at Hackerrank (but still solve the original problem).

gray problems are already solved but I haven't published my solution yet.

blue problems are solved and there wasn't a Hackerrank version of it at the time I solved it or I didn't care about it because it differed too much.

red problems are solved but exceed the time limit of one minute or the memory limit of 256 MByte.

*Please click on a problem's number to open my solution to that problem:*

1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 |

26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 |

51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 | 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 | 71 | 72 | 73 | 74 | 75 |

76 | 77 | 78 | 79 | 80 | 81 | 82 | 83 | 84 | 85 | 86 | 87 | 88 | 89 | 90 | 91 | 92 | 93 | 94 | 95 | 96 | 97 | 98 | 99 | 100 |

101 | 102 | 103 | 104 | 105 | 106 | 107 | 108 | 109 | 110 | 111 | 112 | 113 | 114 | 115 | 116 | 117 | 118 | 119 | 120 | 121 | 122 | 123 | 124 | 125 |

126 | 127 | 128 | 129 | 130 | 131 | 132 | 133 | 134 | 135 | 136 | 137 | 138 | 139 | 140 | 141 | 142 | 143 | 144 | 145 | 146 | 147 | 148 | 149 | 150 |

151 | 152 | 153 | 154 | 155 | 156 | 157 | 158 | 159 | 160 | 161 | 162 | 163 | 164 | 165 | 166 | 167 | 168 | 169 | 170 | 171 | 172 | 173 | 174 | 175 |

176 | 177 | 178 | 179 | 180 | 181 | 182 | 183 | 184 | 185 | 186 | 187 | 188 | 189 | 190 | 191 | 192 | 193 | 194 | 195 | 196 | 197 | 198 | 199 | 200 |

201 | 202 | 203 | 204 | 205 | 206 | 207 | 208 | 209 | 210 | 211 | 212 | 213 | 214 | 215 | 216 | 217 | 218 | 219 | 220 | 221 | 222 | 223 | 224 | 225 |

226 | 227 | 228 | 229 | 230 | 231 | 232 | 233 | 234 | 235 | 236 | 237 | 238 | 239 | 240 | 241 | 242 | 243 | 244 | 245 | 246 | 247 | 248 | 249 | 250 |

251 | 252 | 253 | 254 | 255 | 256 | 257 | 258 | 259 | 260 | 261 | 262 | 263 | 264 | 265 | 266 | 267 | 268 | 269 | 270 | 271 | 272 | 273 | 274 | 275 |

276 | 277 | 278 | 279 | 280 | 281 | 282 | 283 | 284 | 285 | 286 | 287 | 288 | 289 | 290 | 291 | 292 | 293 | 294 | 295 | 296 | 297 | 298 | 299 | 300 |

301 | 302 | 303 | 304 | 305 | 306 | 307 | 308 | 309 | 310 | 311 | 312 | 313 | 314 | 315 | 316 | 317 | 318 | 319 | 320 | 321 | 322 | 323 | 324 | 325 |

326 | 327 | 328 | 329 | 330 | 331 | 332 | 333 | 334 | 335 | 336 | 337 | 338 | 339 | 340 | 341 | 342 | 343 | 344 | 345 | 346 | 347 | 348 | 349 | 350 |

351 | 352 | 353 | 354 | 355 | 356 | 357 | 358 | 359 | 360 | 361 | 362 | 363 | 364 | 365 | 366 | 367 | 368 | 369 | 370 | 371 | 372 | 373 | 374 | 375 |

376 | 377 | 378 | 379 | 380 | 381 | 382 | 383 | 384 | 385 | 386 | 387 | 388 | 389 | 390 | 391 | 392 | 393 | 394 | 395 | 396 | 397 | 398 | 399 | 400 |

401 | 402 | 403 | 404 | 405 | 406 | 407 | 408 | 409 | 410 | 411 | 412 | 413 | 414 | 415 | 416 | 417 | 418 | 419 | 420 | 421 | 422 | 423 | 424 | 425 |

426 | 427 | 428 | 429 | 430 | 431 | 432 | 433 | 434 | 435 | 436 | 437 | 438 | 439 | 440 | 441 | 442 | 443 | 444 | 445 | 446 | 447 | 448 | 449 | 450 |

451 | 452 | 453 | 454 | 455 | 456 | 457 | 458 | 459 | 460 | 461 | 462 | 463 | 464 | 465 | 466 | 467 | 468 | 469 | 470 | 471 | 472 | 473 | 474 | 475 |

476 | 477 | 478 | 479 | 480 | 481 | 482 | 483 | 484 | 485 | 486 | 487 | 488 | 489 | 490 | 491 | 492 | 493 | 494 | 495 | 496 | 497 | 498 | 499 | 500 |

501 | 502 | 503 | 504 | 505 | 506 | 507 | 508 | 509 | 510 | 511 | 512 | 513 | 514 | 515 | 516 | 517 | 518 | 519 | 520 | 521 | 522 | 523 | 524 | 525 |

526 | 527 | 528 | 529 | 530 | 531 | 532 | 533 | 534 | 535 | 536 | 537 | 538 | 539 | 540 | 541 | 542 | 543 | 544 | 545 | 546 | 547 | 548 | 549 | 550 |

I scored 13,183 points (out of 15300 possible points, top rank was 17 out of ≈60000 in August 2017) at Hackerrank's Project Euler+.

Look at my progress and performance pages to get more details.

My username at Project Euler is

**stephanbrumme**while it's stbrumme at Hackerrank.

# Copyright

I hope you enjoy my code and learn something - or give me feedback how I can improve my solutions.

All of my solutions can be used for any purpose and I am in no way liable for any damages caused.

You can even remove my name and claim it's yours. But then you shall burn in hell.

The problems and most of the problems' images were created by Project Euler.

Thanks for all their endless effort.

<< problem 347 - Largest integer divisible by two primes | Langton's ant - problem 349 >> |