<< 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==
.
Interactive test
You can submit your own input to my program and it will be instantly processed at my server:
This is equivalent toecho 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)
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.
Benchmark
The correct solution to the original Project Euler problem was found in 5.6 seconds on an Intel® Core™ i7-2600K CPU @ 3.40GHz.
(compiled for x86_64 / Linux, GCC flags: -O3 -march=native -fno-exceptions -fno-rtti -std=gnu++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)
Code in various languages:
Python github.com/nayuki/Project-Euler-solutions/blob/master/python/p348.py (written by Nayuki)
Python github.com/steve98654/ProjectEuler/blob/master/348.py
C++ github.com/Meng-Gen/ProjectEuler/blob/master/348.cc (written by Meng-Gen Tsai)
C++ github.com/roosephu/project-euler/blob/master/348.cpp (written by Yuping Luo)
C++ github.com/smacke/project-euler/blob/master/cpp/348.cpp (written by Stephen Macke)
Java github.com/nayuki/Project-Euler-solutions/blob/master/java/p348.java (written by Nayuki)
Java github.com/thrap/project-euler/blob/master/src/Java/Problem348.java (written by Magnus Solheim Thrap)
Mathematica github.com/steve98654/ProjectEuler/blob/master/348.nb
Those links are just an unordered selection of source code I found with a semi-automatic search script on Google/Bing/GitHub/whatever.
You will probably stumble upon better solutions when searching on your own. Maybe not all linked resources produce the correct result and/or exceed time/memory limits.
Heatmap
Please click on a problem's number to open my solution to that problem:
green | solutions solve the original Project Euler problem and have a perfect score of 100% at Hackerrank, too | |
yellow | solutions score less than 100% at Hackerrank (but still solve the original problem easily) | |
gray | problems are already solved but I haven't published my solution yet | |
blue | solutions are relevant for Project Euler only: there wasn't a Hackerrank version of it (at the time I solved it) or it differed too much | |
orange | problems are solved but exceed the time limit of one minute or the memory limit of 256 MByte | |
red | problems are not solved yet but I wrote a simulation to approximate the result or verified at least the given example - usually I sketched a few ideas, too | |
black | problems are solved but access to the solution is blocked for a few days until a new problem is published | |
the flashing problem is the one I solved most recently |
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 |
551 | 552 | 553 | 554 | 555 | 556 | 557 | 558 | 559 | 560 | 561 | 562 | 563 | 564 | 565 | 566 | 567 | 568 | 569 | 570 | 571 | 572 | 573 | 574 | 575 |
576 | 577 | 578 | 579 | 580 | 581 | 582 | 583 | 584 | 585 | 586 | 587 | 588 | 589 | 590 | 591 | 592 | 593 | 594 | 595 | 596 | 597 | 598 | 599 | 600 |
601 | 602 | 603 | 604 | 605 | 606 | 607 | 608 | 609 | 610 | 611 |
I scored 13,486 points (out of 15700 possible points, top rank was 17 out of ≈60000 in August 2017) at Hackerrank's Project Euler+.
My username at Project Euler is stephanbrumme while it's stbrumme at Hackerrank.
Look at my progress and performance pages to get more details.
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 >> |