Would the function

$$\sum_{a=2}^\infty H\!\left(x-a\sum_{n=0}^\infty H(x-na)\right)$$

(H(x) is the Heaviside step function) Work as a test for prime numbers

it is zero when x is prime And a positive integer when x is composite

I have added an image in case the formula didn’t work (https://i.stack.imgur.com/MDxQI.jpg)

  • $\begingroup$ @Bill : Consider the integer 23. How will the Heaviside function put a value of 0 or any other positive integer against 23 without already know if 23 is a prime or not? $\endgroup$ – Nilos Apr 14 at 8:55

Your formula doesn't quite work, but a similar function will. Consider

$$f(x) = \sum_{a=2}^\infty H\!\left( \left(a\sum_{n=1}^\infty H(x-na)\right) - x\right).$$

We can write $\sum_{n=1}^\infty H(x-na) = \sum_{1 \leq n \leq x /a} 1$, or the number of integers $n \geq 1$ with $n \leq x/a$, or equivalently, $n \leq \lfloor x /a \rfloor$; thus $$\sum_{n=1}^\infty H(x-na) = \lfloor x / a \rfloor.$$ Then

$$f(x) = \sum_{a=2}^\infty H\!\left(a\lfloor x / a \rfloor -x\right).$$

Note that $a\lfloor x / a \rfloor = x$ when $a | x$, and otherwise $a \lfloor x / a \rfloor < x$. Therefore the summand $H\!\left(a\lfloor x / a \rfloor -x\right) = 1$ if $a | x$ and is $0$ otherwise. Thus when $x$ is prime, $f(x) = 1$ since $x$ has only one divisor $d > 2$, but if x is composite then $f(x) > 1$.

(in your original formula you get $$\sum_{a=2}^\infty H\!\left(x - a(1+\lfloor x / a \rfloor)\right)$$

which is always $0$ since $a(1 + \lfloor x /a \rfloor) > x$ always.)

Of course, evaluating this function is like performing trial division for all integers below $x$, so it is not very fast.


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.