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

A more formal way to describe n and f(n) is:

(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 to`echo 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 a 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=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

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)

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

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 |

I scored 13,386 points (out of 15600 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 >> |