# Find formula for function of $n$ returning $0$ if $n$ is composite and $1$ if $n$ is prime

Sample problem:

Find an equation $$\theta(n)$$ for which $$\theta(n)=\left\{ \begin{array} &0, \text{when } n\in \text{Composed} \\ n, \text{when } n\in \text{Prime} \end{array} \right.$$

This problem is from the International Youth Math Challenge $$2018$$ and since they do not return marked sheets, I am unsure if my solution was correct.

My final answer was: $$\theta (n)=n-n\cdot \text{sgn} \left(\prod_{i=1}^{\infty} |n-p_i|\right)$$ where $$p_i$$ is the $$i^{\text{th}}$$ prime number. This is all I could come up with and to be honest, I am not too happy with it, because I feel like I have basically chosen something that will only give the answer I want. Is this solution correct, mathematically? Is there a better solution?

Note: $$\text {sgn}(n)$$ is the $$\text{sign}$$ or $$\text{signum}$$ function and $$\text{sgn}(n)=\left\{ \begin{array} &-1; \ \ n\lt 0\\ \ \ \ 0; \ \ n=0\\ \ \ \ 1; \ \ n\gt 0 \end{array} \right.$$

• Are you sure you're giving the complete statement of the problem? I don't think it makes sense without some sort of restriction as to what kind of functions/primitives you are allowed to use in a solution. – Evangelos Bampas Dec 21 '18 at 10:20
• The infinite product formula you suggest requires to compute an infinite product, which cannot be done in practice (and to define the signum function at $+\infty$, which is not so usual), and to know the full set of primes, which seems rather impractical as well. Easy remedies to these two defects are suggested below. – Did Dec 21 '18 at 10:59
• @Did which is what my title wonders. I only get the results I want, I cannot make further assumptions. – Mohammad Zuhair Khan Dec 21 '18 at 15:33

I'm not sure what kind of functions are allowed but here is a similar one (might be equivalent after some small changes), the differences being it's finite and doesn't require ability to select primes:

For any positive integer $$p$$, define this function $$f(n,p):= \left\lceil \frac{n-p\lfloor \frac{n}{p}\rfloor}{n} \right\rceil$$ If $$p$$ divides $$n$$ then $$f(n,p)=0$$, otherwise $$n-p\lfloor n/p\rfloor\neq 0$$ so $$f(n,p)=1$$.

You can then use this to make the following: $$\theta(n):= n - n\prod_{p=2}^{n-1}f(n,p)$$ If $$n$$ is composite then one of the $$p$$'s will make the product $$0$$ and hence $$\theta(n)=n$$. Otherwise $$n$$ is prime and the product is $$1$$, giving $$\theta(n)=0$$.

Good try; but there's something that needs fixing. When $$n$$ is composite, the product diverges to $$\infty$$; so you should define $$\text {sgn} (\infty) = 1$$.

• Thanks for the advice. But, unless I am mistaken, $+\infty \gt 0?$ – Mohammad Zuhair Khan Dec 21 '18 at 6:05
• @MohammadZuhairKhan Yes; just personally, I would mention that case, since often people assume that youre working in $\mathbb{R}$ instead of the extended number system. I would just put it to make sure there's no chance of getting points off. – Ovi Dec 21 '18 at 6:09
• Oh okay thank you. Ofcourse, as it is done already, I can not (and would not) update my answer. But is there any other solution for this problem? I have a suspicion that this might be an open problem, or atleast a sensible version of it will. – Mohammad Zuhair Khan Dec 21 '18 at 6:11
• @MohammadZuhairKhan I am thinking about it – Ovi Dec 21 '18 at 6:12
• @Ovi I would definitely not assume we are working in $\mathbb{R}$, $\mathbb{N}$ might be a better choice (nitpicks). I also don't see any reason to include such a definition, I would much prefer simpy choosing and noting which set does $n$ belong to. I would go as far as to consider writing $\text{sgn}(\infty)$ a mistake without well explaining why are you doing that and what do you mean by that. – J.E Dec 21 '18 at 11:10

Instead of the sign function, you could potentially use the Kronecker delta, which is defined as

$$\delta_{mn}=\begin{cases} 1 & \text{if }n=m\\ 0 & \text{if }n\neq m \end{cases}$$

It basically compares two numbers and gives $$1$$ if there is a match and $$0$$ otherwise. By summing over such Kronecker delta's, you could build:

$$\theta(n)=n\sum_{i=1}^{\infty}\delta_{np_i}$$

(where $$p_i$$ is the $$i$$-th prime number). However, I'm wondering if this would be accepted because it kind of bypasses the question of "checking if $$n$$ is prime". Both our formulas are just a nice rewording of the "text-form" formula given in the question, so I'm not certain this was the kind of answer that was expected.

• To be honest, the entire problem seems to be a test of a student's thought process. – Mohammad Zuhair Khan Dec 21 '18 at 15:36