<< problem 288 - An enormous factorial | Panaitopol Primes - problem 291 >> |
Problem 290: Digital Signature
(see projecteuler.net/problem=290)
How many integers 0 <= n < 10^18 have the property that the sum of the digits of n equals the sum of digits of 137n?
My Algorithm
A brute-force algorithm can be written without much thinking (and just stealing the digitSum()
function from problem 119).
It works pretty well for n <= 10^8.
There is a small optimization which I added based on the observation:
if n is not a multiple of 9 then the sum of digits of n never matches the sum of digits of 137n.
Coming up with a faster algorithm took me two months - well, I was working on other problems in the meantime, but this problem was a tough nut to crack -
escpecially considering the short solution that I finally found. Note: apparently almost everyone found the same algorithm, the fastest solver needed just 7 minutes (!) according to the forum.
While the brute-force algorithm works for every n, the faster algorithm requires n to be a power of ten, that is n = 10^k, e.g. n = 10^18.
Let's say S(n) returns the sum of digits of n. Then I have to find all n < 10^18 where
(1) S(n) = S(137n)
If I partition n into n = 10x + y then y is the last digit of n and x everything else.
(2) S(n) = S(10x + y) = S(x) + y
Combining (1) and (2):
(3) S(x) + y = S(137 * (10x + y))
(4) S(x) + y = S(137 * 10x + 137y)
If I partition 137y into 137y = 10u + v then
(5) u = \lfloor dfrac{137y}{10} \rfloor
(6) v = 137y mod 10
(7) S(x) + y = S(137 * 10x + 10u + v)
(8) S(x) + y = S(137x + u) + v
If n < 10, that means the number of digits is 1, then x = 0 and (8) simplifies accordingly.
If n >= 10 then x has one digit less than n (it's missing the right-most digit which is y) and
(9) S(137n) = S(137x + u) + v
So that the recursion pattern is
(10) u_{next} = \lfloor dfrac{137u}{10} \rfloor
(11) v_{next} = 137u mod 10 + v - digit
Note
I didn't find the final steps not by sitting in front of a piece of paper - instead it was laborous work fitting the equations to the results of my brute-force search.
As mentioned before, several solvers went the straight way and immediately found the correct algorithm. Not me, I was stupid ...
Usually I rely on std::map
for caching because it's simple:
- no need to pre-allocate memory and fill it with an
Unknown
indicator - works great when the
id
s have huge gaps inbetween
When I have the correct solution, I often try to speed up the program because
std::map
involves lots of calls to new
and delete
.An
std::unordered_map
is a plug-in replacement. Since most hash maps are based on a big blocks of continuous memory, there are less new
and delete
.That small difference (combined with better locality / CPU caching) is enough to solve the current problem almost three times faster: in only 0.120 seconds.
There are no huge gaps between
id
s so that I converted the cache
container to std::vector
and finish in just 0.027 seconds, again 4 times faster than std::unordered_map
.Even more important, each
new
consumes a few bytes on its own. Therefore the faster std::vector
version needs 50% less memory, too.Feel free to experiment with
#define FAST
.
Interactive test
You can submit your own input to my program and it will be instantly processed at my server:
This is equivalent toecho 4 | ./290
Output:
Note: the original problem's input 18
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. Or just jump to my GitHub repository.
#include <iostream>
#include <map>
#include <unordered_map>
#include <vector>
#include <cmath>
// compare x and 137x
const unsigned int Signature = 137;
// copied from problem 119
unsigned int digitSum(unsigned long long x)
{
unsigned int result = 0;
while (x > 0)
{
result += x % 10;
x /= 10;
}
return result;
}
// the brute-force algorithm is surprisingly fast for limit < 10^8
unsigned long long bruteForce(unsigned long long limit)
{
unsigned long long count = 0;
for (unsigned long long i = 0; i < limit; i += 9) // observation: always multiples of 9
if (digitSum(i) == digitSum(i * Signature))
count++;
return count;
}
// different container types:
// std::vector: 0.027s
// std::unordered_map: 0.120s
// std::map: 0.415s
#define FAST
#ifdef FAST
const long long Unknown = -1;
std::vector<long long> cache((18+1) * 137 * 240, Unknown); // see search() for the constants
#else
std::unordered_map<unsigned int, long long> cache;
//std::map<unsigned int, long long> cache;
#endif
// count all numbers where digitSum(x) == digitSum(137x)
unsigned long long search(unsigned int numDigits, unsigned int u = 0, int v = 0)
{
// memoize
unsigned int id = numDigits;
id *= 137;
id += u; // 0..136
id *= 240;
id += v + 120; // -116..+116
#ifdef FAST
if (cache[id] != Unknown)
return cache[id];
#else
auto lookup = cache.find(id);
if (lookup != cache.end())
return lookup->second;
#endif
// only one digit left ?
if (numDigits == 1)
{
// digitSum(137d + u) must be identical to digit + v
// check every possible digit 0..9
unsigned int result = 0;
for (unsigned int digit = 0; digit <= 9; digit++)
if (digitSum(Signature * digit + u) + v == digit)
result++;
cache[id] = result;
return result;
}
// "shave off" one digit and continues with recursion ...
unsigned long long result = 0;
for (auto digit = 0; digit <= 9; digit++)
{
auto nextU = (Signature * digit + u) / 10;
auto nextV = (Signature * digit + u) % 10 + v - digit;
result += search(numDigits - 1, nextU, nextV);
}
cache[id] = result;
return result;
}
int main()
{
// analyze all numbers below 10^18
unsigned int limit = 18;
std::cin >> limit;
//std::cout << bruteForce(pow(10, limit)) << std::endl;
std::cout << search(limit) << std::endl;
return 0;
}
This solution contains 11 empty lines, 16 comments and 12 preprocessor commands.
Benchmark
The correct solution to the original Project Euler problem was found in 0.02 seconds on an Intel® Core™ i7-2600K CPU @ 3.40GHz.
Peak memory usage was about 7 MByte.
(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
November 14, 2017 submitted solution
November 14, 2017 added comments
Difficulty
Project Euler ranks this problem at 50% (out of 100%).
Links
projecteuler.net/thread=290 - the best forum on the subject (note: you have to submit the correct solution first)
Code in various languages:
Python github.com/HaochenLiu/My-Project-Euler/blob/master/290.py (written by Haochen Liu)
Python github.com/LaurentMazare/ProjectEuler/blob/master/e290.py (written by Laurent Mazare)
Python github.com/Meng-Gen/ProjectEuler/blob/master/290.py (written by Meng-Gen Tsai)
Python github.com/roosephu/project-euler/blob/master/290.py (written by Yuping Luo)
Mathematica github.com/steve98654/ProjectEuler/blob/master/290.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 the next problem is published | |
[new] | the flashing problem is the one I solved most recently |
I stopped working on Project Euler problems around the time they released 617.
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 | 612 | 613 | 614 | 615 | 616 | 617 | 618 | 619 | 620 | 621 | 622 | 623 | 624 | 625 |
626 | 627 | 628 | 629 | 630 | 631 | 632 | 633 | 634 | 635 | 636 | 637 | 638 | 639 | 640 | 641 | 642 | 643 | 644 | 645 | 646 | 647 | 648 | 649 | 650 |
651 | 652 | 653 | 654 | 655 | 656 | 657 | 658 | 659 | 660 | 661 | 662 | 663 | 664 | 665 | 666 | 667 | 668 | 669 | 670 | 671 | 672 | 673 | 674 | 675 |
676 | 677 | 678 | 679 | 680 | 681 | 682 | 683 | 684 | 685 | 686 | 687 | 688 | 689 | 690 | 691 | 692 |
I scored 13526 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 288 - An enormous factorial | Panaitopol Primes - problem 291 >> |