|
1
|
|
|
""" |
|
2
|
|
|
Project Euler Problem 40: Champernowne's Constant |
|
3
|
|
|
================================================= |
|
4
|
|
|
|
|
5
|
|
|
.. module:: solutions.problem40 |
|
6
|
|
|
:synopsis: My solution to problem #40. |
|
7
|
|
|
|
|
8
|
|
|
The source code for this problem can be |
|
9
|
|
|
`found here <https://bitbucket.org/nekedome/project-euler/src/master/solutions/problem40.py>`_. |
|
10
|
|
|
|
|
11
|
|
|
Problem Statement |
|
12
|
|
|
################# |
|
13
|
|
|
|
|
14
|
|
|
An irrational decimal fraction is created by concatenating the positive integers: |
|
15
|
|
|
|
|
16
|
|
|
.. math:: |
|
17
|
|
|
|
|
18
|
|
|
0.12345678910\\color{red}{1}112131415161718192021 \\dots |
|
19
|
|
|
|
|
20
|
|
|
It can be seen that the :math:`12^{th}` digit of the fractional part is :math:`1`. |
|
21
|
|
|
|
|
22
|
|
|
If :math:`d_n` represents the :math:`n^{th}` digit of the fractional part, find the value of the following expression. |
|
|
|
|
|
|
23
|
|
|
|
|
24
|
|
|
.. math:: |
|
25
|
|
|
|
|
26
|
|
|
d_1 \\times d_{10} \\times d_{100} \\times d_{1000} \\times d_{10000} \\times d_{100000} \\times d_{1000000} |
|
|
|
|
|
|
27
|
|
|
|
|
28
|
|
|
Solution Discussion |
|
29
|
|
|
################### |
|
30
|
|
|
|
|
31
|
|
|
Explicitly building this decimal representation is not clever but will work, a :math:`1000000` digit number is not large |
|
|
|
|
|
|
32
|
|
|
in the scheme of things. |
|
33
|
|
|
|
|
34
|
|
|
Use Python to build the fractional part as a string of decimal digits and then simply index into the relevant points to |
|
|
|
|
|
|
35
|
|
|
extract each :math:`d_i` needed. Finally, multiply these values to compute the answer. |
|
36
|
|
|
|
|
37
|
|
|
Solution Implementation |
|
38
|
|
|
####################### |
|
39
|
|
|
|
|
40
|
|
|
.. literalinclude:: ../../solutions/problem40.py |
|
41
|
|
|
:language: python |
|
42
|
|
|
:lines: 45- |
|
43
|
|
|
""" |
|
44
|
|
|
|
|
45
|
|
|
from functools import reduce |
|
46
|
|
|
from operator import mul |
|
47
|
|
|
|
|
48
|
|
|
|
|
49
|
|
|
def solve(): |
|
50
|
|
|
""" Compute the answer to Project Euler's problem #40 """ |
|
51
|
|
|
|
|
52
|
|
|
upper_limit = 200000 # large enough s.t. the total string length exceeds the highest index |
|
53
|
|
|
|
|
54
|
|
|
fractional_string = "".join(["{}".format(i + 1) for i in range(upper_limit)]) # build the string representation |
|
|
|
|
|
|
55
|
|
|
|
|
56
|
|
|
# Extract the relevant d_i values |
|
57
|
|
|
indices = [1, 10, 100, 1000, 10000, 100000, 1000000] |
|
58
|
|
|
digits = [fractional_string[i - 1] for i in indices] # Python using 0-based indices |
|
59
|
|
|
|
|
60
|
|
|
# Multiply each d_i together to get the answer |
|
61
|
|
|
answer = reduce(mul, map(int, digits)) |
|
62
|
|
|
|
|
63
|
|
|
return answer |
|
64
|
|
|
|
|
65
|
|
|
|
|
66
|
|
|
expected_answer = 210 |
|
|
|
|
|
|
67
|
|
|
|
Loading history...
This check looks for lines that are too long. You can specify the maximum line length.