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 '17 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$ – Peter Košinár Mar 17 '17 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$ – Linus Rastegar Mar 17 '17 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 '17 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$ – Peter Košinár Mar 17 '17 at 22:51

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$ – Linus Rastegar Mar 18 '17 at 18:16
  • $\begingroup$ Also, you haven't provided an upper bound for your first function. $\endgroup$ – Linus Rastegar Mar 18 '17 at 18:54
  • $\begingroup$ The "first function" is not satisfactory, since "equally distribution" assumption is not true in general. $\endgroup$ – didgogns Mar 19 '17 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$ – Linus Rastegar Mar 20 '17 at 19:57

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.