# Search NKS | Online

1 - 10 of 13 for Quotient

In base 6, (3/2) n is a cellular automaton with rule
{a_, b_, c_} 3 Mod[a + Quotient[b, 2], 2] + Quotient[3 Mod[b, 2] + Quotient[c, 2], 2]
(Note that this rule is invertible.)

Numbering scheme [for Turing machines]
One can number Turing machines and get their rules using
Flatten[MapIndexed[{1, -1} #2 + {0, k} {1, 1, 2} Mod[Quotient[#1, {2k, 2, 1}], {s, k, 2}] + {1, 0, -1} &, Partition[IntegerDigits[n, 2 s k, s k], k], {2}]]
The examples on page 79 have numbers 3024, 982, 925, 1971, 2506 and 1953.

3n+1 problem as cellular automaton
If one writes the digits of n in base 6, then the rule for updating the digit sequence is a cellular automaton with 7 possible colors (color 6 works as an end marker that appears to the left and right of the actual digit sequence):
{a_, b_, c_} If[b 6, If[EvenQ[a], 6, 4], 3 Mod[a, 2] + Quotient[b, 2] /. 0 6 /; a 6]
The 3n+1 problem can then be viewed as a question about the existence of persistent structure in this cellular automaton.

(For multiplier m in base k , the relative frequencies of pairs {i, j} are given by Quotient[a i - j - 1 + m, k] - Quotient[m i - j - 1, k] .)

The value of the cell at position n from the end of row t is thus the n th digit of m t , or Mod[Quotient[m t , k n ], k] .

MapIndexed[ #1 First[#2] &, Union[Map[# 〚 1, 1 〛 &, #]]] &[ With[{b = Ceiling[Log[2, k]] - 1}, Flatten[Table[ {Table[{Table[{{m, i, n, d}, c} {{m, Mod[i, 2 n - 1 ], n - 1, d}, Quotient[i, 2 n - 1 ], 1}, {n, 2, b}, {i, 0, 2 n - 1}], Table[{ {m, i, 1, d}, c} {{m, -1, 1, d}, i, d}, {i, 0, 1}], Table[ {{m, -1, n, d}, c} {{m, -1, n + 1, d}, c, d}, {n, b - 1}], {{m, -1, b, d}, c} {{0, 0, m}, c, d}}, {d, -1, 1, 2}], Table[{{i, n, m}, c} {{ i + 2 n c, n + 1, m}, c, -1}, {n, 0, b - 1}, {i, 0, 2 n - 1}], With[{r = 2 b }, Table[ If[i + r c ≥ k, {}, Cases[rule, ({m, i + r c} {x_, y_, z_}) {{i, b, m}, c} {{x, Mod[y, r], b, z}, Quotient[y, r], 1})]], {i, 0, r - 1}]]}, {m, s}, {c, 0, 1}]]]]
Some of these states are usually unnecessary, and in the main text such states have been pruned.

(h) Mod[Quotient[s, 2 n ], 2] extracts the digit associated with 2 n in the base 2 digit sequence of s .

When m itself divides k , the cellular automaton rule is {_, b_, c_} m Mod[b, k/m] + Quotient[c, k/m] ; in other cases the rule can be obtained by composition.

The evolution of the arithmetic system is given by
ASEvolveList[{n_, rules_}, init_, t_] := NestList[(Mod[#, n] /. rules)[#] &, init, t]
Given a value m obtained in the evolution of the arithmetic system, the state of the register machine to which it corresponds is
{Mod[m, p] + 1, Map[Last, FactorInteger[ Product[Prime[i], {i, nr}] Quotient[m, p]]] - 1}
Note that it is possible to have each successive step involve only multiplication, with no addition, at the cost of using considerably larger numbers overall.

From various number-theoretical results many relations can readily be encoded as integer equations:
(a 0 ∨ b 0) ↔ a b 0
(a 0 ∧ b 0) ↔ a + b 0
a < b ↔ b a + c + 1
a Mod[b, c] ↔ (b a + c d ∧ a < c)
a Quotient[b, c] ↔ (b a c + d ∧ d < c)
a Binomial[b, c] ↔ With[{n = 2 b + 1}, (n + 1) b n c (a + d n) + e ∧ e < n c ∧ a < n]
a b! ↔ 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)!… The simplest known way of doing this (see note below ) involves a degree 8 equation with 60 variables:
a b c ↔ α [d, 4 + b e, 1 + z] ∧ α [f, e, 1 + z] ∧ a Quotient[d, f] ∧ α [g, 4 + b, 1 + z] ∧ e 16 g(1 + z)
λ [a_, b_, c_] := Module[{x}, 2 a + x 1 c ∧ (Mod[b - a, c] 0 ∨ Mod[b + a, c] 0)]
α [a_, b_, c_] := Module[{x}, x 1 2 - b x 1 x 2 + x 2 2 1 ∧ x 3 2 - b x 3 x 4 + x 4 2 1 ∧ 1 + x 4 + x 5 x 3 ∧ Mod[x 3 , x 1 2 ] 0 ∧ 2x 4 + x 7 b x 3 ∧ Mod[-b + x 8 , x 7 ] 0 ∧ Mod[-2 + x 8 , x 1 ] 0 ∧ x 8 - x 11 3 ∧ x 12 2 - x 8 x 12 x 13 + x 13 2 1 ∧ 1 + 2 a + x 14 x 1 ∧ λ [a, x 12 , x 7 ] ∧ λ [c, x 12 , x 1 ]]
(This roughly uses the idea that solutions to Pell equations grow exponentially, so that for example x 2 2y 2 + 1 has solutions With[{u = 3 + 2 √ 2 }, (u n + u -n )/2] .)