Given a number $2n$, where $n$ is an integer greater than $2$, how many odd composites $x ∈ [9,n]$ share at least one odd prime factor less than or equal to $n$ or have the same remainder with $2n$ when divided by at least one odd prime less than or equal to $n$? Please express your answer by defining the function $f(2n)$ which tells this number based on $n$. If your answer is approximate, please provide a lower and upper bound, especially for $\pi(n)$, and refrain from using probabilities as best you can. Leaving $\pi(n)$ without approximating it is fine too.

Examples of what the function should evaluate to:

$f(18) = 1, f(30)=2, f(32)=0, f(42)=3, f(46) = 1, f(66) = 5$

$f(18)$ evaluates to $1$ because there is one odd composite less than or equal to $n$, which is $9$ in this case; $9$. $18$ and $9$ both share the factor 3.

$f(30)$ evaluates to $2$ because there are two odd composites less than or equal to $15$; $9, 15$. Since $30$ is divisible by $3$ and $5$, and $9$ is divisible by $3$, and $15$ is divisible by $3$ and $5$, $f(30)$ evaluates to $2$.

$f(32)$ evaluates to $0$ because no composite shares a remainder with it when divided by any prime less than or equal to $n$.

So far, I know that there are $\lfloor\frac{n}{2}\rfloor - \pi(n) + 1 $ odd composites up to $n$, but I haven't been able to get much farther.


I have been made aware that this question is the same as asking, find a function $f(2n)$ that increases by one for a value $2n$ every time $(2n-x)$ can be divided by an odd prime, where $x$ is any odd composite less than or equal to $n$.

  • 1
    $\begingroup$ explain more! and give some examples that we could understand what are you asking $\endgroup$
    – Ahmad
    Mar 13, 2017 at 20:13
  • $\begingroup$ You might want to clear up your notation; when discussing $f(18)$ you seem to be referring to $n=9$ and likewise for $f(30)$. Also, could you elaborate on $f(32)$ being equal to $1$ (no odd composite shares a common factor with $32$; where does this "one" come from?)? $\endgroup$ Mar 17, 2017 at 17:01
  • $\begingroup$ @PeterKošinár Both of your suggestions are fixed. This was a mistake on my part which I've fixed now. $\endgroup$ Mar 17, 2017 at 19:09
  • $\begingroup$ @LinusRastega Your question is still unclear, you should define $f(2n)$ clearly (at least using mathematical symbols, I cannot follow your explanations in English) $\endgroup$
    – Elaqqad
    Mar 17, 2017 at 20:43
  • 2
    $\begingroup$ Numbers $A$ and $B$ give the same remainder if they are divided by $C$ if and only if $C$ divides the difference $(A-B)$. In this case, the condition "$x$ and $2n$ gives the same remainder when divided by an odd prime not exceeding $n$" is equivalent to requiring $(2n-x)$ being divisible by some odd prime not exceeding $n$. Since $x$ was odd, so is $(2n-x)$ and all of its divisors are odd too. If it was composite, at least one of its prime factors must be $n$ or less. Thus, it can only fail the condition if it happens to be a prime itself. $\endgroup$ Mar 17, 2017 at 22:51

1 Answer 1


As you wrote, there are roughly $\frac{n}{2}-\frac{n}{\ln n}$ odd composite numbers up to $n$. Let's suppose they are all "equally distributed" so that, for any odd composite number $m$ and prime $p$ less than $n$, the event of $E_{n,m,p}:2n \equiv m(\mod p)$ is independent each other for any fixed $n,m$. Then, the probability of $m$ having no primes sharing remainders with $2n$ will be $$\prod _{2 \lt p \le n}\left(1-\frac{1}{p}\right)=2\prod _{p \le n}\left(1-\frac{1}{p}\right)\approx \frac{e^{-γ}}{\ln n}$$ where last approximation is from Mertens' 3rd theorem and γ is Euler-Mascheroni constant. Therefore,$$f(2n)\approx n\left(\frac{1}{2}-\frac{1}{\ln n}\right)\left(1-\frac{e^{-γ}}{\ln n}\right)$$ with some assumption.

Another try. Let $a+b=2n$, $1<a\le n \le b$ and $a,b$ are odd numbers. There are 4 possiblities.
1. Both $a,b$ are prime
2. $a$ is prime, $b$ is not.
3. $b$ is prime, $a$ is not.
4. Both $a,b$ are composites.

We are interested in the number of possibility 4. We know that there are $\lfloor \frac{n-3}{2} \rfloor$ odd solutions to $a+b=2n$, $1<a\le n \le b$, sum of possibility 1, 2 are $\pi(n)-1$, and sum of possibility 1, 3 are $\pi(2n)-\pi(n)$, but we cannot compute the number of possibility 1 accurately, as we don't know even whether Goldbach's conjecture is true or not.

Heuristic arguments give that the number of possibility 1 is roughly $\frac{n}{2 \ln^2 n}$, which is almost negligible compared to possibilities 2 and 3. So, lets approximate possibility 1 to $O\left(\frac{n}{\ln^2 n}\right)$. Then $$f(2n)= \lfloor \frac{n-3}{2} \rfloor-(\pi(2n)-\pi(n))-(\pi(n)-1)+O\left(\frac{n}{\ln^2 n}\right)=\frac{n}{2}-\frac{2n}{\ln n}+O\left(\frac{n}{\ln^2 n}\right)$$


  • $\begingroup$ Hi there. Thanks for the answer! I'm going to have to read this over several times. Thanks for the straightforward explanations of your derivation as well. $\endgroup$ Mar 18, 2017 at 18:16
  • $\begingroup$ Also, you haven't provided an upper bound for your first function. $\endgroup$ Mar 18, 2017 at 18:54
  • $\begingroup$ The "first function" is not satisfactory, since "equally distribution" assumption is not true in general. $\endgroup$
    – didgogns
    Mar 19, 2017 at 1:05
  • $\begingroup$ After reading through your proof a couple times, your answer makes more sense. As @didgogns already mentioned, "equal distribution" is not true in general, and as I have already pointed out, you have not provided upper or lower bounds for either of your two answers. $\endgroup$ Mar 20, 2017 at 19:57

You must log in to answer this question.

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