Can I efficiently (without brute force) determine the smallest number having the given property?

72 Views Asked by At

If $d(n)$ denotes the number of positive divisors of $n$ , define $$f(n):=d(n)\cdot d(n+1)$$

Can I find efficiently (without brute-force) the smallest integer $n\ge 1$ such that $f(n)\ge m$ , for a given integer $m\ge 1$ ?

For example , $m=49\ 000$ gives $n=589\ 466\ 240$

1

There are 1 best solutions below

0
On

You can find prime patterns that have lots of factors. In your example one of $n,n+1$ must have more than $\sqrt{49000} \gt 221$ factors. $589\ 466\ 240$ has $256$ factors as it factors as $2^7$ times five primes. $589\ 466\ 241$ has $256$ factors as it factors as $3^5$ times five primes. You could find the patterns that have at least $222$ factors, assign small primes to them, add and subtract $1$ and factor the result. That is a lot harder to program but will lead to checking many fewer numbers.