-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathproject-euler-problem-125.html
174 lines (160 loc) · 11.9 KB
/
project-euler-problem-125.html
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
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8" />
<meta name="generator" content="Pelican" />
<title>Project Euler Problem #125</title>
<link rel="stylesheet" href="https://yashaslokesh.github.io/theme/css/main.css" />
<link href="https://yashaslokesh.github.io/feeds/all.atom.xml" type="application/atom+xml" rel="alternate" title="Yashas's Blog Atom Feed" />
<meta name="description" content="Solving Project Euler's problem #125" />
</head>
<body id="index" class="home">
<header id="banner" class="body">
<h1><a href="https://yashaslokesh.github.io/">Yashas's Blog</a></h1>
<nav><ul>
<li><a href="https://yashaslokesh.github.io/pages/about-me.html">About</a></li>
<li><a href="https://yashaslokesh.github.io/category/misc.html">misc</a></li>
<li class="active"><a href="https://yashaslokesh.github.io/category/python.html">Python</a></li>
</ul></nav>
</header><!-- /#banner -->
<section id="content" class="body">
<article>
<header>
<h1 class="entry-title">
<a href="https://yashaslokesh.github.io/project-euler-problem-125.html" rel="bookmark"
title="Permalink to Project Euler Problem #125">Project Euler Problem #125</a></h1>
</header>
<div class="entry-content">
<footer class="post-info">
<abbr class="published" title="2018-12-31T11:58:00-05:00">
Published: Mon 31 December 2018
</abbr>
<br />
<abbr class="modified" title="2018-12-31T11:58:00-05:00">
Updated: Mon 31 December 2018
</abbr>
<address class="vcard author">
By <a class="url fn" href="https://yashaslokesh.github.io/author/yashas-lokesh.html">Yashas Lokesh</a>
</address>
<p>In <a href="https://yashaslokesh.github.io/category/python.html">Python</a>.</p>
<p>tags: <a href="https://yashaslokesh.github.io/tag/python.html">python</a> <a href="https://yashaslokesh.github.io/tag/math.html">math</a> </p>
</footer><!-- /.post-info --> <p>Here's the <a href="https://projecteuler.net/problem=125">problem link</a>.</p>
<p>If you haven't attempted solving this problem, yet, go try it first!!</p>
<p>The problem wants us to find the sum of all palindromic numbers which can be written as the sum of consecutive squares of integers, under 10 million. This range is small enough that we don't have to do any optimizations, so I brute-forced the search.</p>
<p>A palindromic number is such that when its reversed, it's still the same number. Some examples: 1, 121, 595, 67876, 923329. Since we'll be computing the sum of squares of integers, we need an upper limit for the integers, which will be the square root of our limit: 10 thousand. 10 thousand squared will be exactly the limit, so we will go upto 10 thousand in our integer ranges. We're not counting 1 because the problem states that we're only concerned with the squares of positive integers.</p>
<p>So we'll go with <strong>i = 1..9,999</strong> and create a new variable for summing up the squares of consecutive integers. This new variable will start with the value <strong>i**2</strong>. Then, we make another loop inside this loop, going with <strong>j = i+1..9,999</strong>. We start with <strong>i+1</strong> for <strong>j</strong> so that we start with the square of the next consecutive integer. Then we can add <strong>j**2</strong> to our temporary sum. There <em>is</em> still a possibility that we will go over the limit with our temporary sum, like with:</p>
<div class="math">$$
9,999^2 + 9,998^2 = 199940005
$$</div>
<p>An extreme example, but it illustrates the need for an extra limit-check. Let's add in a check for if our temporary sum is greater than the limit; if it is, we'll exit the inner loop and continue with a new start integer for our temporary sum.</p>
<p>Here's what our code looks like so far:
<script src="https://gist.github.com/yashaslokesh/73a32aed50c87bda7d739e9284467056.js"></script></p>
<p>Okay, now we'll be generating all numbers which are sums of squares of consecutive integers. This is where we check if the number is a palindrome! Python makes this extremely easy with their slice objects syntax. Any <strong>str</strong> type in Python is an iterable, so we can use the syntax <strong>iterable[start:stop:step]</strong> to reverse a string: <strong>string[::-1]</strong>. We omit the start and stop, so the whole string is included, and then we use <strong>-1</strong> as the step size, which will reverse the string, then, we can check if the number is a palindrome by first converting it to a string, and then comparing this string to its reversed version. If they equal, then we have a palindrome.</p>
<p>If the candidate number is indeed a palindrome, then we have to add it to the overall sum we're trying to find. Recall: the sum of palindromic numbers which, in turn, can be written as the sum of squares of consecutive integers. So let's make a <strong>result_sum = 0</strong> that we'll add to if a number is a palindrome.</p>
<p>Here's the updated code:
<script src="https://gist.github.com/yashaslokesh/4ed6d1e48b6143d19f26c9cd96ca59c8.js"></script></p>
<p>The last if-statement is ugly, so we'll turn it into a function to make our code cleaner and easier to read:
<script src="https://gist.github.com/yashaslokesh/a8fe484a57bab4d18db150f7f68f0dc7.js"></script></p>
<p>There's still one case we haven't considered: what if two different sums turn out to be the same? This has an easy fix, let's keep track of every number. We could use a list or a set.</p>
<p>In the case of a list, we add the temporary sum to the result sum if and only if the temporary sum is not in the list and the temporary sum is a palindrome. Otherwise, we can just continue the inner loop without any special case handling. If we want to use a set, we know that a set contains only unique elements. With a set, we know that the sum of all the elements in the final set will be the answer we're looking for, so we wouldn't need a result sum in this case. I've included both cases below:</p>
<script src="https://gist.github.com/yashaslokesh/be8bd509220b9b7fbe7d66dc5fa47a6d.js"></script>
<p>Running either function gives the correct answer, as verified by Project Euler: <strong>2906969179</strong>.</p>
<p>Thanks for reading! If you have any comments, questions, or suggestions for improvement, feel free to reach out to me on <a href="https://twitter.com/yashaslokesh_">Twitter</a> or on <a href="https://github.com/yashaslokesh">GitHub</a>.</p>
<script type="text/javascript">if (!document.getElementById('mathjaxscript_pelican_#%@#$@#')) {
var align = "center",
indent = "0em",
linebreak = "false";
if (false) {
align = (screen.width < 768) ? "left" : align;
indent = (screen.width < 768) ? "0em" : indent;
linebreak = (screen.width < 768) ? 'true' : linebreak;
}
var mathjaxscript = document.createElement('script');
mathjaxscript.id = 'mathjaxscript_pelican_#%@#$@#';
mathjaxscript.type = 'text/javascript';
mathjaxscript.src = 'https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.3/latest.js?config=TeX-AMS-MML_HTMLorMML';
var configscript = document.createElement('script');
configscript.type = 'text/x-mathjax-config';
configscript[(window.opera ? "innerHTML" : "text")] =
"MathJax.Hub.Config({" +
" config: ['MMLorHTML.js']," +
" TeX: { extensions: ['AMSmath.js','AMSsymbols.js','noErrors.js','noUndefined.js'], equationNumbers: { autoNumber: 'none' } }," +
" jax: ['input/TeX','input/MathML','output/HTML-CSS']," +
" extensions: ['tex2jax.js','mml2jax.js','MathMenu.js','MathZoom.js']," +
" displayAlign: '"+ align +"'," +
" displayIndent: '"+ indent +"'," +
" showMathMenu: true," +
" messageStyle: 'normal'," +
" tex2jax: { " +
" inlineMath: [ ['\\\\(','\\\\)'] ], " +
" displayMath: [ ['$$','$$'] ]," +
" processEscapes: true," +
" preview: 'TeX'," +
" }, " +
" 'HTML-CSS': { " +
" availableFonts: ['STIX', 'TeX']," +
" preferredFont: 'STIX'," +
" styles: { '.MathJax_Display, .MathJax .mo, .MathJax .mi, .MathJax .mn': {color: 'inherit ! important'} }," +
" linebreaks: { automatic: "+ linebreak +", width: '90% container' }," +
" }, " +
"}); " +
"if ('default' !== 'default') {" +
"MathJax.Hub.Register.StartupHook('HTML-CSS Jax Ready',function () {" +
"var VARIANT = MathJax.OutputJax['HTML-CSS'].FONTDATA.VARIANT;" +
"VARIANT['normal'].fonts.unshift('MathJax_default');" +
"VARIANT['bold'].fonts.unshift('MathJax_default-bold');" +
"VARIANT['italic'].fonts.unshift('MathJax_default-italic');" +
"VARIANT['-tex-mathit'].fonts.unshift('MathJax_default-italic');" +
"});" +
"MathJax.Hub.Register.StartupHook('SVG Jax Ready',function () {" +
"var VARIANT = MathJax.OutputJax.SVG.FONTDATA.VARIANT;" +
"VARIANT['normal'].fonts.unshift('MathJax_default');" +
"VARIANT['bold'].fonts.unshift('MathJax_default-bold');" +
"VARIANT['italic'].fonts.unshift('MathJax_default-italic');" +
"VARIANT['-tex-mathit'].fonts.unshift('MathJax_default-italic');" +
"});" +
"}";
(document.body || document.getElementsByTagName('head')[0]).appendChild(configscript);
(document.body || document.getElementsByTagName('head')[0]).appendChild(mathjaxscript);
}
</script>
</div><!-- /.entry-content -->
</article>
</section>
<section id="extras" class="body">
<div class="blogroll">
<h2>links</h2>
<ul>
<li><a href="http://getpelican.com/">Pelican</a></li>
<li><a href="http://python.org/">Python.org</a></li>
<li><a href="http://jinja.pocoo.org/">Jinja2</a></li>
<li><a href="http://tutorial.math.lamar.edu/">Paul's Calc Notes</a></li>
<li><a href="https://www.pygame.org/news">Pygame</a></li>
</ul>
</div><!-- /.blogroll -->
<div class="social">
<h2>social</h2>
<ul>
<li><a href="https://yashaslokesh.github.io/feeds/all.atom.xml" type="application/atom+xml" rel="alternate">atom feed</a></li>
<li><a href="https://twitter.com/yashaslokesh_">My Twitter</a></li>
<li><a href="https://www.linkedin.com/in/yashaslokesh/">My LinkedIn</a></li>
<li><a href="https://github.com/yashaslokesh">My GitHub</a></li>
</ul>
</div><!-- /.social -->
</section><!-- /#extras -->
<footer id="contentinfo" class="body">
<address id="about" class="vcard body">
Proudly powered by <a href="https://getpelican.com/">Pelican</a>, which takes great advantage of <a href="https://www.python.org/">Python</a>.
</address><!-- /#about -->
<p>The theme is by <a href="https://www.smashingmagazine.com/2009/08/designing-a-html-5-layout-from-scratch/">Smashing Magazine</a>, thanks!</p>
</footer><!-- /#contentinfo -->
<script type="text/javascript">
(function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
(i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
})(window,document,'script','https://www.google-analytics.com/analytics.js','ga');
ga('create', 'UA-123139556-3', 'auto');
ga('send', 'pageview');
</script>
</body>
</html>