Post series

The Twelve Days of Christmas and Tetrahedral Numbers

• The Twelve Days of Christmas and Tetrahedral Numbers
• Computing tetrahedral numbers
• Triangular number formula (Challenge #8)
• Binomial coefficients
• Challenge #8 solution
• Binomial coefficients and Pascal’s triangle
• Tetrahedral numbers, exposed!

Fibonacci numbers and the golden ratio

• Golden ratio properties (Challenge #10)
• Challenge #10 Solution
• Golden powers
• Explicit Fibonacci numbers

Perfect numbers

• Perfect numbers, part I
• Perfect numbers, part II
• Perfect numbers, interlude (Challenge #11)
• Perfect numbers, part III

Recounting the Rationals

• Recounting the Rationals, part I
• Recounting the Rationals, part II (fractions grow on trees!)
• Recounting the Rationals, part III
• Recounting the Rationals, part IV
• Recounting the Rationals, part IVb: the Euclidean Algorithm
• Challenge #12: sums of powers of two
• Challenge #12 solution, part II
• More hyperbinary fun
• Hyperbinary conjecture seeking proof for a good time, long walks on the beach
• The hyperbinary sequence and the Calkin-Wilf tree

Rational and irrational numbers

• Rational and irrational numbers
• Rational numbers and decimal expansions
• Decimal expansion zoo
• More on decimal expansions
• More on repetend lengths

Predicting Pi

• Predicting Pi
• Predicting Pi: solution
• Predicting pi: pretty graphs and convergents

Irrationality of pi

• Irrationality of pi
• Irrationality of pi: the unpossible function
• Irrationality of pi: derivatives of f
• Irrationality of pi: curiouser and curiouser
• Irrationality of pi: the impossible integral
• Irrationality of pi: the integral that wasn’t

Decadic numbers

• A curiosity
• An invitation to a funny number system
• What does “close to” mean?
• The decadic metric
• Infinite decadic numbers
• More fun with infinite decadic numbers
• A self-square number
• u-tube
• Computing with decadic numbers

A combinatorial proof

• Differences of powers of consecutive integers
• Differences of powers of consecutive integers, part II
• Combinatorial proofs
• Making our equation count
• How to explain the principle of inclusion-exclusion?
• PIE Day
• Post without words #16
• Post without words #17
• Post without words #18
• Post without words #19
• A probability puzzle
• Probabilistic PIE
• Have a piece of PIE
• Formal PIE
• PIE: proof by algebra
• PIE: proof by counting
• More to come…

What I Do

• What I Do: Part 0
• What I Do, Part 1: Programming languages
• More to come…

MaBloWriMo 2015: The Lucas-Lehmer Test and Group Theory

1. The Lucas-Lehmer test
2. Mersenne composites
3. Mersenne composites in binary
4. not all prime-index Mersenne numbers are prime
5. The Lucas-Lehmer Test
6. The Proof Begins
7. s via omega
8. definition of s and mod
9. omega and its ilk
10. Groups
11. Examples of Groups
12. Groups and Order
13. Elements of finite groups have an order
14. Element orders are no greater than group size
15. One more fact about element orders
16. Recap and outline
17. X marks the spot
18. X is not a group
19. groups from monoids
20. the group X star
21. the order of omega, part I
22. the order of omega, part II
23. contradiction!
24. Bezout’s identity
25. Subgroups
26. Left cosets
27. From subgroups to equivalence relations
28. Equivalence relations are partitions
29. Equivalence classes are cosets
30. Cyclic subgroups

The chocolate bar game

• Visualizing nim-like games
• The chocolate bar game
• The chocolate bar game: losing positions in binary
• The chocolate bar game: losing positions characterized
• The chocolate bar game: losing positions proved
• The chocolate bar game: variants

Fibonacci numbers and golden numbers

• Testing Fibonacci numbers
• Testing Fibonacci numbers: the proofs
• Fibonacci numbers are golden
• Golden numbers are Fibonacci

Apollonian gaskets and Descartes’ theorem

• Post without words #6
• Apollonian gaskets
• Apollonian gaskets and Descartes’ Theorem
• Apollonian gaskets and Descartes’ Theorem II

Roots of unity and the Möbius function

• Post without words #10
• A few words about PWW #10
• Post without words #11
• Totient sums
• Complexifying our dots
• Complex multiplication and roots of unity
• Complex multiplication: proof
• Primitive roots of unity
• Sums and symmetry
• Sums of primitive roots
• Computing sums of primitive roots
• The Möbius function
• The Möbius function proof, part 1
• The Möbius function proof, part 2 (the subset parity lemma)
• Dirichlet convolution
• Dirichlet convolution and the Möbius function
• Möbius inversion
• More fun with Dirichlet convolution
• Dirichlet generating functions
• The Riemann zeta function
• The Basel problem
• The MacLaurin series for sin(x)
• The Riemann zeta function and prime numbers

The greedy coins game

• The greedy coins game
• Ties in the greedy coins game
• Greedy coins game update
• Another greedy coins game update
• Computing optimal play for the greedy coins game
• Computing optimal play for the greedy coins game, part 2
• Computing optimal play for the greedy coins game, part 3
• Computing optimal play for the greedy coins game, part 4

The silver ratio

• The curious powers of 1 + sqrt 2
• The curious powers of 1 + sqrt 2: conjecture
• The curious powers of 1 + sqrt 2: a clever solution
• The curious powers of 1 + sqrt 2: recurrences
• To be continued…?

Primality testing

• New baby, and primality testing
• Four formats for Fermat
• Four formats for Fermat: correction!
• Fermat’s Little Theorem: proof by modular arithmetic
• Euler’s Theorem: proof by modular arithmetic
• Fermat’s Little Theorem: proof by necklaces
• Fermat’s Little Theorem: proof by group theory
• A tale of three machines
• Fast and slow machines
• The Fermat primality test
• Modular exponentiation
• Modular exponentiation by repeated squaring
• Post without words #22
• Efficiency of repeated squaring
• Efficiency of repeated squaring: proof
• Efficiency of repeated squaring: another proof
• Primality testing: recap
• Quickly recognizing primes less than 100
• Quickly recognizing primes less than 1000: divisibility tests
• Quickly recognizing primes less than 1000: memorizing exceptional composites
• Making the Fermat primality test deterministic
• The Fermat primality test and the GCD test
• Post without words #24
• Fermat witnesses and liars (some words on PWW #24)
• More on Fermat witnesses and liars
• To be continued…

Orthogons

• Post without words #21
• Orthogonal polygons
• Properties of orthogons I
• Properties of orthogons II
• Orthogons and orthobraces
• Listing orthobraces
• Haskell code to naively list orthobraces
• Efficiently listing orthobraces
• Why drawing orthogons is hard
• Drawing orthogons with an SMT solver
• SMT solutions

The chromatic number of the plane

• The chromatic number of the plane, part 1
• The chromatic number of the plane, part 2: lower bounds
• The chromatic number of the plane, part 3: a new lower bound
• The chromatic number of the plane, part 4: an upper bound
• Post without words #22
• Some words on PWW #22
• Chromatic number of the plane roundup

Prefix and repetend length

• Finding prefix and repetend length
• Finding the prefix length of a decimal expansion
• Finding the repetend length of a decimal expansion
• Post without words #25
• A few words about PWW #25
• More words about PWW #25: The Chinese Remainder Theorem
• Chinese Remainder Theorem proof
• Post without words #26
• Computing the Euler totient function, part 1
• Computing the Euler totient function, part 2: seeing phi is multiplicative
• Computing the Euler totient function, part 3: proving phi is multiplicative
• Computing the Euler totient function, part 4: totient of prime powers