<< problem 357 - Prime generating integers | Hilbert's New Hotel - problem 359 >> |
Problem 358: Cyclic numbers
(see projecteuler.net/problem=358)
A cyclic number with n digits has a very interesting property:
When it is multiplied by 1, 2, 3, 4, ... n, all the products have exactly the same digits, in the same order, but rotated in a circular fashion!
The smallest cyclic number is the 6-digit number 142857 :
142857 * 1 = 142857
142857 * 2 = 285714
142857 * 3 = 428571
142857 * 4 = 571428
142857 * 5 = 714285
142857 * 6 = 857142
The next cyclic number is 0588235294117647 with 16 digits :
0588235294117647 * 1 = 0588235294117647
0588235294117647 * 2 = 1176470588235294
0588235294117647 * 3 = 1764705882352941
...
0588235294117647 * 16 = 9411764705882352
Note that for cyclic numbers, leading zeros are important.
There is only one cyclic number for which, the eleven leftmost digits are 00000000137 and the five rightmost digits are 56789
(i.e., it has the form 00000000137...56789 with an unknown number of digits in the middle).
Find the sum of all its digits.
My Algorithm
Wikipedia explains basically all I need (see en.wikipedia.org/wiki/Cyclic_number).
Cyclic numbers c are related to so-called reptend primes: c = dfrac{b^{p-1}-1}{p}
b is the base and for decimal numbers b=10: c = dfrac{10^{p-1}-1}{p}
The numerator is simply a number consisting of 9s only (and the number of its digits is p-1) and p is a reptend prime.
A list of small reptend primes can be found on the Wikipedia page or in OEIS A001913.
The smallest reptend prime is 7. For the first example the formula becomes:
c = dfrac{10^{7-1}-1}{7} = dfrac{999999}{7} = 142857
The next reptend prime is 17. And it verifies the second example:
c = dfrac{10^{17-1}-1}{17} = dfrac{9999999999999999}{17} = 588235294117647
Note that I still must prepend a zero to that cyclic number so it has p-1 = 17-1 = 16 digits.
I know that the cyclic number ends with ...56789:
56789 * p mod 100000 = 99999
56789 * p + 1 mod 100000 = 0
The function endsWith56789()
checks exactly that.
Furthermore, the cyclic number must start with 00000000137...:
the cyclic number also appears as the first digits of 1/p, so 1/p must be 0.00000000137...
The function startsWith137()
verifies this property.
The algorithm found three candidates for the reptend prime - but according to the problem statement the number must be unique.
When I wrote the cycleDigitSum()
function I observed that two of these candidates have a cycle length shorter than p-1.
The digit sum is computed as follows:
- start with a fraction n/p = 1/p
- multiply it by 10 (→ n becomes 10n in the first iteration)
- extract the integer part i = \lfloor n/p \rfloor
- n := n - i * p so that n/p < 1 again
- add all i
- that's more or less the long division algorithm taught in school (plus adding the digits)
Only one number out of the three candidates satisfies this condition → and that's the correct result.
Alternative Approaches
All primes satisfying endsWith56789()
end with ...09891. This reduces the search space considerably.
All primes satisfying startsWith137()
are between 724637681 and 729927007.
Only three primes satisfy both conditions - that means you don't really need my prime sieve and could replace it by a much faster Miller-Rabin test (saving lots of memory, too).
Note
There is a faster way to calculate the digit sum:
when a cyclic number is split in two halves and I add the n-th digit of the first half to the n-th digit of the second half then their sum is always 9.
The number of digits of a cyclic number is p - 1, so there will be (p - 1) / 2 nines, which gives a digit sum of 9 * (p - 1) / 2.
However, my cyclicDigitSum
function serves two purposes: it calculates the digit sum and checks the cycle length.
I haven't found a faster way for the latter.
I cheated a little bit: once I knew the result I reversed the for
-loop to start at 750000000 and go backwards instead of starting at 1 and going forward.
It reduced the total time from 13 to 9.6 seconds. Now the program spends most of the time in cyclicDigitSum()
.
Interactive test
This feature is not available for the current problem.
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>
// ---------- code from my toolbox ----------
// odd prime numbers are marked as "true" in a bitvector
std::vector<bool> sieve;
// return true, if x is a prime number
bool isPrime(unsigned int x)
{
// handle even numbers
if ((x & 1) == 0)
return x == 2;
// lookup for odd numbers
return sieve[x >> 1];
}
// find all prime numbers from 2 to size
void fillSieve(unsigned int size)
{
// store only odd numbers
const unsigned int half = (size >> 1) + 1;
// allocate memory
sieve.resize(half, true);
// 1 is not a prime number
sieve[0] = false;
// process all relevant prime factors
for (unsigned int i = 1; 2*i*i < half; i++)
// do we have a prime factor ?
if (sieve[i])
{
// mark all its multiples as false
unsigned int current = 3*i+1;
while (current < half)
{
sieve[current] = false;
current += 2*i+1;
}
}
}
// ---------- problem-specific code ----------
// return true if prime * 56789 ends with ...99999
bool endsWith56789(unsigned int prime)
{
// cyclic = (10^(p-1) - 1) / p
// cyclic * p = 10^(p-1) - 1
// the last 5 digits of cyclic are ...56789
// => cyclic * p must end with 5 nines (99999)
// => add 1 to both sides => 99999 + 1 mod 100000 = 0
auto cyclic = 56789;
auto modulo = 100000;
auto product = cyclic * (unsigned long long)prime;
return (product + 1) % modulo == 0;
}
// return true if 9999...9999 / p = 137....
bool startsWith137(unsigned int prime)
{
double cyclic = 1.0 / prime;
return cyclic > 0.00000000137 &&
cyclic < 0.00000000138;
}
// return the digit sum if the prime produces a cyclic number with a cycle length of prime - 1, else return 0
unsigned int cyclicDigitSum(unsigned int prime)
{
// compute all digits of the cycle:
// compute 1/prime, 10/prime, 100/prime, etc.
// whenever the
unsigned long long result = 0;
unsigned long long numerator = 1;
unsigned int cycleLength = 0;
while (true)
{
cycleLength++;
// produce next leading digit
numerator *= 10;
result += numerator / prime;
numerator %= prime;
// cycle found (or cycle too long)
if (numerator <= 1 || cycleLength == prime)
break;
}
// wrong cycle length
if (cycleLength != prime - 1)
return 0;
// return digit sum
return result;
}
int main()
{
unsigned int limit = 750000000;
fillSieve(limit);
// check each prime
//for (unsigned int prime = 1; ; prime += 2)
for (unsigned int prime = limit-1; prime > 1; prime -= 2)
{
if (!isPrime(prime))
continue;
// verify digits
if (startsWith137(prime) && endsWith56789(prime))
{
// compute digit sum
auto digitSum = cyclicDigitSum(prime);
if (digitSum > 0) // accept only if the prime actually produces a cycle number with correct cycle length
{
std::cout << digitSum << std::endl;
break;
}
}
}
return 0;
}
This solution contains 17 empty lines, 32 comments and 2 preprocessor commands.
Benchmark
The correct solution to the original Project Euler problem was found in 9.6 seconds on an Intel® Core™ i7-2600K CPU @ 3.40GHz.
Peak memory usage was about 48 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
October 26, 2017 submitted solution
October 26, 2017 added comments
Difficulty
Project Euler ranks this problem at 25% (out of 100%).
Links
projecteuler.net/thread=358 - 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/358.cc (written by Meng-Gen Tsai)
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 | |
[new] | 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 | 614 | 615 | 616 | 617 | 618 | 619 | 620 | 621 | 622 | 623 | 624 | 625 |
626 | 627 | 628 | 629 | 630 | 631 | 632 | 633 |
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 357 - Prime generating integers | Hilbert's New Hotel - problem 359 >> |