[Edu-sig] a quick look at GIS

[kirby urner]

> 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