mersenneforum.org LL pseudoprimes?
 Register FAQ Search Today's Posts Mark Forums Read

 2023-01-23, 03:50 #1 Andrew Usher   Dec 2022 5×43 Posts LL pseudoprimes? The Lucas-Lehmer test, with the standard starting value 4, can only work for numbers that are 7 mod 24 (from properties of Lucas sequences), a form possessed by all odd-exponent Mersennes. We can think of it, then, in the reverse fashion, by saying that any composite 7 mod 24 that divides the corresponding term of the Lucas sequence, as a pseudoprime to the test. Then the LL test says that no such pseudoprime is 2^n-1, and the LLR extension (which gave me the idea) that none is k*2^n-1 for k < 2^n. In fact, one can show it must be somewhat higher than that, but I've forgotten the details (which I didn't write down). Stringent requirements almost make one doubt that there could be any, but every test has some, and the analogue for the ordinary Lucas numbers has all the Fibonacci pseudoprimes that are 3 mod 4 (appears to be half of them). So any pseudoprime can be defined best as a composite number 7 mod 24 dividing the (n+1)/8'th term of A011943 or its double which is V(14,1) (the numbers in the LL test are the powers of two in that sequence). I was writing a program to search for such pseudoprimes to 2^32; it is not complete and I am sorry to say that defending myself from attacks on this forum seems to have for the present robbed me of the energy to complete it, though I think I have figured out how. So I am posting now to see if anyone else has had any interest in the idea or knows of any such pseudoprime.
 2023-01-23, 12:07 #2 Andrew Usher   Dec 2022 5·43 Posts I did write that last part to get it working and the program, which verified itself by correctly getting zero residues for every prime 7 mod 24, obtained 60 composite pseudoprimes to 2^32. The smallest is over a million; only two have more than 2 prime factors and those, 31*223*607 and 31*607*1567, both divide the 28th term. I will list them all if requested.

 Similar Threads Thread Thread Starter Forum Replies Last Post a1call Miscellaneous Math 22 2018-08-09 11:11 devarajkandadai Number Theory Discussion Group 7 2017-12-06 01:46 TheoryQuest1 Factoring 10 2016-09-19 16:08 CRGreathouse Computer Science & Computational Number Theory 36 2013-11-21 07:47 efeuvete Math 7 2013-05-26 11:24

All times are UTC. The time now is 01:58.

Thu Feb 2 01:58:17 UTC 2023 up 167 days, 23:26, 1 user, load averages: 1.14, 0.99, 0.97