I have recently stumbled upon an algorithmic problem and I can't get the end of it. You're given a positive integer N < 10^13, and you need to choose a nonnegative integer M, such that the sum: MN + N(N-1) / 2 has the least number of divisors that lie between 1 and N, inclusive. Can someone point me to the right direction for solving this problem? Thank you for your time.
Find a prime P greater than N. There are a number of ways to do this.
If N is odd, then M*N + N*(N-1)/2 is a multiple of N. It must be divisible by any factor of N, but if we choose M = P - (N-1)/2, then M*N + N*(N-1)/2 = P*N, so it isn't divisible by any other integers between 1 and N.
If N is even, then M*N + N*(N-1)/2 is a multiple of N/2. It must be divisible by any factor of N/2, but if we choose M = (P - N + 1)/2 (which must be an integer), then M*N + N*(N-1)/2 = (P - N + 1)*N/2 + (N-1)*N/2 = P*N/2, so it isn't divisible by any other integers between 1 and N.