Playing with Python

Jonathon Sumner
Physics Department
Dawson College
Sameer Bhatnagar
Physics Department
Dawson College
March 8, 2020
March 8, 2020

Meeting 2

A review of the basics... but mainly riddles!

Reference material

In our opinion, the best way to learn a coding language is to just start using it and figure out things as you go along. It may sound a bit odd to approach something as systematic as computer programming in such a random way, but don't worry: it works out just fine.

When you need to look up some new syntax or get help with how Python can be used to solve a certain problem, where should you go? The Python Tutorial. With a basic understanding of sections 3, 4, and 5 you can go a very long way! They cover:

We won't repeat any of that stuff here; you should refer to those pages as needed while we tackle the tasks below.

Warm ups

To get started, let's try the first problem on Project Euler. If you want to be able to check your answer and track your progress, you will have to register for a free account.

Sample task

Here is our solution:

Code sample: Project Euler Problem 1 - Solution
# Problem 1 
sum = 0
for i in range(1,1000):
    if i%3 == 0 or i%5 == 0:
        sum += i

print(sum)

There are a few key ideas to take note of:

  1. Variable assignment. In Python, you just use the = sign, no need to declare the type of variable.
  2. The for loop. Notice the compact notation: no extra brackets as in many other languages. The range function simply returns integers between 1 and 999, inclusively.
  3. The if statement. Again, no extra brackets are needed. The == sign is used to evaluate equality.
  4. The print() statement outputs to the terminal.

Perhaps the most important thing to notice is that scope is defined by indentation: everything that belongs to the for loop is indented once with respect to the line that it started on. The same is true for the if statement.

Now it is your turn to try one.

Individual task

Success?

Ok, let's do one more. Project Euler Problem 3 is asking us to find the largest prime factor for a very large number. We are not going to be fancy here: brute force is fine. But, we should start thinking about coding style. Checking for a prime number is a common enough task and we should write a function for that job.

Individual task

The Python Challenge

Now let's try something with more of a Python focus. Nadav Samet launched the Python Challenge back in 2005 as "an entertaining way to explore the Python Programming Language." It is essentially a series of riddles, each of which requires a little bit of Python to solve. The game is very addictive. I am currently on Level 6 of 33 and spend far too much time working on it.

Group task

Postscript

Nice work today!

A last thought on Project Euler Problem 3 (spoiler alert: solution below). One person at the meet-up today had an excellent solution for this problem... I don't remember exactly how he did it, but I've tried to reproduce something similar here.

Recall that we want to find the largest prime factor for a very large number. The key idea here is the fundamental theorem of arithmetic, which states that any number is either prime or can be produced by multiplying a unique set of primes together. Let $X$ represent the number we wish to factor and $p$ a prime number. If $X$ is not prime it can be expressed as:

\[ X = p_1\times p_2\times p_3 \times ... \times p_n \]

So our search for the largest prime factor is really a search for $p_n$ and we can rearrange the above equation to solve for it

\[ p_n = \frac{X}{p_1\times p_2\times p_3 \times ... \times p_{n-1}} \]

Our code doesn't have to check every number from 1 to $X$. We just have to search for prime numbers. Whenever we find one that is a factor of $X$ we divide $X$ by it (we should actually try to divide $X$ by the factor many times as prime factors can be repeated). We stop when our search passes the current value of $X$.

Code sample: Searching for the largest prime factor
number = 600851475143
prime_list = [2]
largest_prime_factor = 1
i = 3
while i <= number:
    for j in prime_list:
        if i%j == 0:
            break # not prime so move on to next number
    else:
        prime_list.append(i) # we made it through without breaking, number must be prime so append it to the list
        if number%i == 0:
            largest_prime_factor = i
            number = int(number / i)
    i += 1

print(largest_prime_factor)

This code introduces some new ideas. First, prime_list is a list (like an array in other languages) and we can access values stored in the list using [], i.e. prime_list[0] stores the value 2. We also introduce break, which simply tells Python to leave the current loop. The else is special: it only runs IF the for loop gets all the way to the end (i.e. the break statement is never encountered). This is some pretty dense Python!