# Functions about integers which are divisible by all numbers less than or equal to a fractional power of the integer

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

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

-
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$. –  user25235 Jun 16 '13 at 15:07
What do you want to do with this function, aside from defining it? –  S. Carnahan Jun 16 '13 at 15:13
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 –  Gerhard Paseman Jun 16 '13 at 20:18
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 –  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.

-
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 –  Gerhard Paseman Jun 16 '13 at 20:21
Can you please tell me how you reached this conclusion (i.e. this function) from the Prime Number Theorem? –  Mriganka Basu Roy Chowdhury Jun 17 '13 at 7:26
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. –  Charles Matthews Jun 17 '13 at 13:17