Project Euler problem 312 is one of the harder problems we have worked through. It combines graph theory, fractal geometry, combinatorial counting, and modular arithmetic, and the final answer requires computing C(C(C(10000))) mod 13^8 where C(n) is the number of Hamiltonian cycles on a Sierpiński graph of order n.

We ended up leaning on OEIS to get the recurrence in closed form, which we will confess to below. Full notes: Project Euler/312.

The Problem

A Sierpiński graph of order 1, denoted S_1, is an equilateral triangle - three vertices, three edges.

S_{n+1} is …

Project Euler problem 227 - "The Chase" - is a nice example of a problem where the brute force approach is completely reasonable to reach for first, completely infeasible to actually finish, and directly points you at the right mathematical reformulation.

This is what we ended up with. Our full working notes are on the wiki at Project Euler/227.

The Problem

An even number of players sit around a table. Two players sitting directly opposite each other each start with a die. Each round, both players roll:

• Roll a 1 → pass the die to your left neighbor
• Roll a 6 → pass …

Project Euler problem 198 is a number theory problem that turns out to be almost entirely about continued fractions. The problem hides this - the statement talks about "ambiguous" real numbers - but the ambiguity has a clean characterization in terms of continued fraction expansions, and once you see it, the problem gets a lot smaller.

Wiki notes: Project Euler/198.

The Problem

Define a best approximation to a real number x with denominator bound d as a rational r/s in reduced form with s ≤ d, such that any other rational p/q closer to x than r/s has q …

Project Euler problem 60 is a nice mid-difficulty combinatorial search problem. It has enough structure that pure brute force falls over, and enough structure that a handful of small observations gives you a very tractable search.

Our working notes: Project Euler/60.

The Problem

The primes 3, 7, 109, and 673 are "quite remarkable" - concatenating any two of them in either order gives another prime. So 7109, 1097, 3673, 6733, 109673, 673109, and so on, are all prime. That is 12 concatenations, all prime.

The sum of these four primes is 792, and the problem states this is the smallest …

This is part 3 of our series on generating functions. Part 1 handled the quicksort recurrence. Part 2 used ordinary generating functions to count marbles in a can.

In this post we introduce exponential generating functions, which are what you reach for when the order of the objects you are counting matters. As with the earlier posts, our working notes live on the Generating Functions page of our wiki.

When Order Matters

The marbles-in-a-can problem from part 2 was order-independent. A can containing three reds, two blues, and one yellow is the same can no matter what order you put …

This is part 2 of our series on generating functions. In part 1 we used generating functions to solve the quicksort recurrence, which is a serious industrial-strength application. This time we will use them for something a lot more whimsical: counting how many different cans of colored marbles you can put together under a bunch of arbitrary rules.

The example is from Trotter's Applied Combinatorics. Our working notes for this one, along with a few related exercises, live on the Generating Functions page of our wiki.

The Problem

We are packing cans of marbles. Each can holds 20 marbles, in …

This post is part 1 of a series on generating functions, based on notes we have been working through from Sedgewick and Flajolet's Analysis of Algorithms and Trotter's Applied Combinatorics. The full set of notes lives on our wiki: Generating Functions.

Generating functions are one of those techniques that look completely mysterious the first time you see them, and then look like the obvious thing to do the tenth time you see them. They turn recurrences into functions, functions into series, and series back into closed forms for the coefficients you actually wanted. This post walks through one of the …

Here is a nice little problem from Paul Nahin's Will You Be Alive 10 Years From Now?. It is a problem from the 1654 correspondence between Antoine Gombaud (the Chevalier de Méré) and Blaise Pascal - one of the founding episodes of probability theory, dressed up as a gambling puzzle.

(This one lives on our wiki as FMM21, part of our Friday Morning Math Problem series.)

The Two Games

Game 1. You toss a single die \(N_1\) times. What should \(N_1\) be to make the probability of seeing at least one 6 greater than \(\tfrac{1}{2}\)?

Game 2. You toss …

Favorite Pi Approximations

What's your favorite \(\pi\) approximation?

Some of my favorite approximations of \(\pi\) come from Ramanujan-Sato series. These are mathematical series that generalize from a remarkable formula for \(\pi\) given by Srinivasa Ramanujan, an Indian mathematician:

