Homework 4, Problem 4: Sequence Sums
[30 extra points; individual or pair]

Submission: Submit your hw4pr4.py file to Canvas

This problem investigates the "Read-it-and-weep" sequence:

The sequence starts like this:

1, 11, 21, 1211, 111221, 312211, 13112221, ...

This sequence is called the Look and Say sequence, or sometimes, the "Read it and Weep" sequence. (Read it out loud and you will understand why.)

Optional, but recommended:

Write a helper function readOne( s ) that takes in a string of digits s and returns the string that represents the "reading" of s. For example:

>>> readOne( '1' )

'11'

>>> readOne( '11' )

'21'

>>> readOne( '21' )

'1211'

>>> readOne( '1211' )

'111221'

A special case to consider for readOne is the case when the input, s, has length 1.

The required part: finding the first n terms...

Write a function called Weep(n) that generates and prints the first n terms in this sequence. It should also return the final term of the sequence. You will notice that generating the numbers in this sequence requires very little "math" in the classical sense, but rather logic, some string manipulation, and probably more than one loop. You may also create helper functions, if you wish (though it's not required).

Here is an example run in which the elements of the sequence are held as strings -- that is probably the most accessible way to approach the problem:

>>> Weep(10)

11

21

1211

111221

312211

13112221

1113213211

31131211131221

13211311123113112211

11131221133112132113212221

'11131221133112132113212221'

Save your Weep function in your hw4pr4.py file and submit that file.

Extra credit problems - up to +15 points

If you do write one or more of these functions, please include them in your hw4pr4.py file.

(a) The harmonic series is defined as:

1/1 + 1/2 + 1/3 + 1/4 + ...

This series can be shown to diverge; that is, the series goes to infinity. However, this series diverges very slowly. Write a function called harmonicN( numToReach ) that returns the least number of terms that must be summed in order to reach or exceed numToReach.

While this series goes to infinity, python will have trouble as the terms get very small. To handle very small numbers, you need to use a special representation that is not built into Python but available in a package called decimal. This package comes with python 2.4, so you should not need to download it. To use this package, include the statement

from decimal import *

at the top of your program. Then, you can set the "precision" (number of places of accuracy after the decimal point by including the line

getcontext().prec = 20

This gives you 20 digits of precision. You can have as much as you want!

Now, rather than using regular numbers in your code, "wrap" all of your numbers with the word Decimal. Here is an example:

>>> from decimal import *

>>> getcontext().prec = 20

>>> Decimal(1) / Decimal(3)

Decimal("0.33333333333333333333")

>>> n = 5

>>> 42 + Decimal(1)/n

Decimal("42.2")

>>> n = 17

>>> 42 + Decimal(1)/n

Decimal("42.058823529411764706")

Please note that the argument to Decimal can be a string or an integer, but may not be a floating point number! However, you can do things like this:

>>> x = 3.1415 # x is a float!

>>> y = Decimal(str(x)) # convert x to a string and then give that to Decimal!

Moreover, since Decimals are different from floats or integers, you cannot make a comparison like if Decimal("1.2") > 1.1: blah, blah, blah. However, you can do things like

if Decimal("1.2") == Decimal(str(1.2)): blah, blah, blah

For more information on the decimal package see this link.

While the harmonic series diverges, a very slight modification to this series turns it into one that converges! For any digit d between 0 and 9, if you remove those terms that contain the digit d anywhere in the denominator, then this series converges. For example, if we consider the case when digit d is 2, then we remove the terms 1/2, 1/12, 1/20, 1/21, 1/22, 1/23, ..., then this series will converge! While this may seem counter-intuitive, note that as the numbers in the denominator get large, the denominators without d become quite sparse, and the series eventually converges (although very slowly).

(b) Write a function called withoutd( d, Numterms ) that evaluates this new series with respect to digit d by adding up the first Numterms terms of the series and returning this value. Note that Numterms does not include the terms that were "thrown out" - it is the actual number of terms that were added. Use the decimal package again here for high-precision!

Here are a few things that will be useful to you:

• A number of type Decimal can be cast into a string. For example:

>>> x = 1/Decimal(3)

>>> x

Decimal("0.33333333333333333333")

>>> str(x)

'0.33333333333333333333'

• You can determine how many times a particular symbol occurs in a string using the built-in count method. It works like this: If s is some string then s.count("5") will return the number of times that the symbol 5 occurs in string s. Notice that the argument to count is a string itself! For example, "foo".count("o") will return 2.

If you have gotten to this point, you have completed problem4. You should submit your hw4pr4.py file at Canvas .