The Context: de Bruijn Graphs

In Part 1 of this post we discussed a data structure called a de Bruijn graph and covered its application to genome assembly. To summarize, a de Bruijn graph is a type of graph that represents a set of k-mers as a set of directed edges on …

The Context: Rosalind.info

To provide a bit of context for a discussion of Euler paths and Euler cycles: starting around December, a group of us in the Lab for Data Intensive Biology (DIB Lab) started working through the textbook Bioinformatics Algorithms: An Active Learning Approach and the associated website, Rosalind.info.

Rosalind.info is a site that is similar in style …

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 …

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