CodeWords

Transition to New Site

2011-10-26T23:55:00.000-06:00

This blog is now being retired in favor of the notes on my new site, which has an explanation of the transition. This blog will remain but will no longer be updated.

Steve Jobs, Rest in Peace

2011-10-05T22:13:00.001-06:00

Today a great entrepreneur, one of the great American capitalists, Steve Jobs, passed away at the rather young age of 56. As others have said, we are all a bit poorer for it.

I didn't always agree with his style, I wasn't always a fan of his company's products, and I certainly didn't like the personality cult that surrounded him, but I have great respect for the man who believed in what he did, thought big, sought to empower people, and did it with style and aesthetics. He is an inspiration to us all.

Project Euler Problem #102 Solution

2011-09-01T22:08:00.001-06:00

A triangle in $ \mathbb{R}^2 $ contains the origin iff it has two edges such that

one edge intercepts the $ y $-axis at $ b_1 > 0 $, and
the other edge intercepts the $ y $-axis at $ b_2 < 0 $.

Therefore, for each triangle specified in the provided file, we can perform that test:

Finding Files with PowerShell, Part 2

2011-08-29T11:12:00.004-06:00

This version (see Finding Files with PowerShell) gives the full path of the items:

Project Euler Problem #92 Solution

2011-08-18T22:00:00.000-06:00

A brute-force approach works well enough for this problem, too. The code below has the idea:

The LeadsTo extension method on Int32 is where the real work happens:

Project Euler Problem #52 Solution

2011-08-16T22:12:00.003-06:00

Brute-force search is quite effective for this problem. Just go through the integers from $ 1 $ onward, and find the first one that satisfies the criteria. Nota bene: I used C out of nostalgia, just for kicks.

Finding Files with PowerShell

2011-08-16T14:22:00.003-06:00

I miss the UNIX find command in Windows. I could get it with Cygwin or GNUWin32, but that requires littering my machine with extra stuff. So, PowerShell to the rescue:

Reddit's Unique Web Server

2011-07-15T22:44:00.000-06:00

Reddit has quite a unique web server.

How Likely Are You to Be Dealt a Royal Flush?

2011-06-20T08:12:00.006-06:00

In the game of poker, you have a royal flush when you have a 10, J, Q, K, and A all of the same suit. Assuming a uniform random distribution of cards in the deck, what is the probability of being dealt a royal flush?

A royal flush consists of a certain five cards of the same suit. Assume we are dealt one of these cards. Then the suit is determined, and we now need the remaining four cards of that suit. So, let's take the probability of being dealt one of the certain five cards (10, J, Q, K, A) of any suit. Since there are five such cards per suit, and there are four suits (the set of suits is $ \{ \diamondsuit, \heartsuit, \clubsuit, \spadesuit \} $), then we can get any one of those cards to start building a royal flush. Therefore, the probability of getting a starting card is \[ P(\text{starting card}) = \frac{20}{52}. \] Once we have a starting card of a certain suit, our suit is restricted. That is, we may only get the remaining four cards from the same suit as our starting card. Then the probability of getting one of the four cards from the same suit is \[ P(\text{one of the four from the same suit}) = \frac{4}{51}. \] Likewise, after we get the second card, there are three left to get, so the probabilities are $ 3/50 $, then $ 2/49 $, and then $ 1/48 $. What, then, is the probability that we will get all of the necessary cards? It is the product of all these probabilities: \[ P(\text{all}) = \frac{20}{52} \cdot \frac{4}{51} \cdot \frac{3}{50} \cdot \frac{2}{49} \cdot \frac{1}{48} = \frac{1}{649\,740} = 1.539\ldots \times 10^{-6} = 0.000\,153\,9\ldots \%. \] Not very good odds.

Calculating the Number of Trailing Zeros in a Factorial

2011-06-18T21:54:00.007-06:00

The factorial function, denoted $ n! $, where $ n \in \mathbb{Z}^* $, is defined as follows: \[ n! = \begin{cases} 1 & \text{if $n = 0$,} \\ n(n - 1)! & \text{otherwise}. \end{cases} \] In the case of $ n = 10 $, $ 10! = 3\,628\,800 $. Note that that value has two trailing zeros. When $ n = 20 $, $ 20! = 2\,432\,902\,008\,176\,640\,000 $ and has four trailing zeros. Can we devise an algorithm to determine how many trailing zeroes there are in $ n! $ without calculating $ n! $?

Let us define a function $ z : \mathbb{N} \to \mathbb{N} $ that accepts an argument $ n $ that yields the number of trailing zeros in $ n! $. So, using our two examples above, we know that $ z(10) = 2 $ and $ z(20) = 4 $. Now, what is $ z(100) $?

