Projects

Number Theory

An O(n) algorithm for finding fundamental solutions to Pell Equations (Python)

Uses the continued fraction representation of $\sqrt{d}$ to compute the fundamental solution of the Pell equation $x^2-dy^2=1$ and to determine whether or not the negative Pell equation $x^2-dy^2=-1$ has a solution or not. This was also featured in a corresponding blog post. The output for $90\le d<100$ is shown below. Notice the only value with a solution to the negative Pell equation in this range is $d=97$ since every other number has a divisor that is $3\pmod{4}$ .

Fundamental solution to x^2-dy^2=1 for d=90 is x=19, 2
Fundamental solution to x^2-dy^2=1 for d=91 is x=1574, 165
Fundamental solution to x^2-dy^2=1 for d=92 is x=1151, 120
Fundamental solution to x^2-dy^2=1 for d=93 is x=12151, 1260
Fundamental solution to x^2-dy^2=1 for d=94 is x=2143295, 221064
Fundamental solution to x^2-dy^2=1 for d=95 is x=39, 4
Fundamental solution to x^2-dy^2=1 for d=96 is x=49, 5
Fundamental solution to x^2-dy^2=1 for d=97 is x=62809633, y=6377352:
Fundamental solution to x^2-dy^2=-1 for d=97 is x=5604, y=569
Fundamental solution to x^2-dy^2=1 for d=98 is x=99, 10
Fundamental solution to x^2-dy^2=1 for d=99 is x=10, 1

Fundamental solution to x^2-dy^2=1 for d=90 is x=19, 2
Fundamental solution to x^2-dy^2=1 for d=91 is x=1574, 165
Fundamental solution to x^2-dy^2=1 for d=92 is x=1151, 120
Fundamental solution to x^2-dy^2=1 for d=93 is x=12151, 1260
Fundamental solution to x^2-dy^2=1 for d=94 is x=2143295, 221064
Fundamental solution to x^2-dy^2=1 for d=95 is x=39, 4
Fundamental solution to x^2-dy^2=1 for d=96 is x=49, 5
Fundamental solution to x^2-dy^2=1 for d=97 is x=62809633, y=6377352:
Fundamental solution to x^2-dy^2=-1 for d=97 is x=5604, y=569
Fundamental solution to x^2-dy^2=1 for d=98 is x=99, 10
Fundamental solution to x^2-dy^2=1 for d=99 is x=10, 1

Search and Simulations

Eight Queens Puzzle Solution (C)

Uses hill-climbing search to solve the classical eight queens puzzle. Starts in a given starting configuration (numbered by which row a piece is in), and locally makes improvements to find the solution. The improvements are based on a heuristic of how many conflicts (queens that attack each other) exist on the board, and tries to reduce this to zero. To avoid getting stuck in ridges, the algorithm automatically chooses a random neighbour amongst ones with the same lowest heuristic.

Poker Hand Simulator (C)

A poker hand simulator written by me and Zeb Burke-Conte in the C programming language. The simulator randomly generates several poker playing hands, and outputs who has the winning hand:

Supports up to 29109 hands simultaneously being generated:

Missionaries and Cannibals Puzzle Simulator (iPython)

A Python program I wrote using a Breadth-first search to solve an extension of the famous Missionaries and Cannibals puzzle. The program prompts the user for the number of cannibals, missionaries, and people that are able to cross the boat at a time, which leads to many interesting variations of the initial puzzle.