Obtaining the coefficients of the number with the smallest sum in O (1)

Question

I am trying to find pairs of factors of the least sum number in O (1).

Here is an explanation:

If number is 100. Then all the possible pairs are : 1 X 100 2 X 50 4 X 25 5 X 20 10 X 10 20 X 5 25 X 4 50 X 2 100 X 1 

Here the pair with the smallest sum is 10.10, which is clearly the average

 Similarly if number is 12 then pairs are as follows 1 X 12 2 X 6 3 X 4 4 X 3 6 X 2 12 X 1 

Here the required pair is 3.4 or 4.3.

 If a number has 'p' pairs then the required one is always ceil(p/2). 

If the given number is an ideal square, the task is quite simple. The pair will be just sqrt(number),sqrt(number).

If not, the pair will be either ceil(sqrt(number)),number/ceil(sqrt(number))

given that ceil(sqrt(number)) is a factor of number

or immediate factor neighbour of sqrt(number):

For example, consider "6". 6 is not a perfect square.

ceil of sqrt (6) is 3 and 3 is a factor of 6. Therefore, the required pair is 3,6/3=2

 Now consider 102. All pairs are : 1 * 102.0 2 * 51.0 3 * 34.0 6 * 17.0 17 * 6.0 34 * 3.0 51 * 2.0 102 * 1 

The required pair in this case is 17.6 or 6.17. Here ceil(sqrt(102)) is 11 . The immediate neighbor factor is 11 - 17 or 6. Now this is what we actually find.

How to find the nearest neighbor factor?

Here is my implementation of O (n):

 import math l = [] n = int(input()) for i in range(1, n + 1): if n % i is 0: l.append(i) middle = l[math.ceil(len(l) / 2)] print("Required pair is ", middle, ",", n / middle) 

Answer 1

Here is the proof that finding a pair should be at least as tough as integer factoring (which means that there is no known O (1) algorithm):

If we start with the number N and get the pair with the smallest sum, as shown, the divisors are closest to sqrt (N), so there are only 2 possibilities:
1. The pair is 1 - N, which means that N is simple. What a trivial case. 2. We found some nontrivial divisor k. This means that we can consistently apply the algorithm for k and N / k, and ultimately we find all simple divisors efficiently.

Answer 2

I can only think of the O (sqrt (n)) method

 from math import sqrt, ceil m = 200 for i in range(ceil(sqrt(m)), 0, -1): if m % i == 0: print(i, int(m / i)) break 

we got 10, 20

We know that

 (a - b)^2 >= 0 

then we got

 a^2 + b^2 >= 2ab 

for our case

 x + m/x 

we have

 x + m/x >= 2sqrt(m) 

therefore we got the border min (sum (x + m / x)), the minimum amount should be generated by two factors that are very close to sqrt (m); the mathematical problem behind is the function x + m / x when x = sqrt (m), sum (x + m / x) is minimized, but due to the need x and m / x are both integers, so we should try to find closest to sqr (m).

Answer 3

Not O(n) , but you can reduce the time complexity using the following program

 from math import * val = floor(sqrt(n)) l2 = [] for i in range(val,n): if n%i == 0: l2.extend([i,n//i]) break print(l2) 

Here, we mainly calculate the square root of a number and check if it is a factor in a given input. We increase by 1 until we find the first factor. A pair of this factor and the resulting factor has the smallest amount.

Speed ​​comparison for two programs

 from math import * from time import time n = 1120304 t0 = time() l = [] for i in range(1, n + 1): if n % i is 0: l.append(i) middle = l[math.ceil(len(l) / 2)] # print("Required pair is ", middle, ",", n / middle) t1 = time() val = floor(sqrt(n)) l2 = [] for i in range(val,n): if n%i == 0: l2.extend([i,n//i]) break t2 = time() t1-t0 # 0.1386280059814453 t2-t1 # 0.009765148162841797 

Answer 4

I do not think this question is a new question. I saw some similar questions since many years ago, but never saw an O(1) solution.

So let's look at reality, O(sqrt(n)) might be the best situation.