Problems & Puzzles: Puzzles

Puzzle 998. A306431

Paolo Lava sent the following puzzle:

I was looking at a sequence I edited on OEIS exactly one year ago: A306431.
The question could be:

Q1. Which is the least number x>1 (supposedly prime due to Giuga's conjecture) such that x^n|1 + Sum_{k=1..x-1} k^(x-1), for n>2.

In fact, I calculate the least number for n=1 that is 2 and for n=2 that is 1277 (see Comments in A306431)

Contributions came from Jan van Delden and Oscar Volpatti, during the week ending May 2, 2020


Jan wrote:

It is conjectured by Giuga that 1+sum(k=1..m-1,k^(m-1))=0 mod m implies that m is prime. The first counterexample, where m is composite, if it exists, occurs for m having more than 13800 digits (Giuga’s conjecture on primality, D. Borwein, J. M. Borweinz, P. B. Borwein, R. Girgensohn). For now it is safe to test only n=p, prime.

Before asking whether p^n is a divisor, with n>2, first ask for the second occurence of n=2. I tested untill p=3000017. Which is a rather small bound, I agree. If one would calculate the number of digits of the sum (which I wouldn’t recommend) we would end up with 19431475 digits (or 1 less).

I did not find another solution. It reminds me of Wilson or Wieferich primes. But I’m probably impatient.



Oscar wrote:

I found no solution x for n>2 so far.

However, a straightforward evaluation of the sum
S(n,x) = 1 + Sum_{k=1..x-1} k^(x-1) mod x^n
is very slow, and I checked x only up to 1.6e7.

But it may be the case that no solutions exist for n>2, considering the following heuristic argument.

Let's estimate the number of solutions x within interval 2..y:
C(n,y) = Sum_{x=2..y} c(n,x),
where c(n,x) is a guess about the chance that relation S(n,x) = 0 holds.
Assuming that all permitted residues are equally likely:
c(n,x) = 1/(x^(n-1))  if x is prime. as we know that x divides S(n,x),
c(n,x) = 1/(x^n)   if x is composite (not assuming Giuga's conjecture).

For n=2, the contribution of primes diverges as  ln(ln(y)) + 0.261497, while the contribution of composites converges to 0.192687.
C(2,y) exceeds 2 for y=103 and exceeds 3 for y=345133; maybe too optimistic, as the only solutions before 1.6e7 are x=1277 and x=780887.

For n=3, both contributions converge, so C(3,y) converges to 0.452247+0.027294=0.479542.
For n>3, C(n,y) converges to smaller and smaller values.



Records   |  Conjectures  |  Problems  |  Puzzles