Such choices are particularly convenient on computers where machine integers are represented by 32 binary digits. … Maximal period is assured when in addition PrimeQ[2 n - 1] .) … This particular idea did not work well, but generalizations based on the recurrence f[n_] :=Mod[f[n - p] + f[n - q], 2 k ] have been studied extensively, for example with p = 24 , q = 55 .

These colors satisfy s[n_] := If[EvenQ[n], 1 - s[n/2], s[(n + 1)/2]] with s[1] = 1 . … (d) (Cantor set) The color of the element at position n is given by If[FreeQ[IntegerDigits[n - 1, 3], 1], 1, 0] , which turns out to be equivalent to If[OddQ[n], Sign[Mod[Binomial[n - 1, (n - 1)/2], 3]], 0, 1] There are 3 t elements after t steps, of which 2 t are black.

In effect it expresses the idea that the integers form a single ordered sequence, and it provides a basis for the notion of recursion. In the early history of mathematics arithmetic with integers did not seem to need formal axioms, for facts like x + y  y + x appeared to be self-evident. … It is not clear however exactly what minimal set of axioms is needed, for example, for the existence of solutions to integer equations to be undecidable (see page 787 ).

Sierpiński pattern Other ways to generate step n of the pattern shown here in various orientations include: • Mod[Array[Binomial, {2, 2} n , 0], 2] (see pages 611 and 870 ) • 1 - Sign[Array[BitAnd, {2, 2} n , 0]] (see pages 608 and 871 ) • NestList[Mod[RotateLeft[#] + #, 2] &, PadLeft[{1}, 2 n ], 2 n - 1] (see page 870 ) • NestList[Mod[ListConvolve[{1, 1}, #, -1], 2] &, PadLeft[{1}, 2 n ], 2 n - 1] (see page 870 ) • IntegerDigits[NestList[BitXor[2#, #] &, 1, 2 n - 1], 2, 2 n ] (see page 906 ) • NestList[Mod[Rest[FoldList[Plus, 0, #]], 2] &, Table[1, {2 n }], 2 n - 1] (see page 1034 ) • Table[PadRight[ Mod[CoefficientList[(1 + x) t - 1 , x], 2], 2 n - 1], {t, 2 n }] (see pages 870 and 951 ) • Reverse[Mod[CoefficientList[Series[1/(1 - (1 + x)y), {x, 0, 2 n - 1}, {y, 0, 2 n - 1}], {x, y}], 2]] (see page 1091 ) • Nest[Apply[Join, MapThread[ Join, {{#, #}, {0 #, #}}, 2]] &, {{1}}, n] (compare page 1073 ) The positions of black squares can be found from: • Nest[Flatten[2# /. … (OddQ[Length[#]] &), {2}] (see page 358 ) • Flatten[Table[Map[{t, #} &, Fold[Flatten[{#1, #1 + #2}] &, 0, Flatten[2^(Position[ Reverse[IntegerDigits[t, 2]], 1] - 1)]]], {t, 2 n - 1}], 1] (see page 870 ) • Map[Map[FromDigits[#, 2] &, Transpose[Partition[#, 2]]] &, Position[Nest[{{#, #}, {#}} &, 1, n], 1] - 1] (see page 509 ) A formatting hack giving the same visual pattern is DisplayForm[Nest[SubsuperscriptBox[#, #, #] &, "1", n]]

The 3n+1 problem The system described here is similar to the so-called 3n+1 problem, in which one looks at the rule n  If[EvenQ[n], n/2, (3n + 1)/2] and asks whether for any initial value of n the system eventually evolves to 1 (and thereafter simply repeats the sequence 1, 2, 1, 2, ...). … An alternative formulation is to ask whether for all n FixedPoint[(3#/2^IntegerExponent[#, 2] + 1)/2 &, n]  2 With the rule n  If[EvenQ[n], 5n/2, (n + 1)/2] used in the main text, the sequence produced repeats if n ever reaches 2, 4 or 40 (and possibly higher numbers).

Some integer functions can readily be obtained by supplying integer arguments to continuous functions, so that for example Mod[x, 2] corresponds to Sin[ π x/2] 2 or (1 - Cos[ π x])/2, Mod[x, 3] ↔ 1 + 2/3(Cos[2/3 π (x - 2)] - Cos[2 π x/3]) Mod[x, 4] ↔ (3 - 2 Cos[ π x/2] - Cos[ π x] - 2 Sin[ π x/2])/2 Mod[x, n] ↔ Sum[j Product[(Sin[ π (x - i - j)/n]/ Sin[ π i/n]) 2 , {i, n - 1}], {j, n - 1}] (As another example, If[x > 0, 1, 0] corresponds to 1 - 1/Gamma[1 - x] .) And in this way the discrete system x  If[EvenQ[x], 3x/2, 3(x + 1)/2] from page 122 can be emulated by the continuous iterated map x  (3 + 6 x - 3 Cos[ π x])/4 .

So for example the equation a 2 + b 2  0 has solutions that are exactly those integers that satisfy the relation a  0 ∧ b  0 . … ↔ a  Quotient[c b , Binomial[c, b]] a  GCD[b, c] ↔ (b c > 0 ∧ a d  b ∧ a e  c ∧ a + c f  b g) a  Floor[b/c] ↔ (a c + d  b ∧ d < c) PrimeQ[a] ↔ (GCD[(a - 1)!… One can reduce such an exponential equation to a pure polynomial equation by encoding powers using integer equations.

This typically begins by using so-called Church numerals (based on work by Alonzo Church on lambda calculus), and defining a combinator e n to correspond to an integer n if e n [a][b]//.crules yields Nest[a, b, n] . … Another approach involves representing integers directly as combinator expressions. … (Searches based on other representations for integers have also not yielded much.

Here are examples of how some of the basic Mathematica constructs used in the notes in this book work: • Iteration Nest[f, x, 3] ⟶ f[f[f[x]]] NestList[f, x, 3] ⟶ {x, f[x], f[f[x]], f[f[f[x]]]} Fold[f, x, {1, 2}] ⟶ f[f[x, 1], 2] FoldList[f, x, {1, 2}] ⟶ {x, f[x, 1], f[f[x, 1], 2]} • Functional operations Function[x, x + k][a] ⟶ a + k (# + k&)[a] ⟶ a + k (r[#1] + s[#2]&)[a, b] ⟶ r[a] + s[b] Map[f, {a, b, c}] ⟶ {f[a], f[b], f[c]} Apply[f, {a, b, c}] ⟶ f[a, b, c] Select[{1, 2, 3, 4, 5}, EvenQ] ⟶ {2, 4} MapIndexed[f, {a, b, c}] ⟶ {f[a, {1}], f[b, {2}], f[c, {3}]} • List manipulation {a, b, c, d} 〚 3 〛 ⟶ c {a, b, c, d} 〚 {2, 4, 3, 2} 〛 ⟶ {b, d, c, b} Take[{a, b, c, d, e}, 2] ⟶ {a, b} Drop[{a, b, c, d, e}, -2] ⟶ {a, b, c} Rest[{a, b, c, d}] ⟶ {b, c, d} ReplacePart[{a, b, c, d}, x, 3] ⟶ {a, b, x, d} Length[{a, b, c}] ⟶ 3 Range[5] ⟶ {1, 2, 3, 4, 5} Table[f[i], {i, 4}] ⟶ {f[1], f[2], f[3], f[4]} Table[f[i, j], {i, 2}, {j, 3}] ⟶ {{f[1, 1], f[1, 2], f[1, 3]}, {f[2, 1], f[2, 2], f[2, 3]}} Array[f, {2, 2}] ⟶ {{f[1, 1], f[1, 2]}, {f[2, 1], f[2, 2]}} Flatten[{{a, b}, {c}, {d, e}}] ⟶ {a, b, c, d, e} Flatten[{{a, {b, c}}, {{d}, e}}, 1] ⟶ {a, {b, c}, {d}, e} Partition[{a, b, c, d}, 2, 1] ⟶ {{a, b}, {b, c}, {c, d}} Split[{a, a, a, b, b, a, a}] ⟶ {{a, a, a}, {b, b}, {a, a}} ListConvolve[{a, b}, {1, 2, 3, 4, 5}] ⟶ {2a + b, 3a + 2b, 4a + 3b, 5a + 4b} Position[{a, b, c, a, a}, a] ⟶ {{1}, {4}, {5}} RotateLeft[{a, b, c, d, e}, 2] ⟶ {c, d, e, a, b} Join[{a, b, c}, {d, b}] ⟶ {a, b, c, d, b} Union[{a, a, c, b, b}] ⟶ {a, b, c} • Transformation rules {a, b, c, d} /. b  p ⟶ {a, p, c, d} {f[a], f[b], f[c]} /. f[a]  p ⟶ {p, f[b], f[c]} {f[a], f[b], f[c]} /. f[x_]  p[x] ⟶ {p[a], p[b], p[c]} {f[1], f[b], f[2]} /. f[x_Integer]  p[x] ⟶ {p[1], f[b], p[2]} {f[1, 2], f[3], f[4, 5]} /. f[x_, y_]  x + y ⟶ {3, f[3], 9} {f[1], g[2], f[2], g[3]} /. f[1] | g[_]  p ⟶ {p, p, f[2], p} • Numerical functions Quotient[207, 10] ⟶ 20 Mod[207, 10] ⟶ 7 Floor[1.45] ⟶ 1 Ceiling[1.45] ⟶ 2 IntegerDigits[13, 2] ⟶ {1, 1, 0, 1} IntegerDigits[13, 2, 6] ⟶ {0, 0, 1, 1, 0, 1} DigitCount[13, 2, 1] ⟶ 3 FromDigits[{1, 1, 0, 1}, 2] ⟶ 13 The Mathematica programs in these notes are formatted in Mathematica StandardForm .

In the late 1970s it was noted that by evaluating PowerMod[a, n - 1, n]  1 for several random integers a one can with high probability quickly deduce PrimeQ[n] . (In the 1960s it had been noted that one can factor polynomials by filling in random integers for variables and factoring the resulting numbers.)