<< problem 39 - Integer right triangles | Pandigital prime - problem 41 >> |

# Problem 40: Champernowne's constant

(see projecteuler.net/problem=40)

An irrational decimal fraction is created by concatenating the positive integers:

0.12345678910\red{1}112131415161718192021...

It can be seen that the 12th digit of the fractional part is 1.

If d_n represents the nth digit of the fractional part, find the value of the following expression.

d_1 * d_10 * d_100 * d_1000 * d_10000 * d_100000 * d_1000000

# My Algorithm

The original problem can be solved in a trivial way:

- a `for`

-loop appends numbers to a long string until that string contains enough digits

- read relevant digits, convert them from ASCII to integers and multiply them

The Hackerrank problem asks for digits at positions up to 2^18 which cannot be done the brute force way

because we would be running out of memory (and CPU time).

My function `getDigit`

finds a digit without building such a long string.

It is based on the following observation:

- there are 9 numbers with one digit (1 to 9)

- there are 90 numbers with one digit (10 to 99)

- there are 900 numbers with one digit (100 to 999)

- ... and so on

The first part of `getDigit`

figures out how many digits the number has which is pointed to by the parameter `pos`

.

- the first 9 numbers are represented by 1*9 digits in Champernowne's constant

- the next 90 numbers are represented by 2*90=180 digits

- the next 900 numbers are represented by 3*900=2700 digits

- ... and so on: `range`

will be 9, 90, 900, ... and `digits`

will be 1, 2, 3, ...

The variable `skip`

will contain 9, 9+2*90 = 189, 9+2*90+3*900 = 2890 until the next step would exceed `pos`

.

Now that the function knows how many digit the number (pointed to by `pos`

) has, `getDigit`

process its digits.

To do so, it moves `first`

closer to `pos`

by repeated adding `range`

.

Whenever `range`

becomes too large, the next (smaller) digit has to be adjusted until we have the final value of `first`

.

That number is converted to a string and the desired digit returned.

# My code

… was written in C++11 and can be compiled with G++, Clang++, Visual C++. You can download it, too.

#include <string>
#include <iostream>
// return the digit at position "pos"
// first digit after then decimal dot has pos = 1 (not zero !)

unsigned int getDigit(unsigned long long pos)
{
// assume pos has one digit
unsigned int digits = 1;
// then there are 9 other numbers
unsigned long long range = 9;
// the smallest of them is 1
unsigned long long first = 1;
// there are 9 numbers with 1 digit
// there are 90 numbers with 2 digits
// there are 900 numbers with 3 digits
// there are 9000 numbers with 4 digits
// ...
// let's figure out the number of digits
// skip numbers with too few digits
unsigned long long skip = 0;
while (skip + digits*range < pos)
{
skip += digits*range;
// digits = 2 => range = 90 and
// digits = 3 => range = 900
// digits = 4 => range = 9000, etc.
digits++;
range *= 10;
first *= 10;
}
// now that we know the number of digits
// adjust "first" and "skip" such that the left-most/highest digit of pos and skip are identical
// then continue with the next digit
while (range > 9)
{
// could be replace by some modular arithmetic, but I'm too lazy for tough thinking ;-)
while (skip + digits*range < pos)
{
skip += digits*range;
first += range;
}
// next lower digit
range /= 10;
}
// right-most digit (basically same inner loop as above when range == 1)
while (skip + digits < pos)
{
first++;
skip += digits;
}
// skip all "skippable" digits
pos -= skip;
// strings are zero-based whereas input is one-based
pos--;
// create a string version of our number
auto s = std::to_string(first);
// extract digit and convert from ASCII to an integer
return s[pos] - '0';
}
int main()
{
unsigned int tests;
std::cin >> tests;
while (tests--)
{
unsigned int product = 1;
// read 7 positions
for (unsigned int i = 0; i < 7; i++)
{
unsigned long long pos;
std::cin >> pos;
// multiply all digits
product *= getDigit(pos);
}
// print result
std::cout << product << std::endl;
}
return 0;
}

This solution contains 12 empty lines, 28 comments and 2 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 "1 1 2 3 4 5 6 7" | ./40`

Output:

*Note:* the original problem's input `1 10 100 1000 10000 100000 1000000`

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

(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

February 25, 2017 submitted solution

April 18, 2017 added comments

# Hackerrank

see https://www.hackerrank.com/contests/projecteuler/challenges/euler040

My code solves **9** out of **9** test cases (score: **100%**)

# Difficulty

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

Hackerrank describes this problem as **medium**.

*Note:*

Hackerrank has strict execution time limits (typically 2 seconds for C++ code) and often a much wider input range than the original problem.

In my opinion, Hackerrank's modified problems are usually a lot harder to solve. As a rule thumb: brute-force is rarely an option.

# Links

projecteuler.net/thread=40 - **the** best forum on the subject (*note:* you have to submit the correct solution first)

Code in various languages:

Python: www.mathblog.dk/project-euler-40-digit-fractional-part-irrational-number/ (written by Kristian Edlund)

Haskell: github.com/nayuki/Project-Euler-solutions/blob/master/haskell/p040.hs (written by Nayuki)

Java: github.com/nayuki/Project-Euler-solutions/blob/master/java/p040.java (written by Nayuki)

Mathematica: github.com/nayuki/Project-Euler-solutions/blob/master/mathematica/p040.mathematica (written by Nayuki)

C: github.com/eagletmt/project-euler-c/blob/master/40-49/problem40.c (written by eagletmt)

Javascript: github.com/dsernst/ProjectEuler/blob/master/40 Champernowne's constant.js (written by David Ernst)

Scala: github.com/samskivert/euler-scala/blob/master/Euler040.scala (written by Michael Bayne)

# 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 39 - Integer right triangles | Pandigital prime - problem 41 >> |