# Approximating Pi (Happy Pi Day)

Posted in Mathematics

## 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:

$$\pi^{-1} = \dfrac{\sqrt{8}}{99^2} \sum_{k \geq 0} \dfrac{ (4k)! }{ \left( 4^k k! \right)^4 } \dfrac{ 1103 + 26390k }{ 99^{4k} }$$

This completely novel formula opened up new branches of mathematics and provided a whole new class of $$\pi$$ approximations (the Ramanujan-Sato series) and approximations that are extremely accurate, making them very useful for computer applications. (Each term of …

# Project Euler Problem 172

Posted in Mathematics

# 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 …

# 4x4 Rubik's Cube: Part 1: Representations

Posted in Rubiks Cube

This is Part 1 of a 4-part blog post on the mathematics of the 4x4 Rubik's Cube, its relation to algorithms, and some curious properties of Rubik's Cubes.

You are currently reading Part 1 of this blog post: Part 1: Representations

See Part 2 of this blog post here: Part 2: Permutations

See Part 3 of this blog post here: Part 3: Factoring Permutations

See Part 4 of this blog post here: Part 4: Sequence Order

# Euler's Theorem, the Totient Function, and Calculating Totients By Hand

Posted in Mathematics

## 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:

$$a \equiv b \mod m$$

or

$$f(x) \equiv 0 \mod m$$

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

 \sin \left …

# Mad Combinatoric Castles

Posted in Mathematics

# 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 …

# Project Euler Problem 1

Posted in Mathematics

# 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 …

# Shortest Lattice Paths and Multiset Permutations

Posted in Mathematics

## 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 …

# Computing Square Roots: Part 2: Using Continued Fractions

Posted in Mathematics

## 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 …

# Computing Square Roots: Part 1: Using Newton's Method

Posted in Mathematics

## 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 …