2023-01-23, 03:50 | #1 |
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 |
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. |
Thread Tools | |
Similar Threads | ||||
Thread | Thread Starter | Forum | Replies | Last Post |
Are Mersenne Pseudoprimes are all Relatively Prime? | a1call | Miscellaneous Math | 22 | 2018-08-09 11:11 |
Pseudoprimes in special fields | devarajkandadai | Number Theory Discussion Group | 7 | 2017-12-06 01:46 |
On generating Strong PseudoPrimes DataBase? | TheoryQuest1 | Factoring | 10 | 2016-09-19 16:08 |
Pseudoprimes | CRGreathouse | Computer Science & Computational Number Theory | 36 | 2013-11-21 07:47 |
Odd Fibonacci pseudoprimes | efeuvete | Math | 7 | 2013-05-26 11:24 |