Re: Lucas super-pseudoprime puzzle
- --- In email@example.com,
"mikeoakes2" <mikeoakes2@...> wrote:
> Any pari code I come up with is horribly sluggishThis was the puzzle:
> for n more than about 10^6.
> I await your 4 lines with interest!
> Puzzle: Find a composite positive odd integer n that passesn = 7056721 is the unique solution with n < 10^10.
> the Lucas test V(a,1,n) = a mod n, for every integer a.
However, I have more than 144000 larger solutions on file.
Using Pari-GP, I found a candidate solution as follows:
Then by googling
> pseudoprime 7056721I 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
- --- In firstname.lastname@example.org, "djbroadhurst" <d.broadhurst@...> wrote:
>You did very much what I did.
> I tried 1/n^c:
> v=[1237.1, 328.7, 105.4, 28.01, 6.22 , 1.510, 0.439, 0.0939];
> [0.5815, 0.5805, 0.5682, 0.5691, 0.5785, 0.5821, 0.5780, 0.5856]
> and then A/n^c, using the first datum to remove A:
> [0.5756, 0.5348, 0.5484, 0.5747, 0.5827, 0.5750, 0.5885]
> In both cases c =~ Euler looks rather convincing,
> given the statistics. Well spotted, Sir!
I nearly fell off the chair when I averaged everything out and saw 0.57... :-)
> How strongly are you committed to A = 1, for the average,Not very.
> given the variability of the overall factor with a?
Would you buy an appeal to Occam's razor, mon vieux?