> Ninth graders wanna Fermat test ( pow(2, p - 1, p) == 1 for p in > primes ) and like that -- so forget the TI calculators for now, get > some more real estate (screen space), real beef (Intel inside), or an > XO or whatever. Then ( pow(2, p - 1, p) == 1 for p in pseudoprimes ) > with primes and pseudoprimes writable as generators. > > Kirby > 4D
Like from a TECC prototype Python session: Grab the opening sequence from OEIS, run a few bases. Theorem precondition is gcd( base, p) == 1 where p is some pseudoprime, which is why the test fails for 3. You're looking at Carmichael Numbers, composites that pass the Fermat Test, no matter the base, given said precondition. IDLE 1.2.1 >>> ultrapseudo = [ 561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, >>> 29341, 41041, 46657, 52633, 62745, 63973, 75361, 101101, 115921, 126217, >>> 162401, 172081, 188461, 252601, 278545, 294409, 314821, 334153, 340561, >>> 399001, 410041, 449065, 488881, 512461 ] >>> ( pow(2, p - 1, p) == 1 for p in ultrapseudo ) <generator object at 0x00E68328> >>> um = ( pow(2, p - 1, p) == 1 for p in ultrapseudo ) >>> um.next() True >>> um.next() True >>> um.next() True >>> um.next() True >>> um.next() True >>> um.next() True >>> um = ( pow(3, p - 1, p) == 1 for p in ultrapseudo ) >>> >>> um.next() # <---- starting over at 561, but gcd(561, 3) is not 1. False >>> um.next() True >>> um.next() True >>> um.next() True >>> um.next() True >>> um.next() True http://www.research.att.com/~njas/sequences/A002997 Kirby 4D _______________________________________________ Edu-sig mailing list Edu-sig@python.org http://mail.python.org/mailman/listinfo/edu-sig
