|
1
|
|
|
""" |
|
2
|
|
|
Project Euler Problem 46: Goldbach's Other Conjecture |
|
3
|
|
|
===================================================== |
|
4
|
|
|
|
|
5
|
|
|
.. module:: solutions.problem46 |
|
6
|
|
|
:synopsis: My solution to problem #46. |
|
7
|
|
|
|
|
8
|
|
|
The source code for this problem can be |
|
9
|
|
|
`found here <https://bitbucket.org/nekedome/project-euler/src/master/solutions/problem46.py>`_. |
|
10
|
|
|
|
|
11
|
|
|
Problem Statement |
|
12
|
|
|
################# |
|
13
|
|
|
|
|
14
|
|
|
It was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and twice a |
|
|
|
|
|
|
15
|
|
|
square. |
|
16
|
|
|
|
|
17
|
|
|
.. math:: |
|
18
|
|
|
|
|
19
|
|
|
9 &= 7 + 2 \\times 1^2 \\\\ |
|
20
|
|
|
15 &= 7 + 2 \\times 2^2 \\\\ |
|
21
|
|
|
21 &= 3 + 2 \\times 3^2 \\\\ |
|
22
|
|
|
25 &= 7 + 2 \\times 3^2 \\\\ |
|
23
|
|
|
27 &= 19 + 2 \\times 2^2 \\\\ |
|
24
|
|
|
33 &= 31 + 2 \\times 1^2 |
|
25
|
|
|
|
|
26
|
|
|
It turns out that the conjecture was false. |
|
27
|
|
|
|
|
28
|
|
|
What is the smallest odd composite that cannot be written as the sum of a prime and twice a square? |
|
29
|
|
|
|
|
30
|
|
|
Solution Discussion |
|
31
|
|
|
################### |
|
32
|
|
|
|
|
33
|
|
|
Iterate through all odd composite numbers :math:`k` in ascending order and search for a solution of the form: |
|
|
|
|
|
|
34
|
|
|
|
|
35
|
|
|
.. math:: |
|
36
|
|
|
|
|
37
|
|
|
k = p + 2 \\times i^2 |
|
38
|
|
|
|
|
39
|
|
|
Given :math:`k` and a list of primes less than :math:`k` the only remaining unknown is :math:`i`. Any solutions can be |
|
|
|
|
|
|
40
|
|
|
found by testing whether the following is a square for any prime :math:`p \\lt k`: |
|
41
|
|
|
|
|
42
|
|
|
.. math:: |
|
43
|
|
|
|
|
44
|
|
|
\\frac{k - p}{2} |
|
45
|
|
|
|
|
46
|
|
|
Apply this search logic and return the first and thus lowest :math:`k` without any such solutions. |
|
47
|
|
|
|
|
48
|
|
|
Solution Implementation |
|
49
|
|
|
####################### |
|
50
|
|
|
|
|
51
|
|
|
.. literalinclude:: ../../solutions/problem46.py |
|
52
|
|
|
:language: python |
|
53
|
|
|
:lines: 56- |
|
54
|
|
|
""" |
|
55
|
|
|
|
|
56
|
|
|
from lib.numbertheory import is_square |
|
57
|
|
|
from lib.sequence import Primes |
|
58
|
|
|
|
|
59
|
|
|
|
|
60
|
|
|
def solve(): |
|
61
|
|
|
""" Compute the answer to Project Euler's problem #46 """ |
|
62
|
|
|
|
|
63
|
|
|
upper_bound = 10000 # found by trial and error |
|
64
|
|
|
|
|
65
|
|
|
primes = list(Primes(upper_bound=upper_bound)) |
|
66
|
|
|
|
|
67
|
|
|
k = 3 |
|
68
|
|
|
while k < upper_bound: |
|
69
|
|
|
while k in primes: |
|
70
|
|
|
k += 2 # ensure k is an odd composite |
|
71
|
|
|
|
|
72
|
|
|
# Search for a satisfying p,i s.t. k = p + 2 * i^2 |
|
73
|
|
|
for prime in [prime for prime in primes if prime < k]: |
|
74
|
|
|
x = (k - prime) // 2 |
|
|
|
|
|
|
75
|
|
|
if is_square(x): |
|
76
|
|
|
break |
|
77
|
|
|
else: |
|
78
|
|
|
return k |
|
79
|
|
|
|
|
80
|
|
|
k += 2 |
|
81
|
|
|
|
|
82
|
|
|
|
|
83
|
|
|
expected_answer = 5777 |
|
|
|
|
|
|
84
|
|
|
|
Loading history...
This check looks for lines that are too long. You can specify the maximum line length.