Category Archives: proof

Efficiency of repeated squaring: another proof

Posted on September 6, 2018 by Brent

In my previous post I proved that the “binary algorithm” (corresponding to the binary expansion of a number ) is the most efficient way to build using only doubling and incrementing steps. Today I want to explain another nice proof, … Continue reading →

Posted in computation, proof | Tagged binary, double, efficiency, exponent, increment, proof, repeated, squaring, steps | 3 Comments

Efficiency of repeated squaring: proof

Posted on September 1, 2018 by Brent

My last post proposed a claim: The binary algorithm is the most efficient way to build using only doubling and incrementing steps. That is, any other way to build by doubling and incrementing uses an equal or greater number of … Continue reading →

Posted in computation, proof | Tagged binary, double, efficiency, exponent, increment, proof, repeated, squaring, steps | 2 Comments

The chromatic number of the plane, part 4: an upper bound

Posted on June 2, 2018 by Brent

In my previous posts I explained lower bounds for the Hadwiger-Nelson problem: we know that the chromatic number of the plane is at least 5 because there exist unit distance graphs which we know need at least 5 colors. Someday, … Continue reading →

Posted in geometry, proof | Tagged bound, chromatic, graph, number, plane, proof, upper | Comments Off

Iterating squared digit sums in other bases

Posted on May 25, 2018 by Brent

In a previous post I wrote about iterating the squared digit sum function, which adds up the sum of the squares of the digits of a number; for example, . Denis left a comment asking about other bases—what happens if … Continue reading →

Posted in arithmetic, computation, proof | Tagged base, digit, loop, squared, sum | 7 Comments

The chromatic number of the plane, part 3: a new lower bound

Posted on May 15, 2018 by Brent

In my previous post I explained how we know that the chromatic number of the plane is at least 4. If we can construct a unit distance graph (a graph whose edges all have length ) which needs at least … Continue reading →

Posted in geometry, proof | Tagged bound, chromatic, graph, number, plane, proof | 1 Comment

The chromatic number of the plane, part 2: lower bounds

Posted on May 1, 2018 by Brent

In a previous post I explained the Hadwiger-Nelson problem—to determine the chromatic number of the plane—and I claimed that we now know the answer is either 5, 6, or 7. In the following few posts I want to explain how … Continue reading →

Posted in geometry, proof | Tagged bound, chromatic, graph, number, plane, proof | 3 Comments

Iterating squared digit sum

Posted on April 26, 2018 by Brent

Another fun fact I learned from John Cook. Let be the function which takes a positive integer and outputs the sum of the squares of its digits. For example, . Since the output is itself another positive integer, we can … Continue reading →

Posted in arithmetic, computation, proof | Tagged digit, loop, Porges, proof, squared, sum | 12 Comments

The chromatic number of the plane, part 1

Posted on April 18, 2018 by Brent

About a week ago, Aubrey de Grey published a paper titled “The chromatic number of the plane is at least 5”, which is a really cool result. It’s been widely reported already, so I’m actually a bit late to the … Continue reading →

Posted in geometry, proof | Tagged chromatic, graph, number, plane, proof | 4 Comments

Properties of orthogons I

Posted on February 5, 2018 by Brent

First things first: from now on, when talking about polygons with only right angles, instead of calling them “orthogonal polygons” I’m going to start calling them “orthogons”, which sounds cool, is much less clunky than “orthogonal polygons”, and doesn’t seem … Continue reading →

Posted in combinatorics, geometry, proof | Tagged concave, convex, orthogonal, orthogons, polygons, proof, properties, vertices | 10 Comments

Fermat’s Little Theorem: proof by group theory

Posted on December 21, 2017 by Brent

It’s time for our third and final proof of Fermat’s Little Theorem, this time using some group theory. This proof is probably the shortest—explaining this proof to a professional mathematician would probably take only a single sentence—but requires you to … Continue reading →

Posted in group theory, number theory, primes, proof | Tagged combinatorics, group, order, proof, theory | Comments Off