login
Least number x > 1 such that n*x divides 1 + Sum_{k=1..x-1} k^(x-1).
1

%I #65 Feb 16 2025 08:33:55

%S 2,3,13,7,19,31,41,31,13,19,43,31,23,83,139,31,61,67,113,79,251,43,19,

%T 31,199,23,13,167,53,139,83,127,157,67,293,431,443,151,103,79,61,251,

%U 113,47,337,19,179,31,41,199,67,23,19,499,181,367,607,139,257,359

%N Least number x > 1 such that n*x divides 1 + Sum_{k=1..x-1} k^(x-1).

%C If n = 1, all the solutions of x | 1 + Sum_{k=1..x-1} k^(x-1) should be prime numbers, according to Giuga's conjecture.

%C If n*x | 1 + Sum_{k=1..x-1} k^(x-1), then certainly x does, so Giuga's conjecture would say x must be prime. Similarly if x^n divides it, so does x, so again Giuga would say x is prime. - _Robert Israel_, Apr 26 2019

%C E.g., the first solution for x^2 | 1 + Sum_{k=1..x-1} k^(x-1) is x = 1277, that is prime.

%H Robert Israel, <a href="/A306431/b306431.txt">Table of n, a(n) for n = 1..2000</a>

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/GiugasConjecture.html">Giuga's Conjecture</a>

%F Least solution of n*x | 1 + Sum_{k=1..x-1} k^(x-1), for n = 1, 2, 3, ...

%e a(4) = 7 because (1 + 1^6 + 2^6 + 3^6 + 4^6 + 5^6 + 6^6) / (4*7) = 67172 / 28 = 2399 and it is the least prime to have this property.

%p P:=proc(j) local k,n; for n from 2 to 10^6 do

%p if frac((add(k^(n-1),k=1..n-1)+1)/(j*n))=0

%p then RETURN(n); break; fi; od; end: seq(P(i),i=1..60);

%t a[n_] := For[x = 2, True, x++, If[Divisible[1+Sum[k^(x-1), {k, x-1}], n x], Return[x]]];

%t Array[a, 60] (* _Jean-François Alcover_, Oct 16 2020 *)

%o (PARI) a(n) = my(x=2); while (((1 + sum(k=1, x-1, k^(x-1))) % (n*x)), x++); x; \\ _Michel Marcus_, Apr 27 2019

%Y Cf. A191677. All the solutions for n = m: A000040 (m=1), A002145 (m=2), A007522 (m=4), A127576 (m=8), A141887 (m=10), A127578 (m=16), A142198 (m=20), A127579 (m=32), A095995 (m=50).

%K nonn,easy,changed

%O 1,1

%A _Paolo P. Lava_, Apr 05 2019