Category Archives: proof

Efficiency of repeated squaring: another proof

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 , , , , , , , , | 3 Comments

Efficiency of repeated squaring: proof

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 , , , , , , , , | 2 Comments

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

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 , , , , , ,

Iterating squared digit sums in other bases

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 , , , , | 7 Comments

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

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 , , , , , | 1 Comment

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

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 , , , , , | 3 Comments

Iterating squared digit sum

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 , , , , , | 12 Comments