An integer $ a $ has $ k $ trailing zeros iff $ a = b \cdot 10^k $ for some integer $ b $. Now, the prime factors of $ 10 $ are $ 2 $ and $ 5 $. So, what if we consider the prime factors of each factor in a factorial product? For example, consider the first six terms (after $ 1 $) of $ 100! $ and their prime factors. We omit $ 1 $ because of its idempotence: \[ \begin{align} 2 &= 2 \\ 3 &= 3 \\ 4 &= 2^2 \\ 5 &= 5 \\ 6 &= 2 \cdot 3 \\ 7 &= 7 \end{align} \] We see that $ 7! $ contains one $ 5 $ and (more than) one $ 2 $. Therefore, $ 7! $ contains a factor of $ 10 $, so we should expect there to be one trailing zero in $ 7! $. And we see that $ 7! = 5040 $, which does indeed have one trailing zero. This suggests that we could, for any integer $ n $ in $ n! $, cycle through the integers from $ 2 $ to $ n $, finding the prime factorization of each integer, and counting pairs of $ 2 $ and $ 5 $ that we find.

You might have noticed from our example of $ 7! $ that there are four $ 2 $s and only one $ 5 $. Consider that there are $ n/2 $ even factors in $ n! $—that is, every other integer factor of $ n! $, starting at $2$, is even. So there are $ n/2 $ even factors. Each of these has at least one $ 2 $ in its prime factorization, and many of them have more than one. Now consider how many factors of $ 5 $ there are in $ n! $: there are, in fact, $ n / 5 $. So, we can see that, for every $ 5 $ we find in $ n! $, there is a $ 2 $ we can match with it. This suggests that we only need count the $ 5 $s and not the pairs of $ 2 $ and $ 5 $.

This now suggests an algorithm, presented here in Java:

Using this algorithm, we find that $ z(100) = 24 $.

Project Euler Problem #37 Solution

2011-06-10T21:30:00.000-06:00

Here I use the trusted Fermat primality tester. Given the knowledge that there are eleven "truncatable primes," we can stop after we've found those eleven.

Note that at no time does my solution turn candidate numbers into strings.

And I used Java, for old time's sake.

Adobe Reader's Big Problem

2011-06-10T16:27:00.000-06:00

I use PDFs often. Nothing excels them in fidelity of design to documents for which design is important. The Adobe Reader, in its 5.5 days and earlier, was the standard PDF reader of choice. But with version 6, serious bloat occurred, and Adobe Reader is only now, in its latest versions, recovering from that problem. I have a new problem with Adobe Reader, though. Take a look:

This is a document that appears to be made of scanned images placed in text pages, produced by $ \mathrm{\TeX} $. Note how the scanned images appear as completely useless gray boxes. Here is how the document should look, and does look, in other PDF viewers:

I have searched and searched on this matter, but the results are few and old, and whenever I try to employ a solution I do find, it doesn't work.

Project Euler Problem #33 Solution

2011-06-08T20:20:00.000-06:00

In this one, I take advantage of Python's tuple type:

Generate a Zero-Valued UUID

2011-06-06T16:51:00.001-06:00

Say you want a UUID of 00000000-0000-0000-0000-000000000000, but you just want to make one fast, without having to find out the number and grouping of digits. Here's a way to do it:

The Beauty of Scheme

2011-05-27T11:14:00.001-06:00

Bertrand Russell once noted that

Mathematics, rightly viewed, possesses not only truth, but supreme beauty—a beauty cold and austere, like that of sculpture, without appeal to any part of our weaker nature, without the gorgeous trappings of painting or music, yet sublimely pure, and capable of a stern perfection such as only the greatest art can show. The true spirit of delight, the exaltation, the sense of being more than Man, which is the touchstone of the highest excellence, is to be found in mathematics as surely as poetry.

I think much the same can be said of code, especially code written in certain languages. There is something so elegantly simple and beautiful about Scheme (and Racket), for example, that shares the same aesthetics of mathematics.

Project Euler Problem #55 Solution

2011-05-26T20:38:00.013-06:00

"A Lychrel number is a natural number which cannot form a palindrome through the iterative process of repeatedly reversing its base 10 digits and adding the resulting numbers" (Wikipedia). We are given in the problem description that, for the purposes of the problem, any natural number $ n \in \mathbb{N} \cap [0, 10\,000) $ that produces no palindrome in 50 iterations is Lychrel. With that knowledge, a simple recursive test is in order:

~~The flip function is goofy, I know; I'm probably not familiar enough with Racket to reverse a string the "right" way, but it does work.~~

