Search NKS | Online
1 - 10 of 23 for GCD
Given the horizontal and vertical positions x and y a square is white when GCD[x, y] 1 and is black otherwise. The condition GCD[x, y] 1 is equivalent to the statement that x and y are relatively prime, or that no reduction is required to bring the fraction x/y to lowest terms.
Rest[list]/#1) &, Apply[ ExtendedGCD, Drop[list, -1]]]}, {Mod[ α , #], #} &[ Fold[GCD[#1, If[#1 0, #2, Mod[#2, #1]]] &, 0, ListCorrelate[{ α , -1}, list]]]]
With slightly more effort both x and {a, m} can be found just from First[IntegerDigits[list, 2, p]] .
Note that GCD[m, n] yields a more complicated pattern (see page 613 ), as do JacobiSymbol[m, 2n - 1] (see page 1081 ) and various combinations of functions (see page 747 ).
GCD array
(See also page 950 .) … GCD can be computed using Euclid's algorithm as discussed on page 915 .
The digits of 1/n in base b repeat with period
MultiplicativeOrder[b, FixedPoint[#/GCD[#, b] &, n]]
which is equal to MultiplicativeOrder[b, n] for prime n , and is at most n - 1 .
Particularly dramatic are the concatenation systems discussed on page 913 , as well as successive rows in nested patterns such as Flatten[IntegerDigits[NestList[BitXor[#, 2 #] &, 1, 500], 2]] and sequences based on numbers such as Flatten[Table[If[GCD[i, j] 0, 1, 0], {i, 1000}, {j, i}]] (see page 613 ).
The repetition period is given by n/GCD[m, n] .
If a , b and c are rational, Sin[a x] + Sin[b x] + Sin[c x] is periodic with period 2 π /GCD[a, b, c] , and there are a limited number of different spacings between zeros.
When GCD[k, n] 1 the dot can never visit position 0.
History [of continued fractions]
Euclid's algorithm states that starting from integers {a,b} iterating {a_, b_} If[a > b, {a - b, b}, {a, b - a}] eventually leads to {GCD[a, b], 0} .