IntroductionToPython.sagews

A quick introduction to Python

Sage is based on the python programming language. This demo is introduction to the basics of the python language.

Variables and simple types

In Python, typing is dynamic; there is no such thing as declaring variables.

a = 3
a = "123"

The function type returns the type of an object obj.

type(a)

a = True
type(a)

To convert an object to a type typ just write typ(obj) as in int("123"). The command isinstance(ex, typ) returns whether the expression ex is of type typ.

int(a)

bool("123")

isinstance(a,int)

Some simple types of Python: bool, str, int.

type(True)

type("123")

type(int(3))

By default, integers are not int but Sage Integers.

type(3)

a = 150
type(a)

a.factor()

Other python types

standard types also contain list, tuple, set, dict.

A list is a data structure which groups values. It is constructed using brackets as in [1, 3, 4]. The range function creates integer lists. One can also create lists using list comprehension:

l = [1,2,3,4]
l

l = ["a","b",3,4.5]
l

l = range(5)
l

l = [3*i for i in range(5)]
l

You can access and modify elements of the list.

l[3]

l[3] = 2
l

l.append(8)
l

You can extend a list or concatenate it with another list.

l2 = [1,2,3]
l.extend(l2)
l

[1,3,5] + [2,4,6]

some other operations:

l

l.reverse()
l

l.sort()
l

A tuple is very similar to a list, it is constructed using parentheses and cannot be changed after its creation, it is immutable.

t = (1,2,3)
t

t = tuple(range(5))
t

t = tuple(3*i for i in range(5))
t

t[3]

t[3] = 2

A set is a data structure which contains values without multiplicities or order. One creates it from a list (or any iterable) with the constructor set(). The elements of a set must be hashable, only immutable elements can be hashable.

s = set([1,2,1,3])
s

s.add(3)
s

s.add(4)
s

tset = set()
tset

tset.add([1,3])

tset.add((1,3))
tset.add((1,4))
tset

s = {x for x in 'abracadabra' if x not in 'abc'}
s

A dictionary is an association table, which associate values to keys. Keys must be hashable. One creates dictionaries using the constructor dict, or using the syntax:

d = {"a":58, "b":27}
d

d["a"]

d["c"] = 52
d

d["a"] = 30
d

d = dict((i,i^2) for i in xrange(5))
d

d = {i:i^2 for i in xrange(5)}
d

You can iterate either on keys, values or both.

[key for key in d]

[val for val in d.itervalues()]

[(key,val) for key,val in d.iteritems()]

Controle structures

In Python, there is no keyword for the beginning and the end of an instructions block. Blocks are delimited thanks to indentation. Most of the time a new block is introduced by :. Python has the following control structures:

• Conditional instruction:

b = 8
if b%2==0:
    a = b/2
else:
    a = 3*b +1
a

a = b/2 if b%2==0 else 3*b+1
a

if b==8:
    a = 3
     c = 4

• Iterative instructions

for i in xrange(3):
    print i

l = [2,4,5,68]
for i in l:
    print i

a = 5
while a!=1:
    print a
    if a%2==0:
        a/=2
    else:
        a=a*3+1

Functions

In what follows, we deal with functions in the sense of programming languages. Mathematical functions are handled by sage in a different way. In particular it doesn’t make sense to do mathematical manipulation such as additions or derivations on Python functions.

def my_function(a):
    if(a%2):
        return a*3+1
    else:
        return a/2

my_function(5)

Functions are first class objects like any other.  For example, they can be passed in as arguments to other functions.

my_function

f = my_function
f(3)

def c(x):
    return x*x

def compose(f,x,n):
    for i in range(n):
        x = f(x)
    return x

compose(c,2,3)

Python is object oriented: some functions are methods in objects.

a = 45
f = a.factor
f

f()

You can give default values for arguments in functions:

def add_n(x, n=1):
      return x + n

add_n(4)

add_n(4, n=100)

add_n(4, 1000)

You can return multiple things from a function:

def g(x):
      return x, x*x

g(2)

Exercices

Creating Lists I: [Square brackets]¶

Example:

L = [3, Permutation([5,1,4,2,3]), 17, 17, 3, 51]
L

Exercise: Create the list [63, 12, -10, \text{``a''}, 12], assign it to the variable L, and print the list.

# edit here

Exercise: Create the empty list (you will often need to do this).

# edit here

Creating Lists II: range¶

The range function provides an easy way to construct a list of integers. Here is the documentation of the range function:

range([start,] stop[, step]) -> list of integers

