Wikipedia:Reference desk/Archives/Mathematics/2024 March 4

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

March 4

For which natural number n, 1^k+2^k+3^k+…+n^k can be prime?

I saw the sequence (sequence A164307 in the OEIS), and now I have a problem: for For which natural number n, 1^k+2^k+3^k+…+n^k can be prime?

n=2, this is exactly the Fermat primes

n=3, numbers cannot be prime since they are divisible by 2

n=4, numbers cannot be prime since they are divisible by 2

n=5, no fixed small divisor of the numbers, but k must be divisible by 20 since they are divisible by 5 if k is not divisible by 4 and they are divisible by 11 if k == 4, 8, 12, 16 mod 20, and indeed the term k=1440 is prime, but are there infinitely many such primes?

n=6, numbers cannot be prime since they are divisible by 7 if k is not divisible by 6, while they are divisible by 13 if k is divisible by 6

n=7, numbers cannot be prime since they are divisible by 2

n=8, numbers cannot be prime since they are divisible by 2

n=9, numbers cannot be prime since they are divisible by 3

n=10, no fixed small divisor of the numbers, but k must be divisible by 20 since they are divisible by 11 if k is not divisible by 10 and they are divisible by 5 if k == 10 mod 20, but is there any such primes?

n=11, numbers cannot be prime since they are divisible by 2

n=12, numbers cannot be prime since they are divisible by 2

n=13, numbers cannot be prime since they are divisible by 13 if k is not divisible by 12, while they are divisible by 3 if k is divisible by 12

n=14, numbers cannot be prime since they are divisible by 7 if k is not divisible by 6, while they are divisible by 5 if k == 6 mod 12, while they are divisible by 13 if k is divisible by 12

n=15, numbers cannot be prime since they are divisible by 2

n=16, numbers cannot be prime since they are divisible by 2 218.187.65.97 (talk) 15:05, 4 March 2024 (UTC)

These sums have values given by Faulhaber's formula. That article has quite a bit about it but does not touch this question. I'm not sure it'll help much but it's worth a good look. NadVolum (talk) 21:43, 4 March 2024 (UTC)

Faulhaber should definitely be looked at here. The problem is that it involves those pesky Bernoulli numbers which aren't integers. If a prime is not a factor of the corresponding denominators then you can say something about whether it divides the sum, but otherwise the situation is more complicated. Let S(k, n) denote the sum. There are two variations on the problem here: First, given k, determine n so that S(k, n) is prime, and second, given n, determine k so that S(k, n) is prime. Faulhaber seems more relevant to the first problem, but the problem as stated in the question is more like the second version. For example, in the n=5 case the problem becomes: For which k is 1^k+2^k+3^k+4^k+5^k prime? Faulhaber doesn't seem to be very useful here since it gives a different formula for each k; you might as well just compute the sum manually. Fermat's little theorem seems more relevant since it implies that, for a fixed n, S(k, n) has period p-1 mod p. So if p|S(k, n) then p|S(j, n) for any j congruent to k mod p-1 (Edit: Assuming p>n). Unfortunately, unless p is very small, this only eliminates a fraction of possible k's (if any), This is the point where I would consult the literature, for which OEIS would be the starting point. But that's where this whole thing began. It would be nice to get some kind of result as in the n=2 case, that k must have a particular form such as 2^a, but that seems unlikely for n>2 unless you can eliminate all k as in the n=3 case. --RDBury (talk) 15:26, 5 March 2024 (UTC)

Note: There is a small error above in the n=6 case: S(12, 6) ≡ 2438235715 is not divisible by 7 or 13. All you can state from divisibility by p=7 and 13 these is that 12|k. But you can eliminate 4|k using p=5. Between p=5, 7 & 13 you can eliminate n=6. --RDBury (talk) 16:18, 5 March 2024 (UTC)

Also note: You can show that if S(k, 10) is prime then k is a multiple of 60; consider also p=7. I didn't see any other easy improvements though. S(60, 10) is composite having a factor of 137. S(120, 10) exceeded the amount of computation time I'm allowed on WolframAlpha; a primality test on a 120 digit number is not infeasible though. --RDBury (talk) 16:55, 5 March 2024 (UTC)

Our article on Faulhaber's formula points out that for odd $k>1$, $S(k,n)$ is a polynomial which has $n^{2}$ and $(n+1)^{2}$ terms. In general, we can write $S(k,n)={\frac {n^{2}(n+1)^{2}P(n)}{N}}$ where $P(n)$ is a polynomial with integer coefficients and $N$ is a constant positive integer. We can see that if $P(x)$ and $Q(x)$ are integer-valued polynomials, then if $P(n)Q(n)/N$ is an integer, then it must be composite if $P(n)>N$ and $Q(n)>N$, since some factor must remain of both $P(n)$ and $Q(n)$ after division by $N$. So if $n^{2}(n+1)^{2}>N$ and $P(n)>N$, then $S(k,n)$ cannot be prime. Since $P(n)>N$ if and only if ${\frac {n^{2}(n+1)^{2}P(n)}{N}}>n^{2}(n+1)^{2}$, we see that $S(k,n)$ cannot be prime for odd $k$ if $S(k,n)>n^{2}(n+1)^{2}>N$. For even $k$ an analogous result exists, except replacing $n^{2}(n+1)^{2}$ with $n(n+1)(2n+1)$. Of course, this leaves the problem of finding out what $N$ actually is. GalacticShoe (talk) 19:19, 5 March 2024 (UTC)

$N$ is given by the sequence OEIS:A064538. I couldn't find an upper bound in the references. It appears to be extraordinarily fast growing. GalacticShoe (talk) 04:25, 6 March 2024 (UTC)

For odd $k\geq 7$, $S(k,n)>n^{2}(n+1)^{2}$ when $n\geq 2$, and for even $k\geq 6$, $S(k,n)>n(n+1)(2n+1)$ when $n\geq 2$. So really, since $S(k,1)=1$ is never prime, the only inequality that matters is $n^{2}(n+1)^{2}>N$ for odd $k\geq 7$ and $n(n+1)(2n+1)>N$ for even $k\geq 6$. GalacticShoe (talk) 05:16, 6 March 2024 (UTC)

For $k=5$, all $n\geq 3$ cannot produce primes, and by direct testing $S(5,2)$ is not. So there are no $S(5,n)$ primes.

For $k=4$, all $n\geq 3$ cannot produce primes, but again by direct testing, $S(4,2)$ is prime (17).

For $k=3$ we can no longer use the limits, since $S(3,n)={\frac {n^{2}(n+1)^{2}}{4}}<n^{2}(n+1)^{2}$, but for obvious reasons there are no $S(3,n)$ primes.

For $k=2$ we again run into a problem with the limits as $S(3,n)={\frac {n(n+1)(2n+1)}{6}}<n(n+1)(2n+1)$, but again it can be seen that $S(2,2)=5$ is the only prime here.

For $k=1$ we see that $S(1,2)=3$ is the only prime.

In sum (pun intended), for $k\leq 5$ the only primes are $S(1,2),S(2,2),S(4,2)$. The set of primes for any fixed value of $k>5$ can be established with a finite but apparently quickly-growing computation. GalacticShoe (talk) 05:30, 6 March 2024 (UTC)

Coming back to this, for $k$ from $1$ through $48$ (the last term that A064538 has listed), the only primes are $S(1,2),S(2,2),S(4,2),S(8,2),S(16,2)$, all Fermat primes as the OP pointed out. GalacticShoe (talk) 07:48, 9 March 2024 (UTC)