Table of Contents

• Overview: Problem 172
• Background
  • Multiset Permutations
  • A Simple Problem (And Solution)
  • A Slightly More Complicated Problem
• Algorithm
  • Ignoring Numbers Starting with 0
• Code
  • Test Cases
  • Recursion
  • Pseudocode
  • Python Code
• Final Answer

Overview: Problem 172

How many 18-digit numbers \(n\) (without leading zeros) are there such that no digit occurs more than three times in \(n\)?

Link to Project Euler Problem 172

Background

Project Euler Problem 172 is your classic Project Euler problem: short, simple, and overwhelmingly complicated.

To nail this one, it's important to start simple - very simple. What I'll do is walk through the process of …

An Integral from Hardy

Every once in a while you run across an integral that looks straightforward at first glance, but the more you stare at it, the less obvious it becomes how to proceed. This is one of those integrals. It's the sort of problem that G. H. Hardy - the great English mathematician who taught at Cambridge for decades and famously collaborated with Ramanujan - liked to pose to students as a way to sharpen their instincts about integration.

Here's the integral:

At a glance, this doesn't fit any of the …

Table of Contents

• Introduction
• Complete and Reduced Residue Systems
• Euler's Totient Function
• Calculating the Totient Function by Hand

Introduction

Today we're going to delve into a little bit of number theory.

In number theory, we are usually dealing with modular arithmetic - expressions of the form:

or

The mod indicates we're doing modular arithmetic, which is (formally) an algebraic system called a ring, which consists of the integers 0 through m.

An analogy to modular arithmetic is the way that the sine and cosine function "wrap around," and

Table of Contents

• Overview: The Problem
• Polyominoes
  • Castle Rules for Polynominoes
• Don't Generate - Enumerate!

Overview: The Problem

In an earlier post, I mentioned my efforts on Project Euler problems and the wide variety of problems there that can offer some profound mathematical insights.

Given that the first post covered Project Euler problem 1, I thought it would be nice if the next problem cranked up the difficulty factor by an order of magnitude. Project Euler Problem 502 is a very hairy combinatorics problem that required me to learn about a wide variety of combinatorial enumeration techniques.

Let's start with the …

Table of Contents

• Overview: The Problem
• Why This Problem?
• Going Deeper: An Example

Overview: The Problem

Project Euler is a website that provides mathematically-oriented programming problems. There are many (over 500) and they are a rich source of profound mathematical insights.

I have been considering a writeup that goes deep into a particular problem, so why not do it with problem 1?

Problem 1 of Project Euler asks:

Find the sum of all the multiples of 3 or 5 below 1000.

It is a pretty simple task - one of the first things covered in a decent programming course is the …

The Lattice Paths Problem

I first came across the lattice paths problem in Project Euler problem 15. The question described a 2x2 square lattice, and illustrated the 6 ways of navigating from the top left corner to the bottom right corner by taking the minimum number of steps - 2 right …

Table of Contents

• Number Systems and Representations
• Continued Fraction Representations
• Convergents of Continued Fractions
• Example: Continued Fraction Coefficients of \(\sqrt{14}\)
• Example: Convergents of \(\sqrt{14}\)
• Approximating Square Roots

Continued Fractions

Let's start part 2 of our discussion of computing square roots by talking about continued fractions. When we first learn mathematics, we learn to count in the base 10 system: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. We can construct representations of all of the integers using these 10 digits, by arranging them in a different order. So, for example, saying 125 is equivalent to saying …

Table of Contents

• Newton's Method for Finding Roots of Equations

• Newton's Method for Finding Square Roots

• Newton's Method for Finding Square Roots: Program

• Accuracy

• Speed

• Next Steps

• References

Newton's Method for Finding Roots of Equations

Suppose we have a function \(f(x)\) and we want to compute values of \(x\) for which \(f(x)=0\). These values of \(x\) are called the roots of \(f(x)\).

We can compute the roots using Newton's Method, which utilizes the derivative of the function to iteratively compute the roots of the function.

Newton's method begins with an initial guess. It evaluates the derivative …