Add Me!Close Menu Navigation

From fighting crime and arresting pirates to blasting away zombies, you can always count on a superhero. Unfortunately, I am definitely not that person.

Add Me!Open Categories Menu
29 December

Counting Binary Trees (The Hard Way)

In this post, we prove the closed form of a nonlinear recurrence corresponding to the count of binary trees with n nodes.

28 December

Calculating Modified Fibonacci Numbers, Quickly and Exactly

This is inspired by an article of similar name called Calculating Fibonacci Numbers, Quickly and Exactly. Consider the a modified fibonacci sequence given by the recurrence c_0 = 2, c_1 = 1, c_k = c_{k-1} + c_{k-2}. We shall look at various algebraic and analytic properties of this sequence, find two algorithms that computes c_k in O(\log(k)) time, and finally look at a motivating example where we need to compute this sequence quickly and exactly.

9 November
Posted in Article, Math Problems

Counting Words

Suppose that we are given the alphabet \Sigma = \Rec{0,1,2}; a word of length n: x_n \in \Sigma^5, is an ordered n-tuple whose elements all came from \Sigma. For example, a word of length 5 in \Sigma might be the tuple (0,0,2,1,0), which we will hereon denote as 00210. For some natural number k \le n, how many words of length n are there that contains exactly k zeros?

6 November

Annoying Mclaurin Series

Suppose that we’re given the function B(z) = \frac{1 + z}{1 - z - z^2}, find the ordinary generating function associated with it in the form of B(z) = \sum_{k=0}^\infty b_k k^z. Furthermore, find/compute \sigma_n = \sum_{k=0}^n b_k.

15 October

Infinity Norm of the Inverse of Lower Bidiagonal Matrices

We consider the problem of efficiently computing the infinity norm of the inverse of a lower bidiagonal matrix L in linear time.

Limit Preserving Functions in CPOs

Very short proof that limit preserving functions (continuous functions) on complete partial orders are necessarily monotone.

28 May

Introduction to Scientific Computing: Error Propagation

The first part on a series designed to survey the design and analysis of various numerical methods will look at error propagation.

Subtype Ambiguity in Java

Let’s take a look at an example of a situation where ambiguity occurs during the derivation of subtyping proofs in Java. In general, it’s conjectured that subtyping in Java is undecidable.

16 March
Posted in Article, OCaml

Neat way of counting OCaml objects satisfying certain types

We use a very natural semantic translation from OCaml styled types (or really any almost algebraic types) to the count of the instances of those types and do some cool stuff with this translation.

18 January

Fixing floating point cancellation I

How can you compute \sqrt{x^2+1}-x to 14 digits of accuracy within the domain |x| < 10^8?

17 January
Posted in Numerical Analysis

Floating point quirks

In this post, we’ll explore a scenario where the non-commutativityassociativity of floating point arithmetic can lead us into trouble.

Let a_k = \frac{1}{k(k+1)} and S_n = \sum_{k=1}^n a_k. Write a computer program to compute this sum.

25 November
Posted in Reading Diary

Solving first order PDEs with Characteristics

Use the method of characteristics to solve the PDE system

     $$\begin{cases} u_x + xu_y = 0 \\ u(0,y) = f(y) \end{cases}$$

15 August
Posted in Article, Math Problems

Power Reduction in Congruences

Suppose you have integers a,b that are relatively prime to m such that

    $$ a^x \equiv b^x \mod m \hspace{4mm}\mbox{ and }\hspace{4mm} a^y \equiv b^y \mod m $$

then

    $$ a^{\gcd(x,y)} \equiv b^{\gcd(x,y)} \mod m $$

14 August
Posted in Article, Math Problems

Even Pascals

Let a=4k-1, where k is an integer. Prove that for any positive integer n the number

     $$ s_n = 1 - {n \choose 2}a + {n \choose 4}a^2 - {n \choose 6}a^3 + \cdots $$

is divisible by 2^{n-1}.

14 August
Posted in Article, Math Problems

Sequences in Sequences

Define the sequence (a_n)_n recursively by a_1 = 1 and

     $$ a_{n+1} = \frac{1 + 4a_n + \sqrt{1+24a_n}}{16} ,\hspace{4mm} \mbox{for $n \ge 1$.} $$

Find an explicit formula for a_n in terms of n.

14 August
Posted in Article, Math Problems

More Linear Recurrences

