($\lambda$ Calc vs $\Delta$ Calc)
In one of the shoptalks or namespaces around here, we get the proposal to bifurcate the math track through high school along what used to be called college prep and vocational lines. The vocational track had fallen out of vogue and gotten defunded, because higher education had become mandatory for most white collar and many blue collar professions.
Meanwhile, computer science had proved relevant to society at all levels and many high schools were pushing to develop their computer science faculty, as distinct from the mathematics faculty, mirroring many colleges.
The $\Delta$- and $\lambda$- calc bifurcation would keep everything mathematical, as computer technology needs to permeate even everyday math by osmosis. However some of the topics abandoned in the rush to delta calc (the calculus), could now be covered under the rubric of this other calculus. The original $\lambda$-calc of Alonso Church & Co. would be included under the newer expanded domain, following subsequent branding down around $\lambda$ in the computer field.
from IPython.display import YouTubeVideo
YouTubeVideo("eTDH7m4vEiM")
Number Theory often begins with the Fundamental Theorem of Arithmetic: all positive integers may be distilled into a unique set of prime factors. If -1 is considered a prime factor, per J.H. Conway's suggestion, then all of $Z$ (except 0) may be so distilled.
Determining whether a number is really prime or not, and therefore whether it has factors, is a difficult problem. The unfactorability of large composites is at the basis of the Rivest Shamir Adelson (RSA) method of public key cryptography.
The School of Tomorrow introduces number theory in steps, with a goal of making RSA comprehensible. To this end, some vocabulary is needed, most specifically: prime, composite, totatives, totient, coprime (stranger) and modulo arithmetic i.e. operations relative to some modulus.
Python offers the modulo operator (%) and divmod as tools for doing modulo arithmetic.
We start by distinguishing primes from composites in the positive integers, and then look at GCD and LCM, or Greatest Common Divisor and Lowest Common Multiple.
Missing from many a high school math textbook in the late 1900s was Euclid's Method, often expressed recursively in lambda calculus, but not always.
def gcd(a, b):
while b:
a, b = b, a % b
return a
gcd(55, 20)
5
def lcm(a, b):
return (a * b) // gcd(a, b)
from functools import reduce
reduce(lcm, (12, 24, 6))
24
Two positive integers with no prime factors in common, or in other words a GCD of just one, are said to be coprime, relatively prime, and/or strangers.
def coprime(a, b):
return True if gcd(a,b)==1 else False
coprime(200, 99)
True
prime = int("""\
53084469288402965415857953902888840109250315594591772197851275320
59910735745658243457138160802170063601085186072703319516241231606
86858731799078163479147444957979157038109676507221794134810159187
99946828292780972255445123198357952762990102770564813212521111380
68349356142222060588948481473772481328151681322128358047354205784
70540373426870045719371801557904317944239925854314103160489406736
99060594293236420918525997085793619098456109204165164418661475892
01109662597018777150106134376006906212249382614768188594613749419
81773446881694503562852062669737115544391406458301430146238093071
02894114746014041621168186006763973309046545159248106457826024237
26295585692705999572335711556642484343647905815411003310539537633
41950800883057333667657184487306007957156203546941504909814030908
34965188540308705963440466656812927154037805823279990648845960204
63331562527077555356154644447566217362506777244670808476000607805
03811498534406491478259767678703610171309197408223291080531370612
62650405840051780819121599354652788179742394248611555080762986718
96826790066089904275315943211982421764246751417927128802586925712
27099955857542532516878558368313422620050604202219808465512659996
23064148740328947837353070554937134618609926277437895029980245174
01474719468068984349536087237870814923058804265001775440222136692
19497268319149971553957338283899722324260346170316327132892172432
93414823219221781561202067498414863282586486396494894086735311984
87542808513750059732993808185407922249214024344950525276107816857
04707717662079906664246810240363777462148167179131661698526525933
27455038156208677911356439404008565505518270407112444336214476635
90179341953108431111005767617305509479336875319574363889314007557
80075653313610206913250864729950372237487765836958630210102788727
36316538995288936776915812144955490067485142591851239438281782980
49266403870939263057525714093639423600887115586024837895236645603
39309565092104096166270212323904043359754209734891624081548291170
80360665817900770688282037236785560524155682291636091743772117655
59023604955032646389401878907537621901104165756011023874877122701
96250964612099585830958920626319449976949804992786372992220222097
60635584717392117583345925369515540556572166535535975903825177497
033726681165539444448225642477607711558401523711""".replace("\n",""))
You might need to change the scale of your browser window to see this Mercator clearly. It's 150 x 50 characters and is the binary expression of the above prime.
mercator = bin(prime)[2:]
def the_map():
for i in range(50):
pos = i * 150
print(mercator[pos:pos + 150])
# the_map()
Because older generations are concerned with how younger generations are introduced to their culture, the process of hammering out a curriculum tends to involve political considerations.
For example, to what extent was Number Theory purged from some curricula owing to anti-German sentiment and a wish to deprecate all things German? Too much Gauss would never do, and yet he was a Principal. Solution: spend more time on Euclidean Geometry instead. But did it have to be either / or?
Sometimes our Notebook will be more of a springboard, a diving board, into a deep well or chasm (sounds dramatic). You may jump into Number Theory through Cryptography as well, and may wish to study them together. Indeed, what has brought Number Theory back into vogue, if it ever went away, is the ubiquity (omnipresence) of cryptography in our daily lives today.
In practice the security layer, called TLS, provided by a web browser, may use eliptic curve cryptography instead of RSA. The public key system is the used to exchange symmetric keys for a faster encrypted connection.
You'll want to learn about Fermat's Little Theorem, about totatives and totients, and about Diophantine Equations. Even earlier, let's start out with Euclid's Method for the GCD (greatest common divisor), as one of the earliest numeric algorithms out there.
Links:
from IPython.display import YouTubeVideo
YouTubeVideo("X63MWZIN3gM")
I had you two lengths and ask you what size length in whole number size, will divide into both with no remainder.
Start with the two lengths also being whole number. Everything in this picture is an integer, a positive integer, a length.
What integer length divides evenly into these two? Clearly 1 does, as 1 divides into everything. How about 2? How about 3? What's the greatest number that divides them both, without remainder?
Well, what if the smaller length already divides the larger into two. If we call them A and B and divide A into B, not knowing which is longer, then if A is longer, it won't go into B at all. If it does, does it go just once? If so, we're done, and A is the GCD. Otherwise, last possibility, there's some remainder.
That remainder then, is the next shorter length of interest. If there's a GCD > 1, it will divide both of these, as if it does, it will also divide into B, which consists of N As + R for remainder. So make R the new A, and B the new longest length, what used to be A.
N, R = divmod(12, 3) # how many times goes in N, what remainder R
(N, R)
(4, 0)
divmod(3, 12) # 12 doesn't go into 3, 3 is left
(0, 3)
Here's a recursive solution, based on the description above:
def GCD(A, B):
N, R = divmod(B, A) # bigger by smaller?
if N == 0: # if not
return GCD(B, A) # then switch
elif R == 0:
return A # if no remainder, we're done
elif R == 1:
return 1 # down to 1, nowhere to go so 1
elif R > 0:
return GCD(R, B) # keep drilling down
GCD(100, 30)
10
GCD(81, 18)
9
However Guido came up with a more brilliant, non-recursive solution, that automatically switches the arguments if a > b:
18 % 81 # 81 doesn't go into 18, 18 remains
18
print(81 % 18) # 18 goes into 81 4 times, remainder 9
print(divmod(81, 18))
9 (4, 9)
12 % 24 # 24 doesn't go into 12, 12 is the remainder
12
def gcd(a, b):
while b:
b, a = a % b, b
return a
gcd(18, 81)
9
gcd(100, 30)
10
gcd(12, 3)
3
gcd(3, 12)
3
Finally, how about the Lowest Common Multiple or LCM. That turns out to be the product of A and B (all factors combined) divided by the GCD (all factors common to both).
def lcm(a, b):
return int((a * b)/gcd(a, b))
lcm(11, 9)
99
If two positive integers have no factors in common other than 1, they're considered "co-prime" to one another or, more colorfully, they're considered "strangers".
All numbers < N that are coprime to N are called "totatives on N" and the number of such totivatives is considered "the totient of N". Lets do some Python.
def totatives(N):
return [totative for totative in range(1, N) if gcd(N, totative)==1]
totatives(12)
[1, 5, 7, 11]
def 𝜙(N):
# the totient function was called 𝜙 or "phi" by Euler
return len(totatives(N))
𝜙(100)
40
If ${a}$ is an integer and $m$ is a positive integer relatively prime to $a$,Then ${a}^{\phi (m)}\equiv 1 \pmod {m}$.
", ".join(map(str, totatives(1000)))
'1, 3, 7, 9, 11, 13, 17, 19, 21, 23, 27, 29, 31, 33, 37, 39, 41, 43, 47, 49, 51, 53, 57, 59, 61, 63, 67, 69, 71, 73, 77, 79, 81, 83, 87, 89, 91, 93, 97, 99, 101, 103, 107, 109, 111, 113, 117, 119, 121, 123, 127, 129, 131, 133, 137, 139, 141, 143, 147, 149, 151, 153, 157, 159, 161, 163, 167, 169, 171, 173, 177, 179, 181, 183, 187, 189, 191, 193, 197, 199, 201, 203, 207, 209, 211, 213, 217, 219, 221, 223, 227, 229, 231, 233, 237, 239, 241, 243, 247, 249, 251, 253, 257, 259, 261, 263, 267, 269, 271, 273, 277, 279, 281, 283, 287, 289, 291, 293, 297, 299, 301, 303, 307, 309, 311, 313, 317, 319, 321, 323, 327, 329, 331, 333, 337, 339, 341, 343, 347, 349, 351, 353, 357, 359, 361, 363, 367, 369, 371, 373, 377, 379, 381, 383, 387, 389, 391, 393, 397, 399, 401, 403, 407, 409, 411, 413, 417, 419, 421, 423, 427, 429, 431, 433, 437, 439, 441, 443, 447, 449, 451, 453, 457, 459, 461, 463, 467, 469, 471, 473, 477, 479, 481, 483, 487, 489, 491, 493, 497, 499, 501, 503, 507, 509, 511, 513, 517, 519, 521, 523, 527, 529, 531, 533, 537, 539, 541, 543, 547, 549, 551, 553, 557, 559, 561, 563, 567, 569, 571, 573, 577, 579, 581, 583, 587, 589, 591, 593, 597, 599, 601, 603, 607, 609, 611, 613, 617, 619, 621, 623, 627, 629, 631, 633, 637, 639, 641, 643, 647, 649, 651, 653, 657, 659, 661, 663, 667, 669, 671, 673, 677, 679, 681, 683, 687, 689, 691, 693, 697, 699, 701, 703, 707, 709, 711, 713, 717, 719, 721, 723, 727, 729, 731, 733, 737, 739, 741, 743, 747, 749, 751, 753, 757, 759, 761, 763, 767, 769, 771, 773, 777, 779, 781, 783, 787, 789, 791, 793, 797, 799, 801, 803, 807, 809, 811, 813, 817, 819, 821, 823, 827, 829, 831, 833, 837, 839, 841, 843, 847, 849, 851, 853, 857, 859, 861, 863, 867, 869, 871, 873, 877, 879, 881, 883, 887, 889, 891, 893, 897, 899, 901, 903, 907, 909, 911, 913, 917, 919, 921, 923, 927, 929, 931, 933, 937, 939, 941, 943, 947, 949, 951, 953, 957, 959, 961, 963, 967, 969, 971, 973, 977, 979, 981, 983, 987, 989, 991, 993, 997, 999'
m = 1000
pow(7, 𝜙(m), m) # m % 7 ** 𝜙(m)
1
Given public key N:
$$ \gcd(p, q) = 1 $$$$ N = pq $$and a number $e$ with inverse $d$ (secret), modulo $\phi(N)$, such that:
$$ ed \equiv 1 \pmod{\phi(N)}$$Encryption: $$ c \equiv m^e \pmod{N}$$ Decryption: $$ m^\prime \equiv c^d \pmod{N} $$ $$ m^\prime \equiv (m^e)^d \equiv m^{ed} \pmod{N} $$
Is it true that $m^\prime \equiv m$?
Thanks to Euler's Theorem:
$$ a^{\phi(N)} \equiv 1 \pmod{N}, \text{ if } \gcd(a,N) = 1. $$Write $ed = 1 + k~\phi(N)$: $$ m^\prime \equiv m^{1+k\phi(N)} \pmod{N}$$ $$ m^\prime \equiv m\cdot m^{k\phi(N)} \pmod{N}$$ $$ m^\prime \equiv m\cdot \underbrace{m^{k\phi(N)}}_{1} \pmod{N}$$
So $m^\prime \equiv m \pmod{N}$.
We can use that to define a Fraction, or rational number (Rat). Our adventures in Python's object oriented model might, in fact, begin here, even though Python's standard library already includes a Fraction class in fraction. Our tests might compare their behaviors.
from fractions import Fraction
In the Rational Number or alternative fraction class below, we make use of the gcd
and lcm
functions defined above.
If you haven't looked at Python a lot, you may miss some of what's going on: Python's special names define the guts of a fraction in terms of its operations.
When you add two fractions, what happens? A lowest common multiple makes for a denominator. Given the initialization process reduces the fraction to lowest terms, just multiplying the two denominators together would also work.
Complexity arises when we let integers play with Rationals, which we should, as they're a subset of same. $N \subset Z \subset Q \subset R \subset C$ as we say.
from __future__ import annotations
from functools import total_ordering
from typing import Union
@total_ordering
class Rat:
def __init__(self, n, d=None):
if type(d) is None:
d = 1
if d == 0:
raise ZeroDivisionError
_gcd = gcd(n, d)
self.numer = n//_gcd
self.denom = d//_gcd
def _convert(self, other: int) -> Rat:
if type(other) is int:
return Rat(other, 1)
elif type(other) is Rat:
return other
else:
raise TypeError("Not int or Rat")
def __repr__(self):
return "(%s/%s)" % (self.numer, self.denom)
def __eq__(self, other: Union[int, Rat]) -> bool:
other = self._convert(other)
return ((self.numer == other.numer)
and (self.denom == other.denom))
def __gt__(self, other: Union[int, Rat]) -> bool:
other = self._convert(other)
_lcm = lcm(self.denom, other.denom)
return ((self.numer * _lcm//self.denom)
> (other.numer * _lcm//other.denom))
def __add__(self, other: Union[int, Rat]) -> Rat:
# get an lcm before adding
other = self._convert(other)
_lcm = lcm(self.denom, other.denom)
return Rat(self.numer * _lcm//self.denom
+ other.numer * _lcm//other.denom,
_lcm) # denominator
def __sub__(self, other: Union[int, Rat]) -> Rat:
# add the additive inverse of other
other = self._convert(other)
return self + (-other)
def __neg__(self) -> Rat:
# return the additive inverse of self
return Rat(-self.numer, self.denom)
def __mul__(self, other: Union[int, Rat]) -> Rat:
# multiply two rationals
other = self._convert(other)
return Rat(self.numer * other.numer,
self.denom * other.denom)
def __truediv__(self, other: Union[int, Rat]) -> Rat:
# multiply by the multiplicative inverse of other
other = self._convert(other)
return self * other**(-1)
def __pow__(self, n : int) -> Rat:
# raise self to the nth power
if n < 0:
n = abs(n)
return Rat(self.denom ** n, self.numer ** n)
return Rat(self.numer ** n, self.denom ** n)
__rmul__ = __mul__
__radd__ = __add__
__rtruediv__ = __truediv__
Lets approach our development challenge by means of unittests.
from unittest import TestCase
import unittest
class TestRat(TestCase):
def test_1(self):
p = Rat(1, 3)
q = Rat(2, 3)
self.assertEqual(p + q, 1)
def test_2(self):
fp = Fraction(16,32)
fq = Fraction(18,56)
p = Rat(16,32)
q = Rat(18,56)
fproduct = fp * fq
product = p * q
self.assertEqual(fproduct.numerator, product.numer)
self.assertEqual(fproduct.denominator, product.denom)
def test_3(self):
p = Rat(16,32)
q = Rat(18,56)
result = p - q
fp = Fraction(16,32)
fq = Fraction(18,56)
fresult = fp - fq
self.assertEqual(fresult.numerator, result.numer)
self.assertEqual(fresult.denominator, result.denom)
def test_4(self):
p = Rat(2,3)
q = Rat(3,4)
self.assertTrue(q > p)
self.assertTrue(p <= q)
p = Rat(2,3)
q = Rat(3,4)
p + q
(17/12)
unittest.main(argv=[''], verbosity=3, exit=False)
test_1 (__main__.TestRat) ... ok test_2 (__main__.TestRat) ... ok test_3 (__main__.TestRat) ... ok test_4 (__main__.TestRat) ... ok ---------------------------------------------------------------------- Ran 4 tests in 0.032s OK
<unittest.main.TestProgram at 0x108fa6090>
# %load genius_identity.py
#!/usr/bin/env python3
"""
Created on Mon Jun 8 17:48:56 2020
@author: Kirby Urner
Verifying a Ramanujan Identity
https://flic.kr/p/2j9NcAd
Keywords: recursion, number theory, arbitrary precision
School of Tomorrow
https://medium.com/@kirbyurner/calculator-of-tomorrow-using-arbitrary-precision-8f219b0092d9
https://repl.it/@kurner/RamanujanIdentity01
"""
import mpmath
from mpmath import e, pi
print(mpmath.libmp.BACKEND)
mpmath.mp.dps = 100
two = mpmath.mpf('2')
five = mpmath.mpf('5')
root5 = mpmath.mpf('5').sqrt()
phi = (1 + root5)/2
term = "(1 + (e ** (-2*{} * pi))/{})"
def cont_frac(n, c=1):
"""
Recursively build the continued fraction,
as a string, to level of depth n
"""
if n==0:
return "1"
else:
return "(1 + ((e ** (-2*{} * pi)/{})))".format(c, cont_frac(n-1, c+1))
print(eval(cont_frac(10))) # evaluate the continued fraction
print(1/(((phi * root5).sqrt() - phi) * e ** (two/five * pi))) # left side of the equation
print("Ta daa!")
gmpy 1.001867436219318606077227680424157087122424127427497054500130190210949798909562825712938250353099963 1.001867436219318606077227680424157087122424127427497054500130190210949798909562825712938250353099963 Ta daa!
import numpy as np
magic_square = np.zeros((9,), dtype=np.int32)
magic_square.shape
(9,)
magic_square[:] = 2,7,6,9,5,1,4,3,8
magic_square = magic_square.reshape((3,3))
magic_square
array([[2, 7, 6], [9, 5, 1], [4, 3, 8]], dtype=int32)
[magic_square[:,column].sum() for column in range(0,3)]
[15, 15, 15]
[magic_square[row,:].sum() for row in range(0,3)]
[15, 15, 15]
magic_square.diagonal().sum()
15
np.diag(np.fliplr(magic_square)).sum()
15