UPDATE: I've improved the flip function to be more Scheme-y.

A Human-Usable URL Parser for Python

2011-05-24T16:44:00.002-06:00

Yes, there is the urlparse module in Python 2.7 and the urllib.parse function in Python 3, but each of them just creates a 6-tuple of URL parts, and it's up to you to know that the query part, for example, is at position 4.

So here's a neat little wrapper around that functionality which gives named fields to each part:

So, to get the query part, you just do parsed_url.query instead of parsed_url[4].

How I Saved My Friends Lots of Money

2011-05-19T22:00:00.001-06:00

Last night I got a phone call from one of my neighbors. She told me that she needed to use some courseware for a class at her university and said that she was unable to use it, and that she was told by someone that she needed to upgrade Windows to use it. They further said that, since a Windows license costs on the order of $200, she should just buy a new laptop. Now, this courseware is a web application—just a web site—yet she was told to get a new laptop. Naturally, my BS-meter went off, and I asked if I could come take a look.

I went over and looked, and saw that the real problem was not that the web site didn’t work—it worked just fine—but that the course documents were Microsoft Word .docx files. Not having Office or any other office apps, she had nothing with which to open them. So, I told her the nature of the problem and installed LibreOffice. Problem solved for $0.

The moral of this story? These points:

“Computer literacy,” so called, is woefully scarce in our society. I don’t really fault my neighbor so much as the yahoo she spoke with who told her such outrageous nonsense.
Professors should make their course documents available as PDFs, which is the proper interchange format for important documents. (What’s interesting about this is that Microsoft Word 2007 and 2010, which use the .docx format natively, make producing PDFs from Word easier than ever before.)

Project Euler Problem #35 Solution

2011-05-19T21:28:00.006-06:00

Using Scala this time, I tackled the problem of finding all of the circular primes less than $ 10^6 $.

A circular prime is a prime number such that every "circular" permutation of its digits is also prime. For example, 197, 971, and 719 are circular primes. The single-digit primes 2, 3, 5 and 7 are considered circular primes for the purposes of this problem. Now, some interesting observations about circular primes:

No circular prime greater than 5 may contain the digits 0, 2, 4, 5, 6, or 8. If some prime $ p > 5 $ were to contain any of these digits, then it would have a circular permutation $ m $ of the form $ 10^n \times d_0 + 10^{n - 1} \times d_1 + \cdots + 10^1 \times d_{n-1} + 10^0 \times d_n $, where $ d_n $ is the offending digit. If the offending digit is 0, 2, 4, 6, or 8, then $ m $ is even and therefore not prime. If the offending digit is 5, then $ m $ is divisible by 5 and therefore not prime. Therefore, only those primes greater than 5 whose digits consist solely of 1, 3, 7, or 9 may be circular primes.
The number 11 is the only two-digit circular prime with one and only one permutation. That is, if you rotate the digits of 11, you get…11. So 11 is a circular prime.

Observation 2 is mainly a curiosity. But Observation 1 allows us to narrow down the numbers we have to examine.

To determine the primality of a number, I use the Fermat Primality Test used previously. Note that this is a probabilistic algorithm, which is to say that it can only tell us whether a number is probably prime. But we can tune it to any degree of certainty (less than 1) by increasing the number $ k $ of rounds. When we use this algorithm, the probability that it falsely tells us that a number is prime is as follows: \[ P(\text{false positive}) < \frac{1}{2^k}. \] In my use of the algorithm here, I chose $ k = 20 $. This yields a probability of correctness of: \[ P(\text{true positive}) > 1 - \frac{1}{2^{20}} = 0.9999990463256836\ldots. \] Good enough for me. So, remembering that I'm new to Scala, here's the code:

Project Euler Problem #34 Solution

2011-03-22T21:39:00.000-06:00

I used an approach similar to that used in Problem 30, as shown in the code below.

Project Euler Problem #30 Solution

2011-03-22T20:46:00.000-06:00

Let $ S : \mathbb{N} \to \mathbb{N} $ be a function that takes a natural number $ n $ and returns the sum of the fifth powers of its digits. Now, let’s consider some properties of this function. Suppose we limit ourselves to four-digit numbers; what is the maximum value of $ S $? It is $ S(9999) = 9^5 + 9^5 + 9^5 + 9^5 = 4 \cdot 9^5 = 236\,196 $. What is the maximum of $ S $ over five-digit numbers? It’s $ S(99\,999) = 5 \cdot 9^5 = 295\,245 $. How about six-digit numbers? $ S(999\,999) = 6 \cdot 9^5 = 354\,294 $. Note that $ S(9999) > 9999 $, $ S(99\,999) > 99\,999 $, but $ S(999\,999) < 999\,999 $. Thus the largest number $ n $ that is equal to the sum of the fifth powers of its digits cannot be more than $ S(999\,999) = 354\,294 $. So, we iterate through the naturals from $ 1 $ to $ 354\,294 $ and add the ones in which $ S(n) = n $, as in the code below.

