Another lesson plan (Euler's Theorem) from OCN / CSN
So here's more computer algebra, ready for phasein, base camps in the Columbia Gorge (like computer camps for girl scouts, astronomy encouraged). You can project computer languages around the campfire if you have the right equipment, bed sheet between trees, but that's really a lot of work probably, thinking ahead to Montana (NPYM). Might just all download the same Podcasts and watch separately, when the time comes (still a group storytelling experience). OK, so here's the shell session, nothing spectacular, just another one of our "theorem checkers" using try/except around an assert, something we expect to always be true, provided stipulations get met. Here's what's interesting: the last example craps out, not because of the newly added __pow__ method, which is optimized internally for modulo powering (special algorithm per Knuth, Tim Peters confirming it's in Python) but because my totatives function is completely inefficient. The preferred pipeline for totient, memorialized in my raytracing of that formula for phi (Euler's preferred right?), in that paper with K. Iverson, was to show the prime factors approach, much more affordable (once you get those prime factors, let's not bleep over): http://www.4dsolutions.net/ocn/graphics/phistone.jpg http://www.4dsolutions.net/ocn/Jlang.html Ah, but getting prime factors is a hard problem, or can be, whereas my little engine starts up the Himalayas at a snail's speed, breaks before getting to the summit. But that's really OK. We're exploring the meme pool, and time/energy *is* a factor, as Gregor so eloquently riffed about. We accept that a conceptually clear algorithm may be impracticable in some real world situations, want students hip and alert to that fact. Let's be clear: sometimes we just *don't have* any algorithm for job x, that'll work in your life time. Because of proofs in mathematics we're able to be up front about that, tell the brat emperor when there's just no way (in theory anyway, gets dicey sometimes). The flip side of that shortcoming is we have pretty good privacy when we need it. So, without further ado:
from algebra import * euler_checker(217, base=5) True!: pow(5, 180, 217) == 1 euler_checker(17) True!: pow(2, 16, 17) == 1 euler_checker(13452199029039023920, base=2) Pick a different base please euler_checker(13452199029039023921, base=2) Traceback (most recent call last): File "<pyshell#47>", line 1, in <module> euler_checker(13452199029039023921, base=2) File "/home/kirby/algebra.py", line 37, in euler_checker totient = len(totatives(N)) File "/home/kirby/algebra.py", line 9, in totatives return [ x for x in range(1, n) if gcd(x, n) == 1] File "/home/kirby/algebra.py", line 9, in <listcomp> return [ x for x in range(1, n) if gcd(x, n) == 1] File "/home/kirby/algebra.py", line 5, in gcd a, b = b, a % b KeyboardInterrupt
============= from random import choice def gcd(a,b): while b: a, b = b, a % b return a def totatives(n): return [ x for x in range(1, n) if gcd(x, n) == 1] class Modulo: m = 12 def __init__(self, n): self.n = n % Modulo.m def __mul__(self, other): return Modulo(self * other) def __pow__(self, n): return Modulo(pow(self.n, n, Modulo.m)) def __eq__(self, other): return self.n == other.n def __repr__(self): return str(self.n) def closure_checker(pool): while True: a, b = choice(pool), choice(pool) result = a * b assert result in pool yield "%s * %s == %s" % (a, b, result) def euler_checker(N, base=2): """ a check (not a proof) of Euler's Theorem """ if gcd(base, N) == 1: # coprime? totient = len(totatives(N)) try: assert pow(base, totient, N) == 1 print("True!: pow(%s, %s, %s) == 1" % (base, totient, N)) except: print("False!: pow(%s, %s, %s) != 1" % (base, totient, N)) else: # (base, N) not coprime print("Pick a different base please.") Kirby Urner Abbreviations decoded: OCN: Oregon Curriculum Network (4dsolutions.net/ocn) CSN: Coffee Shops Network (YouTube commercial: http://www.youtube.com/watch?v=0Oad0libltM special thx to jimmlott.com, and csn.cto nirel) Here's another geeky YouTube commercial I like, for Ruby on Rails: http://www.youtube.com/watch?v=91C7ax0UAAc&feature=recHMfresh+div (more from Python Nation?  still needing judges for 'The Writhe' contest: http://mybizmo.blogspot.com/2008/10/ppug20081014.html )
participants (1)

kirby urner