<< problem 273 - Sum of Squares | A Modified Collatz sequence - problem 277 >> |
Problem 274: Divisibility Multipliers
(see projecteuler.net/problem=274)
For each integer p > 1 coprime to 10 there is a positive divisibility multiplier m < p which preserves divisibility by p
for the following function on any positive integer, n:
f(n) = (all but the last digit of n) + (the last digit of n) * m
That is, if m is the divisibility multiplier for p, then f(n) is divisible by p if and only if n is divisible by p.
(When n is much larger than p, f(n) will be less than n and repeated application of f provides a multiplicative divisibility test for p.)
For example, the divisibility multiplier for 113 is 34.
f(76275) = 7627 + 5 * 34 = 7797 : 76275 and 7797 are both divisible by 113
f(12345) = 1234 + 5 * 34 = 1404 : 12345 and 1404 are both not divisible by 113
The sum of the divisibility multipliers for the primes that are coprime to 10 and less than 1000 is 39517.
What is the sum of the divisibility multipliers for the primes that are coprime to 10 and less than 107?
My Algorithm
Oops, I didn't understand the problem statement - and had to read it five times until I truly knew what Project Euler is asking for:
- if n is a multiple of p then f(n) is a multiple of p, too
- if n isn't a multiple of p then f(n) isn't a multiple of p as well
(1) n = 10a + b
(2) f(n) = a + bm
If n is a multiple of p:
(3) n == 0 mod p therefore 10a + b == 0 mod p
(4) f(n) == 0 mod p therefore a + bm == 0 mod p
I picked a few random numbers and got lucky:
(5) 10a + b == a + bm
(6) n == a + bm
(7) n - a == bm
(8) dfrac{n - a}{b} == m
To my surprise the result was wrong for the sum of all prime n up to 1000 !
It turns out I forgot that equations (5) to (8) are simply wrong because I replaced f(n) by n and they are missing mod p.
That happens when I start thinking about a Project Euler problem after a long day at work ...
Then I wrote the brute-force routine
findM
which iterates over several multiples of p until it finds some m.For performance reasons I abort after just 10 iterations - and this time the result is correct for n < 1000 (even for bigger n but then
findM
becomes slow).An interesting observation was that equations (5) are actually working if the last digit is not 7 !
I can't (and won't) prove that because I'm a software engineer and not a mathematician but there is probably an elegant way.
So what's the problem with
lastDigit = 7
?Let's start again and find some equations based on (1) to (4):
(3) 10a + b == 0 mod p (just repeated from above)
(9) 10a == -b mod p
(4) a + bm == 0 mod p (just repeated from above)
(10) 10 * (a + bm) == 0 mod p
(11) 10a + 10bm == 0 mod p
Merging (9) and (11):
(12) -b + 10bm == 0 mod p
(13) b * (10m - 1) == 0 mod p
This should be valid for every b, even for b = 1:
(14) 10m - 1 == 0 mod p
(15) 10m = 1 mod p
If m is the modular inverse of 10 mod p then f(n) is a multiple of p.
So it all boils down to adding the modular inverses of 10 for each n.
There are multiple way to find the modular inverse. In problem 381 I implemented Fermat's little theorem and the Extended Euclidean algorithm.
I copied the former (which means I copied
powmod
from my toolbox and then the modular inverse is powmod(10, n-2, n)
).
Alternative Approaches
After submitting my solution I saw some astonishingly simple solutions exploiting the repeated nature of modulo.
Note
The Extended Euclidean algorithm is faster than Fermat's little theorem. However, powmod
is part of so many solutions that I kind of like it.
And I could write it's code instantly (if I lost my toolbox) whereas I would need to look up the Extended Euclidean algorithm.
Interactive test
You can submit your own input to my program and it will be instantly processed at my server:
This is equivalent toecho 1000 | ./274
Output:
Note: the original problem's input 10000000
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>
// uncomment to run only the slow algorithm
//#define SLOW
// uncomment to revert to fast formula for last digit != 7
#define TRICK7
// if both #defines are not used, then only the inverse modular computation is started
// brute-force way to find the unique m
// see below for more efficient ways
unsigned int findM(unsigned int p)
{
// every multiple of p must fulfil the equations
// kp = 10a + b (split that multiple into the first digits and the last digit)
// (a + mb) % p == 0
for (unsigned int m = 1; m < p; m++)
{
// there are a few "false" positives when k = 1 and b = 7
// but they don't survive when testing against more multiples
const auto AtLeastMultiples = 10; // number was chosen quite arbitrary
bool ok = true;
// test the first 10 multiples of p
for (auto k = 1; k < AtLeastMultiples; k++)
{
// split multiple
auto current = k * p;
auto a = current / 10;
auto b = current % 10;
// each multiple is divisible by p but is a + mb, too ?
if ((a + m * b) % p != 0)
{
ok = false;
break;
}
}
// found a match
if (ok)
return m;
}
// never reached
return 0;
}
// return (base^exponent) % modulo for 32-bit values, no need for mulmod
// copied from my toolbox
unsigned int powmod(unsigned int base, unsigned int exponent, unsigned int modulo)
{
unsigned int result = 1;
while (exponent > 0)
{
// fast exponentation:
// odd exponent ? a^b = a*a^(b-1)
if (exponent & 1)
result = (result * (unsigned long long)base) % modulo;
// even exponent ? a^b = (a*a)^(b/2)
base = (base * (unsigned long long)base) % modulo;
exponent >>= 1;
}
return result;
}
int main()
{
unsigned int limit = 10000000;
std::cin >> limit;
// store only odd numbers (based on standard prime sieve from my toolbox)
// odd prime numbers are marked as "true" in a bitvector
std::vector<bool> sieve(limit, true);
unsigned long long sum = 0;
for (unsigned int n = 3; n < limit; n += 2)
{
// accept only primes
if (!sieve[n >> 1])
continue;
// remove multiples if n < sqrt(limit)
if (n * (unsigned long long)n < limit)
for (auto i = n * n; i < limit; i += 2*n)
sieve[i >> 1] = false;
// not coprime with 10 => reject 2 and 5 (outer loop already ignores 2)
if (n == 5)
continue;
// f(n) = firstDigits + lastDigit * m
// = (n - n % 10) / 10 + (n % 10) * m
auto lastDigit = n % 10;
auto firstDigits = n / 10;
#ifdef SLOW
// use only brute-force algorithm
sum += findM(n);
continue;
#endif
#ifdef TRICK7
// surprisingly, this simple formula works whenever lastDigit is not 7
auto reduced = (n - firstDigits) / lastDigit;
if (lastDigit != 7)
{
sum += reduced;
continue;
}
#endif
// for lastDigit=7 I have to find the modular inverse of 10 mod i
// note: this works for every other lastDigit, too,
// but is much slower than the straightforward formula above
// Fermat's Little Theorem: a^p == a mod p
// divide both sides by a: a^(p-1) == 1 mod p
// once more: a^(p-2) == a^-1 mod p
// where a^-1 is the inverse of a => equal to a^(p-2) % p
// in my case, a=10 and p=n
// thus I need modularInverse(10, n) = powmod(10, n - 2, n)
auto modularInverse = powmod(10, n - 2, n);
sum += modularInverse;
}
// print result
std::cout << sum << std::endl;
return 0;
}
This solution contains 18 empty lines, 40 comments and 7 preprocessor commands.
Benchmark
The correct solution to the original Project Euler problem was found in 0.10 seconds on an Intel® Core™ i7-2600K CPU @ 3.40GHz.
Peak memory usage was about 3 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
August 23, 2017 submitted solution
August 23, 2017 added comments
Difficulty
Project Euler ranks this problem at 65% (out of 100%).
Links
projecteuler.net/thread=274 - the best forum on the subject (note: you have to submit the correct solution first)
Code in various languages:
C++ github.com/Meng-Gen/ProjectEuler/blob/master/274.cc (written by Meng-Gen Tsai)
C++ github.com/roosephu/project-euler/blob/master/274.cpp (written by Yuping Luo)
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 | |
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 | 612 | 613 |
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 273 - Sum of Squares | A Modified Collatz sequence - problem 277 >> |