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

# 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 . We shall look at various algebraic and analytic properties of this sequence, find two algorithms that computes in time, and finally look at a motivating example where we need to compute this sequence quickly and exactly.

# Counting Words

Suppose that we are given the alphabet ; a word of length : , is an ordered -tuple whose elements all came from . For example, a word of length in might be the tuple , which we will hereon denote as . For some natural number , how many words of length are there that contains exactly zeros?

# Annoying Mclaurin Series

Suppose that we’re given the function , find the ordinary generating function associated with it in the form of . Furthermore, find/compute .

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

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

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

# Fixing floating point cancellation I

How can you compute to 14 digits of accuracy within the domain ?

# Floating point quirks

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

Let and . Write a computer program to compute this sum.

# Solving first order PDEs with Characteristics

Use the method of characteristics to solve the PDE system

# Power Reduction in Congruences

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

then

# Even Pascals

Let , where k is an integer. Prove that for any positive integer n the number

is divisible by .

# Sequences in Sequences

Define the sequence recursively by and

Find an explicit formula for in terms of n.

# More Linear Recurrences

Let be defined by the recurrence relation , with . Show that the expression depends only on b and , but not on a.

# Almost Linear

Find the general term of the sequence given by , and

# Polynomial Divisors

Let . Show that for any positive integers there exists unique numbers such that the polynomial is divisible by p(x)

# Analytical Fibonacci

We derive Binet’s equation for the n^{th} Fibonacci number as

# Linear Recursive Sequence

We derive a general technique for solving full rank linear recursive sequences. Formally, a k^{th} linear recursive sequence is defined as

# Odd Coprimes

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

# Interval Scheduling Problem

Let’s consider the *Interval Scheduling Problem*, in which we have a set of n requests ; the request corresponds to an interval of time starting at and finishing at , or request spans interval . 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.

# Prime Congruence Class

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

.

# Sum of Divisors

Suppose we define the function as the sum of the divisors of n

Express in terms of ‘s prime factorization

# That Other Little Gauss Story

Determine the product of distinct positive integer divisors of .

# Congruence by L.C.M

Determine the number of **ordered pairs** of positive integers such that their least common multiple

# Randomly Chosen Divisors

Compute the probability that a randomly chosen positive divisor of is an integer multiple of

# Nothing in common

Let a and b be distinct integers such that . Show that

# The Fib-Fib-Fib Sequence

Consider the sequences , defined recursively by

Show that

# Square Sequence

The sequence satisfies

for all nonnegative integers n,m and . If , determine

# More Sequences

Find a closed form formula for the recurrence relation

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

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

# Infinite GCD

Compute gcd(2002 + 2, 2002^{2}+2, 2002^{3}+2, …)

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

# Maximum Divisor

Prove that the maximum power of 2 divisor of 3^{2n} – 1 is 2^{n+2}

# Counting Primes

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

# Almost Composite

If p and q are primes, and x^{2} – px + q = 0 has distinct positive integer roots, find p and q.

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

# Why not Four?

Let n be a positive integer. Prove that 3^{2n}+1 is divisible by 2,but not by 4.

# In Search of the Magic Pair

Zach has chosen ﬁve 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 ﬁgure out whether the sum of the chosen numbers was even or odd. What is the product of the chosen numbers?

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

# Sum of Consecutive Integers

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

# 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 ﬁrst 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?

# Divisors of Perfect Squares

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

# How to Approximate Like A Boss

1. Find out what 2.001^{5}, 8.6^{2/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.

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

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

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

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

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

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

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

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

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

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

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

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