Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.


Math Forum » Discussions » sci.math.* » sci.math.num-analysis.independent

Topic: Common Divisor’s computing -> Non-Linear Programming task
Replies: 2   Last Post: Jun 22, 2009 6:52 PM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Yuly Shipilevsky

Posts: 17
Registered: 1/25/05
Re: Common Divisor’s computing -> Non-Linear Programming task
Posted: Jun 22, 2009 6:52 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

Author: Yuly Shipilevsky



Algorithms for finding the Common Multiples and Least Common Multiple .

(Reducing of the Common Multiples computing to the solution of a
Non-Linear Programming/Optimization problem).





First algorithm.



Let N be a set of positive integers, N = {1, 2, . . . }

Let N^M denotes a Cartesian product of M sets N,

Let m denotes an arbitrary M-tucle (m1 , . . . , mM) contained in N^M.



Let CM be a Common Multiple of X1, . . . , XM.

There exists an unique M-tucle m0=(m01 , . . . , m0M) that corresponds to the

M-tucle X=( X1, . . . , XM) so that:



(1) CM = m0iXi , 1<= i <= M.



Let lcm(X1, . . . , XM) denotes the Least Common Multiple of X1, . . . , XM.







Lets define the following function:

(2) S2(m,X) = SUM_i,j=1...M,i>j[miXi - mjXj]^2 ,



where m=(m1 , . . . , mM) is contained in N^M





Proposition 1 (Minimum Principle).



for any
M-tucle m contained in N^M the following is true:


min_m { S2(m,X) | N^M } = S2(m0,X) = 0,



(the minimum is being searched amongst all the m
contained in N^M),



S2(m,X) > = S2(m0,X) = 0,



If and only if m0 contained in N^M, corresponds to the

M-tucle X=( X1, . . . , XM) and satisfies (1).





Proof.



It follows from Xs Common Multiples existence and (1) , (2) .

On the base of Proposition 1 we can suggest a








Theorem 1 (Reducing of Common Multiples computing to the solution of a Integer Programming/Optimization problem).

To compute the Least Common Multiples of X1, . . . , XM do the following steps:


(a) Find M-tucles m contained in N^M and minimizing S2
(S2 -> min | N^M)

(b) For each and every M-tucle, determined at step (a) find the

corresponding Common Multiple of X using (1)



(the minimum is being searched amongst all the m
contained in N^M).





Proof.



It follows from the Proposition 1.







Lemma 1.



If S_R_ N^M = {m: mi >= 1, mi - real numbers,
1<= i <=M } ,



then



min_m { S2(m,X) | N^M } =
min_m { S2(m,X) | S_R_ N^M} = 0





Proof.



It follows from the Proposition 1 and (1) , (2).





On the base of Lemma 1 and Theorem 1 we can suggest a



Theorem 2 (Reducing of Common Multiples computing to the solution of a Non-Linear Programming
/Optimization problem).

To compute the Common Multiples of X1, . . . , XM do the following steps:


(a) Find M-tucles m contained in S_R_N^M and minimizing S2
(S2 -> min | S_R_N^M)

(b) For each and every M-tucle, determined at step (a) find the

corresponding Common Multiple of X using (1)





(the minimum is being searched amongst all the m
contained in S_R_N^M).









Second algorithm.







Lets define the following function:



(3) S3(m,X) = SUM_i,j=1...M,i>j [miXi - mjXj]^2 + mkXk ,



where m=(m1 , . . . , mM) is contained in N^M,
1 <= k <= M.





Proposition 2 (Minimum Principle).



The following is true:


lcm(X1, . . . , XM) = min_m { S3(m,X) | N^M } = S3(m0,X)



(the minimum is being searched amongst all the m
contained in N^M).



If and only if m0 corresponds to the

M-tucle X=( X1, . . . , XM) , satisfies



(1) and corresponds to the Least Common Multiple

lcm(X1, . . . , XM).



Proof.



It follows from Xs Common Multiples existence and (1) , (3) .



On the base of Proposition 2 we can suggest a





Theorem 3. (Reducing of lcm computing to the solution of a Integer Programming
/Optimization problem).

To compute the Least Common Multiple of X1, . . . , XM do:


(a) Find an M-tucle m0 contained in N^M and minimizing S3
(S3 -> min | N^M)

(b) Find the Least Common Multiple corresponding to the M-tucle m0 determined at step (a)

as follows:



lcm(X1, . . . , XM) = min_m { S3(m,X)
| N^M } = S3(m0,X).



(the minimum is being searched amongst all the m
contained in N^M).







Lemma 2.



If S_R_ N^M = {m: mi >= 1 , mi - real numbers,
1<= i <=M } ,



then



min_m { S3(m,X) | N^M } = min_m { S3(m,X) | S_R_ N^M}





Proof.



It follows from Proposition 2, the fact that



SUM_i,j=1...M,i>j [miXi - mjXj]^2 >= 0 and



continuosity and monotonicity of mkXk function.







On the base of Lemma 2 and Theorem 3 we can suggest a




Theorem 4. (Reducing of lcm computing to the solution of a Non-Linear Programming
/Optimization problem).

To compute the Least Common Multiple of X1, . . . , XM do:


(a) Find an M-tucle m0 contained in S_R_N^M and minimizing S3
(S3 -> min | S_R_N^M)

(b) Find the Least Common Multiple corresponding to the M-tucle m0 determined at step (a)

as follows:



lcm(X1, . . . , XM) = min_m { S3(m,X) |
S_R_N^M } = S3(m0,X).



(the minimum is being searched amongst all the m
contained in S_R_N^M).



Example.


Finding the Least Common Multiple of 9636, 1456 and 2098 is being reduced to the
following Non-Linear Programming task:



S3(m , X) = ( 9636 m1 - 1456 m2 ) ^2 +
( 1456 m2 - 2098m3 ) ^2 + 9636 m1 -> min



m =(m1, m2, m3) ,



X=(9636, 1456, 2098),



m1, m2, m3 - real numbers,



satisfying the following constraints:




m1 >= 1,



m2 > = 1 ,



m3 >= 1




lcm(9636, 1456, 2098) = min_m { S3(m , X) |
m1 >= 1 , m2 >= 1 , m3 >= 1 }



Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.