[Edu-sig] poking around in Py3k (recycling old algebra)

[kirby urner]

The code below is somewhat boringly similar to other stuff I've
archived here before, about finding all the totatives (defined below)
of some N, then multiplying all possible pairs (a Cartesian product)
modulo N to show how you've got closure i.e. you never get outside the
group.

The totatives of N are the numbers 1...(N-1) with no factors in common
with N.  If N is prime, every integer 1...(N-1) is a totative.  The
totient of N is *how many* totatives it has.  Think how it'd only take
you a few lessons to have your students impressing their guardians
with stuff Euler talked about (make sure they pronounce "Euler"
right).

Hey, did you know Ellipsis is a new primitive object in Python 3, denoted ... ?

>>> ...
Ellipsis

What's a little bit different in this pass is I'm applying some stuff
I learned from Steve Holden @ Pycon re iterators, other subsequent
trainings.

Iterators are "one way streets" that become exhausted (dead end in
StopIteration) so you might need to clone them ahead of time.

The itertools tee is good for that e.g.  lazyA, lazyB = itertools.tee(
iteratorX ) will give you two for the price of one, then don't use
iteratorX anymore (it's exhausted).

Below, I want the totient (== number of totatives), so consume a whole
iterator going totient = len(list(theiterator)) -- but fortunately I
tee first.

Hey, I was just learning from David Beazley on Safari that __repr__ is
generally supposed to emit a string that'll eval right back to the
object represented.  So if I have Modulo type and go k = Modulo(10)
then my __repr__ should maybe just emit 'Modulo(10)'.  __str__ is for
something prettier maybe (adding makeup).

itertools.product will pair each with every, given two iterators
(actually, takes any number, proceeds odometer style), but again, if
you were to use the same iterator twice, you'd end up consuming all
the rows so nothing left for columns or vice versa.

That's where the repeat keyword argument comes in, which I use as an
alternative to tee for a check (see multiply_a vs. multiply_b).

Other little known features of Python 3.x, the ability to write:

>>> def f(x:int) -> int:  return x * x

>>> f.__annotations__
{'x': <class 'int'>, 'return': <class 'int'>}

The new __prepare__ method allowing processing in the classdict you're
about to hand off to __new__, bolstering metaclass definitions.

Set and dictionary comprehensions, cool.

I play with a set comprehension below, limiting the output of the
Cayley table to unique terms only (note curly braces in output) --
what takes the most room are the powering tables, where I take each
totative t and go pow( t, e, N) with e ranging from 0 to totient-1 (a
list comprehension).  This relates to RSA.

Also this is kinda weird (newly legal syntax):

>>> alpha, *junk, omega = "This is sorta cool syntax eh?".split()
>>> alpha
'This'
>>> junk
['is', 'sorta', 'cool', 'syntax']
>>> omega
'eh?'
>>>

OK, the rest is source code, with output listed at the end...

"""
product does a cartesian product of two iterables
tee replicates iterables 'repeat' times (default repeat=2)

More of what this is actually about:

http://www.4dsolutions.net/ocn/flash/group.html
(yikes, evil noise!  turn down those headphones!)

"""

from itertools import product, tee

def gcd(a,b):
    """
    EA per Guido
    """
    while b:
        a, b = b, a % b
    return a

def tots(n):
    """
    returns iterator of no factors
    in common (totatives)
    """
    return (i for i in range(n) if gcd(i, n) == 1)

def multiply_a(ts,n):
    """
    Cayley Table of ts x ts modulo n
    """
    ps = product(ts, repeat=2)
    return (i*j % n for i,j in ps)

def multiply_b(ts,n):
    """
    Cayley Table of ts x ts modulo n
    (alternate implementation)
    """
    row, col = tee(ts)
    ps = product(row, col)
    return (i*j % n for i,j in ps)

def powers(ts,n):
    a,b = tee(ts)
    totient = len(list(b))
    for t in a:
        print([pow(t,exp,n) for exp in range(totient)])

def test(n):
    print({i for i in multiply_a(tots(n),n)})
    # print({i for i in multiply_b(tots(n),n)})
    powers(tots(n),n)

if __name__ == '__main__':
    test(12)
    test(15)
    test(21)
    test(24)

So what's the printout if you run it?....

>>> ================================ RESTART ================================
>>>
{1, 11, 5, 7}
[1, 1, 1, 1]
[1, 5, 1, 5]
[1, 7, 1, 7]
[1, 11, 1, 11]
{1, 2, 4, 7, 8, 11, 13, 14}
[1, 1, 1, 1, 1, 1, 1, 1]
[1, 2, 4, 8, 1, 2, 4, 8]
[1, 4, 1, 4, 1, 4, 1, 4]
[1, 7, 4, 13, 1, 7, 4, 13]
[1, 8, 4, 2, 1, 8, 4, 2]
[1, 11, 1, 11, 1, 11, 1, 11]
[1, 13, 4, 7, 1, 13, 4, 7]
[1, 14, 1, 14, 1, 14, 1, 14]
{1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20}
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 2, 4, 8, 16, 11, 1, 2, 4, 8, 16, 11]
[1, 4, 16, 1, 4, 16, 1, 4, 16, 1, 4, 16]
[1, 5, 4, 20, 16, 17, 1, 5, 4, 20, 16, 17]
[1, 8, 1, 8, 1, 8, 1, 8, 1, 8, 1, 8]
[1, 10, 16, 13, 4, 19, 1, 10, 16, 13, 4, 19]
[1, 11, 16, 8, 4, 2, 1, 11, 16, 8, 4, 2]
[1, 13, 1, 13, 1, 13, 1, 13, 1, 13, 1, 13]
[1, 16, 4, 1, 16, 4, 1, 16, 4, 1, 16, 4]
[1, 17, 16, 20, 4, 5, 1, 17, 16, 20, 4, 5]
[1, 19, 4, 13, 16, 10, 1, 19, 4, 13, 16, 10]
[1, 20, 1, 20, 1, 20, 1, 20, 1, 20, 1, 20]
{1, 5, 7, 11, 13, 17, 19, 23}
[1, 1, 1, 1, 1, 1, 1, 1]
[1, 5, 1, 5, 1, 5, 1, 5]
[1, 7, 1, 7, 1, 7, 1, 7]
[1, 11, 1, 11, 1, 11, 1, 11]
[1, 13, 1, 13, 1, 13, 1, 13]
[1, 17, 1, 17, 1, 17, 1, 17]
[1, 19, 1, 19, 1, 19, 1, 19]
[1, 23, 1, 23, 1, 23, 1, 23]
>>>

As I said, kinda boring maybe....

Kirby