--- In firstname.lastname@example.org
"mikeoakes2" <mikeoakes2@...> wrote:
> Any pari code I come up with is horribly sluggish
> for n more than about 10^6.
> I await your 4 lines with interest!
This was the puzzle:
> Puzzle: Find a composite positive odd integer n that passes
> the Lucas test V(a,1,n) = a mod n, for every integer a.
n = 7056721 is the unique solution with n < 10^10.
However, I have more than 144000 larger solutions on file.
Using Pari-GP, I found a candidate solution as follows:
Then by googling
> pseudoprime 7056721
I arrived at
which proves that n is a solution if and only if it is an odd
square-free composite integer such that for each prime p|n
n = +/- 1 mod p-1 ... 
n = +/- 1 mod p+1 ... 
This paper claims that 7056721 is the unique solution with n < 10^10.
It is easy to construct larger solutions. For example
provides a link to 246 solutions in
with n = 1 mod p^2-1, for each prime p|n.
For 144153 such solutions, see the 12 MB file
obtained by Robert Gerbicz on 1 April 2009 and verified here:
print(c"/"#ls" failures in "round(gettime/10^3)" seconds");
0/144153 failures in 27 seconds
Puzzle: Find the smallest composite integer n > 7056721
such that V(a,1,n) = a mod n, for every integer a.
Comment: The solution is not known to me.
David Broadhurst, 24 May 2010