# Relevant primes

Let's call a prime number $p$ "relevant" if there exists an integer $n>1$ such that the integer part of the sum $$\sum_{k=1}^{p^n} \sqrt[n]{\frac{1}{k^{n-1}}}$$ is $2016$.

How many "relevant" primes are there?

On the topic of whether or not this is more appropriate for math SE

I considered this to be a more suitable problem for puzzling (with the math tag) rather than math SE. It is a mathematical puzzle to which I know the answer and which does not require anything mathematically technical to solve (pre-university maths is more than sufficient). I have certainly seen far more difficult problems posted on this SE under the math tag.

• I might be terribly wrong, but isn't it more suitable on Math SE? – Novarg Apr 5 '16 at 17:01
• I'm guessing this has a tricky answer that has waited years to become relevant – humn Apr 5 '16 at 18:04
• @Novarg If you're right, shouldn't this be migrated instead of closed? Or is closing a prerequisite to migration? – Lacklub Apr 5 '16 at 19:11
• definitely not $0$ since $1009$ is prime and works for $n=2$ – Jonathan Allan Apr 5 '16 at 22:35
• Sorry I've taken so long to get back on this. I considered this to be a more suitable problem for puzzling (with the math tag) rather than math SE. It is a mathematical puzzle to which I know the answer and which does not require anything too technical to solve (pre-university maths is more than sufficient). I have certainly seen far more difficult problems posted on this SE under the math tag. On the other hand, my view is that questions appropriate for math SE are questions for which the asker does not know the answer and is interested to find out. – hexomino Apr 6 '16 at 8:57

The term under summation is: $$f(n,k)=\sqrt[n]{\frac1{k^{n-1}}} =k^{\frac1n-1}$$ Note that: $$f(n,k-1)>f(n,k)$$ The total of the sum is the area under a decreasing stepwise function and is then bounded below and above by the integrals over the summation range of $f(n, k)$ and $f(n, k-1)$, respectively: $$\int_1^{p^n}k^{\frac1n-1}dk<\sum_1^{p^n}k^{\frac1n-1}<\int_1^{p^n}(k-1)^{\frac1n-1}dk$$

$f(n,k)$ passes through the left-hand points of the stepwise function, $f(n,k-1)$ passes through the right-hand points - so the summation is a left Riemann sum of $f(n,k)$ and a right Riemann sum of $f(n,k-1)$. The upper bound may be tightened by noting that the first term in the summation is $1$: $$\int_1^{p^n}k^{\frac1n-1}dk<\sum_1^{p^n}k^{\frac1n-1}<1 + \int_2^{p^n}(k-1)^{\frac1n-1}dk<1+\int_2^{p^n+1}(k-1)^{\frac1n-1}dk$$

Now evaluating the left and rightmost integrals:$$\int_1^{p^n}k^{\frac1n-1}dk=nk^\frac1n\big|_1^{p^n}=np-n=n(p-1)$$ $$1+\int_2^{p^n+1}(k-1)^{\frac1n-1}dk=1+\big(n(k-1)^\frac1n\big|_2^{p^n+1}\big)=1+np-n=1+n(p-1)$$

Therefore: $$n(p-1)<\sum_1^{p^n}k^{\frac1n-1}<1+n(p-1)$$

Since $n$ and $p$ are integers and $1+n(p-1)-n(p-1)=1$ we have that the lower bound is the integral part of the summation as required.

Solutions for the integral part being $2016$ then satisfy:$$n(p-1)=2016\space\forall n\in\Bbb N,p\space\text prime$$.

Yielding $17$ "relevant" primes (listed here with their respective $n$):

\begin{align} p&=1009;&n&=2\\ p&=673;&n&=3\\ p&=337;&n&=6\\ p&=127;&n&=16\\ p&=113;&n&=18\\ p&=97;&n&=21\\ p&=73;&n&=28\\ p&=43;&n&=48\\ p&=37;&n&=56\\ p&=29;&n&=72\\ p&=19;&n&=112\\ p&=17;&n&=126\\ p&=13;&n&=168\\ p&=7;&n&=336\\ p&=5;&n&=504\\ p&=3;&n&=1008\\ p&=2;&n&=2016\\ \end{align}

Other relevant material related to this puzzle for those interested can be found on Wikipedia:

Newton's identities

Euler-Mascheroni constant (the fractional part tends to this)

Credit to humn and ffao for elucidating my thoughts while I slept!

• You can try to prove this by approximating the sum by an integral. The integral of x ^ -(1 + 1/n) from 1 to p^n is exactly n(p-1), and then you should be able to bound the error term. – ffao Apr 6 '16 at 3:52
• You've made excellent progress. I feel like I should give you some encouragement since you've persevered while others have been turned off. See if you can prove your claim. Are there any upper/lower bounds you can place on the individual terms in the sum? – hexomino Apr 6 '16 at 8:48
• @hexomino - glad I noticed my upper bound was not tight enough before you or humn. Fixed it. – Jonathan Allan Apr 6 '16 at 21:24
• Would ^vote a second time if possible – humn Apr 6 '16 at 22:06