Return a list containing an arithmetic progression of integers.
range(i, j) returns [i, i+1, i+2, ..., j-1]; start (!) defaults to 0.
When step is given, it specifies the increment (or decrement). For
example, range(4) returns [0, 1, 2, 3].  The end point is omitted!
These are exactly the valid indices for a list of 4 elements.

Exercise: Use range to construct the list [1,2,\ldots,50].

# edit here

Exercise: Use range to construct the list of even numbers between 1 and 100 (including 100).

# edit here

Exercise: The step argument for the range command can be negative. Use range to construct the list [10, 7, 4, 1, -2].

# edit here

The range function returns python int, they are different from Sage Integer. The srange function is an equivalent of the range function that returns Sage Integers.

Exercise: look at the different outputs below then create a list of all Integer factorizations for 0<n<100.

b = int(2)
[i/b for i in range(20)]

[i/b for i in srange(20)]

Creating Lists III: list comprehensions¶

List comprehensions provide a concise way to create lists from other lists (or other data types).

Example We already know how to create the list [1, 2, \dots, 16]:

range(1,17)

Using a list comprehension, we can now create the list [1^2, 2^2, 3^2, \dots, 16^2] as follows:

[i^2 for i in range(1,17)]

sum([i^2 for i in range(1,17)])

Exercise: [Project Euler, Problem 6]

The sum of the squares of the first ten natural numbers is

(1^2 + 2^2 + ... + 10^2) = 385

The square of the sum of the first ten natural numbers is

(1 + 2 + ... + 10)^2 = 55^2 = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is

3025 - 385 = 2640

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

# edit here

# edit here

# edit here

Filtering lists with a list comprehension¶

A list can be filtered using a list comprehension.

Example: To create a list of the squares of the prime numbers between 1 and 100, we use a list comprehension as follows.

[p^2 for p in [1,2,..,100] if is_prime(p)]

Exercise: Use a list comprehension to list all the natural numbers below 20 that are multiples of 3 or 5. Hint:

• To get the remainder of 7 divided by 3 use 7%3.
• To test for equality use two equal signs (==); for example, 3 == 7.

# edit here

Project Euler, Problem 1: Find the sum of all the multiples of 3 or 5 below 1000.

# edit here

Nested list comprehensions¶

List comprehensions can be nested!

Examples:

[(x,y) for x in range(5) for y in range(3)]

[[i^j for j in range(1,4)] for i in range(6)]

matrix([[i^j for j in range(1,4)] for i in range(6)])

Exercise:

A Pythagorean triple is a triple (x,y,z) of positive integers satisfying x^2+y^2=z^2. The Pythagorean triples whose components are at most 10 are:

[(3, 4, 5), (4, 3, 5), (6, 8, 10), (8, 6, 10)]\,.

Using a filtered list comprehension, construct the list of Pythagorean triples whose components are at most 50.

# edit here

# edit here

Project Euler, Problem 9: There exists exactly one Pythagorean triplet for which a + b + c = 1000. Find the product abc.

# edit here

Slicing Lists¶

You can slice a list using the syntax L[start : stop : step]. This will return a sublist of L.

Exercise: Below are some examples of slicing lists. Try to guess what the output will be before evaluating the cell.

L = range(20)
L

L[3:15]

L[3:15:2]

L[15:3:-1]

L[:4]

L[:]

L[::-1]

Advanced exercise: The following function combines a loop with the some of the list operations above. What does the function do?

def f(number_of_iterations):
      L = [1]
      for n in range(2, number_of_iterations):
          L = [sum(L[:i]) for i in range(n-1, -1, -1)]
      return numerical_approx(2*L[0]*len(L)/sum(L), digits=50)

Using sets and dictionaries

Exercise:   create the set of letters different than 'b' contained in the string "abracadabra"

#edit here

Exercise: The method a.factor() when a is an Integer gives an object that represents the prime factors of a. It can be converted to a list or a dictionary. Test the methods below then create a dictionary  that associate with a natural number n<100, the number of different prime factors of n.

Note: be carreful, the range function returns python int and not Sage Integer, you can compute the factor method only on Sage Integer, use the srange function instead.

a = 150
a.factor()

list(a.factor())

dict(a.factor())

len(a.factor())

# edit here

Functions

Exercises:

1. Write a function is_even returning True if n is even and False otherwise.
2. Write a function every_other which takes a list l and returns a list containing every other element of l
3. Write a function computing the n-th Fibonacci number. Try to improve performance.