0
$\begingroup$

[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$.

Improve this question
$\endgroup$
4
  • 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, 2013 at 15:07
  • $\begingroup$ What do you want to do with this function, aside from defining it? $\endgroup$
    – S. Carnahan ♦
    Jun 16, 2013 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, 2013 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, 2013 at 21:12

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\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, 2013 at 20:21
  • $\begingroup$ Can you please tell me how you reached this conclusion (i.e. this function) from the Prime Number Theorem? $\endgroup$
    – RandomStudent
    Jun 17, 2013 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, 2013 at 13:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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