Prove A New Method For Finding Primes.

I was recently messing around with harmonic numbers - that is $H_x = \sum^x_{k=1}\frac{1}{k}$ - and I was thinking what would happen if you applied Gauss' trick to the sum, which is to add up the first and last term, then the second and second-to-last term and so on. This is usually used in adding natural numbers, but when I applied it to the sum I noticed a recurring numerator. $$\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\frac{1}{6}\to\frac{7}{6}+\frac{7}{10}+\frac{7}{12}$$ I also noticed there were some cases where there wasn't, like $H_{8}$ $$\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\frac{1}{6}+\frac{1}{7}+\frac{1}{8}\to\frac{9}{8}+\frac{9}{14}+\frac{\textbf{1}}{2}+\frac{9}{20}$$ From this I guessed that if $H_x$ with Gauss' trick applied has a constant numerator, then $x+1$ is prime. I tried proving this, but I'm not sure if I'm right.

• Gauss Trick
• Harmonic Numbers

Solution 1:

Notice that if you write $\frac12$ in your second example as $\frac{9}{18}$, then you get your nice pattern back.

Generally each term of your sequence has the form $$ \frac{1}{n} + \frac{1}{x+1-n} = \frac{x+1}{n(x+1-n)} $$ and if $x+1$ is prime then you can be sure it doesn't reduce further.

On the other hand, if $x+1$ is composite, then there will be at least one of the $n$s that divide it, so in the term for that $n$ both of the numerator and the denominator will be divisible by that $n$, so it can be reduced.

On the other other hand, the term for $n=1$ is $\frac{x+1}{x}$, which never reduces.

So all of the reduced numerators are equal exactly if $x+1$ is prime.

This is hardly a "method for finding primes", though, because computing and reducing all of the sums takes at least as much work as checking whether $x+1$ is prime by trial division anyway.

Solution 2:

As noted in a comment, you are generating sequence of numbers $$\frac{1}{i}+\frac{1}{n+1-i} = \frac{n+1}{i(n+1-i)}.$$ Now notice that this fraction will simplify if nominator and denominator have common divisor, but both numbers $i,n+1-i < n+1$ iterate through all numbers less than $n+1$, so if there is a number dividing $n+1$, it will simplify the fraction eventually (i.e. if $n+1$ is composite) and it will not simplify the fraction if there is no such number (hence $n+1$ is a prime).