Let (x_n )_n = 0 be defined by the recurrence relation x_{n + 1} = ax_n + bx_{n - 1}, with x_0 = 0. Show that the expression x^2_n - x_{n - 1} x_{n + 1} depends only on b and x_1, but not on a.

13 August
Posted in Article, Math Problems

Almost Linear

Find the general term of the sequence given by x_0 = 3, x_1 = 4, and

    $$(n + 1 )(n + 2 )x_n = 4 (n + 1 )(n + 3 )x_{n - 1} - 4 (n + 2 )(n + 3 )x_{n - 2}$$

13 August
Posted in Article, Math Problems

Polynomial Divisors

Let p(x) = x^2 -3x + 2. Show that for any positive integers  n \ge 2 there exists unique numbers a_n, b_n such that the polynomial  x^n - a_n x - b_n is divisible by p(x)

13 August
Posted in Article, Math Problems

Analytical Fibonacci

We derive Binet’s equation for the nth Fibonacci number as

     $$ F_n = \frac{1}{\sqrt 5}\left( \left(\frac{1+\sqrt 5}{2}\right)^n -  \left(\frac{1-\sqrt 5}{2}\right)^n  \right) $$

13 August
Posted in Article, Math Problems

Linear Recursive Sequence

We derive a general technique for solving full rank linear recursive sequences. Formally, a kth linear recursive sequence is defined as

     $$ x_n = a_1 x_{n-1} + a_2 x_{n-2} + a_3 x_{n-3} + \stackrel{k}{\ldots} + a_k x_{n-k} $$

12 August
Posted in Article, Math Problems

Odd Coprimes

Let a be an odd integer. Prove that a^{2^n} + 2^{2^n} and a^{2^m}+2^{2^m} are relatively prime for all distinct positive integers n and m.

12 August
Posted in Article, Math Problems

More Prime Congruences

Find all primes p and q such that p+q = (p-q)^3

12 August
Posted in Algorithm, Article, Lua

Interval Scheduling Problem

Let’s consider the Interval Scheduling Problem, in which we have a set of n requests \{1,2,\cdots,n\}; the i^{th} request corresponds to an interval of time starting at s_i and finishing at f_i, or request $i$ spans interval $ [s_i,f_i]$. Suppose that a subset of the requests is compatible if no two of them overlap in time; find the largest compatible subset of any set of requests in a reasonable number of steps.

11 August
Posted in Article, Math Problems

Prime Congruence Class

Show that there are infinitely many primes of the form 4k - 1.

10 August
Posted in Article, Math Problems

Just the Evens

Find the sum of even positive divisors of 100000

10 August
Posted in Article, Math Problems

Sum of Divisors

Suppose we define the function \sigma: \mathbb{N} \to \mathbb{N} as the sum of the divisors of n

     $$ \sigma(n) = \sum_{d|n} d $$

Express \sigma(n) in terms of n‘s prime factorization

9 August
Posted in Article, Math Problems

That Other Little Gauss Story

Determine the product of distinct positive integer divisors of n = 420^4.

9 August
Posted in Article, Math Problems

Congruence by L.C.M

Determine the number of ordered pairs of positive integers (a,b) such that their least common multiple [a,b] = 2^35^711^{13}

9 August
Posted in Article, Math Problems

Randomly Chosen Divisors

Compute the probability that a randomly chosen positive divisor of 10^{99} is an integer multiple of 10^{88}

9 August
Posted in Article, Math Problems

Nothing in common

Let a and b be distinct integers such that a^2 + ab + b^2|ab(a+b). Show that

     $$ |a - b| > \sqrt[3]{ab} $$

8 August
Posted in Article, Math Problems

The Fib-Fib-Fib Sequence

Consider the sequences (a_n)_n, (b_n)_n, defined recursively by

     $$ \begin{tabular}{l l l l} $a_0 = 0$, & $a_1 = 2$, & $a_{n+1} = 4a_n + a_{n-1}$ & $n \ge 0$ \\ $b_0 = 0$, & $b_1 = 1$, & $b_{n+1} = a_n - b_n + b_{n-1}$ & $n \ge 0$ \end{tabular} $$

Show that (a_n)^3 = b_{3n} \fa n

7 August
Posted in Article, Math Problems

Square Sequence

The sequence f_1, f_2, \cdots satisfies

    $$ f_{m+n} + f_{m - n} = \frac{f_{2m} + f_{2n}}{2}$$

