Can we extend and generalise the ruler function by using only powers of $-1$ or other "simple" means, and then sum over the primes to efficiently test primality?

The ruler function (let's call it $r(n)$) is the exponent of the largest power of 2 that divides $n$: $0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,\ldots$

A string of its values can easily be generated by beginning with the string $0$ and repeatedly appending to the end, the entire string incremented by 1.

This can be generalised to give the powers of any prime factor $p$ in any given integer $n$, by always appending the current string to itself $p-1$ times and incrementing the $(p-1)^{th}$ by 1. For example the string for 3 is:


The strings up to any given prime $p$ can be added, yielding a number which is accurate up to the $(p+1)^{th}$ prime in yielding a $1$ in the $n^{th}$ term if and only if $n$ is prime. This fact would still be true if we replaced every nonzero number in the string with a $1$, although there may be benefit in retaining the full information. Let's call this the simplified ruler $s$. I thought it might be interesting to build a closed form for the primality of any given number by this means, and see if it simplifies to something useful.

Let's call the ruler function $r_2$ and generalise to $r_n$ although we are really interested in $r_p$ for any prime. We can easily create the simplified ruler $s_2$ by raising $-1$ to powers of $n$ as follows:


Logic suggests we can do the same for the number 3. Since $(-1)^n$ is binary for whole numbers, I suspect the method is to use a base 2 or binomial expansion of any given number, so calculate $s_3=s_4-s_1$ but I can't quite build it. What does $s_3$ look like, and what is this function generalised for all $n$ or for all $p$?

By "simple" what I actually mean, is to create some function that is easy to work with and has some nice properties, I think I may be looking for meromorphic function, but please correct me. But ideally I'd like to build it by powers of $-1$ or if necessary, complex numbers with unitary coefficients.

Can we also enhance this and build $r_p$?

Finally, does the sum across primes simplify in any way that gives us a powerful way of testing for nonzero values greater than some prime? This prime testing identity holds for both the sum over all primes, and for the sum over all primes less than any given prime:

$$\mathbb{P}(x)=1\iff x\in prime$$

holds for both:

$$\mathbb{P}(x)=\sum\limits_{k\in prime}^{\leq x}s_k(x)$$ and $$\mathbb{P}(x)=\sum\limits_{k\in prime}s_k(x)$$

In summary, just to make sure there can be no "it is unclear what you are asking", I'm asking if anybody can firstly generalise to $s_p$, the simplified ruler function $s_2$ and secondly sum $s_p(n)$ across either all primes, or all primes less than $n$.

I'm hoping this can be answered by the steps described, without just jumping directly to some statement like "s is the dirichlet generating function for $s(n)$"!

  • $\begingroup$ In other words, you want a formula for the function that is one at multiples of p and zero for other integers? $\endgroup$ – Daniel McLaury Aug 14 '16 at 16:04
  • $\begingroup$ @DanielMcLaury basically yes, that will be the ultimate conclusion of the exercise, but a nice (meromorphic?) function and ideally arrived at by the method above. The method might reveal multiple ways of attempting it. Having gone and had a game of tennis I'm thinking the above method requires complex nth roots of unity. $\endgroup$ – samerivertwice Aug 14 '16 at 16:54
  • $\begingroup$ @DanielMcLaury if we say the nth root of unity is $e^{2pi.i.\frac{k}{n}}\forall k: 0\leq k<n$ perhaps we can choose $k$'s or multiply multiple roots with different k's to create a function that's zero for non factors of $n$. $\endgroup$ – samerivertwice Aug 14 '16 at 17:13

As I understand the question, we desire a function $s_n(z)$ which takes on the value one at multiples of $n$ and zero at other integers.

There are infinitely many meromorphic functions taking on prescribed values at countably many points, so it would take additional conditions to specify a unique one.

One way of doing things, that generalizes the expression you have for $n = 2$ and results in a periodic holomorphic function, would be to take

$$s_n(z) := \frac{1}{n} \sum_{k=0}^{n-1} e^{2 \pi k z i / n}$$

That is, you need to take all the $n$-th roots of unity together, not just one of them.

For the case where $n$ is prime it's easy to see this works: if $z$ is an integer divisible by $n$, then each $n$-th root of unity taken to the $n$-th power results in one, so you get $n$ of them all together. If $z$ is an integer not divisible by $n$, then taking $z$-th powers fixes the one and permutes the other roots, and of course all the $n$-th roots of unity sum to zero. (It takes a bit more work to see what's going on when $n$ is composite.)

Alternatively, you can view this expression as the simplest Fourier series that gives you the desired behavior.

Note that this is still not unique; there are infinitely many periodic holomorphic functions taking on finitely many prescribed values on a period.

  • $\begingroup$ Is summing intended as I was expecting a product? Although I have summed below... confused! $\endgroup$ – samerivertwice Aug 15 '16 at 17:53
  • $\begingroup$ A sum is intended, yes. The point is that the nth roots of unity sum to zero. (Proof: the roots of a monic polynomial sum to the second highest degree coefficient of the polynomial, which is zero in the case of $x^n -1$.) $\endgroup$ – Daniel McLaury Aug 16 '16 at 0:45
  • $\begingroup$ Thanks. That's what I was looking for. I vaguely remember a famous theorem that the sum of all numbers less than any number n are zero mod n if it's prime, and 1 otherwise. $\endgroup$ – samerivertwice Aug 16 '16 at 7:16
  • $\begingroup$ Or something like that. But if that were true I would expect to be adding the exponents of $e$ and therefore finding the product but maybe I have the theorem wrong. $\endgroup$ – samerivertwice Aug 16 '16 at 7:24
  • 1
    $\begingroup$ I don't think there's any connection between Wilson's theorem and the formula I gave. The formula I gave doesn't care whether n is prime or not, for instance. $\endgroup$ – Daniel McLaury Aug 17 '16 at 3:13

Ok I'm using this answer to annotate a work in progress so please don't downvote for now... any help is welcome. For now the best I can do is suggest to use the nth root of unity, which raised to the power n then minus 1, will yield zero iff p factors n:

$$s_p(n)=\exp(\frac{2n\pi i}{p})-1$$

So the following function is zero for all primes n:

$$\mathbb{P}(n)=\sum\limits_{p\in prime}^{}s_p(n)=\sum\limits_{p\in prime}^{}(\exp(\frac{2n\pi i}{p})-1)=0\Leftarrow n\in prime$$

I can't simplify this sum, nor can Wolfram Alpha! But I have at least yielded some identity, namely that for any prime number $n$, $$\sum\limits_{p\in prime}^{}(\exp(\frac{2n\pi i}{p})-1)=0$$

Which I think will equal zero for any number p, and summing over any set of primes $P$ which are coprime with p.

A quick test with some numbers says I've made an error here. Please feel free to correct.


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.