<< 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()`

.

# 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.

# 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 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)*

# Benchmark

The correct solution to the original Project Euler problem was found in 0.4 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 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

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 170 - Find the largest 0 to 9 pandigital that can ... | Investigating numbers with few repeated digits - problem 172 >> |