for all nonnegative integers n,m and m \ge n. If f_1 = 1, determine f_n

7 August
Posted in Article, Math Problems

Super Fibonacci

Show that k|a_k where a_k defined as

     \begin{align*} a_0 &= 0 \hspace{4mm} a_1 = 1 \\ a_2 &= 2 \hspace{4mm} a_3 = 6 \\ a_{n+4} &= 2a_{n+3} + a_{n+2} - 2a_{n+1} - a_n \end{align*}

6 August
Posted in Article, Math Problems

More Sequences

Find a closed form formula for the recurrence relation

     \begin{align*} x_1 &= 1 \\ x_n &= \begin{cases} x_{n-1} + n &\mbox{if $n$ odd} \\  x_{n-1} + n - 1 & \mbox{if $n$ even} \end{cases}  \end{align*}

6 August
Posted in Article, C

Somewhat Fast Square Root

Written for a challenge from /r/dailyprogrammer, I present to you an algorithm to approximate square roots that is still unfortunately slower than the _mm_sqrt_ps primitive offered by Intel. The following article is largely inspired by the brilliantly written Fast InvSqrt algorithm from id software.

6 August
Posted in Article, Math Problems

Arithmetic Sequences

Find a closed form formula for the sequence {1,2,2,3,3,3,4,4,4,4,5,5,5,5,5,…}

5 August
Posted in Article, Math Problems

Infinite GCD

Compute gcd(2002 + 2, 20022+2, 20023+2, …)

5 August
Posted in Article, Math Problems

Multiples of 864

If a positive integer multiple of 864 is chosen randomly, with each multiple having the same probability of being chosen, what is the probability that it is divisible by 1944?

5 August
Posted in Article, Math Problems

Maximum Divisor

Prove that the maximum power of 2 divisor of 32n – 1 is 2n+2

5 August
Posted in Article, Math Problems

Counting Primes

This is a classic problem first solved by Euclid: Show that there are infinitely many prime numbers.

5 August
Posted in Article, Math Problems

Find 100 Consecutive Composite Numbers

5 August
Posted in Article, Math Problems

Almost Composite

If p and q are primes, and x2 – px + q = 0 has distinct positive integer roots, find p and q.

5 August
Posted in Article, Math Problems

The Mysterious Case of the Hidden Evens

Find all positive integers n for which 3n−4, 4n−5, and 5n−3 are all prime numbers.

5 August
Posted in Article, Math Problems

Why not Four?

Let n be a positive integer. Prove that 32n+1 is divisible by 2,but not by 4.

4 August
Posted in Article, Math Problems

In Search of the Magic Pair

Zach has chosen five numbers from the set {1, 2, 3, 4, 5, 6, 7}. If he told Claudia what the product of the chosen numbers was, that would not be enough information for Claudia to figure out whether the sum of the chosen numbers was even or odd. What is the product of the chosen numbers?

4 August
Posted in Article, Math Problems

What are the Odds?

Let k be an even number. Is it possible to write 1 as the sum of the reciprocals of k odd integers?

4 August
Posted in Article, Math Problems

Sum of Consecutive Integers

Let n be an integer greater than 1, show that 2n is the sum of two consecutive odd integers. Furthermore, show that 3n is the sum of three consecutive integers.

4 August
Posted in Article, Math Problems

The Locker Room Problem

Twenty bored students take turns walking down a hall that contains a row of closed lockers, numbered 1 to 20. The first student opens all the lockers; the second student closes all the lockers numbered 2, 4, 6, 8, 10, 12, 14,16, 18, 20; the third student operates on the lockers numbered 3, 6, 9, 12, 15, 18: if a locker was closed, he opens it, and if a locker was open, he closes it; and so on. How many lockers remain open after all the students finish?

3 August
Posted in Article, Math Problems

Divisors of Perfect Squares

In this article, we prove that only perfect squares have an odd number of divisors

29 May
Posted in Article

How to Approximate Like A Boss

1. Find out what 2.0015, 8.62/3, e-0.15, and 1/1200 are approximately without using a calculator.

We use a really simple method that works well for polynomials and describe how we can determine how well our approximation does relative to the actual answer.

23 May
Posted in Article, Lua

Problem Solving with Lua

Chapter 11. The project team problem part 1

