<< problem 523 - First Sort I | Divisibility of factorials - problem 549 >> |
Problem 539: Odd elimination
(see projecteuler.net/problem=539)
Start from an ordered list of all integers from 1 to n.
Going from left to right, remove the first number and every other number afterward until the end of the list.
Repeat the procedure from right to left, removing the right most number and every other number from the numbers left.
Continue removing every other numbers, alternating left to right and right to left, until a single number remains.
Starting with n = 9, we have:
1 2 3 4 5 6 7 8 9
2 4 6 8
2 6
6
Let P(n) be the last number left starting with a list of length n.
Let S(n) = sum_{k=1}^n{P(k)}
You are given P(1)=1, P(9) = 6, P(1000)=510, S(1000)=268271.
Find S(10^18) mod 987654321.
Not solved yet
My code works for the "small" example but can't find the solution to the "big" problem.
What I've Done So Far
The brute-force code to find P(n)
filters an array and returns the last number (see bruteForceP
).
bruteForceS
is a simple loop and calls bruteForceP
.
These two functions can solve S(1000) quite fast but anything beyond n = 10^5 would take forever.
Looking at the values produces by bruteForceP
I spotted a pattern after a while:
- two consecutive numbers P(x) and P(x+1) are always P(x)=P(x+1) if x is even (it's a multiple of 2)
- two consecutive numbers P(x) and P(x+2) are always P(x)=P(x+2)-2 if x is a multiple of 4
- combining both: P(x+1) = P(x+3) - 2 if x is a multiple of 4
- for whatever reason P(2) is an exception
n12345678910111213141516
P(n)1222244668866886
Even more interesting, P(x) = 4 * P(x div 4) if x-2 or x-3 is a multiple of 4.
If x or x-1 is a multiple of 4 then I have to subtract 2.
E.g. P(7) = 4 * P( 7 div 4) = 4 * P(1) = 4 * 1 = 4
and P(12) = 4 * P(12 div 4) - 2 = 4 * P(3) - 2 = 4 * 2 - 2 = 6
Now I can easily compute P(10^18) but S(10^18) would still require a loop with 10^18 iterations.
It's easy to compute 4 numbers at once, but it doesn't help much because S(10^18) is still out of reach.
S(10^8) is found in a few seconds and OpenMP might help me to solve even S(10^10) in under a minute.
I think that computing more than four numbers at once is possible but can't deduce a nice pattern.
So far my solution was based on a "lucky" discovery and I'm afraid that I don't get lucky twice on the same problem.
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>
// find last number standing ... between 1 and n
unsigned int bruteForceP(unsigned int n)
{
std::vector<unsigned int> numbers;
// fill with 1..limit
for (unsigned int i = 1; i <= n; i++)
numbers.push_back(i);
bool left2right = true;
while (numbers.size() > 1)
{
std::vector<unsigned int> next;
// from left to right: keep numbers at odd positions (1,3,5,...), note: zero-based index
// from right to left: if there is an odd amount of numbers, keep odd numbers, else even numbers
size_t i = left2right ? 1 : numbers.size() % 2;
for (; i < numbers.size(); i += 2)
next.push_back(numbers[i]);
// ... and the other direction in the next iteration
left2right = !left2right;
numbers = std::move(next);
}
return numbers[0];
}
// sum of bruteForceP(1..limit)
// solves S(10^5) in a few seconds
unsigned int bruteForceS(unsigned int limit)
{
unsigned int sum = 0;
for (unsigned int i = 1; i <= limit; i++)
sum += bruteForceP(i);
return sum;
}
// there is a pattern:
// P(n) = 4 * P(n/4) - 2 if n % 4 = {0,1}
// P(n) = 4 * P(n/4) if n % 4 = {2,3}
// and the initial values are P(1) = 1, P(2) = P(3) = 2
unsigned long long fastP(unsigned long long n)
{
// it's pretty fast to solve P() for small n with brute force
const size_t CacheSize = 20;
static unsigned char cache[CacheSize] = { 0 };
if (n <= CacheSize)
{
// actually I could hard-wire 1 => 1, 2 => 2, 3 => 2, 4 => 2
// but that would render my nice brute-force code useless ;-)
if (cache[n] == 0)
cache[n] = bruteForceP(n);
return cache[n];
}
auto result = fastP(n / 4) * 4;
// keep result unchanged if second-to-last bit is set (same as n % 4 >= 2)
return result + (n & 2) - 2; // branch-free code of if (n%4>=2) return result; else return result - 2;
}
// right now almost the same code as bruteForceS, but calls fastP instead of bruteForceP and respects the modulo
// solves S(10^8) in a few seconds
unsigned long long slowS(unsigned long long limit, unsigned int modulo = 987654321)
{
unsigned long long sum = 0;
for (unsigned long long i = 1; i <= limit; i++)
{
auto current = fastP(i);
sum += current;
//std::cout << i << ": +" << current << " =" << sum << std::endl;
// avoid too frequent modulo operations
if (sum > 10 * modulo)
sum %= modulo;
}
return sum % modulo;
}
// no idea yet how to accelerate slowS ...
unsigned long long fastS(unsigned long long /*limit*/, unsigned int /*modulo = 987654321*/)
{
return 0;
}
int main()
{
unsigned long long limit = 1000000000000000000ULL;
std::cin >> limit;
// solve examples
//std::cout << bruteForceP(9) << std::endl;
//std::cout << bruteForceS(1000) << std::endl;
std::cout << slowS(limit) << std::endl;
return 0;
}
This solution contains 14 empty lines, 23 comments and 2 preprocessor commands.
Changelog
October 25, 2017 solve up to 10^9
Difficulty
Project Euler ranks this problem at 30% (out of 100%).
Links
projecteuler.net/thread=539 - 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 | |
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 | 614 |
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 523 - First Sort I | Divisibility of factorials - problem 549 >> |