[Integers here refer to positive integers. $n$ is a positive integer.]

I had been thinking about this problem:

Find all integers $n$ which are divisible by all integers $m \leq \sqrt{n}$ .

After some work, I figured that this was possible only for a finitely many such numbers (One reason is that, $ \lfloor {\sqrt{n} }\rfloor \# $ grows faster than $n$ , where $ x \# $ is the primorial of $x$).

Again, we note that for all $n$ , all integers below $ \sqrt[n]{n} $ divide $n$. It is easily seen by noting that $\sqrt[n]{n} < 2$ for all $n \in \mathbb{N} $.

So, I thought about developing a function that, for all $n \in \mathbb{N} $ , tells me the smallest possible value $m$ such that all integers less than (or equal to) $ \sqrt[m]{n} $ divides $n$.

The problem can be restated as:

Find the smallest function (here I mean that the function takes on smallest possible values) $f:\mathbb{N} \to \mathbb{N}$ such that all integers below(or equal to) $ \sqrt[f(n)]{n} $ divide $n$.

  • 1
    $\begingroup$ There's an obvious (and unique) answer to your question : $f(n)$ is the smallest $m$ such that all integers $\leq \sqrt[m]{n}$ divide $n$. $\endgroup$ – user25235 Jun 16 '13 at 15:07
  • $\begingroup$ What do you want to do with this function, aside from defining it? $\endgroup$ – S. Carnahan Jun 16 '13 at 15:13
  • $\begingroup$ Let g(n) be 1 + ceiling (log_2 n). Then n^1/g < 2, and so your divisibility relation holds. If you wish it to hold for odd numbers, you won't do much better than g(n). Gerhard "Close Enough Sometimes Good Enough" Paseman, 2013.06.16 $\endgroup$ – Gerhard Paseman Jun 16 '13 at 20:18
  • $\begingroup$ For numbers k which are prime powers and n that are divisible by all integers up to but not including k, one can use ceil(log_k(n)) instead of ceil(log_2(n)). Gerhard "Ask Me About System Design" Paseman, 2013.06.16 $\endgroup$ – Gerhard Paseman Jun 16 '13 at 21:12

You will end up taking m as around log n/loglog n, asymptotically, by the Prime Number Theorem? So again, your motivation. For small n something less easy to describe but computable will occur. For large n we are looking at something to do with the error term in the Prime Number Theorem.

  • $\begingroup$ For odd numbers, I think ceiling(log_2(n)) is the function he wants. Gerhard "Happy Father's Day To You" Paseman, 2013.06.16 $\endgroup$ – Gerhard Paseman Jun 16 '13 at 20:21
  • $\begingroup$ Can you please tell me how you reached this conclusion (i.e. this function) from the Prime Number Theorem? $\endgroup$ – Mriganka Basu Roy Chowdhury Jun 17 '13 at 7:26
  • $\begingroup$ By taking the lcm of the numbers up to M, then its logarithm, and then looking at the Prime Number Theorem in the form with the von Mangoldt function in it. I may have the calculation wrong. $\endgroup$ – Charles Matthews Jun 17 '13 at 13:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.