Number Theory Algorithms. Most dividers on a segment

Question

I am looking for an efficient algorithm to solve the following problem. Denote by d(n) number of positive divisors n , where n is a positive integer. We are given some 1 <= a <= b <= 10^18 , and the task is to find the maximum value of d on the segment [a..b] and (maybe we need a more complex algorithm for this part), to find a number that maximizes the value of d .

Some time ago, I found the following code in the public domain: http://ideone.com/qvxPj

 unsigned long long n, res; int p, primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 51, 53, 59, 61, 67, 71}; unsigned long long mul(unsigned long long a, unsigned long long b){ unsigned long long res = 0; while (b){ if (b & 1LL) res = (res + a); if (res >= n) return 0; a = (a << 1LL); b >>= 1LL; } return res; } void backtrack(int i, int lim, unsigned long long val, unsigned long long r){ if (r > res) res = r; if (i == p) return; int d; unsigned long long x = val; for (d = 1; d <= lim; d++){ x = mul(x, primes[i]); if (x == 0) return; backtrack(i + 1, d, x, r * (d + 1)); } } int main(){ p = sizeof(primes) / sizeof(int); while (scanf("%llu", &n) != EOF){ res = 0; backtrack(0, 100, 1, 1); printf("Maximum number of divisors of any number less than %llu = %llu\n", n, res); } return 0; } 

I will be very happy if someone explains to me how this works, because (as for me) this program works very fast.

Thanks in advance for your help.

Answer 1

It iterates over all numbers as follows:

 num = P1^D1 * P2^D2 * P3^D3 * ... * Ps^Ds constraints: Pi <= 71 1 <= Di <= 100 sequence (Pi) is a sorted list of first s primes sequence (Di) is nonincreasing num <= n 

Check the first restriction. Suppose that the prime factor has a prime factor q> 71. If no prime number p <= 71 is used in this number, then we can replace q with p by the same degree. Obviously, the number of divisors will remain the same, but the number will decrease → contradiction. Then there is no unused prime number less than 71. But the product of all primes up to 71 is already so large that the number we consider must be greater than 64-bit n. It's impossible.

Now let's explain the second and third limitations. Suppose that our minimum optimal number has prime q in its factorization, but does not have some prime p, where p <sq. Then we can replace q with p in the same order, the number will have the same number of divisors, but it will become less → a contradiction. This means that all primes in the factorization of the desired optimal (minimum) number must be exactly the first s-numbers. The set of primes should not have holes. BTW, Di <= 100 is obvious because even 2 ^ 100 no longer matches a 64-bit integer.

Now we must explain the fourth limitation. Suppose that D [i] D [i + 1] for some i. Then we can replace P [i] ^ D [i] * P [i + 1] ^ D [i + 1] with P [i] ^ D [i + 1] * P [i + 1] ^ D [i ], and the number decreases. For example, replace 5 ^ 2 * 7 ^ 3 with 5 ^ 3 * 7 ^ 2: the number of divisors is the same, but the result is less. Obviously, if we are looking for the minimum optimal number, we can safely assume this condition.

Now consider the code. mul is a small function that calculates the product of a and b. It is calculated by a funny binary procedure. The main reason for this procedure is: if the product is greater than n, the function returns 0. This procedure is only protection against overflow, which could happen otherwise.

Finally, we got to the backtrack . This is a regular recursive search. val is the current number, r is its number of divisors, i shows the prime number index that we will add now, lim limits the power of each prime number to 100. At the very beginning, you see the update of the current optimal answer (stored in res ) and the hard stop condition (all spaces used).

Then there is a loop that checks each power for the current prime. It starts with power 1, since zero power is prohibited. It maintains the current number in x and multiplies it by each iteration of Pi to increase power. If x becomes greater than n, it stops immediately. Finally, he calls himself to search for the next prime number.

Answer 2

As a complement to @stgatilov's answer, I will justify the choice to limit primes to less than primes less than or equal to 71.

I used a slightly modified version of the code to mark the largest number with the maximum number of divisors. For 1000000000000000000 or 999999999999999999 I got:

897612484786617600 = 2 ⁸ * 3 ⁴ * 5 ² * 7 ² * 11 * 13 * 17 * 19 * 23 * 29 * 31 * 37

with a total number of dividers 103680.

This means that for the whole number of 18 decimal digits there should be nothing more than 37 - to find the integer with the largest number of divisors.