My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Reply
 
LinkBack Thread Tools Display Modes
July 14th, 2013, 12:15 AM   #1
Newbie
 
Joined: Jun 2012

Posts: 13
Thanks: 0

specific search

I have two products
P1 = x1*x2*x3*...xn
P2 = y1*y2*y3* ...yn

xi,yi integers

I want to make abs(P1/P2 - 1) the best smallest value by changing only one pair xi,yj in the products.
f.e. x1*y3*x3.... and y1*y2*x2* ...
I have to search for the best pair.
I can do that by calculating all the possible values P'1,P'2 by taking all the possible pairs but I want to do that without doing the multiplications, perhaps by examining all the values xi/yj.
How can I search for the best xi.yj.
Thanks for any resonse
andreaugust is offline  
 
July 14th, 2013, 05:14 AM   #2
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: specific search

You want to swap one pair, right?

Take the quotient Q = P1/P2. If you swap xi and yj you get Q' = Q * yj^2/xi^2, and so you want yj^2/xi^2 to be as close as possible to 1/Q and thus xi/yj to be as close as possible to sqrt(Q). For each x, find the y closest (geometrically) to x/sqrt(Q). The pair producing the smallest geometric distance is the right one to choose.
CRGreathouse is offline  
July 15th, 2013, 05:30 AM   #3
Newbie
 
Joined: Jun 2012

Posts: 13
Thanks: 0

Re: specific search

Thanks, CRGreathouse !
andreaugust is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
search, specific



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Average search cost of an unsuccessful search in a BST? flexdec Applied Math 0 July 16th, 2013 05:25 AM
Book search Mark_sr Math Books 3 October 16th, 2012 07:05 AM
In search of a formula. Mr. Clueless Algebra 4 May 22nd, 2012 06:09 PM
In search of a formula. Mr. Clueless Calculus 0 December 31st, 1969 04:00 PM





Copyright © 2018 My Math Forum. All rights reserved.