Category Archives: recursion

Computing optimal play for the greedy coins game, part 4

Posted on May 12, 2017 by Brent

Last time I explained a method for computing best play for instances of the greedy coins game, which is feasible even for large games. This general approach is known as dynamic programming and is applicable whenever we have some recursively … Continue reading →

Posted in computation, games, recursion | Tagged coins, dynamic, game, optimal, play, programming, proof, recurrence, strategy, tree, two-player, zero-sum | Comments Off

Computing optimal play for the greedy coins game, part 3

Posted on May 10, 2017 by Brent

In a previous post we saw how we can organize play sequences in the greedy coins game into a tree. Then in the last post, we saw how to work our way from the bottom of the tree upward and … Continue reading →

Posted in computation, games, recursion | Tagged coins, game, optimal, play, proof, recurrence, strategy, tree, two-player, zero-sum | 2 Comments

Computing optimal play for the greedy coins game, part 2

Posted on May 4, 2017 by Brent

I want to explain in more detail how we can think about computing the best possible score for Alice in the greedy coins game, assuming best play on the part of both players. I glossed over this too quickly in … Continue reading →

Posted in computation, games, recursion | Tagged coins, game, optimal, play, proof, recurrence, strategy, tree, two-player, zero-sum | 1 Comment

Computing optimal play for the greedy coins game

Posted on May 2, 2017 by Brent

Recall the greedy coins game, in which two players alternate removing one of the coins from either end of a row, and the player with the highest total at the end is the winner. What if we wanted to play … Continue reading →

Posted in computation, games, recursion | Tagged coins, dynamic programming, game, optimal, play, proof, recurrence, strategy, two-player, zero-sum | 2 Comments

The Recamán sequence

Posted on June 12, 2016 by Brent

I recently learned about a really interesting sequence of integers, called the Recamán sequence (it’s sequence A005132 in the Online Encyclopedia of Integer Sequences). It is very simple to define, but the resulting complexity shows how powerful self-reference is (for … Continue reading →

Posted in arithmetic, recursion, sequences | Tagged difference, integers, Recamán, repeat, sequence | 5 Comments

Apollonian gaskets and Descartes’ Theorem II

Posted on June 10, 2016 by Brent

In a few previous posts I wrote about “kissing sets” of four mutually tangent circles, and the fact that their signed bends satisfy Descartes’ Theorem, (Remember that the signed bend of a circle is like the curvature , except that … Continue reading →

Posted in geometry, pattern, pictures, recursion | Tagged Apollonian, bend, center, circle, complex, Descartes, gasket, theorem | 1 Comment

Apollonian gaskets and Descartes’ Theorem

Posted on May 4, 2016 by Brent

In my previous post, I explained a recursive procedure for drawing Apollonian gaskets. Given any three mutually tangent circles, there are exactly two other circles which are mutually tangent to all three (forming what we called a “kissing set”). This … Continue reading →

Posted in geometry, pattern, pictures, recursion | Tagged Apollonian, bend, circle, Descartes, gasket, theorem | 2 Comments

Apollonian gaskets

Posted on April 27, 2016 by Brent

In my last post I showed off this tantalizing picture: This pattern of infinitely nested circles is called an Apollonian gasket. Over the next post or two I’ll explain some cool math behind actually constructing them. Mostly I will state … Continue reading →

Posted in geometry, pattern, pictures, recursion | Tagged Apollonian, gasket, recursion, tree | 4 Comments

More factorization diagrams

Posted on November 5, 2012 by Brent

My post on factorization diagrams from a month ago turned out to be (unexpectedly) quite popular! I got ten times as many hits as usual the day it was published, and since then quite a few other people have created … Continue reading →

Posted in arithmetic, links, pictures, primes, programming, recursion | Tagged diagrams, factorization, Haskell | 15 Comments

Factorization diagrams

Posted on October 5, 2012 by Brent

In an idle moment a while ago I wrote a program to generate "factorization diagrams". Here’s 700: It’s easy to see (I hope), just by looking at the arrangement of dots, that there are in total. Here’s how I did … Continue reading →

Posted in arithmetic, pictures, primes, programming, recursion | Tagged diagrams, factorization, Haskell | 72 Comments