This question was posted in MSE. It got many upvotes but no answer hence posting it in MO.

A number is either prime or composite, hence primality is a binary concept. Instead I wanted to put a value of primality to every number using some function $f$ such that $f(n) = 1$ iff $n$ is a prime otherwise, $0 < f(n) < 1$ and as the number divisors of $n$ increases, $f(n)$ decreases on average. Thus $f(n)$ is a measure of the degree of primeness of $n$ where 1 is a perfect prime and 0 is a hypothetical perfect composite. Hence $\frac{1}{N}\sum_{r \le N} f(r)$ can be interpreted as a the average primeness of the first $N$ integers.

After trying several definitions and going through the ones in literature, I came up with:

Define $f(n) = \dfrac{2s_n}{n-1}$ for $n \ge 2$, where $s_n$ is the standard deviation of the divisors of $n$.

One reason for using standard deviation was that I was already studying the distribution of the divisors of a number.

Question 1: Does the average primeness tend to zero? i.e. does the following hold?

$$ \lim_{N \to \infty} \frac{1}{N}\sum_{r = 2}^N f(r) = 0 $$

Question 2: Is $f(n)$ injective over composites? i.e., do there exist composites $3 < m < n$ such that $f(m) = f(n)$?

My progress

  • $f(4.35\times 10^8) \approx 0.5919$ and decreasing so the limit if it exists must be between 0 and 0.5919.
  • For $2 \le i \le n$, computed data shows that the minimum value of $f(i)$ occurs at the largest highly composite number $\le n$.

Note: Here standard deviation of $x_1, x_2, \ldots , x_n$ is defined as $\sqrt \frac{\sum_{i=1}^{n} (x-x_i)^2}{n}$. Also notice that even if we define standard deviation as $\sqrt \frac{\sum_{i=1}^{n} (x-x_i)^2}{n-1}$ our questions remain unaffected because in this case in the definition of $f$, we will be multiplying with $\sqrt 2$ instead of $2$ to normalize $f$ in the interval $(0,1)$.

  • $\begingroup$ From the linked question it seems that $s_n$ grows faster than $n$ so that $f(n)$ doesn't go to zero. $\endgroup$
    – lcv
    Apr 8, 2019 at 10:18
  • 1
    $\begingroup$ @lcv No $s_n$ doesn't grow faster than $n$. What are you looking at? $\endgroup$ Apr 8, 2019 at 10:27
  • 1
    $\begingroup$ "...I wanted to have a continuous function...". In what topology is $f$ continuous? If you put discrete topology on natural numbers, then any function is continuous so you probably have something else in mind. $\endgroup$
    – user74900
    Apr 8, 2019 at 13:56
  • $\begingroup$ I have verified that $f$ is injective over composites less than 10,000,000. $\endgroup$
    – user44143
    Apr 8, 2019 at 14:00
  • 1
    $\begingroup$ @NilotpalKantiSinha - This may be interesting for you. Have a look at this question. There is a definition of "compositeness" of a number. Here, the value approaches zero as numbers become more prime-like, and approaches infinity as they become more composite. $\endgroup$
    – swami
    Dec 1, 2021 at 5:51

1 Answer 1


The answer to Question 1 is "yes". To see this, notice that $s_n$ is at most square root of the average square of divisor, i.e. $$ s_n\leq \sqrt{\frac{\sum_{d\mid n}d^2}{\sum_{d\mid n} 1}}=\sqrt{\frac{\sigma_2(n)}{\sigma_0(n)}}, $$

where $\sigma_k(n)$ is the sum of $k$-th powers of divisors of $n$. Now,

$$ \sigma_2(n)=n^2\sigma_{-2}(n), $$


$$ \sigma_2(n)<\frac{\pi^2}{6}n^2 $$

for all $n$. Therefore we have

$$ f(n)\leq \frac{2}{n-1} \sqrt{\frac{\pi^2}{6}n^2/\sigma_0(n)}\leq \frac{5.14}{\sqrt{\sigma_0(n)}} $$

for all $n$. Now, almost all $n\leq N$ have at least $0.5\ln\ln N$ distinct prime factors. In particular, for almost all $n\leq N$ we have $\sigma_0(n)\geq 0.5\ln\ln N$. Therefore, our bound for $f(n)$ together with the trivial observation that $0\leq f(n)\leq 1$ gives

$$ \sum_{n\leq N} f(n)\leq \sum_{n\leq N, \sigma_0(n)\geq 0.5\ln\ln N} \frac{5.14}{\sqrt{\sigma_0(n)}}+\sum_{n\leq N, \sigma_0(n)<0.5\ln\ln N} 1= o(N), $$

as needed.

Using contour integration method one can even prove something like

$$ \sum_{n\leq N} f(n)=O(N(\ln N)^{1/\sqrt{2}-1}) $$

  • 7
    $\begingroup$ That last expression reminds me an XKCD alt-text: "If you ever find yourself raising $\log(\text{anything})^{1/\sqrt{2}}$, set down the marker and back away from the whiteboard; something has gone horribly wrong." $\endgroup$ Apr 8, 2019 at 18:13
  • 3
    $\begingroup$ @MichaelSeifert Bah, it was $\log(anything)^e$ not $\frac{1}{\sqrt{2}}$. Log to the power of one over the sqrt of 2 is mundane; log of something to the power e is a sign of insanity. $\endgroup$
    – Yakk
    Apr 8, 2019 at 19:08
  • 2
    $\begingroup$ @Yakk Yeah, but Randall also says that taking $\pi$-th root of anything is insane. However, the paper "Mean values of multiplicative functions" by Montgomery and Vaughan, Theorem 5, contains $(\log x)^{1/\pi-1}$ and is totally fine! (P.S. Is inequality $n_p<p^{\frac{1}{4\sqrt{e}}+o(1)}$ ok?..) $\endgroup$ Apr 8, 2019 at 20:05
  • 2
    $\begingroup$ @AsymptotiacK: Thanks for the good answer to Question 1. I think that in general if $f(n)$ is any function who value decreases from 1 to zero as its defined measure of primness decreases then the mean value of $f$ must tend to zero because as we go higher up the number line, for any $k \ge 2$, the probability of of finding numbers with $\le k$ factors should decrease $\endgroup$
    – Space
    Apr 9, 2019 at 6:11

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.