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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .