Roberto Selbach

Programming

Euler 3

python programming project-euler

So the other night I was a bit bored and decided to do something to pass the time. I first came across Project Euler a while ago, but had never gone further than problem #1. Boredom is a great motivator and I went through problems #2 thru #9 last night and I decided to post my solutions in search of better ones. Feel free to comment with your suggestions.

Project Euler’s Problem #3 statement is —

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

My solution is really ugly and is basically dumb-, brute-force.

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

<span class='line'><span class="c">#!/usr/bin/python</span>
</span><span class='line'>
</span><span class='line'><span class="kn">import</span> <span class="nn">math</span>
</span><span class='line'>
</span><span class='line'><span class="n">top_number</span> <span class="o">=</span> <span class="mi">600851475143</span>
</span><span class='line'>
</span><span class='line'><span class="k">def</span> <span class="nf">is_divisor</span><span class="p">(</span><span class="n">divisor</span><span class="p">):</span>
</span><span class='line'>        <span class="k">return</span> <span class="n">top_number</span> <span class="o">%</span> <span class="n">divisor</span> <span class="o">==</span> <span class="mi">0</span>
</span><span class='line'>
</span><span class='line'><span class="k">def</span> <span class="nf">is_prime</span><span class="p">(</span><span class="n">divided</span><span class="p">):</span>
</span><span class='line'>        <span class="n">divisor</span> <span class="o">=</span> <span class="mi">3</span>
</span><span class='line'>        <span class="n">sqrt_divided</span> <span class="o">=</span> <span class="n">math</span><span class="o">.</span><span class="n">sqrt</span><span class="p">(</span><span class="n">divided</span><span class="p">)</span>
</span><span class='line'>        <span class="k">if</span> <span class="n">divided</span> <span class="o">==</span> <span class="mi">1</span><span class="p">:</span>
</span><span class='line'>                <span class="k">return</span> <span class="n">true</span>
</span><span class='line'>        <span class="k">while</span> <span class="n">divisor</span> <span class="o"><=</span> <span class="n">sqrt_divided</span><span class="p">:</span>
</span><span class='line'>                <span class="k">if</span> <span class="n">divided</span> <span class="o">==</span> <span class="n">divisor</span><span class="p">:</span>
</span><span class='line'>                        <span class="k">return</span> <span class="bp">True</span>
</span><span class='line'>                <span class="k">elif</span> <span class="n">divided</span> <span class="o">%</span> <span class="n">divisor</span> <span class="o">==</span> <span class="mi">0</span><span class="p">:</span>
</span><span class='line'>                        <span class="k">return</span> <span class="bp">False</span>
</span><span class='line'>                <span class="k">else</span><span class="p">:</span>
</span><span class='line'>                        <span class="n">divisor</span> <span class="o">+=</span> <span class="mi">2</span>
</span><span class='line'>        <span class="k">return</span> <span class="bp">True</span>
</span><span class='line'>
</span><span class='line'><span class="k">def</span> <span class="nf">main</span><span class="p">():</span>
</span><span class='line'>        <span class="n">count</span> <span class="o">=</span> <span class="mi">3</span>
</span><span class='line'>        <span class="n">go_to</span> <span class="o">=</span> <span class="n">top_number</span>
</span><span class='line'>
</span><span class='line'>        <span class="n">first_list</span> <span class="o">=</span><span class="p">[]</span>
</span><span class='line'>        <span class="k">while</span> <span class="n">count</span> <span class="o"><=</span> <span class="n">go_to</span><span class="p">:</span>
</span><span class='line'>                <span class="k">if</span> <span class="n">is_divisor</span><span class="p">(</span><span class="n">count</span><span class="p">):</span>
</span><span class='line'>                        <span class="n">first_list</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">count</span><span class="p">)</span>
</span><span class='line'>                        <span class="n">go_to</span> <span class="o">=</span> <span class="n">top_number</span> <span class="o">/</span> <span class="n">count</span>
</span><span class='line'>                        <span class="n">first_list</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">go_to</span><span class="p">)</span>
</span><span class='line'>
</span><span class='line'>                <span class="n">count</span> <span class="o">+=</span> <span class="mi">2</span>
</span><span class='line'>
</span><span class='line'>        <span class="n">second_list</span> <span class="o">=</span> <span class="nb">map</span><span class="p">(</span><span class="n">is_prime</span><span class="p">,</span> <span class="n">first_list</span><span class="p">)</span>
</span><span class='line'>        <span class="k">print</span> <span class="s">"</span><span class="si">%s</span><span class="s">"</span> <span class="o">%</span> <span class="nb">max</span><span class="p">(</span><span class="nb">zip</span><span class="p">(</span><span class="n">second_list</span><span class="p">,</span> <span class="n">first_list</span><span class="p">))[</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span>
</span><span class='line'>
</span><span class='line'><span class="k">if</span> <span class="n">__name__</span> <span class="o">==</span> <span class="s">"__main__"</span><span class="p">:</span>
</span><span class='line'>        <span class="n">main</span><span class="p">()</span>
</span>

Euler 8

python programming project-euler

So the other night I was a bit bored and decided to do something to pass the time. I first came across Project Euler a while ago, but had never gone further than problem #1. Boredom is a great motivator and I went through problems #2 thru #9 last night and I decided to post my solutions in search of better ones. Feel free to comment with your suggestions.

Project Euler’s Problem #8 statement is —

Find the greatest product of five consecutive digits in the 1000-digit number.

73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450

This is another very straightforward problem. My solution —

number = '73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450'

max_prod = 0
for i in range(1, len(number) - 4):
        prod = reduce(lambda x,y: x*y, [int(s) for s in number[i:i+5]])
        if prod > max_prod:
                max_prod = prod

print max_prod

This ran in 0m0.023s.

Euler 7

python programming project-euler

So the other night I was a bit bored and decided to do something to pass the time. I first came across Project Euler a while ago, but had never gone further than problem #1. Boredom is a great motivator and I went through problems #2 thru #9 last night and I decided to post my solutions in search of better ones. Feel free to comment with your suggestions.

Project Euler’s Problem #7 statement is —

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10001st prime number?

It’s a straightforward problem to solve using brute force, but I went with a mixed approach doing some math instead.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

<span class='line'><span class="c">#!/usr/bin/python</span>
</span><span class='line'><span class="kn">import</span> <span class="nn">math</span>
</span><span class='line'>
</span><span class='line'><span class="k">def</span> <span class="nf">is_prime</span><span class="p">(</span><span class="n">n</span><span class="p">):</span>
</span><span class='line'>    <span class="k">return</span> <span class="ow">not</span> <span class="p">(</span><span class="n">n</span> <span class="o"><</span> <span class="mi">2</span> <span class="ow">or</span> <span class="nb">any</span><span class="p">(</span><span class="n">n</span> <span class="o">%</span> <span class="n">x</span> <span class="o">==</span> <span class="mi">0</span> <span class="k">for</span> <span class="n">x</span> <span class="ow">in</span> <span class="nb">xrange</span><span class="p">(</span><span class="mi">2</span><span class="p">,</span> <span class="nb">int</span><span class="p">(</span><span class="n">n</span> <span class="o">**</span> <span class="mf">0.5</span><span class="p">)</span> <span class="o">+</span> <span class="mi">1</span><span class="p">)))</span>
</span><span class='line'>
</span><span class='line'><span class="n">currentMax</span> <span class="o">=</span><span class="mi">0</span>
</span><span class='line'><span class="n">primes</span> <span class="o">=</span> <span class="mi">1</span>
</span><span class='line'><span class="n">counter</span> <span class="o">=</span> <span class="mi">3</span>
</span><span class='line'>
</span><span class='line'><span class="k">while</span> <span class="p">(</span><span class="n">primes</span> <span class="o"><</span> <span class="mi">10001</span><span class="p">):</span>
</span><span class='line'>    <span class="k">if</span> <span class="p">(</span><span class="n">is_prime</span><span class="p">(</span><span class="n">counter</span><span class="p">)):</span>
</span><span class='line'>        <span class="n">currentMax</span> <span class="o">=</span> <span class="n">counter</span>
</span><span class='line'>        <span class="n">primes</span><span class="o">+=</span><span class="mi">1</span>
</span><span class='line'>        <span class="n">counter</span><span class="o">+=</span><span class="mi">2</span>
</span><span class='line'>
</span><span class='line'><span class="k">print</span> <span class="n">currentMax</span>
</span>

I initially used a dumb brute-force which ended up running fast enough. But reading about primes, I came across this property by which if a number cannot be divided by any number smaller than sqrt(n), it is a prime. That required significantly less tests to be performed inside is_prime, but then again, it had to perform a square root calculation for every number we need to test. In the end, the algorithm above performed slightly better (0.02s to be exact.)

Updated: Thanks to Eduardo Habkost for pointing out the fact that I had mistakenly pasted the wrong version of the script. I fixed the text to reflect that.