#!/usr/bin/env python
# coding: utf-8
# # Part 1. Computing with Python.
# What is the difference between *Python* and a calculator? We begin this first lesson by showing how Python can be used **as** a calculator, and we move into some of the basic programming language constructs: data types, variables, lists, and loops.
#
# This programming lesson complements Chapter 0 (Foundations) in [An Illustrated Theory of Numbers](http://bookstore.ams.org/mbk-105/).
# ## Table of Contents
#
# - [Python as a calculator](#calculator)
# - [Calculating with booleans](#booleans)
# - [Declaring variables](#variables)
# - [Ranges](#ranges)
# - [Iterating over a range](#iterating)
#
# ## Python as a calculator
# Different kinds of data are stored as different *types* in Python. For example, if you wish to work with integers, your data is typically stored as an *int*. A real number might be stored as a *float*. There are types for booleans (True/False data), strings (like "Hello World!"), and many more we will see.
#
# A more complete reference for Python's numerical types and arithmetic operations can be found in the [official Python documentation](https://docs.python.org/2/library/stdtypes.html#numeric-types-int-float-long-complex). The [official Python tutorial](https://docs.python.org/2/tutorial/introduction.html) is also a great place to start.
#
# Python allows you to perform arithmetic operations: addition, subtraction, multiplication, and division, on numerical types. The operation symbols are `+`, `-`, `*`, and `/`. Evaluate each of the following cells to see how Python performs operations on *integers*. To evaluate the cell, click anywhere within the cell to select it (a selected cell will probably have a thick green line on its left side) and use the keyboard shortcut *Shift-Enter* to evaluate. As you go through this and later lessons, try to *predict* what will happen when you evaluate the cell before you hit Shift-Enter.
# In[ ]:
2 + 3
# In[ ]:
2 * 3
# In[ ]:
5 - 11
# In[ ]:
5 / 11
# The results are probably not surprising, except for the last one. Try the following for contrast.
# In[ ]:
5.0 / 11.0
# That seems better. So what is going on? Python *interprets* the input number 5 as an *int* (integer) and 5.0 as a *float*. "Float" stands for "floating point number," which are decimal approximations to real numbers. The word "float" refers to the fact that the decimal (or binary, for computers) point can float around (as in 1.2345 or 12.345 or 123.45 or 1234.5 or 0.00012345). There are deep computational issues related to how computers handle decimal approximations, and you can [read about the IEEE standards](https://en.wikipedia.org/wiki/IEEE_754) if you're interested.
#
# The distinct results of `5/11` and `5.0/11.0` show that Python *operates* on different types in different ways. The creators of Python decided that the result of integer division should be an integer: specifically, the integer obtained by *rounding down* the quotient.
#
# You might disagree with this decision... it is confusing at first! In fact the designers of Python changed their mind. If you're using Python 3.x, then the result of integer division 5/11 will be a float 0.4545... But in versions 2.x, the result of integer division will be an int. We assume that you are using **Version 2.x** throughout the tutorial!
#
# To be safe, however, you can use the modified operation `//` for integer division. This yields the same result in Python 2.x and 3.x.
# In[ ]:
-12 // 5
# Why use integer division `//` and why use floating point division? In practice, integer division is typically a faster operation. So if you only need the rounded result (and that will often be the case), use integer division. It will run much faster than carrying out floating point division then manually rounding down.
#
# Observe that floating point operations involve approximation. The result of `5.0/11.0` might not be what you expect in the last digit. Over time, especially with repeated operations, *floating point approximation* errors can add up!
# Python allows you to group expressions with parentheses, and follows the order of operations that you learn in school.
# In[ ]:
(3 + 4) * 5
# In[ ]:
3 + (4 * 5)
# In[ ]:
3 + 4 * 5 # What do you think will be the result? Remember PEMDAS?
# Now is a good time to try a few computations of your own, in the empty cell below. You can type any Python commands you want in the empty cell. If you want to insert a new cell into this notebook, it takes two steps:
# 1. Click to the left of any existing cell. This should make a blue bar appear to the left of the cell.
# 2. Use the keyboard shortcut **a** to insert a new cell **above** the blue-selected cell or **b** to insert a new cell **below** the blue-selected cell.
# You can also use the keyboard shortcut **x** do delete a blue-selected cell... be careful!
# In[ ]:
# An empty cell. Have fun!
# For number theory, *division with remainder* is an operation of central importance. Integer division provides the quotient, and the operation `%` provides the remainder. It's a bit strange that the percent symbol is used for the remainder, but this [dates at least to the early 1970s](https://softwareengineering.stackexchange.com/questions/294297/in-what-programming-language-did-the-use-of-the-percent-sign-to-mean-modulo) and has become standard across computer languages.
# In[ ]:
23 // 5 # Integer division
# In[ ]:
23 % 5 # The remainder after division
# Note in the code above, there are little "comments". To place a short comment on a line of code, just put a hashtag `#` at the end of the line of code, followed by your comment.
#
# Python gives a single command for division with remainder. Its output is a *tuple*.
# In[ ]:
divmod(23,5)
# In[ ]:
type(divmod(23,5))
# All data in Python has a type, but a common complaint about Python is that types are a bit concealed "under the hood". But they are not far under the hood. Anyone can find out the type of some data with a single command.
# In[ ]:
type(3)
# In[ ]:
type(3.0)
# In[ ]:
type('Hello')
# In[ ]:
type([1,2,3])
# The key to careful computation in Python is always being *aware of the type* of your data, and *knowing* how Python operates differently on data of different types.
# In[ ]:
3 + 3
# In[ ]:
3.0 + 3.0
# In[ ]:
'Hello' + 'World!'
# In[ ]:
[1,2,3] + [4,5,6]
# In[ ]:
3 + 3.0
# In[ ]:
3 + 'Hello!'
# In[ ]:
# An empty cell. Have fun!
# As you can see, addition (the `+` operator) is interpreted differently in the contexts of numbers, strings, and lists. The designers of Python allowed us to add *numbers* of different types: if you try to operate on an *int* and a *float*, the *int* will typically be *coerced* into a float in order to perform the operation. But the designers of Python did not give meaning to the addition of a number with a string, for example. That's why you probably received a *TypeError* after trying the above line.
#
# On the other hand, Python does interpret *multiplication* of a natural number with a string or a list.
# In[ ]:
3 * 'Hello!'
# In[ ]:
0 * 'Hello!'
# In[ ]:
2 * [1,2,3]
# Can you create a string with 100 A's (like `AAA...`)? Use an appropriate operation in the cell below.
# In[ ]:
# Practice cell
# Exponents in Python are given by the `**` operator. The following lines compute 2 to the 1000th power, in two different ways.
# In[ ]:
2**1000
# In[ ]:
2.0**1000
# As before, Python interprets an operation (`**`) differently in different contexts. When given integer input, Python evaluates `2**1000` **exactly**. The result is an integer type called a *long* integer. A nice fact about Python, for number theorists, is that it handles exact integers of arbitrary length! Many other programming languages (like C++) will give an error message if integers get too large in the midst of a computation. The letter "L" at the end of the result indicates that Python is treating the integer as a long integer.
#
# The reason that Python uses two different types, *int* and *long*, for integers is that computer hardware has built-in functionality for arithmetic of somewhat small integers (typically integers with magnitude up to 2 to the 31st or 2 to the 63rd power). So for small integers, Python will exploit the speedy hardware in computations, while for very large integers, Python will rely on its own routines.
#
# For scientific applications, one often wants to keep track of only a certain number of significant digits. If one computes the floating point exponent `2.0**1000`, the result is a decimal approximation. It is still a float. The expression "e+301" stands for "multiplied by 10 to the 301st power", i.e., Python uses *scientific notation* for large floats.
# In[ ]:
type(2**1000)
# In[ ]:
type(2.0**1000)
# In[ ]:
# An empty cell. Have fun!
# Now is a good time for reflection. Double-click in the cell below to answer the given questions. Cells like this one are used for text rather than Python code. Text is entered using *markdown*, but you can typically just enter text as you would in any text editor without problems. Press *shift-Enter* after editing a markdown cell to complete the editing process.
#
# Note that a dropdown menu in the toolbar above the notebook allows you to choose whether a cell is Markdown or Code (or a few other things), if you want to add or remove markdown/code cells.
# ### Exercises
#
# 1. What data types have you seen, and what kinds of data are they used for? Can you remember them without looking back?
#
# 2. How is division `/` interpreted differently for different types of data?
#
# 3. How is multiplication `*` interpreted differently for different types of data?
#
# 4. Why does Python have different types for short and long integers?
# Double-click this markdown cell to edit it, and answer the exercises.
#
# ## Calculating with booleans
# A *boolean* (type *bool*) is the smallest possible piece of data. While an *int* can be any integer, positive or negative, a *boolean* can only be one of two things: *True* or *False*. In this way, booleans are useful for storing the answers to yes/no questions.
#
# Questions about (in)equality of numbers are answered in Python by *operations* with numerical input and boolean output. Here are some examples. A more complete reference is [in the official Python documentation](https://docs.python.org/2/library/stdtypes.html#boolean-operations-and-or-not).
# In[ ]:
3 > 2
# In[ ]:
type(3 > 2)
# In[ ]:
10 < 3
# In[ ]:
2.4 < 2.4000001
# In[ ]:
32 >= 32
# In[ ]:
32 >= 31
# In[ ]:
2 + 2 == 4
# Which number is bigger: $23^{32}$ or $32^{23}$? Use the cell below to answer the question!
# In[ ]:
# Write your code here.
# The expressions `<`, `>`, `<=`, `>=` are interpreted here as **operations** with numerical input and boolean output. The symbol `==` (two equal symbols!) gives a True result if the numbers are equal, and False if the numbers are not equal. An extremely common typo is to confuse `=` with `==`. But the single equality symbol `=` has an entirely different meaning, as we shall see.
# Using the remainder operator `%` and equality, we obtain a divisibility test.
# In[ ]:
63 % 7 == 0 # Is 63 divisible by 7?
# In[ ]:
101 % 2 == 0 # Is 101 even?
# Use the cell below to determine whether 1234567890 is divisible by 3.
# In[ ]:
# Your code goes here.
# Booleans can be operated on by the standard logical operations and, or, not. In ordinary English usage, "and" and "or" are conjunctions, while here in *Boolean algebra*, "and" and "or" are operations with Boolean inputs and Boolean output. The precise meanings of "and" and "or" are given by the following **truth tables**.
#
# | and || True | False |
# |-----||------|-------|
# |||||
# | **True** || True | False |
# | **False** || False | False|
#
# | or || True | False |
# |-----||------|-------|
# |||||
# | **True** || True | True |
# | **False** || True | False|
#
# In[ ]:
True and False
# In[ ]:
True or False
# In[ ]:
True or True
# In[ ]:
not True
# Use the truth tables to predict the result (True or False) of each of the following, before evaluating the code.
# In[ ]:
(2 > 3) and (3 > 2)
# In[ ]:
(1 + 1 == 2) or (1 + 1 == 3)
# In[ ]:
not (-1 + 1 >= 0)
# In[ ]:
2 + 2 == 4
# In[ ]:
2 + 2 != 4 # For "not equal", Python uses the operation `!=`.
# In[ ]:
2 + 2 != 5 # Is 2+2 *not* equal to 5?
# In[ ]:
not (2 + 2 == 5) # The same as above, but a bit longer to write.
# Experiment below to see how Python handles a double or triple negative, i.e., something with a `not` `not`.
# In[ ]:
# Experiment here.
# Python does give an interpretation to arithmetic operations with booleans and numbers. Try to guess this interpretation with the following examples. Change the examples to experiment!
# In[ ]:
False * 100
# In[ ]:
True + 13
# This ability of Python to interpret operations based on context is a mixed blessing. On one hand, it leads to handy shortcuts -- quick ways of writing complicated programs. On the other hand, it can lead to code that is harder to read, especially for a Python novice. Good programmers aim for code that is easy to read, not just short!
#
# The [Zen of Python](https://www.python.org/dev/peps/pep-0020/) is a series of 20 aphorisms for Python programmers. The first seven are below.
#
# > Beautiful is better than ugly.
#
# > Explicit is better than implicit.
#
# > Simple is better than complex.
#
# > Complex is better than complicated.
#
# > Flat is better than nested.
#
# > Sparse is better than dense.
#
# > Readability counts.
# ### Exercises
#
# 1. Did you look at the truth tables closely? Can you remember, from memory, what `True or False` equals, or what `True and False` equals?
#
# 2. How might you easily remember the truth tables? How do they resemble the standard English usage of the words "and" and "or"?
#
# 3. If you wanted to know whether a number, like 2349872348723, is a multiple of 7 but **not** a multiple of 11, how might you write this in one line of Python code?
#
# 4. You can chain together `and` commands, e.g., with an expression like `True and True and True` (which would evaluate to `True`). You can also group booleans, e.g., with `True and (True or False)`.
#
# 5. Experiment to figure out the order of operations (`and`, `or`, `not`) for booleans.
#
# 6. The operation `xor` means "exclusive or". Its truth table is: `True xor True = False` and `False xor False = False` and `True xor False = True` and `False xor True = True`. How might you implement `xor` in terms of the usual `and`, `or`, and `not`?
#
#
# In[ ]:
# Use this space to work on the exercises
#
# ## Declaring variables
# A central feature of programming is the declaration of variables. When you declare a variable, you are *storing* data in the computer's *memory* and you are assigning a *name* to that data. Both storage and name-assignment are carried out with the *single* equality symbol =.
# In[ ]:
e = 2.71828
# With this command, the float 2.71828 is stored somewhere inside your computer, and Python can access this stored number by the name "e" thereafter. So if you want to compute "e squared", a single command will do.
# In[ ]:
e * e
# In[ ]:
type(e)
# You can use just about any name you want for a variable, but your name *must* start with a letter, *must* not contain spaces, and your name *must* not be an existing Python word. Characters in a variable name can include letters (uppercase and lowercase) and numbers and underscores `_`.
#
# So `e` is a valid name for a variable, but `type` is a bad name. It is very tempting for beginners to use very short abbreviation-style names for variables (like `dx` or `vbn`). But resist that temptation and use more descriptive names for variables, like `difference_x` or `very_big_number`. This will make your code readable by you and others!
#
# There are different style conventions for variable names. We use lowercase names, with underscores separating words, roughly following [Google's style conventions](https://google.github.io/styleguide/pyguide.html#Python_Style_Rules) for Python code.
# In[ ]:
my_number = 17
# In[ ]:
my_number < 23
# After you declare a variable, its value remains the same until it is changed. You can change the value of a variable with a simple assignment. After the above lines, the value of my_number is 17.
# In[ ]:
my_number = 3.14
# This command reassigns the value of my_number to 3.14. Note that it changes the type too! It effectively overrides the previous value and replaces it with the new value.
#
# Often it is useful to change the value of a variable *incrementally* or *recursively*. Python, like many programming languages, allows one to assign variables in a self-referential way. What do you think the value of S will be after the following four lines?
# In[ ]:
S = 0
S = S + 1
S = S + 2
S = S + 3
print S
# The first line `S = 0` is the initial declaration: the value 0 is stored in memory, and the name S is assigned to this value.
#
# The next line `S = S + 1` looks like nonsense, as an algebraic sentence. But reading = as **assignment** rather than **equality**, you should read the line `S = S + 1` as assigning the *value* `S + 1` to the *name* `S`. When Python interprets `S = S + 1`, it carries out the following steps.
#
# 1. Compute the value of the right side, `S+1`. (The value is 1, since `S` was assigned the value 0 in the previous line.)
# 2. Assign this value to the left side, `S`. (Now `S` has the value 1.)
#
# Well, this is a slight lie. Python probably does something more efficient, when given the command `S = S + 1`, since such operations are hard-wired in the computer and the Python interpreter is smart enough to take the most efficient route. But at this level, it is most useful to think of a self-referential assignment of the form `X = expression(X)` as a two step process as above.
#
# 1. Compute the value of `expression(X)`.
# 2. Assign this value to `X`.
# Now consider the following three commands.
# In[ ]:
my_number = 17
new_number = my_number + 1
my_number = 3.14
# What are the values of the variables my_number and new_number, after the execution of these three lines?
#
# To access these values, you can use the *print* command.
# In[ ]:
print my_number
print new_number
# Python is an *interpreted* language, which means (roughly) that Python carries out commands line-by-line from top to bottom. So consider the three lines
#
# ``` python
# my_number = 17
# new_number = my_number + 1
# my_number = 3.14
# ```
#
# Line 1 sets the value of my_number to 17. Line 2 sets the value of new_number to 18. Line 3 sets the value of my_number to 3.14. But Line 3 does *not* change the value of new_number at all.
#
# (This will become confusing and complicated later, as we study mutable and immutable types.)
# ### Exercises
#
# 1. What is the difference between `=` and `==` in the Python language?
#
# 2. If the variable `x` has value `3`, and you then evaluate the Python command `x = x * x`, what will be the value of `x` after evaluation?
#
# 3. Imagine you have two variables `a` and `b`, and you want to switch their values. How could you do this in Python?
# In[ ]:
# Use this space to work on the exercises.
#
# ## Ranges
# Python stands out for the central role played by *lists*. A *list* is what it sounds like -- a list of data. Data within a list can be of any type. Multiple types are possible within the same list! The basic syntax for a list is to use brackets to enclose the list items and commas to separate the list items.
# In[ ]:
type([1,2,3])
# In[ ]:
type(['Hello',17])
# There is another type called a *tuple* that we will rarely use. Tuples use parentheses for enclosure instead of brackets.
# In[ ]:
type((1,2,3))
# The `range` command is a flexible and powerful way to produce lists of integers. The simplest single-input form of the range command produces a list ***starting at zero*** of a given length.
# In[ ]:
range(10)
# A more complicated two-input form of the range command produces a list of integers **starting at** a given number, and **terminating before** another given number.
# In[ ]:
range(3,10)
# In[ ]:
range(-4,5)
# This is a common source of difficulty for Python beginners. While the first parameter (-4) is the starting point of the list, the list ends just before the second parameter (5). This takes some getting used to, but experienced Python programmers grow to like this convention.
# The *length* of a list can be accessed by the len command.
# In[ ]:
len([2,4,6])
# In[ ]:
len(range(10))
# In[ ]:
len(range(10,100)) # Can you figure out the length, before evaluating?
# The final variant of the range command (for now) is the *three-parameter* command of the form `range(a,b,s)`. This produces a list like `range(a,b)`, but with a "step size" of `s`. In other words, it produces a list of integers, beginning at `a`, increasing by `s` from one entry to the next, and going up to (but not including) `b`. It is best to experiment a bit to get the feel for it!
# In[ ]:
range(1,10,2)
# In[ ]:
range(11,30,2)
# In[ ]:
range(-4,5,3)
# In[ ]:
range(10,100,17)
# This can be used for descending lists too, and observe that the final number b in range(a,b,s) is not included.
# In[ ]:
range(10,0,-1)
# How many multiples of 7 are between 10 and 100? We can find out pretty quickly with the range command and the len command (to count).
# In[ ]:
range(10,100,7) # What list will this create? It won't answer the question...
# In[ ]:
range(14,100,7) # Starting at 14 gives the multiples of 7.
# In[ ]:
len(range(14,100,7)) # Gives the length of the list, and answers the question!
# ### Exercises
#
# 1. If `a` and `b` are integers, what is the length of the list `range(a,b)`?
#
# 2. Use a range command to produce the list `[1,2,3,4,5,6,7,8,9,10]`.
#
# 3. Create the list [1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5] with a single range command and another operation.
#
# 4. How many multiples of 3 are there between 300 and 3000?
# In[ ]:
# Use this space to work on the exercises.
#
# ## Iterating over a range
# Computers are excellent at repetitive reliable tasks. If we wish to perform a similar computation, many times over, a computer a great tool. Here we look at a common and simple way to carry out a repetetive computation: the "for loop". The "for loop" *iterates* through items in a list, carrying out some action for each item. Two examples will illustrate.
# In[ ]:
for n in [1,2,3,4,5]:
print n*n
# In[ ]:
for s in ['I','Am','Python']:
print s + "!"
# The first loop, **unraveled**, carries out the following sequence of commands.
# In[ ]:
n = 1
print n*n
n = 2
print n*n
n = 3
print n*n
n = 4
print n*n
n = 5
print n*n
# But the "for loop" is more efficient *and* more readable to programmers. Indeed, it saves the repetition of writing the same command `print n*n` over and over again. It also makes transparent, from the beginning, the range of values that `n` is assigned to.
#
# When you read and write "for loops", you should consider how they look unravelled -- that is how Python will carry out the loop. And when you find yourself faced with a repetetive task, you might consider whether it may be wrapped up in a for loop.
# Try to unravel the loop below, and predict the result, before evaluating the code.
# In[ ]:
P = 1
for n in range(1,6):
P = P * n
print P
# This might have been difficult! So what if you want to trace through the loop, as it goes? Sometimes, especially when debugging, it's useful to inspect every step of the loop to see what Python is doing. We can inspect the loop above, by inserting a print command within the *scope* of the loop.
# In[ ]:
P = 1
for n in range(1,6):
P = P * n
print "n is",n,"and P is",P
print P
# Here we have used the *print* command with strings and numbers together. In Python 2.x, you can print multiple things on the same line by separating them by commas. The "things" can be strings (enclosed by single or double-quotes) and numbers (int, float, etc.).
# In[ ]:
print "My favorite number is",17
# If we unravel the loop above, the linear sequence of commands interpreted by Python is the following.
# In[ ]:
P = 1
n = 1
P = P * n
print "n is",n,"and P is",P
n = 2
P = P * n
print "n is",n,"and P is",P
n = 3
P = P * n
print "n is",n,"and P is",P
n = 4
P = P * n
print "n is",n,"and P is",P
n = 5
P = P * n
print "n is",n,"and P is",P
print P
# Let's analyze the loop syntax in more detail.
# ```python
# P = 1
# for n in range(1,6):
# P = P * n # this command is in the scope of the loop.
# print "n is",n,"and P is",P # this command is in the scope of the loop too!
# print P
# ```
# The "for" command ends with a colon `:`, and the **next two** lines are indented. The colon and indentation are indicators of **scope**. The *scope* of the for loop begins after the colon, and includes all indented lines. The *scope* of the for loop is what is repeated in every step of the loop (in addition to the reassignment of `n`).
# In[ ]:
P = 1
for n in range(1,6):
P = P * n # this command is in the scope of the loop.
print "n is",n,"and P is",P # this command is in the scope of the loop too!
print P
# If we change the indentation, it changes the scope of the for loop. Predict what the following loop will do, by unraveling, before evaluating it.
# In[ ]:
P = 1
for n in range(1,6):
P = P * n
print "n is",n,"and P is",P
print P
# Scopes can be nested by nesting indentation. What do you think the following loop will do? Can you unravel it?
# In[ ]:
for x in [1,2,3]:
for y in ['a', 'b']:
print x,y
# How might you create a nested loop which prints `1 a` then `2 a` then `3 a` then `1 b` then `2 b` then `3 b`? Try it below.
# In[ ]:
# Insert your loop here.
# Among popular programming languages, Python is particular about indentation. Other languages indicate scope with open/close braces, for example, and indentation is just a matter of style. By requiring indentation to indicate scope, Python effectively removes the need for open/close braces, and enforces a readable style.
#
# We have now encountered data types, operations, variables, and loops. Taken together, these are powerful tools for computation! Try the following exercises for more practice. You can also try the exercises at the end of Chapter 0 of [An Illustrated Theory of Numbers](http://bookstore.ams.org/mbk-105/) -- some can be done easily by writing a few lines of Python code.
# ## Exercises
# 1. Describe how Python interprets division with remainder when the divisor and/or dividend is negative.
# 2. What is the remainder when $2^{90}$ is divided by $91$?
# 3. How many multiples of 13 are there between 1 and 1000?
# 4. How many *odd* multiples of 13 are there between 1 and 1000?
# 5. What is the sum of the numbers from 1 to 1000?
# 6. What is the sum of the squares, from $1 \cdot 1$ to $1000 \cdot 1000$?
# In[ ]: