Modified Euclidean Algorithm

The following procedure is a modified Euclidean algorithm. For a pair (n,m)(n,m) of positive integers with n<mn<m we construct a sequence of pairs of positive integers (n0,m0), (n1,m1), ...(n_0,m_0), \ (n_1,m_1),\ ... such that (n0,m0)=(n,m)(n_0,m_0)=(n,m) and for all i0i\geq 0 mi+1=ni; ni+1=min(ri,niri),m_{i+1}=n_i;\ n_{i+1}=\min (r_i,n_i-r_i), where rir_i is the remainder of mim_i divided by nin_i. We repeat this procedure until we get a pair (nk,mk)(n_k,m_k) with nkmkn_k \mid m_k, so that rk=0r_k=0 and the algorithm terminates.

Find the number of pairs (101,m)(101,m) with 101<m<1000101<m<1000 for which this algorithm terminates in no more than 44 steps with nk=1n_k=1 (that is, nk=1n_k=1 for k4k\leq 4).

Details and assumptions

Example: If (n,m)=(101,215)(n,m)=(101,215), then (n0,m0)=(101,215),(n_0,m_0)=(101,215), (n1,m1)=(13,101),(n_1,m_1) =(13,101), (n2,m2)=(3,13),(n_2,m_2)=(3,13), (n3,m3)=(1,3) (n_3,m_3) = (1,3), so for the pair (101,225)(101,225) the algorithm terminates with nk=1n_k=1 in 33 steps.

×

Problem Loading...

Note Loading...

Set Loading...