<< problem 301 - Nim | Primonacci - problem 304 >> |

# Problem 303: Multiples with small digits

(see projecteuler.net/problem=303)

For a positive integer n, define f(n) as the least positive multiple of n that, written in base 10, uses only digits <= 2.

Thus f(2)=2, f(3)=12, f(7)=21, f(42)=210, f(89)=1121222.

Also, \sum_{n=1..100}{dfrac{f(n)}{n}} = 11363107.

Find \sum_{n=1..10000}{dfrac{f(n)}{n}}.

# My Algorithm

Initially I create all positive numbers with one digits that is <= 2 → `zeroOneTwo = { 1, 2 }`

.

Then each number between 1 and 10000 (see `open`

) is checked whether it divides any of the numbers in `zeroOneTwo`

.

The next iteration appends to each value in `zeroOneTwo`

the digits 0, 1 and 2.

That means, `{ 1, 2 }`

→ `{ 10, 11, 12, 20, 21, 22 }`

.

`zeroOneTwo`

grows pretty fast: it contains 2 * 3^{digits-1} elements.

Unfortunately, 11112222222222222222 is the smallest multiple of 9999.

My algorithm would need to allocate enough memory to store 2 * 3^{20-1} approx 2.3 * 10^9 values.

Even worse, it would be pretty slow.

When looking at the multiples of each number, I discovered that numbers where the last digit 9 have large multiples.

Especially large are the multiples when all digits are 9s.

My program easily found the multiples of 9, 99 and 999 and a certain pattern became apparent:

their smallest multiple is a sequence of n ones and 4n twos where n is the number of nines.

You will see that my code precomputes the result for 9999.

Another optimization (see `#ifdef FAST999`

) is to make use of the pattern of multiples of 999:

there are alway three 1s and twelve 2s, except 5*999 and 10*999 which have a trailing zero on top.

If you disable that optimization then the program will be about half as fast but needs four times more memory.

## Alternative Approaches

Heavy use of `std::next_permutation`

and/or base-3 arithmetic could eliminate the need for my `zeroOneTwo`

container

(responsible for the "high" memory consumption) but it seems that performance would suffer significantly.

## Note

My first attempt was based Dynamic Programming but I could make the program fast enough.

# 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 <string>
#include <algorithm>
// see explanation

#define FAST999
int main()
{
unsigned int limit = 10000;
std::cin >> limit;
unsigned long long sum = 0;
// put all numbers 1..10000 in "open"
std::vector<unsigned int> open;
for (unsigned int i = 1; i <= limit; i++)
open.push_back(i);
// repeated 9s follow a certain pattern ... pre-compute them
if (limit >= 9999)
{
sum += 11112222222222222222ULL / 9999;
open.erase(open.begin() + 9999 - 1);
// zero-based index but first element is one, therefore subtract one
}
// special treatment for multiples of 999 (saves memory and makes program faster)
// three 1s, twelve 2s and potentially a trailing zero
#ifdef FAST999
for (unsigned int factor = 10; factor >= 1; factor--)
{
unsigned int current = factor * 999;
if (current > limit)
continue;
// try every permutation of these digits ...
std::string tripleNine = "111222222222222";
do
{
unsigned long long multiple = std::stol(tripleNine);
// 4995 (5*999) and 9990 (10*999) require a trailing zero, too
if (factor % 5 == 0)
multiple *= 10;
// divisible ?
if (multiple % current == 0)
{
// yes, resolved one more number
sum += multiple / current;
open.erase(open.begin() + current - 1);
break;
}
} while (std::next_permutation(tripleNine.begin(), tripleNine.end()));
}
#endif
// all positive numbers of length 1 with digits <= 2
std::vector<unsigned long long> zeroOneTwo = { 1, 2 };
// until a divisor is found for all numbers
while (!open.empty())
{
// numbers where still no divisor was found
std::vector<unsigned int> next;
// look at all unresolved numbers
for (auto current : open)
{
bool lastMustBeZero = current % 5 == 0;
bool found = false;
// check whether any number with digits <= 2 can be divided by it
for (auto multiple : zeroOneTwo)
{
if (lastMustBeZero)
multiple *= 10;
if (multiple % current == 0)
{
// yes, resolved one more number
sum += multiple / current;
found = true;
break;
}
}
// no match found, must look at numbers with one more digit, too
if (!found)
next.push_back(current);
}
// prepare next iteration
open = std::move(next);
if (!open.empty())
{
// append a zero, a one and a two to each number
std::vector<unsigned long long> longer;
for (auto multiple : zeroOneTwo)
{
longer.push_back(multiple * 10);
longer.push_back(multiple * 10 + 1);
longer.push_back(multiple * 10 + 2);
}
zeroOneTwo = std::move(longer);
}
}
// display result
std::cout << sum << std::endl;
return 0;
}

This solution contains 16 empty lines, 20 comments and 7 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 100 | ./303`

Output:

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

__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.6 seconds on a Intel® Core™ i7-2600K CPU @ 3.40GHz.

Peak memory usage was about 46 MByte.

(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 3, 2017 submitted solution

July 3, 2017 added comments

# Difficulty

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

# Links

projecteuler.net/thread=303 - **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 301 - Nim | Primonacci - problem 304 >> |