Prime numbers and primality testing is a Restricted Group with 1137 members. Yahoo Groups Cubic factors of n^n+(n+1)^(n+1) djbroadhurst Oct 21, 2011 ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote: > Puzzle: Find a prime p for which there exist an integer n such that > p^3 divides n^n+(n+1)^(n+1) and 10^500 < n < p*sqrt(3) < 10^600. As there were no takers, I shall post a solution: Lucas solution: p = V(4,1,971)/4; n = (3*U(4,1,971) - 1)/2. I have some concise explanatory notes on this problem, with larger historical examples, if anyone will ask me to post them. Else, silence... David djbroadhurst Oct 21, 2011 ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote: > I have some concise explanatory notes on this problem, > with larger historical examples, if anyone will ask me > to post them. Phil has kindly asked me to do so. > Puzzle: Find a prime p for which there exist an integer n such that > p^3 divides n^n+(n+1)^(n+1) and 10^500 < n < p*sqrt(3) < 10^600. > Lucas solution: p = V(4,1,971)/4; n = (3*U(4,1,971) - 1)/2. Notes: p = V(4,1,k)/4 is a proven prime for these primes k: 3, 5, 7, 11, 13, 17, 19, 79, 151, 199, 233, 251, 317, 863, 971, 3049, 7451, 7487, 18869. At present, http://oeis.org/A117808 lists primes only up to V(4,1,79)/4 = 381765135195632792959100810331957408101589361 and chooses to include 3, as the floor of V(4,1,2)/4 = 7/2. With n = (3*U(4,1,k) - 1)/2, we solve n^2 + n + 1 = 3*p^2. Then (n+1)^(n+1) == +/- n^n (mod p^4) for k == +/- 1 (mod 4). Pari-GP took 0.3 seconds to find k = 971 and proved primality in 30 seconds, thus solving the puzzle, at 555 digits. We also have Williams-Lenstra proofs at k = 7451 and 7487: http://tech.groups.yahoo.com/group/primenumbers/message/2485 while the cases k = 3049 and 18869 solve a different puzzle, with p^4|(n+1)^(n+1)-n^n. The first is an easy proof for PFGW: > Calling N-1 BLS with factored part 47.12% > and helper 15.11% (156.54% proof) > lucasV(4,1,3049)/4 is prime! (2.7309s+0.0453s). and the second, at 10792 digits, was proven in 2009: http://tech.groups.yahoo.com/group/primenumbers/message/20127 David Broadhurst, 22 October 2011 djbroadhurst ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote: > Lucas solution: p = V(4,1,971)/4; n = (3*U(4,1,971) - 1)/2. > > Notes: p = V(4,1,k)/4 is a proven prime for these primes k: > 3, 5, 7, 11, 13, 17, 19, 79, 151, 199, 233, > 251, 317, 863, 971, 3049, 7451, 7487, 18869. PS: I know of no proof of the primality of http://www.primenumbers.net/prptop/searchform.php?form=?32869)? David