7
$\begingroup$

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.$$

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Evangelos Bampas Dec 21 '18 at 10:20
  • $\begingroup$ 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. $\endgroup$ – Did Dec 21 '18 at 10:59
  • $\begingroup$ @Did which is what my title wonders. I only get the results I want, I cannot make further assumptions. $\endgroup$ – Mohammad Zuhair Khan Dec 21 '18 at 15:33
5
$\begingroup$

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$.

$\endgroup$
4
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Thanks for the advice. But, unless I am mistaken, $+\infty \gt 0?$ $\endgroup$ – Mohammad Zuhair Khan Dec 21 '18 at 6:05
  • 2
    $\begingroup$ @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. $\endgroup$ – Ovi Dec 21 '18 at 6:09
  • $\begingroup$ 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. $\endgroup$ – Mohammad Zuhair Khan Dec 21 '18 at 6:11
  • $\begingroup$ @MohammadZuhairKhan I am thinking about it $\endgroup$ – Ovi Dec 21 '18 at 6:12
  • $\begingroup$ @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. $\endgroup$ – J.E Dec 21 '18 at 11:10
3
$\begingroup$

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.

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

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.