Homework 2

Name:
Math 213 - Math with Mathematica
Due September 25, 2009 at 11:59pm.

Introduction: The 3x+1 problem

Read page 19.
We will be investigating two more mathematical questions in Chapter 2.  The first question is that of the 3x+1 problem.  This problem is set up as follows.  Start with any integer.  At each step, look at the integer and determine if it is even or odd.  If the number is even, divide by 2.  If the number is odd, multiply by three and add 1.  What can we learn about this sequence?

We will learn how to program a function txp that does this calculation into Mathematica.  Before we get started, try by hand to understand how the function works by seeing what happens when you start with 2, 3, 5, or 6.
(Why did I not ask about 4?)

Important Concept: Q

The computer will need to determine if the number you give it is even or odd.  
Look at the top of page 20.  The function EvenQ is one of many Mathematica functions that ask a question (Q).  When you evaluate a number, EvenQ determines if the number is even or not.  Enter the next cell.

EvenQ[3]
EvenQ[4]
EvenQ[Sqrt[2]]

Go to the documentation center and search for `Q'.  You will get a good feel for all the sorts of questions you can ask Mathematica to determine if a variable satisfies a property or not.

Important Concept: If

The computer will not only need to be able to determine whether an input is even or odd, but will also need to be able to perform two different procedures depending on whether it is even or odd.  We will use the command If to do this.  The syntax for If is:

?If

That is, you type If[condition,expression1,expression2], and Mathematica will first check the condition.  If the condition is true, then it will do expression1; otherwise it will do expression2.
Evaluate the following cells and see if you understand what is going on.  If you don't, then ask a classmate and discuss.

If[True,3,5]

If[IntegerQ[Pi],4,100]

Table[If[PrimeQ[n],1,0],{n,1,10}]

Table[If[PrimeQ[n],Print[n]],{n,1,10}];

The txp function

On page 20, the function txp is defined, as well as the function tf which evaluates the function txp multiple times and outputs a list of the successive evaluations.  Define these functions in a new cell and try out a few values to confirm that they work well.

Problem 2-1: Complete Exercises 2.1 and 2.2 here.

Important Concept: While loops and negation (!)

Read through to the middle of page 21.  You will see that we will be replacing the function tf above by a function tg that only evaluates the function txp as many times as it takes to make it back to 1.  
To do this, you will be using a While loop.  The syntax for While is:

?While

That is, you type While[condition,expressions], and Mathematica will check the condition, and if it evaluates to True, it will evaluate the expressions.  One of the expressions will change variables in the condition.  Then While will check the condition again and evaluate the expressions and continue until the condition evaluates to False.  Also, just as == checks if two quantities are equal, != checks if two quantities are unequal.  Read each of the following cells and guess what you expect to see before evaluating them.

xx=7;
While[xx≥4,xx=xx-1;]
xx

yy=3;  
While[PrimeQ[yy],yy=yy+2;]
yy

zz=10;
L2 = {};  (* Define an empty list *)
While[zz!=19,L2=Append[L2,zz]; zz=zz+1;]  (* Append inserts an element into a list *)
L2

You will also see the ! operator when you wish verify the negative of a quantity.

!True

!False

aa=90;  
While[!PrimeQ[aa],aa=aa+1;]
aa

Important Concept: Module

When you are creating more complicated functions, you will need to use the Module function.

?Module

As you can see in the explanation of Module, it helps to quarantine the variables that you only use in this function.  This type of variables are called local variables.  As you can see in the following computation, even if i is defined outside the Module, you can use i inside without worrying about contamination.  It is good practice to define your functions in such a way that any variables you only use in your function are defined as local variables.

i=10;
Print["Outside Module, i is ",i]
Module[{i=20},Print["Inside Module, i is ",i]]
Print["Outside Module, i is ",i]

Problem 2-2: Using the modified 3x+1 functions tg and th.

Part (a)

Define here the functions tg and th as included on page 21 of the book, and verify that they give the outputs you expect.  Which of the programs is faster?  Which do you prefer?

Part (b)

Complete Exercise 2.3

Part (c)

Complete Exercise 2.4

Part (d)

Complete Exercise 2.5

Part (e)

Complete Exercise 2.6

Problem 2-3: Explore generalizations of the 3x+1 problem.

Complete Exercise 2.7---try at least three generalizations of the 3x+1 problem that explore different aspects of the 3x+1 problem.  Write up what you learn about each generalization---what is interesting and/or different from the 3x+1 problem.

Introduction: The Digit Cube Sum problem for multiples of three.

The second problem that we investigate in Chapter 2 is the digit cube sum problem.  This problem is based upon another process that we iterate multiple times.  The idea is described at the top of page 23.  We will be implementing this problem with the function dcs.  As with the 3x+1 problem, start out working by hand, applying the digit cube sum process repeatedly to 156.

Important Concepts:  Apply and Map

We will want to cube each digit of n.  We first use the function IntegerDigits to break apart n into a list of its digits.

Digits=IntegerDigits[156]

Mathematica even knows what we mean when we cube a list.

Digits^3

Apply

But now we have to add the entries of the list.  We could do it manually, but we'd like Mathematica to do it automatically.  To do this, we'll use the Apply operator.  Ask for help to see the syntax:

?Apply

What Apply[function,list] does for us is to take the function and apply the function to the entire list.

Apply[Plus,Digits]

Apply[Times,Digits]

Map

A related command is the Map command.  Ask for help to see the syntax:

?Map

What Map[function,list] does for us is to take the function and apply the function to each entry of the list individually and return the results in a list.  So even if Mathematica weren't able to understand Digits^3, we could use Map to do the same thing.

Map[Function[x,x^3],Digits]

In fact, you will need to use Map when your functions are more complicated, such as the txp function from before.  You can see txp does not apply directly to a list, but you can use Map to apply it to each entry of the list.

txp[{2,3}]

Map[txp,Digits]

Putting it all together

So to get the computer to do the Digit Cube Sum calculations, we'll need to define the command dcs:

dcs[x_]:=Apply[Plus,(IntegerDigits[x])^3]

Verify that dcs works by iterating it, starting with 156.

Problem 2-4: Exercises 2.9 through 2.11

Use what you learned from the 3x+1 problem to create similar types of functions related to the digit cube sum problem.

Part (a)

Complete Exercise 2.9

Part (b)

Complete Exercise 2.10

Part (c)

Complete Exercise 2.11.  Save your work so far!

Work through to the bottom of page 26

Learn about FixedPoint and FixedPointList.

Learn about Mod.

Include the function g here.

Problem 2-5: Explore the function g and the list r.

Complete Exercises 2.12 and 2.13.  You will need to read about FixedPoint and FixedPointList on page 25.

Problem 2-6: Advanced Digit Cube Sum problems

The book goes through a proof the DCS process starting at the bottom of page 26.  You can skip to page 30 for now.  If you finish early (see below), Exercises 2.14 and 2.15 are pretty neat and can be completed for extra homework credit.

Part (a)

Complete Exercise 2.16

Part (b)

Complete Exercise 2.17

Important List Concepts:  Last, Drop and MemberQ

Last

In the remainder of the section from the middle of page 30 to the top of page 32, the book discusses what happens when a sequence repeats but does not have a fixed point (a number that repeats forever).  In order to create the function that goes along with determining this occurence, we need three special functions that are not too different from functions you have seen in the past.  First, Last is a function that gives you the last element of a list.  It works just like First; see if you can guess what the following commands do before you enter them.

LL1=Range[10]
Last[LL1]
Last[RotateLeft[LL1]]

L2 =Append[LL1,11]
Last[LL2]

Drop

Drop removes elements from a list, either from the beginning or the end.  For example, Drop[list,2] removes the first two elements.  You can drop the last element(s) by using a negative number, for example, Drop[list,-1].  Try the following examples and see if it does what you expect.

LL3=Range[10]
Drop[LL3,2]
LL3=Drop[LL3,-2]
Drop[LL3,-2]

LL4=Range[10]
LL5=Table[Drop[LL4,n],{n,1,10}]
LL5=Drop[LL5,2]
LL5=Drop[LL5,-3]

MemberQ

You will also need to be able to determine if a given number is an element of a list.  You can use MemberQ to ask this question.

?MemberQ

As you can see, MemberQ[list,element] will return True if element is a member of the list and False if not.  Try to determine what the following will give:

MemberQ[{1,Pi,4,20},4]

MemberQ[Range[10],11]

MemberQ[Range[10],{1}]

Why does the last command give False?

The dcg function

Create the function dcg as described in the book.  Make sure that you understand what MemberQ[Drop[d,-1],Last[d]] does.

Problem 2-7: Digit Cube Sum repeating cycles

Part (a)

Complete Exercise 2.19

Part (b)

Complete Exercise 2.20

For those who complete the assignment early:

If you have finished early, complete some of these exercises for extra homework credit.  These may also become investigatory projects that you can use for the first of your two course projects.

The dcs proof for multiples of three

Go back and take a look at the proof on pages 26-29.  
Try to complete Exercises 2.14 and 2.15. 
If you have taken classes involving proofs before, try to follow the proof the authors give.

The dcs proof for numbers equal to 2 mod 3.

Try out Exercise 2.18.

Other Bases

Complete the section on page 32 about ``Other Bases'', including Exercise 2.21

Josephus Revisited

Complete the section on pages 32-33 about ``Josephus Revisited'', including Exercise 2.22