One of the elementary ways to identify if a number $n \in \mathbb{N}$ is prime is to check if it is divisible by any $k \in \mathbb{N}: 2\leq k \leq \sqrt{n}$. I was thinking of using it to define the following function $f:\mathbb{N}\rightarrow \mathbb{N}$ $$f(t)=\max_{k} \left \{ k \in \mathbb{N}^{*} \mid k \leq \sqrt{t} \space \wedge k \mid t \right \}$$ E.g. $f(2)=1$, $f(4)=2$, $f(6)=2$, $f(8)=2$, $f(9)=3$ etc.

I couldn't find any references of this function, which, given its elementary nature, probably means it is useless or, maybe, I wasn't looking in the right place. Any help is much appreciated.

Few auxiliary notes

One interesting property of this function is ...

Let's note the set $M^n=\{1,2,...,n\}$ and the set $M^n_{k}=\{t \in M^n \mid f(t)=k \}$, All $M^n_k$ form a partition of $M^n$ such that $$\left | M^n \right | = \sum_{k=1}^{n} \left | M^n_k \right |$$ where $M^n_1=1 + \pi(n)$, because $t$ - prime $\Leftrightarrow f(t)=1$, leading to $$n=1+\pi(n)+\sum_{k=2}^{n} \left | M^n_k \right |$$ On top of this $\forall k > \sqrt{n}$, $\left | M^n_k \right |=0$, otherwise, if $\exists t \in M^n_k$ such that $f(t)=k > \sqrt{n}$ then $\sqrt{t}\geq k > \sqrt{n}$ contradicting the fact that $t \in M^n$. As a result $$n=1+\pi(n)+\sum_{k=2}^{k\leq \sqrt{n}} \left | M^n_k \right |$$

  • 1
    $\begingroup$ This function is closely related to the efficiency of Fermat factorization: en.m.wikipedia.org/wiki/Fermat%27s_factorization_method $\endgroup$ – Erick Wong Feb 19 '16 at 10:27

Your Answer

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

Browse other questions tagged or ask your own question.