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-commutativityassociativity 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 nth Fibonacci number as
![]()
Linear Recursive Sequence
We derive a general technique for solving full rank linear recursive sequences. Formally, a kth 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,…}
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 32n – 1 is 2n+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 x2 – 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 32n+1 is divisible by 2,but not by 4.
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?
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 2n is the sum of two consecutive odd integers. Furthermore, show that 3n 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 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?
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.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.
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.