Project Euler Problem #39 Solution

2011-03-08T19:56:00.000-07:00

A variant of Euclid’s formula for generating Pythagorean triples is
\[
\begin{align}
a &= k(m^2 - n^2) \\
b &= 2kmn \\
c &= k(m^2 + n^2),
\end{align}
\]where $ m $, $ n $, and $ k $ are positive integers and $ m > n $. This will generate all triples, primitive or otherwise, but not uniquely. So, using this formula, I find all of the triples that sum to $ p \in [1, 1000] \cap \mathbb{N} $, count them, and return the value of $ p $ that has the greatest number of solutions.

import itertools class PythagoreanTriple(object): def __init__(self, a, b, c): self._a = a self._b = b self._c = c def __hash__(self): return hash(self._a) * hash(self._b) - hash(self._c) def __eq__(self, other): return (self._a == other._a and self._b == other._b) \ or (self._a == other._b and self._b == other._a) and self._c == other._c def __mul__(self, scalar): return PythagoreanTriple(self._a * scalar, self._b * scalar, self._c *scalar) def sum(self): return self._a + self._b + self._c def __str__(self): return "({0}, {1}, {2})".format(self._a, self._b, self._c) def primitive_pythagorean_triples(): for m in itertools.count(1): for n in range(1, m): yield PythagoreanTriple(m ** 2 - n ** 2, 2 * m * n, m ** 2 + n ** 2) best_p = 0 best_count = 0 for p in range(1, 1001): solutions = set() for triple in primitive_pythagorean_triples(): for scalar in itertools.count(1): scaled = triple * scalar perimeter = scaled.sum() if perimeter == p: solutions.add(scaled) elif perimeter > p: break if triple.sum() > p: break if len(solutions) > best_count: best_count = len(solutions) best_p = p print best_p

Project Euler Problem #12 Solution

2011-02-13T22:11:00.000-07:00

By the use of a theorem and a (relatively) efficient factorization algorithm, we can solve this problem fairly quickly. First, the theorem:

Theorem. If $ n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_s^{\alpha_s} $, with each $ p_s $ prime, then the number of divisors of $ n $, $ d(n) $, is
\[
d(n) = (\alpha_1 + 1)(\alpha_2 + 1) \cdots (\alpha_s + 1) = \prod_{i=1}^s (\alpha_i + 1).
\]This theorem tells us that if we can decompose $ n $ into its prime factors, we can efficiently calculate the number of divisors of $ n $. It remains, therefore, for us to find a suitably efficient factorization algorithm. How about this:

def prime_factorization(n): candidate = 2 while n > 1: factors = [] while n % candidate == 0: factors.append(candidate) n /= candidate if factors: yield factors candidate += 1

This algorithm starts with a divisor of 2 and, if n is divisible by the divisor, it divides n by the divisor as long as n is still divisible by the divisor. When n no longer is, it increments the divisor and tries again until n is reduced to 1. Furthermore, each of the prime factors of n that equal each other are grouped into subsequences. That is, for n = 1701, we get [[3, 3, 3, 3, 3], [7]]. This makes it easier to use the theorem above.

We use a generator function to yield the triangle numbers, and a divisor-counting function that makes use of the theorem above, to get the desired number. All of the code, then, together, is:

def triangle_numbers(): n = 1 while True: yield n * (n + 1) / 2 n += 1 def prime_factorization(n): candidate = 2 while n > 1: factors = [] while n % candidate == 0: factors.append(candidate) n /= candidate if factors: yield factors candidate += 1 def count_divisors(n): count = 1 for tuple in prime_factorization(n): count *= (len(tuple) + 1) return count for t in triangle_numbers(): if count_divisors(t) > 500: print t break

Project Euler Problem #14 Solution

2011-02-11T15:21:00.000-07:00

We calculate the length of each Collatz sequence with starting number
$n \in [1, 10^6) \cap \mathbb{N}$ and find the value of $ n $ for which the length is maximum.

Note that we actually calculate one less than the length of each sequence, but since that subtraction is applied to each length, it doesn't matter.

Project Euler Problem #24 Solution

2011-02-08T13:56:00.000-07:00

This code gets the millionth lexicographic permutation of $ (0, 1, 2, \dots, 9) $: