lovely-lucky-lambs (foobar)
This post discusses one of the coding challenges from Google’s foobar program, lovely-lucky-lambs. More specifically, it discusses an error in the official solution to this problem and how this may have occurred.
Category Archives: algorithms
Statistical Attacks on the Autokey Cipher
Letter frequency analysis is a common technique for solving substitution and Vigenère ciphers. In this note, we apply similar techniques to the autokey cipher. This isn’t much harder but appears to be less well-known.
Instructive Examples in Kraitchik’s Method
While discussing the history of the modern factoring, Carl Pomerance’s 1996 expository piece “A Tale of Two Sieves” describes a factoring algorithm called Kraitchik’s Method and demonstrates the algorithm by factoring 2041.
The example is nice; certainly nicer and more illustrative than what you might produce at random. But exactly how special is Pomerance’s 2041 example?
Fractal Sets and Arithmetic Progressions
If a set of positive integers contains no arithmetic progressions, how large can it be? In this post, we study this question in the context of harmonic sums.
On Unparsed Substitution Ciphers
This post discusses the problem of computer-assisted decryption of un-parsed substitution ciphers. Sample Mathematica code is linked within.
Using Groups to Factor Integers
Most factorization algorithms in use today fit in one of two camps: sieve-based methods based on congruences of squares, and algorithms based on decompositions of algebraic groups. In this article, we trace the common thread connecting the latter.
The Forgotten Method of Prosthaphaeresis
In this post, I discuss the method of prosthaphaeresis, a proto-logarithm that enabled celestial navigation for the quarter-century predating the introduction of Napier’s logarithm.
Prime-Generating Polynomials
Just how good are polynomials at producing primes? Do there exist polynomials that produce primes for arbitrarily many consecutive inputs?
In this post, I’ll give a brief overview of what we expect to be able to prove, and show how interpolating polynomials can produce record-breaking prime-generators. (And then break a record, because why not?)
Calendars for the Modern Age
Our modern calendar, the Gregorian calendar, introduced several changes to the Julian calendar, including the introduction of a three-step algorithm for determining leap years.
But just how accurate is the Gregorian model? Can centuries of mathematics and astronomy lead us to a more accurate calendar?
Games of Limited Information (and Topology)
In this post, we’ll look at one-player games of limited information (sometimes classified as puzzles, not games) through a topological lens, and create for each game a poset of topologies under which topologically indistinguishable points correspond to outcomes that are indiscernible in a limited-information context. Expanding this dictionary, we’ll describe a topology on the outcome space under which the “safe” or “warranted” extension of one’s limited information relates to the continuity of certain maps.
a. w. walker 