Is the largest divisor such that two numbers divided by it are equal to one value?

Question

I have an algorithm that can be interpreted as dividing a number line into an equal number of pieces. For simplicity, I will stick to [0,1], it will be divided like this:

0|----|----|----|----|1 

I need to make a series of numbers [j, k) and find the largest number of pieces N, up to some maximum M, which will divide the number string so that [j, k) still all fall into the same “bit”. This is harder than it sounds, since a range can saddle a basket like this:

  j|-|k 0|----|----|----|----|1 

So you may have to get to a pretty low number before the range is fully contained. Moreover, as the number of bins increases, the range can move and exit one bin, so there are local minima.

The obvious answer is to start from M-bins and decrease the number until the range falls into one bit. However, I would like to know if there is a faster way than listing all the possible sections, since my maximum number can be reasonably large (80 million or so).

Is there a better algorithm for this?

Answer 1

Here I would like to give another heuristic that differs from btilly's.

The problem is to find the integers m and n so that m / n <= j < k <= (m + 1) / n , with n being as large as possible (but still under m ).

Intuitively, it is preferable that the m / n fraction be close to j . This leads to the idea of ​​using continued fractions .

The algorithm I propose is quite simple:

• calculate all continued fractions of j using minus signs (so fractions always squeeze j from above) until the denominator exceeds m ;
• for each such fraction m / n , find the largest integer i >= 0 such that k <= (m * i + 1) / (n * i) and n * i <= M , and replace the fraction m / n by (m * i) / (n * i) ;
• among all fractions in 2, find the one with the largest denominator.

The algorithm is not symmetric in j and k . Therefore, there is a similar k -version, which in general should not give the same answer, so you can choose the larger of the two results.

---

Example: here I will take an example of btilly: j = 0.6 and k = 0.65 , but I will take M = 10 .

First I will go through procedure j . To calculate the continuation of the fractional fraction j , we calculate:

  0.6 = 0 + 0.6 = 0 + 1 / (2 - 0.3333) = 0 + 1 / (2 - 1 / (3 - 0)) 

Since 0.6 is a rational number, the decomposition ends in just a few steps. Corresponding fractions:

 0 = 0 / 1 0 + 1 / 2 = 1 / 2 0 + 1 / (2 - 1 / 3) = 3 / 5 

Calculating the corresponding values ​​of i in step 2, we replace three fractions:

 0 / 1 = 0 / 1 1 / 2 = 3 / 6 3 / 5 = 6 / 10 

The largest denominator is 6/10.

---

Continue with the example above, the corresponding procedure k would look like this:

  0.65 = 1 - 0.35 = 1 - 1 / (3 - 0.1429) = 1 - 1 / (3 - 1 / (7 - 0)) 

Therefore, the corresponding fractions:

 1 = 1 / 1 1 - 1 / 3 = 2 / 3 1 - 1 / (3 - 1 / 7) = 13 / 20 

Step 2, we get:

 1 / 1 = 2 / 2 2 / 3 = 6 / 9 13 / 20 = 0 / 0 (this is because 20 is already bigger than M = 10) 

The largest denominator is 6/9.

---

EDIT: experimental results.

To my surprise, the algorithm works better than I thought.

I performed the following experiment, which ignores the estimate of m (equivalently, you can take m large enough).

In each round, I generate a pair (j, k) evenly distributed random numbers in inteval [0, 1) with j < k . If the difference k - j less than 1e-4 , I discard this pair, making this round ineffective. Otherwise, I calculate the true result trueN using a naive algorithm and calculate the heurN result heurN using my algorithm and add it to the statistics. This applies to the 1st round.

Here is the result:

 effective round = 999789 sum of trueN = 14013312 sum of heurN = 13907575 correct percentage = 99.2262 % average quotient = 0.999415 

correct percentage is the percentage of effective rounds, so trueN is heurN , and average quotient is the average of the private heurN / trueN for all effective rounds.

Thus, the method gives the correct answer in 99% + cases.

I also experimented with smaller m values ​​and the results were similar.

Answer 2

The best option for a hopper size should be larger than kj .

Consider the numerical segments [0..j] and [k..1) . If we can split both partial segments into parts using the same bin size, we must solve this problem.

So, if we consider gcd((j-0)/(kj), (1-k)/(kj)) (where we use the largest integer function after division), we should be able to get a good estimate or a better value. There are angular cases: if (kj) > j or (kj) > (1-k) , the best value is 1 . Therefore, a very good estimate should be min(1, (kj) * gcd((j-0)/(kj), (1-k)/(kj)))

Answer 3

Turn it a little.

You would like to find m, n as large as possible (although n < M ) with m/n near, but less than j and k <= (m+1)/n .

All prospective candidates will be at https://en.wikipedia.org/wiki/Stern%E2%80%93Brocot_tree . Indeed, you will get a reasonably good answer by simply going through the Stern-Brokaw tree to find the last “big rational” that matches your limit just below j , the top of which is at k or higher.

There is a complication. Usually the tree converges quickly. But sometimes the Stern-Broco tree has long sequences with very small gaps. For example, the sequence to go to 0.49999999 will include 1/3, 2/5, 3/7, 4/9, ... We always fall into these sequences when a/b < c/d , then we take the median (a+c)/(b+d) , and then we go in one direction, therefore (a+i*c)/(b+i*d) . If you are smart, then instead of walking the entire sequence, you can simply perform a binary search for the correct power i to use.

The trick of this intelligence is to view your workaround as:

• Start with 2 equal fractions.
• Take them to the median. If it exceeds M , then I will finish. Otherwise, find out in which direction I am going from this.
• Try powers 2 in (a+i*c)/(b+i*d) until I find out which range i included for my range and conditions M
• Do a double search to find the last i that I can use.
• (a+i*c)/(b+i*d) (a+i*c+c)/(b+i*d+d) are my two new equal shares. Go back to the first step.

Initial equal shares, of course, 0/1 and 1/1 .

This will always find a worthy answer in O(log(M)) operations. Unfortunately, this reasonably good answer is NOT always correct. Consider the case when M = 3 , j=0.6 and k=0.65 . In this case, the heuristic will stop at 1/2 , while the actual best answer will be 1/3 .

Another way in which he can fail is that he finds only diminished answers. In the above example, if M is 4, he still thinks the best answer is 1/2 when it is actually 1/4 . This is easy to handle by checking if multiple your final answer will work. (This step will improve your response to a fixed but fairly large part of the time.)