Let’s pretend for a moment that you’re working as an undergraduate research assistant for one of the most brilliant professors at your school, which makes you more or less a glorified secretary/coffee dispenser. On the first day of class, you are tasked to divide up his CS101 class into pairs of student who will be working together in order to implement an awesome Pokemon clone. Great, yet another boring and unamusing problem to solve. However, soon you find that the problem wasn’t as easy as you originally thought it to be.

The first part of this problem solving series will deal with problems that may not seem intuitive at first, but will have extremely simple and elegant algorithms.

21 May
Posted in Article, Python

Scientific Computation

Binary representation of numbers and floating point precision arithmetic.

Once upon a time, I absolutely despised matlab. In my own spoiled preconceptions, I believed that matlab was designed without a single shred of care as to how ugly it is. Of course, I eventually had to finally write my first line of matlab and, upon discovering that I’m still in one piece, concluded that matlab wasn’t really that bad. Anyways, I’ve moved onto grander things now, things such as singing obnoxiously in public, browsing reddit for hours on end, and Python.

27 February
Posted in Article, Lua

Learn Lua the Hard Way – Tables

Tables are the most important data structure in Lua thanks to their flexibility, hence we dedicate an entire post to the use of tables. In this tutorial, you will learn how to create and manipulate tables and dictionaries and how to iterate over a table using for and while loops.

19 February
Posted in Article

ISBN Numbers

ISBN is an acronym for International Standard Book Number and is used as unique identifiers for published books. In this entry I will talk about how mathematics plays a role in the development and usage of the ISBN.

17 February
Posted in Article, C, Lua

Polygonal Collision Detection

We will use the Separating Axis theorem to deduce whether two convex polygons are overlapping or not and implement the desired algorithm in both C and Lua. Collision detection is primarily used within the game development industry, but practical uses outside of this industry are also quite common.

15 February
Posted in Article, Lua

Learn Lua the Hard Way

This series more or less mirrors the series of the same name for Python. It’s in my belief that the only way to learn the in and outs of a language is to learn by practice, and by that virtue, to practice as often as possible until you get the hang of the language.

13 February
Posted in Lua

Randomness

People tend to trivialize the concept of randomness in computing. While true randomness cannot be replicated by a computer, the occurrences of randomness in nature have provided us with considerable insight into the properties of a random sequence of numbers. We can replicate these properties in defined numerical sequences that behave tolerably similar to random sequences.

In this post, we will implement and examine a simple yet well known pseudorandom number generation algorithm known as the linear congruential method.

12 February
Posted in Python

Greatest Common Denominator

Imagine that you are nine and you’re going to 3rd grade math class. Your teacher asks for the greatest common denominator between 10 and 15. Everyone else is just as stumped as you are, but being gifted with the incredible ability to program computers, you decide to write a program to do it for you.

11 February
Posted in Article

Muddy Children

A father comes back to his 100 children and tells them that some of them have mud on their head. The father asks “can you tell if you have mud on your head?” and all respond with “no”. The father then repeats the question until on the 15th turn, some of the children suddenly shouts out yes. How many children are muddy?

7 February
Posted in Article

Computers

Far too often, I hear people ask questions like “How am I suppose to know where to put ends for statement blocks?” or “Why can’t the computer just infer that I want this piece of code to do something else?”. These questions reflect something that the computer manufacturing industry have done quite successfully. They have succeeded in selling computers as smart general purpose platforms, which is an essential “feature” for about 99% of the computer users out there.

But programmers don’t usually work under these assumptions that a computer is smart. In order to fully understand programming, we need to start off with the fundamentals, that a computer is nothing more than a dumb calculator.

6 February
Posted in Lua

Common set operations

From freshman year textbook, Discrete Mathematics and Its Applications (sixth edition), Chapter 2 asks the reader that given subsets A and B of some superset, implement A union B, A intersect B, A – B, and find the symmetric difference of A and B.

5 February
Posted in Article

Hello world!

For years, my lack of confidence in my own creations have confined me to an online life of anonymity. Only recently have I discovered that other people aren’t all that scary. In fact, I realized that while people can suck sometimes, they’re usually quite decent.

As a lowly freshman struggling through college and life, I sympathize with the thousands of you out there who’re sometimes a little more than intimidated by the programming community. I am one such individual, and I hope that by the time I wear out this journal, I will be able to proudly claim that I am a passably mediocre programmer.