<< problem 170 - Find the largest 0 to 9 pandigital that can ... | Investigating numbers with few repeated digits - problem 172 >> |
Problem 171: Finding numbers for which the sum of the squares of the digits is a square
(see projecteuler.net/problem=171)
For a positive integer n, let f(n) be the sum of the squares of the digits (in base 10) of n, e.g.
f(3) = 3^2 = 9,
f(25) = 2^2 + 5^2 = 4 + 25 = 29,
f(442) = 4^2 + 4^2 + 2^2 = 16 + 16 + 4 = 36
Find the last nine digits of the sum of all n, 0 < n < 10^20, such that f(n) is a perfect square.
My Algorithm
If two numbers have the same digits (in different order) then they share the same digit sum.
I group these numbers: 102 is treated the same as 210 and even 12 (which is 012).
My search
analyzes the lowest number of each group. That number has all digits in ascending order
(and potentially starts with many zeros).
The parameter digits
contains the number of digits, e.g. digits[2]
represents how many 2's are present in the current number.
atLeastDigit
ensures that digits are in ascending order. digits[anything > atLeastDigit]
is always zero.
And digitsLeft
tells how many digits have to be added to the current number.
The real magic happens in count()
:
it checks whether the sums of the squared digits is a perfect digit.
And then it computes:
count = sum{digits}
result = dfrac{count!}{digits[0]! * digits[1]! * ... * digits[9]!} * dfrac{0 * digits[0] + 1 * digits[1] + ... + 9 * digits[9]}{count} * dfrac{10^{count}-1}{9}
That formula is based on www.quora.com/What-is-a-formula-to-calculate-the-sum-of-all-the-permutations-of-a-given-number-with-repitations
Most of that formula was easy to implement but after about 14 digits my results were plainly wrong:
The very last term of that long equation is a "repunit", that means it's a number where all digits are ones.
However, multiplying a 20 digit number by another large number is not a good idea using native data types on a 64 bit system ...
But the problem statement asks for the last 9 digits only:
for any factor with more than 9 digits only the lowest 9 digits affect the result's lowest 9 digits.
Therefore I apply a modulo 1000000000 to both factors before the multiplication.
Alternative Approaches
There are different "counting techniques" and avoid all those nasty factorials.
Modifications by HackerRank
The upper limit can be any number <= 10^100.
My code can only handle up to 10^20 because otherwise factorial
overflows.
Even worse: the entered limit doesn't have to be a number like 10^k - but that's the only kind of limit my algorithm can handle.
Obviously, the majority of test cases fail.
Note
factorials
and isSquare
are precomputed to accelerate count()
.
Interactive test
You can submit your own input to my program and it will be instantly processed at my server:
This is equivalent toecho 2 | ./171
Output:
Note: the original problem's input 20
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.
The code contains #ifdef
s to switch between the original problem and the Hackerrank version.
Enable #ifdef ORIGINAL
to produce the result for the original problem (default setting for most problems).
#include <iostream>
#include <vector>
// precompute factorials
std::vector<unsigned long long> factorials;
// highest digit sum is 20*9, precompute for each number whether it's a square
std::vector<unsigned char> isSquare; // actually a bit faster than std::vector<bool>
// only the last 9 digits
const unsigned long long Modulo = 1000000000;
// return the sum of all numbers that can be made with all the digits supplied by parameter "digits"
unsigned long long count(const std::vector<unsigned int>& digits)
{
// sum of all squared digits
unsigned int sum = 0;
// and number of digits (always 20)
unsigned int count = 0;
for (size_t current = 0; current < digits.size(); current++)
{
sum += digits[current] * current * current;
count += digits[current];
}
// proceed only if sum is a perfect square
if (!isSquare[sum])
return 0;
// https://www.quora.com/What-is-a-formula-to-calculate-the-sum-of-all-the-permutations-of-a-given-number-with-repitations
unsigned long long result = factorials[count];
for (auto x : digits)
result /= factorials[x];
unsigned long long numerator = 0;
for (size_t current = 0; current < digits.size(); current++)
numerator += current * digits[current];
result *= numerator;
result /= count;
// (10^count-1)/9 is a bunch of ones (111...111) or "repunit"
// the result is modulo 10^9 therefore I need at most a repunit with 9 digits
unsigned long long ones = 1;
for (unsigned int i = 2; i <= count && i <= 9; i++)
ones = ones * 10 + 1;
// if result is large and then multiplied by a large repunit then I get overflows
// only the lowest 9 digits are relevant anyway, truncate result before multiplication
result %= Modulo;
// at most 9 times 9 digits, that's fine with 64 bit arithmetic
result *= ones;
// and only the lowest 9 digits are of interest anyway
return result % Modulo;
}
// recursively add digit-by-digit and call count() after 20 digits
unsigned int search(std::vector<unsigned int>& digits, unsigned int atLeastDigit, unsigned int digitsLeft)
{
// all digits processed, find sum of all combinations
if (digitsLeft == 0)
return count(digits);
// append one more digit, must not be lower than any previous
unsigned long long result = 0;
for (unsigned int current = atLeastDigit; current <= 9; current++)
{
// adjust number of digits
digits[current]++;
result += search(digits, current, digitsLeft - 1);
// and revert
digits[current]--;
}
return result % Modulo;
}
int main()
{
unsigned int result = 0;
// number of digits
unsigned int numDigits = 20;
#define ORIGINAL
#ifdef ORIGINAL
std::cin >> numDigits;
#else
// assume only 10^k as input (which it isn't for most test cases)
unsigned long long limit; // too small for > 10^20
std::cin >> limit;
// quick hack: Hackerrank includes the last number, e.g. 10^k
result += limit % Modulo;
// count digits of 10^k (=> determine k)
numDigits = 0;
while (limit > 1)
{
numDigits++;
limit /= 10;
}
#endif
// precompute factorials
// 0! = 1
factorials.push_back(1);
// and 1! ... 20!
for (unsigned int i = 1; i <= numDigits; i++)
factorials.push_back(i * factorials.back());
// and squares: 20 digits, each is at most 9^2
const unsigned int MaxSquare = 20 * 9 * 9;
isSquare.resize(MaxSquare, false);
for (unsigned int i = 1; i*i <= MaxSquare; i++)
isSquare[i*i] = true;
// "empty" number, none of the digits 0..9 is initially used
std::vector<unsigned int> digits(10, 0);
result += search(digits, 0, numDigits);
std::cout << result << std::endl;
return 0;
}
This solution contains 17 empty lines, 28 comments and 6 preprocessor commands.
Benchmark
The correct solution to the original Project Euler problem was found in 0.4 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 7, 2017 submitted solution
July 7, 2017 added comments
Hackerrank
see https://www.hackerrank.com/contests/projecteuler/challenges/euler171
My code solves 2 out of 20 test cases (score: 5.26%)
I failed 18 test cases due to wrong answers and 0 because of timeouts
Difficulty
Project Euler ranks this problem at 70% (out of 100%).
Hackerrank describes this problem as medium.
Note:
Hackerrank has strict execution time limits (typically 2 seconds for C++ code) and often a much wider input range than the original problem.
In my opinion, Hackerrank's modified problems are usually a lot harder to solve. As a rule thumb: brute-force is rarely an option.
Links
projecteuler.net/thread=171 - the best forum on the subject (note: you have to submit the correct solution first)
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 170 - Find the largest 0 to 9 pandigital that can ... | Investigating numbers with few repeated digits - problem 172 >> |