# Search NKS | Online

81 - 90 of 115 for IntegerDigits

(This value is related to the repetition period for the digit sequence of 1/n in base k , as discussed on page 912 ). … In general, the dot will visit position m = k^IntegerExponent[n, k] every MultiplicativeOrder[k, n/m] steps.

Fibonacci[n] can be obtained in many ways:
• (GoldenRatio n - (-GoldenRatio) -n )/ √ 5
• Round[GoldenRatio n / √ 5 ]
• 2 1 - n Coefficient[(1 + √ 5 ) n , √ 5 ]
• MatrixPower[{{1, 1}, {1, 0}}, n - 1] 〚 1, 1 〛
• Numerator[NestList[1/(1 + #)&, 1, n]]
• Coefficient[Series[1/(1 - t - t 2 ), {t, 0, n}], t n - 1 ]
• Sum[Binomial[n - i - 1, i], {i, 0, (n - 1)/2}]
• 2 n - 2 - Count[IntegerDigits[Range[0, 2 n - 2 ], 2], {___, 1, 1, ___}]
A fast method for evaluating Fibonacci[n] is
First[Fold[f, {1, 0, -1}, Rest[IntegerDigits[n, 2]]]]
f[{a_, b_, s_}, 0] = {a (a + 2b), s + a (2a - b), 1}
f[{a_, b_, s_}, 1] = {-s + (a + b) (a + 2b), a (a + 2b), -1}
Fibonacci numbers appear to have first arisen in perhaps 200 BC in work by Pingala on enumerating possible patterns of poetry formed from syllables of two lengths. … In addition:
• GoldenRatio is the solution to x 1 + 1/x or x 2 x + 1
• The right-hand rectangle in is similar to the whole rectangle when the aspect ratio is GoldenRatio
• Cos[ π /5] Cos[36 ° ] GoldenRatio/2
• The ratio of the length of the diagonal to the length of a side in a regular pentagon is GoldenRatio
• The corners of an icosahedron are at coordinates
Flatten[Array[NestList[RotateRight, {0, (-1) #1 GoldenRatio, (-1) #2 }, 3]&, {2, 2}], 2]
• 1 + FixedPoint[N[1/(1 + #), k] &, 1] approximates GoldenRatio to k digits, as does FixedPoint[N[Sqrt[1 + #],k]&, 1]
• A successive angle difference of GoldenRatio radians yields points maximally separated around a circle (see page 1006 ).

[No text on this page]
Universality in arithmetic, illustrated by an integer equation whose solutions in effect emulate the rule 110 universal cellular automaton from Chapter 11 . … If one fills in fixed values for x 1 , x 2 and x 3 , then only one value for x 4 is ever possible—corresponding to the evolution history of rule 110 for x 3 steps starting from a width x 1 initial condition given by the digit sequence of x 2 .

Computable reals
The stated purpose of Alan Turing 's original 1936 paper on computation was to introduce the notion of computable real numbers, whose n th digit for any n could be found by a Turing machine in a finite number of steps. … And the point is that any such initial conditions can always be encoded as an integer.
As examples of non-computable reals that can readily be defined, Turing considered numbers whose successive digits are determined by the eventual behavior after an infinitely long time of a universal system with successive possible initial conditions (compare page 964 ).

To access location n the left-hand initial conditions must contain Flatten[{0, i, IntegerDigits[n, 2] /. {1 {0, 11}, 0 {0, 2}}}] inserted in a repetitive {0, 1} background.

Mobile automata [emulating cellular automata]
Given the rules for an elementary cellular automaton in the form used on page 867 , the following will construct a mobile automaton which emulates it:
vals = {x, p[0], q[0, 0], q[0, 1], q[1, 0], q[1, 1], p[1]}
CAToMA[rules_] := Table[(# Replace[#, {{q[a_, b_], p[c_], p[d_]} {q[c, {a, c, d} /. rules], 1}, {q[a_, b_], p[c_], x} {q[c, {a, c, 0} /. rules], 1}, {q[_, _], x, x} {p[0], -1}, {q[_, _], q[_, a_], p[_]} {p[a], -1}, {x, q[_, a_], p[_]} {p[a], -1}, {x, x, p[_]} {q[0, 0], 1}, {_, _, _} {x, 0}}]) &[vals 〚 IntegerDigits[i, 7, 3] + 1 〛 ], {i, 0, 7 3 - 1}]
The ordering in vals defines a mapping of symbolic cell values onto colors.

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 .

Unlike ordinary digits, the individual terms in a continued fraction can be of any size. … In a few known cases simple formulas yield numbers that are close but not equal to integers. An example discovered by Srinivasa Ramanujan around 1913 is Exp[ π √ 163 ] , which is an integer to one part in 10 30 , and has second continued fraction term 1,333,462,407,511.

For any input x one can test whether the machine will ever halt using
u[{Reverse[IntegerDigits[x, 2]], 0}]
u[list_] := v[Split[Flatten[list]]]
v[{a_, b_: {}, c_: {}, d_: {}, e_: {}, f_: {}, g___}] := Which[a == {1} || First[a] 0, True, c {}, False, EvenQ[Length[b]], u[{a, 1 - b, c, d, e, f, g}], EvenQ[Length[c]], u[{a, 1 - b, c, 1, Rest[d], e, f, g, 0}], e {} || Length[d] ≥ Length[b] + Length[a] - 2, True, EvenQ[Length[e]], u[{a, b , c, d, f, g}], True, u[{a, 1 - b, c, 1 - d, e, 1, Rest[f], g, 0}]]
This test takes at most n/3 recursive steps, even though the original machine can take of order n 2 steps to halt.

Standard mathematical functions
There are an infinite number of possible functions with integer or continuous arguments. … A variety of standard mathematical functions with integer arguments were introduced in the late 1800s and early 1900s in connection with number theory. A few functions that involve manipulation of digits have also become standard since the use of computers became widespread.