Euclidean Algorithm

Author

Eric W. Weisstein
August 24, 2005

This notebook downloaded from http://mathworld.wolfram.com/notebooks/PrimeNumbers/EuclideanAlgorithm.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/EuclideanAlgorithm.html.

©2005 Wolfram Research, Inc. except for portions noted otherwise

By Hand

Remainder[a_,b_]:=a-Quotient[a,b]b
Remainder[a_,0]:=0

EuclideanAlgorithmList[a_,b_]:=First/@Most[FixedPointList[{Last[#],Remainder@@#}&,{a,b}]]

EuclideanAlgorithmGCD[a_,b_]:=FixedPointList[{Last[#],Remainder@@#}&,{a,b}][[-3,1]]

Examples

EuclideanAlgorithmList[42,30]

EuclideanAlgorithmGCD[42,30]

EuclideanAlgorithmList[144,55]

Algorithm

Assumes a<b

EuclideanSteps[a_,b_]:=1 /;IntegerQ[a/b]

EuclideanSteps[a_,b_]:=Module[{r1=a-b Floor[a/b],r2,tmp,steps=1},
r2=b-Floor[b/r1]r1;
While[r2>0,
tmp=r2;
r2=r1-Floor[r1/r2] r2;
r1=tmp;
steps++
];
steps+1
]

t[m_,0]:=0
t[m_,n_]:=t[m,n]=1+t[n,Mod[m,n]] /; m≥n
t[m_,n_]:=t[m,n]=1+t[n,m] /; m<n

PortersConstant:=6Log[2]/Pi^2(3Log[2]+4EulerGamma-24/Pi^2Zeta'[2]-2)-1/2

Comparison of explicit calculation vs. T(m,n)

Table[With[{m=Random[Integer,{1,100}],
n=Random[Integer,{1,100}]},
t[m,n]-EuclideanSteps[m,n]
],{100}]

Lamé

Log[n]/Log[GoldenRatio]+Log[Sqrt[5]]/Log[GoldenRatio]//N

Log[n]/Log[GoldenRatio]+Log[Sqrt[5]]/Log[GoldenRatio]//N

Log[n]/Log[GoldenRatio]+Log[Sqrt[5]]/Log[GoldenRatio]//N

Log[10]/Log[GoldenRatio]//N

12Log[2]/Pi^2/Log[n]//N

Steps

EuclideanSteps[128,54]

Table[With[{a=Random[Integer,100],b=Random[Integer,100]},{a,b,EuclideanSteps[a,b],
1.6722759381845544`+2.0780869212350273` Log[Max[a,b]],1.6722759381845544`+4.784971966781665` Log[Max[a,b]]}
],{20}]//TableForm

And@@Table[With[{a=Random[Integer,{1,10000}],b=Random[Integer,{1,10000}]},EuclideanSteps[a,b]<=
1.6722759381845544`+2.0780869212350273` Log[Max[a,b]]
],
{10^4}]

Table[{
EuclideanSteps[Fibonacci[n+1],Fibonacci[n+2]],
1.6722759381845544`+2.0780869212350273` Log[Fibonacci[n+1]]},{n,20}]

Solve[4.785Log[10,n]+1.6723==0,n]

Plot[{5Log[10,n],4.785Log[10,n]+1.6723},{n,0,5},
PlotStyle->{Red,Black}]

T(n)

T[n_]:=1/n  Plus@@(t[#,n]&/@Range[0,n-1])

T(5)

t[#,5]&/@Range[0,4]

T[5]//N

Knuth Table

Flatten[Table[{n,T[n]//N},Evaluate[{n,Sequence@@#}]]&/@{{95,105},{996,1001},{9999,10001},{49999,50001},{99999,100001}},1]//TableForm

T[1]

FactorInteger[9]

Length[{}]

Lambda[n_]:=Module[{f=FactorInteger[n]},
If[Length[f]==1,Log[f[[1,1]]],0]
]

Table[Exp[Lambda[n]],{n,10}]

With[{nmax=300},
ListPlot[Table[
T[n]-12Log[2.]/Pi^2(Log[n]-Plus@@(Lambda[#]/#&/@Divisors[n])),
{n,2,nmax}],
PlotJoined->True,
AxesLabel->TraditionalForm/@{n,HoldForm[T[n]-12 Log[2]/π^2 Log[n]-(Underscript[Σ, d|n])((Λ[d])/d)]},
Epilog->{Red,Line[{{0,#},{nmax,#}}&[PortersConstant]]}]
]//Timing

τ(n)

tau[n_]:=1/EulerPhi[n]Plus@@(t[#,n]&/@Select[Range[0,n-1],GCD[#,n]==1&])

Flatten[Table[{n,tau[n]//N},Evaluate[{n,Sequence@@#}]]&/@{{95,105},{996,1001}},1]//TableForm

Flatten[Table[{n,T[n]//N},Evaluate[{n,Sequence@@#}]]&/@{{95,105},{996,1001},{9999,10001},{49999,50001},{99999,100001}},1]//TableForm

With[{nmax=300},
ListPlot[Table[
tau[n]-12Log[2.]/Pi^2Log[n],
{n,2,nmax}],
PlotJoined->True,
AxesLabel->TraditionalForm/@{n,τ[n]-12 Log[2]/π^2 Log[n]},
Epilog->{Red,Line[{{0,#},{nmax,#}}&[PortersConstant]]}
]
]//Timing

Otter

Table[t[128,n]-EuclideanSteps[128,n],{n,150}]

Table[t[128,n],{n,10}]

Table[{n,m},{n,10},{m,n}]

Table[t[n,m],{n,10},{m,0,n-1}]//MatrixForm

Max/@Table[t[n,m],{n,20},{m,n}]

Plus@@#/Length[#]&/@Table[t[n,m],{n,20},{m,0,n-1}]