{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Part 4: Dictionaries, factorization, and multiplicative functions" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The *list type* is perfect for keeping track of ordered data. Here we introduce the *dict* (dictionary) type, which can be used for *key-value pairs*. This data structure is well suited for storing the prime decomposition of integers, in which each prime (*key*) is given an exponent (*value*). As we introduce the *dict* type, we also discuss some broader issues of *objects* and *methods* in Python programming.\n", "\n", "We apply these programming concepts to prime decomposition and multiplicative functions (e.g., the divisor sum function). This material accompanies Chapter 2 of [An Illustrated Theory of Numbers](http://illustratedtheoryofnumbers.com/index.html)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Table of Contents\n", "\n", "- [Dictionaries and factorization](#dictfact)\n", "- [Multiplicative functions](#multfunc)\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Dictionaries and factorization" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Lists, dictionaries, objects and methods" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Lists, like [2,3,5,7] are data structures built for sequentially ordered data. The **items** of a list (in this case, the numbers 2,3,5,7) are *indexed* by natural numbers (in this case, the **indices** are 0,1,2,3). Python allows you to access the items of a list through their index." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "L = [2,3,5,7]\n", "type(L)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "print L[0] # What is the output?" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "print L[3] # What is the output?" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "print L[5] # This should give an IndexError." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Python **dictionaries** are structures built for data that have a *key-value* structure. The **keys** are like indices. But instead of numerical indices (0,1,2,etc.), the keys can be any numbers or strings (technically, any immutable type)! Each key in the dictionary references a **value**, in the same way that each index of a list references an item. The syntax for defining a dictionary is {key1:value1, key2:value2, key3:value3, ...}. A first example is below. You can also read the [official tutorial](https://docs.python.org/2.7/tutorial/datastructures.html#dictionaries) for more on dictionaries." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "nemo = {'species':'clownfish', 'color':'orange', 'age':6}" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "nemo['color'] # The key 'color' references the value 'orange'." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "nemo['age'] # Predict the result." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "nemo[1] # This yields a KeyError, since 1 is not a key in the dictionary." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Dictionaries can have values of any type, and their keys can be numbers or strings. In this case, the keys are all strings, while the values include strings and integers. In this way, dictionaries are useful for storing properties of different kinds -- they can be used to store [records](https://en.wikipedia.org/wiki/Record_(computer_science%29 ), as they are called in other programming languages." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### An interlude on Python objects\n", "\n", "We have discussed how Python stores data of various *types*: int, bool, str, list, dict, among others. But now seems like a good time to discuss the fundamental \"units\" which are stored: these are called Python **objects**. If you have executed the cells above, Python is currently storing a lot of objects in your computer's memory. These objects include nemo and L. Also L[0] is an object and nemo['age'] is an object. Each of these objects are occupying a little space in memory.\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We reference these objects by the names we created, like nemo and L. But for internal purposes, Python assigns every object a unique ID number. You can see an object's ID number with the id function." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "id(L)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "id(nemo)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "id(L[0])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "It is sometimes useful to check the ID numbers of objects, to look \"under the hood\" a bit. For example, consider the following." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "x = 3\n", "y = 3\n", "print x == y # This should be true!" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "id(x)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "id(y)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "What happened? You probably noticed that both variables x and y have the same id number. That means that Python is being efficient, and not filling up two different slots of memory with the same number (3). Instead, it puts the number in one memory slot, and uses x and y as alternative names for this slot.\n", "\n", "But what happens if we change a value of one variable?" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "x = 5" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "id(x)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "id(y)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Python won't be confused by this. When we assigned x = 5, Python opened up a new memory slot for the number 5, and assigned x to refer to the number in this new slot. Note that y still \"points\" at the old slot. Python tries to be smart about memory, remembering where numbers are stored, and putting numbers into slots \"under the hood\" as it sees fit." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "id(3) # Does Python remember where it put 3?" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "id(5) # Does Python remember where it put 5?" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "id(4) # 4 is probably not in memory before. But now it is!" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "y = 5" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "id(y) # Did Python change the number in a slot? Or did it point y at another slot?" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "id(L[2]) # Python doesn't like to waste space." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "This sort of memory management can be helpful to avoid repetetion. For example, consider a list with repetition." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "R = [19,19,19]" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "id(R) # The list itself is an object." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "id(R[0]) # The 0th item in the list is an object." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "id(R[1]) # The 1st item in the list is an object." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "id(R[2]) # The 2nd item in the list is an object." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "By having each list entry point to the same location in memory, Python avoids having to fill three blocks of memory with the same number 19. " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Python *objects* can have **methods** attached to them. Methods are functions which can utilize and change the data within an object. The basic syntax for using methods is `