| symbolic | abstract meaning | concrete meaning in application domain |
| 2 + 3 | 5 | five objects |
| {(1, 2), (1, 3)} | acyclic graph | file system |
| {(1, 2), (2, 3), (3, 1)} | graph with cycle | network |
| {(0,1), (1,2), (2,0)} | permutation | random number sequence |
| formula | meaning | example of one possible Python representation |
| true | always true | True |
| false | always false | False
|
| f1 and f2 | only true if both f1 and f2 are true | True and False |
| f1 or f2 | true if f1 or f2 (or both) are true | True or (False and True) |
| f1 implies f2 |
|
False <= True |
| f1 iff f2 |
|
True == False |
| ¬ f | true if f is false | not (True or (False and True)) |
| ( f ) | true if f is true | (True and (not (False)) |
| predicate example | depends on the definition of the predicate |
isPrime(7) |
isPrime(?) that takes one argument, the meaning of isPrime(7) should be true but the meaning of isPrime(4) should be false.
| meaning of left-hand side (premise) |
meaning of right-hand side (conclusion) |
meaning of entire formula |
comments |
| true | true | true | if the premise is true and the conclusion is true, the claim of implication is true; thus, the whole formula is true |
| true | false | false | if the premise is true but the conclusion is false, the conclusion is not implied by the premise, so the claim of implication is false; thus, the formula is false |
| false | true | true | if the conclusion is true on its own, it doesn't matter that the premise is false, because anything implies an independently true conclusion; thus, the claim of implication is true, and so is the entire formula |
| false | false | true | if we assume that a false premise is true, then "false" itself is "true"; in other words, false implies itself, so the formula is true |
|
| the sun is visible | it is daytime | meaning | interpretation |
| true | true | true | a sunny day |
| true | false | false | |
| false | true | true | a cloudy day |
| false | false | true | nighttime |
|
| term | what it represents | example of one possible Python representation |
| 0 | 0 | 0 |
| 1 | 1 | 1 |
| z1 + z2 | the integer sum of z1 and z2 | 3 + 4
|
| z1 − z2 | the integer difference of z1 and z2 | (1 + 2) - 4
|
| z1 ⋅ z2 | the integer product of z1 and z2 | 3 * 5
|
| z1 mod z2 | the remainder of the integer quotient z1 / z2 z1 - ⌊ z1/z2 ⌋ ⋅ z2 |
17 % 5
|
| z1z2 | product of z2 instances of z1 | 2**3pow(2,3)
|
| formula | what it represents | example of one possible Python representation |
| z1 = z2 | true if z1 and z2 have the same meaning; false otherwise |
1 == 2 |
| z1 < z2 | true if z1 is less than z2; false otherwise |
4 < 3 |
| z1 > z2 | true if z1 is greater than z2; false otherwise |
4 > 3 |
| z1 ≤ z2 | true if z1 is less than or equal to z2; false otherwise |
4 <= 3 |
| z1 ≥ z2 | true if z1 is greater than or equal to z2; false otherwise |
4 >= 3 |
| z1 ≠ z2 | true if z1 is not equal to z2; false otherwise |
4 != 3 |
| predicate definition | example of one possible Python representation |
| P(x) iff x > 0 and x < 2 | def P(x): return x > 0 and x < 2 |
| Q(x) iff x > 3 | Q = lambda x: x > 3 |
| formula | what it represents | example of one possible Python representation |
| P(1) | true | P(1) |
| P(1) or P(2) | true | P(1) or P(2)
|
| Q(1) and Q(2) | false | Q(1) and Q(2)
|
| formula | what it represents |
| x | y |
|
| y is prime |
|
def divides(x, y):
return y % x == 0 # The remainder of y/x is 0.
def prime(y):
for x in range(2,y):
if divides(x,y):
return False
return True
False. This is effectively the implementation of a quantifier, which we introduce further below.
def doesNotDivide(x, y):
return y % x != 0 # The remainder of y/x is nonzero.
def prime(y):
for x in range(2,y):
if not doesNotDivide(x,y):
return False
return True
def checkAll(S, P):
for x in S:
if not P(x):
return False
return True
prime() by supplying appropriate arguments:
>>> checkAll(set(range(2,y)), lambda x: doesNotDivide(x,y))
| term | what it represents | example of one possible Python representation |
| ∅ | a set with no elements in it | set() |
| {1,2,3} | {1,2,3} | {1,2,3} |
| {2,..,5} | {2,3,4,5} | set(range(2,6)) |
| { x | x ∈ {1,2,3,4,5,6}, x > 3 } | {4,5,6} | {x for x in {1,2,3,4,5,6} if x > 3}
|
| |{1,2,3,4}| | 4 | len({1,2,3,4})
|
| term | what it represents | example of one possible Python representation |
| S1 ∪ S2 | {z | z ∈ ℤ, z ∈ S1 or z ∈ S2} | {1,2,3}.union({4,5}){1,2,3} | {4,5} |
| S1 ∩ S2 | {z | z ∈ ℤ, z ∈ S1 and z ∈ S2} | {1,2,3}.intersection({2,3,5}){1,2,3} & {2,3,5} |
| |S| | the number of elements in S | len({1,2,3}) |
| term | what it represents |
| ℕ | {0, 1, 2, ...} |
| ℤ | {..., -2, -1, 0, 1, 2, ...} |
def forall(S, P):
for x in S:
if not P(x):
return False
return True
def exists(S, P):
for x in S:
if P(x):
return True
return False
subset() operation on sets.
def forall(X, P):
S = {x for x in X if P(x)}
return len(S) == len(X)
def exists(X, P):
S = {x for x in X if P(x)}
return len(S) > 0
def subset(X,Y):
return forall(X, lambda x: x in Y)
| formula | what it represents | example of one possible Python representation |
| 1 ∈ {1,2,3} | true | 1 in {1,2,3} |
| 4 ∈ {1,2,3} | false | 4 in {1,2,3} |
| ∀ x ∈ {1,2,3}, x > 0 and x < 4 | true | forall({1,2,3}, lambda x: x > 0 and x < 4) |
| ∃ x ∈ {1,2,3}, x < 1 and x > 3 | false | exists({1,2,3}, lambda x: x < 1 or x > 3) |
| ∀ x ∈ ∅, f | true | |
| ∃ x ∈ ∅, f | false |
| iff |
| |||
| iff |
|
# We provide two equivalent implementations.
def all(X, P):
return forall(X, P)
def all(X, P):
S = {x for x in X if P(x)}
return len(S) == len(X)
# We provide two equivalent implementations.
def none(X, P):
return forall(X, lambda x: not P(x))
def none(X, P):
S = {x for x in X if P(x)}
return len(S) == 0
def atMostOne(X, P):
S = {x for x in X if P(x)}
return len(S) <= 1
# We provide two equivalent implementations.
def atLeastOne(X, P):
return exists(X, P)
def atLeastOne(X, P):
S = {x for x in X if P(x)}
return len(S) >= 1
def prime(p):
return p > 1 and forall(set(range(2, p)), lambda n: p % n != 0)
| formula | what it represents | example of one possible Python representation |
| 3 ∈ {1,2,3} | true | 3 in {1,2,3} |
| {1,2} ⊂ {1,2,3} | true | subset({1,2}, {1,2,3}) |
| {4,5} ⊂ {1,2,3} | false | subset({4,5}, {1,2,3}) |
| formula | what it represents |
| z ∈ S | true if z is an element of S; false otherwise |
| S1 ⊂ S2 | ∀ z ∈ S1, z ∈ S2 |
| S1 = S2 | S1 ⊂ S2 and S2 ⊂ S1 |
| term | what it represents | example of one possible Python representation |
| {1,2} × {5,6,7} | {(1,5),(1,6),(1,7),(2,5),(2,6),(2,7)} | { (x,y) for x in {1,2} for y in {4,5,6,7} } |
| predicate | definition | visual example |
| X × Y is the set product of X and Y | X × Y = { (x,y) | x ∈ X, y ∈ Y } | !relation({'a','b','c'}, {'x','y','z'}, {('a','x'),('a','y'),('a','z'),('b','x'),('b','y'),('b','z'),('c','x'),('c','y'),('c','z')}) |
| R is a relation between X and Y | R ⊂ X × Y | !relation({'a','b','c'}, {'x','y','z'}, {('a','x'),('b','x'),('b','z'),('c','z')}) |
| R is a function from X to Y R is a (many-to-one) map from X to Y |
R is a relation between X and Y and ∀ x ∈ X, there is at most one y ∈ Y s.t. (x,y) ∈ R |
!relation({'a','b','c'}, {'x','y','z'}, {('a','x'),('b','x'),('c','z')}) |
| R is an injection from X to Y |
R is a function from X to Y and ∀ y ∈ Y, there is at most one x ∈ X s.t. (x,y) ∈ R |
!relation({'a','b','c'}, {'x','y','z'}, {('a','x'),('b','y')}) |
| R is a surjection from X to Y |
R is a function from X to Y and ∀ y ∈ Y, there is at least one x ∈ X s.t. (x,y) ∈ R |
!relation({'a','b','c','d'}, {'x','y','z'}, {('a','x'),('c','y'),('d','z')}) |
| R is a bijection between X and Y | R is an injection from X and Y and R is a surjection from X and Y |
!relation({'a','b','c'}, {'x','y','z'}, {('a','y'),('b','z'),('c','x')}) |
| R is a permutation on X |
R ⊂ X × X and R is a bijection between X and X |
!relation({'a','b','c'}, {('a','b'),('b','c'),('c','a')}) |
| R is a reflexive relation on X | R ⊂ X × X and ∀ x ∈ X, (x,x) ∈ R |
!relation({'a','b','c'}, {('a','a'),('b','b'),('c','c')}) |
| R is a symmetric relation on X | R ⊂ X × X and ∀ x ∈ X, ∀ y ∈ X, (x,y) ∈ R implies (y,x) ∈ R |
!relation({'a','b','c'}, {('a','b'),('b','a'),('c','c')}) |
| R is a transitive relation on X | R ⊂ X × X and ∀ x ∈ X, ∀ y ∈ X, ∀ z ∈ X, ((x,y) ∈ R and (y,z) ∈ R) implies (x,z) ∈ R |
!relation({'a','b','c'}, {('a','b'),('b','c'),('a','c')}) |
| R is an equivalence relation on X R is a congruence relation on X |
R ⊂ X × X and R is a reflexive relation on X and R is a symmetric relation on X and R is a transitive relation on X |
!relation({'a','b','c'}, {('a','a'),('b','b'),('a','b'),('b','a'),('c','c')}) |
evens = { 2 * x for x in set(range(0,51)) }
evens = { x for x in set(range(0,101)) if x % 2 == 0 }
X and Y.
def product(X, Y):
return { (x,y) for x in X for y in Y }
def leq(S):
return { (x, y) for x in S for y in S if x <= y }
R is a relation over a set X.
# Using our definition of subset().
def relation(R, X):
return subset(R, product(X, X))
# Using the built-in set implementation.
def relation(R, X):
return R.issubset(product(X, X))
|
R and a set X and determines whether that relation is asymmetric? Recall that we can represent the implication logical operator using the Python operator <=.
def isAsymmetric(X, R):
return relation(R,X) and forall(X, lambda a: forall(X, lambda b: ((a,b) in R) <= (not ((b,a) in R))))
| = |
|
def quotient(X,R):
return {frozenset({y for y in X if (x,y) in R}) for x in X}
>>> quotient({1,2,3,4}, {(1,1),(2,2),(3,3),(2,3),(3,2),(4,4)})
{frozenset({4}), frozenset({2, 3}), frozenset({1})}
def quotientMap(X,R):
return {(x, frozenset({y for y in X if (x,y) in R})) for x in X}
| = |
|
{'Alice', 'Bob', 'Carl', 'Dan', and 'Eve'}:
R = {\
('Alice', 'Alice'), ('Bob', 'Bob'), ('Carl', 'Carl'), ('Dan', 'Dan'), ('Eve', 'Eve'),\
('Alice', 'Carl'), ('Carl', 'Alice'), ('Dan', 'Eve'), ('Eve', 'Dan')\
}
families = quotient({'Alice', 'Bob', 'Carl', 'Dan', 'Eve'}, R)
| = |
|
| = |
|
| = |
|
| ∈ |
| |||
| ∈ |
|
| = |
| |||
| = |
| |||
| = |
|
| term | what it represents |
| z z mod m z + mℤ |
{z + (a ⋅ m) | a ∈ ℤ} |
| c1 + c2 | {(x + y) | x ∈ c1, y ∈ c2} |
| c1 − c2 | {(x − y) | x ∈ c1, y ∈ c2} |
| c1 ⋅ c2 | {(x ⋅ y) | x ∈ c1, y ∈ c2} |
| cz | c ⋅ ... ⋅ c |
| c! | c ⋅ (c-1) ⋅ (c-2) ⋅ ... ⋅ 1 |
| formula | what it represents |
| c1 ≡ c2 | true only if c1 ⊂ c2 and c2 ⊂ c1, i.e., set equality applied to the congruence classes c1 and c2; false otherwise |
| = |
| |||
| = |
| |||
| = |
| |||
| = |
| |||
| = |
| |||
| = |
|
|
| ≡ |
| |||
| = |
| ||||
| = |
| ||||
| = |
| ||||
| = |
| ||||
| = |
| ||||
| = |
| ||||
| = |
| ||||
| ≡ |
| ||||
| ≡ |
|
| property | definition |
| ℤ/mℤ is closed under + | ∀ x,y ∈ ℤ/mℤ, x + y ∈ ℤ/mℤ |
| + is commutative on ℤ/mℤ | ∀ x,y ∈ ℤ/mℤ, x + y ≡ y + x |
| + is associative on ℤ/mℤ | ∀ x,y,z ∈ ℤ/mℤ, (x + y) + z ≡ x + (y + z) |
| + has a (left and right) identity 0 in ℤ/mℤ | ∀ x ∈ ℤ/mℤ, 0 + x ≡ x and x + 0 ≡ x |
| ℤ/mℤ has inverses with respect to + | ∀ x ∈ ℤ/mℤ, (m - x) + x ≡ 0 |
| ℤ/mℤ is closed under ⋅ | ∀ x,y ∈ ℤ/mℤ, x ⋅ y ∈ ℤ/mℤ |
| ⋅ is commutative on ℤ/mℤ | ∀ x,y ∈ ℤ/mℤ, x ⋅ y ≡ y ⋅ x |
| + is associative on ℤ/mℤ | ∀ x,y,z ∈ ℤ/mℤ, (x ⋅ y) ⋅ z ≡ x ⋅ (y ⋅ z) |
| + has a (left and right) identity 1 in ℤ/mℤ | ∀ x ∈ ℤ/mℤ, 1 ⋅ x ≡ x and x ⋅ 1 ≡ x |
| ⋅ distributes across + in ℤ/mℤ | ∀ x,y,z ∈ ℤ/mℤ, x ⋅ (y + z) ≡ (x ⋅ y) + (x ⋅ z) |
| ≡ |
| |||
| ≡ |
|
| = |
| |||
| = |
| |||
| = |
| |||
| ≡ |
|
| = |
| |||
| = |
| |||
| = |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
| | |
| |||
| = |
| |||
| ≡ |
| |||
| ≡ |
|
| = |
| |||
| = |
| |||
| = |
| |||
| ∈ |
| |||
| | |
|
| | |
| |||
| ∈ |
| |||
| = |
| |||
| = |
| |||
| = |
| |||
| = |
|
|
| ≡ |
| |||
| | |
| |||
| | |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
| ∤ |
| |||
| ≢ |
| |||
| ∤ |
| |||
| ≢ |
|
| ≡ |
| |||
| ≡ |
| |||
| = |
| |||
| = |
| |||
| | |
|
| | |
| |||
| = |
| |||
| ≡ |
| |||
| ≡ |
|
| ≡ |
|
| ≡ |
|
| ≡ |
|
| ≡ |
|
| ≡ |
|
| ≡ |
|
| ≡ |
|
| ≡ |
|
| ≡ |
|
| ≡ |
|
| ≡ |
|
| ≡ |
|
| ≡ |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
| ≡ |
|
| ≡ |
|
| ≡ |
|
| = |
|
| = |
| |||
| = |
|
| ≠ |
| |||
| = |
|
| = |
| |||
| = |
| |||
| = |
| |||
| | |
|
| = |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
| = |
| |||
| = |
| |||
| = |
|
| = |
| |||
| = |
| |||
| = |
|
| = |
|
| = |
|
| = |
|
| = |
| |||
| = |
|
| = |
| |||
| = |
| |||
| = |
| |||
| = |
| ||||
| = |
| ||||
| = |
|
def gcd(x, y):
return max({z for z in range(0, min(x,y)) if x % z == 0 and y % z == 0})
|
| ≢ |
| |||
| ≢ |
|
| ≡ |
|
| ≡ |
|
| = |
| |||
| = |
| |||
| = |
| |||
| = |
| |||
| = |
|
| < |
|
| ≤ |
| |||
| ≤ |
|
| > |
|
| = |
| |||
| = |
| |||
|
|
| = |
| |||
| = |
| ||||
| = |
| ||||
| ≈ |
|
| algorithm input | algorithm output | meaning | description |
| actually a composite number (this is not known at time of input) |
composite | the input is composite | true negative |
| actually a prime number (this is not known at time of input) |
prime | the input is prime | true positive |
| algorithm input | algorithm output | meaning | description |
| actually a composite number (this is not known at time of input) |
composite | the input is definitely composite |
true negative |
| actually a composite number (this is not known at time of input) |
probably prime | the input is either composite or prime |
false positive |
| actually a prime number (this is not known at time of input) |
probably prime | the input is either composite or prime |
true positive |
| actually a prime number (this is not known at time of input) |
composite | impossible | false negative (we will not consider algorithms that return such outputs) |
| input number |
perfect algorithm |
perfect probable prime algorithm |
less accurate probable prime algorithm |
very inaccurate probable prime algorithm |
| 2 | prime | probably prime |
probably prime |
probably prime |
| 3 | prime | probably prime |
probably prime |
probably prime |
| 4 | composite | composite | probably prime |
probably prime |
| 5 | prime | probably prime |
probably prime |
probably prime |
| 6 | composite | composite | composite | probably prime |
| 7 | prime | probably prime |
probably prime |
probably prime |
| 8 | composite | composite | probably prime |
probably prime |
| 9 | composite | composite | composite | probably prime |
| 10 | composite | composite | probably prime |
probably prime |
| ≡ |
|
| = |
| |||
| = |
|
| = |
| |||
| = |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
| ≢ |
| |||
| ≢ |
|
| for the chosen a we have... |
what it means | probability of this occurring if m is a non-Carmichael composite |
| a | m | a is a non-trivial factor of m, so m is composite |
(# integers in {2,...,m-1} that are factors with m) / (m-2) |
| gcd(a,m) ≠ 1 | m and a have a non-trivial factor, so m is composite |
(# integers in {2,...,m-1} that share factors with m) / (m-2) |
| am-1 mod m ≠ 1 | a is a Fermat witness that m is composite |
at least 1/2 |
| m = 15 and a = ... | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| a | m | PP | C | PP | C | PP | PP | PP | PP | PP | PP | PP | PP | PP |
| gcd(a,m) ≠ 1 | PP | C | PP | C | C | PP | PP | C | C | PP | C | PP | PP |
| am-1 mod m = ... | 4 | 9 | 1 | 10 | 6 | 4 | 4 | 6 | 10 | 1 | 9 | 4 | 1 |
| Euclid's lemma generalization |
⇐ | multiples of coprime a in ℤ/mℤ are a permutation |
gcd(m,m+1) = 1 | |||
| ⇑ | ⇑ | |||||
| Fermat's little theorem |
random number generator |
⇒ | coprime generator |
|||
| ⇑ | ⇑ | |||||
| greatest common divisor algorithm |
⇐ | Fermat primality test |
⇐ | probable prime detector |
||
| ⇑ | ||||||
| probable prime generator |
| ≡ |
| |||
| ≡ |
|
| ≡ |
|
| ≡ |
|
| ≡ |
|
| ≡ |
|
| ≡ |
| |||
| ≡ |
| ||||
| ≡ |
|
| ≡ |
| |||
| ≡ |
| ||||
| ≡ |
| ||||
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| = |
| |||
| ⋮ | |||||
| = |
|
| ≡ |
| |||
| ⋮ | |||||
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| = |
| |||
| = |
|
| = |
|
| ≡ |
|
| efficient modular arithmetic |
||||
| ⇓ | ||||
| Chinese remainder theorem |
⇐ | CRT solver | ⇐ | range ambiguity resolution |
| ⇑ | ||||
| Shamir secret sharing protocol |
| ≡ |
|
| ≡ |
|
| := |
| |||
| := |
| |||
| := |
| |||
| := |
| |||
| := |
| |||
| ⋮ |
| := |
| |||
| := |
| |||
| := |
| |||
| := |
| |||
| := |
| |||
| ⋮ |
| > |
| |||
| ≥ |
| ||||
| = |
| |||
| ⋮ | |||||
| = |
|
| ≡ |
| |||
| ⋮ | |||||
| ≡ |
|
| = |
|
| greatest common divisor algorithm |
Fermat's little theorem |
Euler's theorem |
||||
| ⇑ | ⇑ | ⇑ | ||||
| Bézout's identity |
⇐ | extended Euclidean algorithm |
⇐ | algorithm for finding multiplicative inverses |
⇒ | Euler's totient function φ |
| ⇑ | ||||||
| Chinese remainder theorem |
⇐ | CRT solver for two equations |
⇑ | |||
| induction | ⇐ | CRT solver for n equations |
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| ||||
| ≡ |
| ||||
| ≡ |
| ||||
| ≡ |
|
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
|
| ≡ |
| |||
| ≡ |
| ||||
| ≡ |
| ||||
| ≡ |
| ||||
| ≡ |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
| ≡ |
|
| ||||||
| ≡ |
|
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| = |
| |||
| ≡ |
|
| ≡ |
|
| ||||||
| ≡ |
|
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
| ||||
| ≡ |
| ||||
| ≡ |
| |||
| ≡ |
| ||||
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
|
| = |
|
| = |
|
| = |
|
| = |
| |||
| = |
| |||
| = |
|
| = |
| |||
| = |
| |||
| = |
|
| = |
|
| = |
| |||
| = |
|
| = |
| |||
| = |
| |||
| = |
| |||
| = |
| |||
| = |
| |||
| = |
|
| < |
|
| < |
| < |
| |||||
| < |
| < |
|
| = |
|
| = |
| |||
| = |
| |||
| ≡ |
| |||
| = |
|
| = |
| |||
| = |
| ||||
| = |
|
| = |
|
| = |
| |||
| ≡ |
| |||
| ≡ |
|
| = |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| = |
|
| ≡ |
| |||
| ≡ |
| ||||
| ≡ |
|
| ≡ |
| |||
| ≡ |
| ||||
| ≡ |
|
| ≡ |
| |||
| ≡ |
| ||||
| ≡ |
|
| ≡ |
| |||
| ⋮ | |||||
| ≡ |
|
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
|
|
| > |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
|
| ≡ |
| ||||||
|
| ≡ |
| ||||||
|
| ≡ |
|
| = |
| |||
| = |
| |||
| = |
| ||||
| = |
|
| = |
| |||
| = |
| ||||
| = |
|
| = |
| |||
| = |
| ||||
| = |
| ||||
| = |
| ||||
| = |
| ||||
| = |
| ||||
| = |
| ||||
| = |
| ||||
| = |
| ||||
| = |
| ||||
| = |
|
| = |
|
| = |
| |||
| = |
|
| = |
|
| = |
| |||
| = |
| |||
| = |
| |||
| = |
| ||||
| = |
| ||||
| = |
| ||||
|
|
| = |
|
| = |
|
| ≡ |
| |||
| = |
| ||||
| = |
| |||
| = |
| ||||
| = |
|
| = |
|
| = |
|
| ≡ |
| |||
| ≡ |
| ||||
| ≡ |
| ||||
| ≡ |
|
| ≡ |
| |||
| = |
| ||||
| = |
| ||||
| = |
|
| ≡ |
| |||
| = |
| ||||
| = |
| ||||
| = |
| ||||
| = |
| ||||
| = |
|
| = |
| |||
| = |
|
| = |
| |||
| = |
| ||||
| = |
| ||||
| = |
| ||||
| = |
|
| ≡ |
| |||
| ≡ |
| ||||
| ≡ |
| ||||
| ≡ |
| ||||
| ≡ |
| ||||
| ≡ |
| ||||
| ≡ |
| ||||
| ≡ |
|
| = |
|
| = |
| |||
| = |
| ||||
| = |
| ||||
| = |
| ||||
| = |
| ||||
| = |
| ||||
| = |
| ||||
| = |
| ||||
| ≡ |
| |||
| ≡ |
| ||||
| ≡ |
|
|
|
|
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
|
| ≡ |
| |||
| ≡ |
|
|
|
|
|
|
|
| = |
| |||
| = |
| |||
| = |
|
| = |
| |||
| = |
|
| = |
| |||
| = |
| ||||
| = |
| ||||
| = |
| ||||
| = |
| ||||
| = |
|
| < |
| ≤ |
|
| = |
| |||
| = |
| ||||
| = |
| ||||
| < |
| ||||
| < |
|
| ≡ |
| |||
| ≡ |
|
| solver for problem B |
⇒ ⇒ ⇒ |
conversion from output(s) from B to output from A |
| ⇑⇑⇑ | ⇓ | |
| conversion from input for A to input(s) for B |
⇐ | solver for problem A |
| problem B | ⇐ | problem A |
| finding multiplicative inverses |
⇐ | solving two-equation systems using CRT |
| problem B premise: can be solved in polynomial time B ∈ P |
⇐ | problem A conclusion: can be solved in polynomial time A ∈ P |
| problem B conclusion: cannot be solved in polynomial time B ∉ P |
⇐ | problem A premise: cannot be solved in polynomial time A ∉ P |
| = |
| |||
| = |
| |||
| = |
| |||
| = |
| |||
| = |
|
| = |
| |||
| = |
|
| = |
| |||
| = |
|
| = |
| |||
| = |
| |||
| = |
| ||||
| = |
| |||
| = |
| |||
| = |
| |||
| = |
| |||
| = |
| |||
| = |
| |||
| ∈ |
| |||
| = |
|
| computing φ(n) conclusion: cannot be solved in polynomial time computing φ(n) ∉ P |
⇐ | factoring n conjecture: cannot be solved in polynomial time factoring ∉ P |
| = |
|
| ≡ |
|
| = |
|
| ||||||
| ∈ |
|
| ||||||
| = |
|
|
| = |
| = |
|
| ∈ |
| |||||||
| ∈ |
| |||||||
| = |
|
|
| = |
| = |
|
| |
| |
| |
| |
| |
| |
|
| |
| |
| |
| |
|
| = |
|
| = |
| |||
| = |
| ||||
| = |
| ||||
| = |
| |||
| = |
| |||
| = |
| ||||
| |
| |
|
| ≡ |
|
| ≡ |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
| ≡ |
|
| ≡ |
|
|
| = |
| |||
| = |
| |||
| = |
| ||||
| = |
| ||||
| = |
| ||||
| = |
| |||
| = |
| ||||
| = |
| |||
| = |
| ||||
| = |
| ||||
| = |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| ||||
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| ||||
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
|
|
| ≡ |
|
| ≡ |
|
| ≡ |
|
| = |
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| | |
|
| | |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
| ≡ |
|
| ≡ |
|
| = |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
| ≡ |
|
| ≡ |
| |||
| ≡ |
| ||||
| ≡ |
| ||||
| ≡ |
|
| ≡ |
| |||
| ≡ |
| ||||
| ≡ |
| ||||
| ≡ |
| ||||
| ≡ |
| ||||
| ≡ |
|
| ≡ |
| |||
| ≡ |
| ||||
| ≡ |
|
| ≡ |
|
| = |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
| ≡ |
|
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| = |
|
| = |
| |||
| = |
| |||
| = |
| ||||
| | |
|
| congruent squares (square roots of congruence classes) |
||||
| ⇑⇓ | ⇑⇓ | |||
| computing φ(n) for n = p ⋅ q |
⇐ ⇒ |
factoring n = p ⋅ q |
||
| ⇑ | ⇑ | |||
| RSA problem (eth roots of congruence classes) |
||||
| discrete logarithm (logarithms of congruence classes) |
||||
| forging private identifier for n conclusion: cannot be solved in polynomial time forging ∉ P |
⇐ | factoring n conjecture: cannot be solved in polynomial time factoring ∉ P |
| alternative efficient algorithm |
⇐ | forging private identifier for n |
⇒ | factoring n |
| ≡ |
| |||
| = |
| ||||
| = |
| |||
| = |
| ||||
| = |
| ||||
| = |
| ||||
| = |
| ||||
| = |
|
| ≡ |
| |||
| ≡ |
|
| breaking Rabin encryption |
⇐ | congruent squares (square roots of congruence classes) |
||||
| ⇑⇓ | ⇑⇓ | |||||
| finding RSA secret key |
⇐ | computing φ(n) for n = p ⋅ q |
⇐ ⇒ |
factoring n = p ⋅ q |
||
| ⇑ | ⇑ | |||||
| decrypting individual RSA messages |
⇐ | RSA problem (eth roots of congruence classes) |
||||
| breaking Diffie-Hellman |
⇐ | discrete logarithm (logarithms of congruence classes) |
||||
| = |
|
| ≡ |
| |||
| ≡ |
| ||||
| ≡ |
| ||||
| ≡ |
|
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
| ≡ |
|
| ≡ |
|
|
|
| = |
|
|
|
| = |
|
| = |
| |||
| = |
| |||
| = |
| |||
| S2 | ℤ/2ℤ |
| [0,1] | 0 |
| [1,0] | 1 |
| S2 | ℤ/2ℤ |
| [0,1] o [0,1] = [0,1] | 0 + 0 = 0 |
| [0,1] o [1,0] = [1,0] | 0 + 1 = 1 |
| [1,0] o [0,1] = [1,0] | 1 + 0 = 1 |
| [1,0] o [1,0] = [0,1] | 1 + 1 = 0 |
| + o |
0 [0,1] |
1 [1,0] |
| 0 [0,1] |
0 [0,1] |
1 [1,0] |
| 1 [1,0] |
1 [1,0] |
0 [0,1] |
| C3 | ℤ/3ℤ |
| [0,1,2] o [0,1,2] = [0,1,2] | 0 + 0 = 0 |
| [0,1,2] o [1,2,0] = [1,2,0] | 0 + 1 = 1 |
| [0,1,2] o [2,0,1] = [2,0,1] | 0 + 2 = 2 |
| [1,2,0] o [0,1,2] = [1,2,0] | 1 + 0 = 1 |
| [1,2,0] o [1,2,0] = [2,0,1] | 1 + 1 = 2 |
| [1,2,0] o [2,0,1] = [0,1,2] | 1 + 2 = 0 |
| [2,0,1] o [0,1,2] = [2,0,1] | 2 + 0 = 2 |
| [2,0,1] o [1,2,0] = [0,1,2] | 2 + 1 = 0 |
| [2,0,1] o [2,0,1] = [1,2,0] | 2 + 2 = 1 |
| = |
| |||
| = |
|
| (ℤ/2ℤ, +) | ((ℤ/3ℤ)*, ⋅) |
| 0 + 0 = 0 | 1 ⋅ 1 = 1 |
| 0 + 1 = 1 | 1 ⋅ 2 = 2 |
| 1 + 0 = 1 | 2 ⋅ 1 = 2 |
| 1 + 1 = 0 | 2 ⋅ 2 = 1 |
| (ℤ/2ℤ, +) | ((ℤ/6ℤ)*, ⋅) |
| 0 + 0 = 0 | 1 ⋅ 1 = 1 |
| 0 + 1 = 1 | 1 ⋅ 5 = 5 |
| 1 + 0 = 1 | 5 ⋅ 1 = 5 |
| 1 + 1 = 0 | 5 ⋅ 5 = 1 |
| ≡ |
|
| ≡ |
|
| ℤ/3ℤ | ℤ/3ℤ |
| 0 | 0 |
| 1 | 2 |
| 2 | 1 |
| ℤ/3ℤ | ℤ/3ℤ |
| 0 + 0 = 0 | 0 + 0 = 0 |
| 0 + 1 = 1 | 0 + 2 = 2 |
| 0 + 2 = 2 | 0 + 1 = 1 |
| 1 + 0 = 1 | 2 + 0 = 2 |
| 1 + 1 = 2 | 2 + 2 = 1 |
| 1 + 2 = 0 | 2 + 1 = 0 |
| 2 + 0 = 2 | 1 + 0 = 1 |
| 2 + 1 = 0 | 1 + 2 = 0 |
| 2 + 2 = 1 | 1 + 1 = 2 |
| = |
| |||
| = |
| |||
| = |
|
| = |
|
| ≡ |
|
| = |
|
| = |
|
| ≡ |
| ≡ |
|
| = |
|
| = |
|
| ≡ |
| ≡ |
|
| ≡ |
|
| ≡ |
|
| = |
|
| = |
|
| = |
|
| = |
|
| = |
| |||
| = |
| |||
| ⊂ |
| |||
| ⊂ |
| |||
| = |
| |||
| ≅ |
|
| ≅ |
|
| ≅ |
| ≅ |
|
| = |
| = |
| = |
|
| = |
| |||
| = |
|
| ≡ |
|
| = |
| |||
| = |
| |||
| = |
| |||
| ≡ |
|
| = |
|
| = |
|
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
|
| ≡ |
|
| ≡ |
|
| ≡ |
|
| ≡ |
|
| = |
| |||
| = |
|
| = |
|
|
|
|
| ≡ |
|
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| = |
|
| ℤ/2ℤ × ℤ/3ℤ | ℤ/6ℤ |
| (0,0) | 0 |
| (0,1) | 4 |
| (0,2) | 2 |
| (1,0) | 3 |
| (1,1) | 1 |
| (1,2) | 5 |
|
|
|
| ≡ |
| |||
| ≡ |
|
| = |
| |||
| = |
|
| ≡ |
| |||
| ≡ |
|
| = |
| |||
| = |
|
| = |
| |||
| = |
|
| ≡ |
| |||
|
|
| ≡ |
| |||
| ≡ |
|
| = |
| |||
| = |
|
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
| ||||||||||
| ≡ |
|
| ≡ |
| ||||||||||
| ≡ |
| |||||||||||
| ≡ |
|
| ≡ |
| ||||||||||
| ≡ |
| ||||||||||
| ≡ |
|
| ≡ |
|
| greatest common divisor algorithm |
Fermat's little theorem |
Euler's theorem |
||||
| ⇑ | ⇑ | ⇑ | ||||
| Bézout's identity |
⇐ | extended Euclidean algorithm |
⇐ | algorithm for finding multiplicative inverses |
⇒ | Euler's totient function φ |
| ⇑ | ||||||
| Chinese remainder theorem |
⇐ | CRT solver for two equations |
⇑ | |||
| linear congruence theorem |
⇐ | general CRT solver for two equations |
⇑ | |||
| induction | ⇐ | general CRT solver for n equations |
| formula for 3+4ℤ primes |
⇐ | square roots modulo p |
⇑ | |||
| Hensel's lemma | ⇐ | square roots modulo pk |
⇑ | |||
| CRT solver for two equations |
⇐ | square roots modulo n ⋅ m |
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
| ≡ |
|
| = |
| = |
| = |
|
| ≡ |
|
| = |
| |||
| = |
|
|
| = |
|
| = |
| |||
| = |
|
| = |
| |||||||||||
| = |
| = |
| = |
| |||||||
| = |
| = |
| = |
| |||||||
| ⋮ | ⋮ | ⋮ |
| = |
|
|
|
| ≡ |
| |||
| ≡ |
|
| |
|
| = |
|
| ≡ |
| |||
| ≡ |
|
csa2/csa3..py. For example, suppose the following is contained within a file called example.py:
# This is a comment in "example.py".
# Below is a Python statement.
print("Hello, world.")
python3, python3.2, python3.3, etc. depending on the Python installation you're using). Note that in the examples below %> represents a terminal prompt, which may look different on your system.
%> python example.py
Hello, world.
%> python
Python 3.2 ...
Type "help", "copyright", "credits" or "license" for more information.
>>> exec(open("example.py").read()) # Load "example.py" module.
Hello, world.
>>> x = "Hello." # Execute an assignment statement.
>>> print(x) # Execute a "print" statement.
Hello.
>>> x # Evaluate a string expression.
'Hello.'
>>> 1 + 2 # Evaluate a numerical expression.
3
True and False.and, or, and not.
>>> True # A boolean constant.
True
>>> False # A boolean constant.
False
>>> True and False or True and (not False) # A boolean expression.
True
+, *, -, and /. The infix operator // represents integer division, and the infix operators ** represents exponentiation. Negative integers are prefixed with the negation operator -.==, !=, <, >, <=, >= are available.int() function can convert a string that looks like an integer into an integer.
>>> 123 # An integer constant.
True
>>> 1 * (2 + 3) // 4 - 5 # An integer expression.
-4
>>> 4 * 5 >= 19 # A boolean expression involving integers.
True
>>> int("123") # A string being converted into an integer
123
' or " characters. Strings can be treated as lists of single-character strings. Another way to look at this is that there is no distinction between a character and a string: all characters are just strings of length 1. Multiline strings can be delimited using """ or ''' (i.e., three quotation mark characters at the beginning and end of the string literal).'' or "".+.len() returns the length of a string.s[i]). These characters are also strings themselves.
>>> 'Example.' # A string.
'Example.'
>>> "Example." # Alternate notation for a string.
'Example.'
>>> len("ABCD") # String length.
4
>>> "ABCD" + "EFG" # String concatenation.
'ABCDEFG'
>>> "ABCD"[2] # Third character in the string.
'C'
[ and ], with the individual list entries separated by commas. Lists cannot be members of sets.[].+.len() returns the length of a list.a[i]).in relational operator.
>>> [1,2,"A","B"] # A list.
[1, 2, 'A', 'B']
>>> [1, 2] + ['A','B'] # Concatenating lists.
[1, 2, 'A', 'B']
>>> len([1,2,"A","B"] ) # List length.
4
>>> [1,2,"A","B"][0] # First entry in the list.
1
>>> 1 in [1, 2] # List containment check.
True
( and ), with entries separated by commas. The main distinction between lists and tuples is that tuples are hashable (i.e., they can be members of sets).().x is denoted using (x, ).+.list() function.tuple() function.len() returns the length of a tuple.t[i]).in relational operator.
>>> (1,2,"A","B") # A tuple.
(1, 2, 'A', 'B')
>>> (1,) # Another tuple.
(1,)
>>> (1, 2) + ('A','B') # Concatenating tuples.
(1, 2, 'A', 'B')
>>> list((1, 2, 'A','B')) # A tuple being converted into a list.
[1, 2, 'A', 'B']
>>> tuple([1, 2, 'A','B']) # A list being converted into a tuple.
(1, 2, 'A', 'B')
>>> len((1,2,"A","B")) # Tuple length.
4
>>> (1,2,"A","B")[0] # First entry in the tuple.
1
>>> 1 in (1, 2) # Tuple containment check.
True
set()..union() and .intersect correspond to the standard set operations.set() function.list() or list() function, respectively.len() returns the size of a set.in relational operator.
>>> {1,2,"A","B"} # A set.
{1, 2, 'A', 'B'}
>>> ({1,2}.union({3,4})).intersection({4,5}) # Set operations.
{4}
>>> set([1, 2]).union(set(('A','B'))) # Converting a list and a tuple to sets.
{'A', 1, 2, 'B'}
>>> len({1,2,"A","B"}) # Set size.
4
>>> 1 in {1,2,"A","B"} # Tuple containment check.
True
frozenset() function.
>>> frozenset({1,2,3}) # A frozen set.
frozenset({1, 2, 3})
>>> {frozenset({1,2}), frozenset({3,4})} # Set of frozen sets.
{frozenset({3, 4}), frozenset({1, 2})}
set data structure must be hashable so that it is easy to deduplicate elements in an unordered set (e.g., {1,1,2,2} == {1,2} should be True, and this would take O(n2) steps to compute in the worst case because sets are not ordered). However, values of type set are not hashable because they can change (e.g., it is possible to insert an element into a set and also to remove an element from a set), which means their hashes could change, as well. Values of type frozenset cannot be changed; once their hash value is computed at the time of creation, it never changes. Thus, it is okay to include values of type frozenset inside instances of set without worrying about incurring a quadratic running time when deduplicating (or, e.g., computing a set union).{}.list(d.keys()).list(d.values()).len() returns the number of entries in the dictionary.d[key]).
>>> {"A":1, "B":2} # A dictionary.
{'A': 1, 'B': 2}
>>> list({"A":1, "B":2}.keys()) # Dictionary keys.
['A', 'B']
>>> list({"A":1, "B":2}.values()) # Dictionary values.
[1, 2]
>>> len({"A":1, "B":2}) # Dictionary size.
2
>>> {"A":1, "B":2}["A"] # Obtain a dictionary value using a key.
1
example() is defined as follows:
def example(x, y, z):
print("Invoked.")
return x + y + z
>>> example(1,2,3)
Invoked.
6
*-operator, the scatter operator, or the splat operator) involves providing a list to the function, preceded by the * symbol; the arguments will be drawn from the elements in the list.
>>> args = [1,2,3]
>>> example(*args)
Invoked.
6
**-operator) involves providing a dictionary to the function, preceded by the ** symbol; each named paramter in the function definition will be looked up in the dictionary, and the value associated with that dictionary key will be used as the argument passed to that parameter.
>>> args = {'z':3, 'x':1, 'y':2}
>>> example(**args)
Invoked.
6
def example(x = 1, y = 2, z = 3):
return x + y + z
>>> example(0, 0)
3
>>> example(0)
5
>>> example()
6
>>> [ x for x in [1,2,3] ]
[1, 2, 3]
>>> [ 2 * x for x in {1,2,3} ]
[2, 4, 6]
>>> [ x + y for x in {1,2,3} for y in (1,2,3) ]
[2, 3, 4, 3, 4, 5, 4, 5, 6]
for clause. This will filter which combinations are actually used to add a value to the resulting list.
>>> [ x for x in {1,2,3} if x < 3 ]
[1, 2]
>>> [ x + y for x in {1,2,3} for y in (1,2,3) if x > 2 and y > 1 ]
[5, 6]
>>> { x for x in [1,2,3,1,2,3] }
{1, 2, 3}
>>> { key : 2 for key in ["A","B","C"] }
{'A': 2, 'C': 2, 'B': 2}
type() can be used to determine the type of a value. Below, we provide examples of how to check whether a given expression has one of the common Python types:
>>> type(True) == bool
True
>>> type(123) == int
True
>>> type("ABC") == str
True
>>> type([1,2,3]) == list
True
>>> type(("A",1,{1,2})) == tuple
True
>>> type({1,2,3}) == set
True
>>> type({"A":1, "B":2}) == dict
True
if, else, and/or elif), an iteration construct (i.e., a for or while loop), a return statement, or a break or continue statement.
x = 10
(x, y) = (1, 2)
def keyword, followed by the name of the function or procedure, and then by one or more arguments (delimited by parentheses and separated by commas).
def example(a, b, c):
return a + b + c
else). The body of each branch is an indented sequence of statements.
def fibonacci(n):
# Computes the nth Fibonacci number.
if n <= 0:
return 0
elif n <= 2:
return 1
else:
return fibonacci(n-1) + fibonacci(n-2)
if). The body is executed over and over until the expression in the condition evaluates to False, or a break statement is encountered.
def example1(n):
# Takes an integer n and returns the sum of
# the integers from 1 to n-1.
i = 0
sum = 0
while i < n:
sum = sum + i
i = i + 1
return sum
def example2(n):
# Takes an integer n and returns the sum of
# the integers from 1 to n-1.
i = 0
sum = 0
while True:
sum = sum + i
i = i + 1
if i == n:
break
return sum
def example3(n):
# Takes an integer n and returns the sum of
# the integers from 1 to n-1.
sum = 0
for i in range(0,n):
sum = sum + i
return sum
def example4(d):
# Takes a dictionary d that maps keys to
# integers and returns the sum of the integers.
sum = 0
for key in d:
sum = sum + d[key]
return sum