(*^ ::[ frontEndVersion = "Microsoft Windows Mathematica Notebook Front End Version 2.2"; microsoftWindowsStandardFontEncoding; fontset = title, "Times New Roman", 24, L0, center, nohscroll, bold; fontset = subtitle, "Times New Roman", 18, L0, center, nohscroll, bold; fontset = subsubtitle, "Times New Roman", 14, L0, center, nohscroll, bold; fontset = section, "Times New Roman", 14, L0, bold, grayBox; fontset = subsection, "Times New Roman", 12, L0, bold, blackBox; fontset = subsubsection, "Times New Roman", 10, L0, bold, whiteBox; fontset = text, "Times New Roman", 12, L0; fontset = smalltext, "Times New Roman", 10, L0; fontset = input, "Courier New", 12, L0, nowordwrap, bold; fontset = output, "Courier New", 12, L0, nowordwrap; fontset = message, "Courier New", 10, L0, nowordwrap, R65535; fontset = print, "Courier New", 10, L0, nowordwrap; fontset = info, "Courier New", 10, L0, nowordwrap; fontset = postscript, "Courier New", 8, L0, nowordwrap; fontset = name, "Times New Roman", 10, L0, nohscroll, italic, B65535; fontset = header, "Times New Roman", 10, L0, right, nohscroll; fontset = footer, "Times New Roman", 10, L0, right, nohscroll; fontset = help, "Times New Roman", 10, L0, nohscroll; fontset = clipboard, "Times New Roman", 12, L0, nohscroll; fontset = completions, "Times New Roman", 12, L0, nowordwrap, nohscroll; fontset = graphics, "Courier New", 10, L0, nowordwrap, nohscroll; fontset = special1, "Times New Roman", 12, L0, nowordwrap, nohscroll; fontset = special2, "Times New Roman", 12, L0, center, nowordwrap, nohscroll; fontset = special3, "Times New Roman", 12, L0, right, nowordwrap, nohscroll; fontset = special4, "Times New Roman", 12, L0, nowordwrap, nohscroll; fontset = special5, "Times New Roman", 12, L0, nowordwrap, nohscroll; fontset = leftheader, "Times New Roman", 12, L0, nowordwrap, nohscroll; fontset = leftfooter, "Times New Roman", 12, L0, nowordwrap, nohscroll; fontset = reserved1, "Courier New", 10, L0, nowordwrap, nohscroll;] :[font = title; inactive; nohscroll; center; ] Lists :[font = subsection; inactive; startGroup; Cclosed; ] List Construction :[font = text; inactive; ] We start with a description of the basic list building commands. The simplest are Range and Table. The first, Range, generates a list of numbers in arithmetic progression. The format is Range[ min, max,step] :[font = input; startGroup; nowordwrap; ] Range[ 1, 90, 8] :[font = output; inactive; formatted; output; endGroup; nowordwrap; ] {1, 9, 17, 25, 33, 41, 49, 57, 65, 73, 81, 89} ;[o] {1, 9, 17, 25, 33, 41, 49, 57, 65, 73, 81, 89} :[font = input; startGroup; nowordwrap; ] Range[ 0.1, 3.0, 0.6] :[font = output; inactive; formatted; output; endGroup; nowordwrap; ] {0.1, 0.7, 1.3, 1.9, 2.5} ;[o] {0.1, 0.7, 1.3, 1.9, 2.5} :[font = text; inactive; ] The Table command is more general as it can take a function as its first argument. :[font = input; startGroup; nowordwrap; ] Table[ i^2, { i, 1, 5}] :[font = output; inactive; formatted; output; endGroup; nowordwrap; ] {1, 4, 9, 16, 25} ;[o] {1, 4, 9, 16, 25} :[font = text; inactive; ] Table can take more than one iterator. :[font = input; startGroup; nowordwrap; ] Table[ x^2+y^2, {x,1,3}, {y,1,4}] :[font = output; inactive; formatted; output; endGroup; nowordwrap; ] {{2, 5, 10, 17}, {5, 8, 13, 20}, {10, 13, 18, 25}} ;[o] {{2, 5, 10, 17}, {5, 8, 13, 20}, {10, 13, 18, 25}} :[font = text; inactive; ] The result is a list of lists in which the first list has x fixed to 1 and y varies from 1 to 4, then x is fixed to 2 and so on. The additional braces can be removed by using the Flatten command. :[font = text; inactive; ] We can add elements to an existing list by using the Append, Prepend and Insert commands. To combine two lists, use the Union and Join commands. :[font = input; startGroup; nowordwrap; ] list= {}; list= Append[ list, 3] list= Append[ list, 5] :[font = message; inactive; formatted; output; nowordwrap; ] General::spell1: Possible spelling error: new symbol name "list" is similar to existing symbol "List". ;[o] General::spell1: Possible spelling error: new symbol name "list" is similar to existing symbol "List". :[font = output; inactive; formatted; output; nowordwrap; ] {3} ;[o] {3} :[font = output; inactive; formatted; output; endGroup; nowordwrap; ] {3, 5} ;[o] {3, 5} :[font = text; inactive; ] We see that Append adds the element to the end of the list. Append returns a list with the element added, but does not modify the argument. For example, list1= Append[ list, 7] will not modify list. :[font = input; startGroup; nowordwrap; ] list1= Append[ list, 7]; list list1 :[font = output; inactive; formatted; output; nowordwrap; ] {3, 5} ;[o] {3, 5} :[font = output; inactive; formatted; output; endGroup; nowordwrap; ] {3, 5, 7} ;[o] {3, 5, 7} :[font = text; inactive; ] To modify the argument so that an additional assignment is not necessary, use the AppendTo command. AppendTo[ list, element] will add the element to the list. The corresponding functions for inserting elements at the beginning of a list are Prepend and PrependTo. To insert an element into a list at an arbitrary position, use Insert. The structure is Insert[list,element, position]. If the specified position is a negative integer, then the element is inserted from the end of the list. :[font = input; startGroup; nowordwrap; ] list= { 3, 5, 7, 13}; list1= Insert[ list, 11, -2] :[font = output; inactive; formatted; output; endGroup; nowordwrap; ] {3, 5, 7, 11, 13} ;[o] {3, 5, 7, 11, 13} :[font = text; inactive; ] To combine lists, use the Union and Join commands. Union removes any duplicates and sorts the result while Join appends the second list to the end of the first.. :[font = input; startGroup; nowordwrap; ] list1= { 1,1,2,3,5,8,13,21}; list2= { 3, 5, 7,11,13}; Union[ list1, list2] Join[list1,list2] :[font = output; inactive; formatted; output; nowordwrap; ] {1, 2, 3, 5, 7, 8, 11, 13, 21} ;[o] {1, 2, 3, 5, 7, 8, 11, 13, 21} :[font = output; inactive; formatted; output; endGroup; endGroup; nowordwrap; ] {1, 1, 2, 3, 5, 8, 13, 21, 3, 5, 7, 11, 13} ;[o] {1, 1, 2, 3, 5, 8, 13, 21, 3, 5, 7, 11, 13} :[font = subsection; inactive; startGroup; Cclosed; ] List Manipulation :[font = text; inactive; ] To access an element of a list we can use the Part command or the [[ ]] operator. Part[ list, k] gives the kth element of the list. :[font = input; startGroup; nowordwrap; ] list= { 1,2,4,8,16,32}; Part[ list,4] :[font = output; inactive; formatted; output; endGroup; nowordwrap; ] 8 ;[o] 8 :[font = input; startGroup; nowordwrap; ] list[[5]] :[font = output; inactive; formatted; output; endGroup; nowordwrap; ] 16 ;[o] 16 :[font = text; inactive; ] To obtain more than one element, use Take. Take[ list, k] makes a new list out of the first k elements of the argument. If k is negative then the last k elements are taken. To obtain the sublist of elements from position i through position j, use the command Take[ list, {i,j}] Similarly, Drop [list,k] makes a new list by removing the first k elements ( or last |k| elements if k is negative). :[font = input; startGroup; nowordwrap; ] list= { 1,3,5,7,9,10} Take[ list,2] :[font = output; inactive; formatted; output; nowordwrap; ] {1, 3, 5, 7, 9, 10} ;[o] {1, 3, 5, 7, 9, 10} :[font = output; inactive; formatted; output; endGroup; nowordwrap; ] {1, 3} ;[o] {1, 3} :[font = input; startGroup; nowordwrap; ] Take[ list, { 2, 3}] :[font = output; inactive; formatted; output; endGroup; nowordwrap; ] {3, 5} ;[o] {3, 5} :[font = text; inactive; ] We illustrate this with an example program which takes a list and returns a new list consistingof pairs of elements from the first list. If the input is { 1,3,5,7,9,11}, then the output is { { 1,3}, { 5,7}, { 9,11} }. :[font = input; nowordwrap; ] makepairs[l_]:=Module[ {newlist={},i=1}, While[i< Length[l], AppendTo[newlist, Take[l, {i,i+1}]]; i=i+2;]; Return[newlist]] :[font = input; startGroup; nowordwrap; ] makepairs[ { 1,3,5,7,9,11}] :[font = output; inactive; formatted; output; endGroup; nowordwrap; ] {{1, 3}, {5, 7}, {9, 11}} ;[o] {{1, 3}, {5, 7}, {9, 11}} :[font = input; startGroup; nowordwrap; ] makepairs[ { 1,3,5,7,9,11,13}] :[font = output; inactive; formatted; output; endGroup; nowordwrap; ] {{1, 3}, {5, 7}, {9, 11}} ;[o] {{1, 3}, {5, 7}, {9, 11}} :[font = text; inactive; ] Exercise: Notice that if the list has an odd number of elements, then the last element is dropped. Modify the program so that the last element is included at the end of the resulting list, possibly by adding a zero to the list if the length is odd. :[font = text; inactive; ] The same result can also be obtained by the Mathematica function Partition. Partition[ list,n] breaks the list into sublists of n elements. :[font = input; startGroup; nowordwrap; ] Partition[ { 1,3,5,7,9,11,13}, 2] :[font = output; inactive; formatted; output; endGroup; nowordwrap; ] {{1, 3}, {5, 7}, {9, 11}} ;[o] {{1, 3}, {5, 7}, {9, 11}} :[font = text; inactive; ] Exercise: Modify the function above to write a function that Partitions a list into sublists of n elements. If the number of elements is not a multiple of n, then add enough zeros to make it a multiple of n. :[font = text; inactive; ] If a list has sublists, then the elements can be accessed using the Part or [[ ]] commands. The ith sublist can be obtained by [[i]], and then the jth element of this can be accessed. A shortcut is to use [[ i,j]], which returns the jth element of the ith sublist. :[font = input; startGroup; nowordwrap; ] list= { { 1,3}, { 5,7}, { 9, 11}}; list[[ 2,2]] :[font = output; inactive; formatted; output; endGroup; nowordwrap; ] 7 ;[o] 7 :[font = text; inactive; ] A list consisting of sublists of equal length is a matrix, and matrix operations can be applied to this. Transpose interchanges the rows and columns of a matrix. Recall that FactorInteger returns the prime factorization of an integer, consisting of a list of lists, where each sublist is of the form { p, e} where p^e is the term corresponding to p in the prime factorization of n. Using Transpose, we can write a function to extract the primefactors of an integer. :[font = input; nowordwrap; ] primefactors[n_]:= First[Transpose[ FactorInteger[n]]]; :[font = input; startGroup; nowordwrap; ] primefactors[ 879312] :[font = output; inactive; formatted; output; endGroup; nowordwrap; ] {2, 3, 7, 2617} ;[o] {2, 3, 7, 2617} :[font = text; inactive; ] Exercise: Write a function to extract all the exponents in the prime factorization. A number n is squarefree if all the exponents are equal to 1. Write a function to check if all the exponents are 1, and hence to detect if a number is squarefree. :[font = text; inactive; ] Additional list manipulation functions are Union, Join, Intersection, and Complement. We discussed Union and Join in the previous section. Complement has the following format. Complement[ universal, list1,list2, ..] removes all occurrences of elements of list1, list2, and so on from universal. :[font = text; inactive; ] Suppose we wish to find the number of integers less than 300 that are multiples of 3 but are not multiples of 7. We can make a table of the multiples of 3 and 7, then use Complement and count the number. (There are better ways than this, but it does illustrate the use of these functions). :[font = input; startGroup; nowordwrap; ] a= Table[ 3i, { i, 1, Floor[ 300/3]}]; b=Table[ 7 i, { i, 1,Floor[ 300/7]}]; result=Length[ Complement[ a,b]] :[font = output; inactive; formatted; output; endGroup; nowordwrap; ] 86 ;[o] 86 :[font = text; inactive; ] Exercise: Write a function to reverse a list. :[font = text; inactive; endGroup; ] Exercise: Write a function to rotate a list by a specified number of elements either clockwise or counterclockwise. For example, the result of rotating { 1,2,3,4,5,6,7} by 2 elements should be { 3,4,5,6,7,1,2}. :[font = subsection; inactive; ] Applying Functions to Lists :[font = subsubsection; inactive; startGroup; Cclosed; ] Map, Apply,and Fold :[font = text; inactive; ] Mathematica has a convenient mechanism to apply functions to lists. This is a very powerful feature and usually much faster than the Do or For loops. The simplest way to apply a function to a list is to make the function listable. This is done using SetAttributes command. :[font = input; startGroup; nowordwrap; ] square[x_]:=x^2; SetAttributes[square, Listable] square[ { 2,5,7,9,11}] :[font = output; inactive; formatted; output; endGroup; nowordwrap; ] {4, 25, 49, 81, 121} ;[o] {4, 25, 49, 81, 121} :[font = text; inactive; ] Making square a listable function allows it to be applied to each element of a list. Notice that there is no need for loops as in other programming languages. Most of Mathematica's built-in functions are Listable and you can make your functions Listable by using the SetAttributes command. :[font = text; inactive; ] In the previous example we defined a function square and made it listable. Sometimes we want to do an operation on a list only a few times, so it is wasteful to define additional functions. Mathematica has a convenient mechanism to define a function inline (using the pure function command) and apply it to lists. This is done via the Map command. :[font = input; startGroup; nowordwrap; ] Map[ #^2 &, { 3,5,7,11}] :[font = output; inactive; formatted; output; endGroup; nowordwrap; ] {9, 25, 49, 121} ;[o] {9, 25, 49, 121} :[font = text; inactive; ] Map takes two arguments, the first is a function and the second a list. In the above example, the function is #^2 &, where # is the variable. The function returns the square of the variable. The ampersand signifies that it is pure function, so thereis no need for the name of the variable. The function is applied to each element. The general format of Map is :[font = input; startGroup; nowordwrap; ] Map[ f, { A,B,C}] :[font = output; inactive; formatted; output; endGroup; nowordwrap; ] {f[A], f[B], f[C]} ;[o] {f[A], f[B], f[C]} :[font = text; inactive; ] To sum the elements of a list, we use the Apply command. Apply[ operator, list] applies the operator to all the elements of the list. Usually, the operator is Plus or Times, so that we get the sum or product of the elements of the List. :[font = input; startGroup; nowordwrap; ] Clear[a,b,c] Apply[Plus, {a,b,c}] :[font = output; inactive; formatted; output; endGroup; nowordwrap; ] a + b + c ;[o] a + b + c :[font = input; startGroup; nowordwrap; ] Apply[Times, {a,b,c}] :[font = output; inactive; formatted; output; endGroup; nowordwrap; ] a*b*c ;[o] a b c :[font = text; inactive; ] Recall, that we wrote a program to determine the prime factors of an integer. Similarly, we can obtain the list of exponents in the prime factorization. To check if a number is squarefree, we have to check that the exponents are all one. One way to do this is to multiply all the exponents and see if the product equals one. The following program returns True if an integer is squarefree and False otherwise. It is limited by a limits of FactorInteger, so it will not work for numbers that have more than 12-15 digits. :[font = input; nowordwrap; ] squarefreeQ[n_]:= Apply[ Times, Last[Transpose[FactorInteger[n]]] ]==1; :[font = input; startGroup; nowordwrap; ] squarefreeQ[ 21] :[font = output; inactive; formatted; output; endGroup; nowordwrap; ] True ;[o] True :[font = input; startGroup; nowordwrap; ] squarefreeQ[75] :[font = output; inactive; formatted; output; nowordwrap; ] False ;[o] False :[font = text; inactive; endGroup; ] Exercise: Write a function to return the number of divisors of an integer. If {e1,e2,e3,..} is the list of exponents in the prime factorization, then the number of positive divisors is (e1+1) (e2+1)(e3+1) .... Don't use any loops in your program. An appropriate combination of Map and Apply is sufficient. :[font = text; inactive; ] Two more functions that are very useful are Fold and FoldList. Using Map, Apply, Fold and FoldList one can create very short programs to do some complex operations, programs that would be hundreds of lines long in languages such as C. The effect of Fold and FoldList is clear from the following, which also shows their usage. :[font = input; startGroup; nowordwrap; ] Fold [ f, x, {a,b,c}] :[font = output; inactive; formatted; output; endGroup; nowordwrap; ] f[f[f[x, a], b], c] ;[o] f[f[f[x, a], b], c] :[font = input; startGroup; nowordwrap; ] FoldList[ f, x, {a,b,c}] :[font = output; inactive; formatted; output; endGroup; nowordwrap; ] {x, f[x, a], f[f[x, a], b], f[f[f[x, a], b], c]} ;[o] {x, f[x, a], f[f[x, a], b], f[f[f[x, a], b], c]} :[font = text; inactive; ] We illustrate the use of these functions by writing a function that returns the divisors of an integer. To determine the divisors, we first obtain the prime factorization. This consists of a list of elements {p,e}, where p is a prime of exponent e. From this we make a list of powers of p and then multiply everything together to make a list of divisors.. Then we write a function to multiply two lists, and then put everything together using Fold. :[font = input; nowordwrap; ] primepowers[n_]:= Map [Table[ #[[1]]^i, { i,0,#[[2]]}] &, FactorInteger[n]] :[font = input; startGroup; nowordwrap; ] primepowers[24] :[font = output; inactive; formatted; output; endGroup; nowordwrap; ] {{1, 2, 4, 8}, {1, 3}} ;[o] {{1, 2, 4, 8}, {1, 3}} :[font = input; nowordwrap; ] multiplylists[ l1_,l2_]:= Union[ Flatten[ Map[ l1 # &,l2]]] :[font = input; startGroup; nowordwrap; ] multiplylists[ {1,2,4,8}, {1,3}] :[font = output; inactive; formatted; output; endGroup; nowordwrap; ] {1, 2, 3, 4, 6, 8, 12, 24} ;[o] {1, 2, 3, 4, 6, 8, 12, 24} :[font = text; inactive; ] Now, we have the two basic functions to be combined to get all the divisors. This can be done using Fold. :[font = input; startGroup; nowordwrap; ] divisors[n_]:= Fold[ multiplylists, {1}, primepowers[n]] :[font = message; inactive; formatted; output; endGroup; nowordwrap; ] General::spell1: Possible spelling error: new symbol name "divisors" is similar to existing symbol "Divisors". ;[o] General::spell1: Possible spelling error: new symbol name "divisors" is similar to existing symbol "Divisors". :[font = input; startGroup; nowordwrap; ] divisors[24] :[font = output; inactive; formatted; output; endGroup; nowordwrap; ] {1, 2, 3, 4, 6, 8, 12, 24} ;[o] {1, 2, 3, 4, 6, 8, 12, 24} :[font = input; startGroup; nowordwrap; ] divisors[ 315] :[font = output; inactive; formatted; output; endGroup; nowordwrap; ] {1, 3, 5, 7, 9, 15, 21, 35, 45, 63, 105, 315} ;[o] {1, 3, 5, 7, 9, 15, 21, 35, 45, 63, 105, 315} :[font = text; inactive; ] This simple function shows the power and elegance of Mathematica. Imagine doing the same in C. :[font = text; inactive; endGroup; ] Exercise: Write a function to find the sum and product of all the divisors. Write another function to compute the sum of the kth powers of the divisors of an integer. :[font = subsubsection; inactive; startGroup; Cclosed; ] Selecting Member of a List :[font = text; inactive; ] There are a few other functions that are useful in manipulating lists. These allow us Select elements of a list satisfying a specified condition. The following four functions are important. MemberQ[ list, element] returns True if the element occurs in the list. Select[ list, condition] returns a list of elements of list satisfying the condition Position[ list, element] returns a list of all places that the element occurs in the list. Count[ list, element] returns the number of occurrences of element in list. :[font = text; inactive; ] Suppose we wish to select primes from a list of integers. Then we can use Select with PrimeQ. :[font = input; startGroup; Cclosed; nowordwrap; ] Select[ { 3, 7, 9, 17, 127, 315}, PrimeQ] :[font = output; inactive; formatted; output; endGroup; nowordwrap; ] {3, 7, 17, 127} ;[o] {3, 7, 17, 127} :[font = input; startGroup; Cclosed; nowordwrap; ] MemberQ[ { 3,7,8, 9, 11}, 9] :[font = output; inactive; formatted; output; endGroup; nowordwrap; ] True ;[o] True :[font = input; startGroup; Cclosed; nowordwrap; ] Position[ { 3, 7, 7, 8, 9, 7, 8, 0}, 7] :[font = output; inactive; formatted; output; endGroup; nowordwrap; ] {{2}, {3}, {6}} ;[o] {{2}, {3}, {6}} :[font = text; inactive; ] Exercise: Write a function to make a list of numbers of the form 5k+3 that are prime. Write another function to make a list of numbers of the form 7k+1 that are squarefree. You can use the function squarefreeQ that was written in the previous section. :[font = text; inactive; endGroup; ] Exercise: Recall that we had a function squareQ that checks if a number is a perfect square by computing its real square root, taking the integer part, squaring it again to see if it equals the number. This is inefficient, and can be made more efficient by checking the remainder when divided by different integers. For example, a perfect square that is divided by 16 has a remainder of 0, 1, 4, or 9. Use this fact to write a function newsquareQ that first checks if Mod[ n, 16] is in the list { 0,1,4,9} before applying the older test. This will eliminate the square root computation is 3/4 of the inputs. ^*)