Smith’s determinant

Here’s a curious identity I ran across while browsing Knuth’s magnum opus.

\[\left|    \begin{array}{llll}       \gcd(1,1) & \gcd(1,2) & \ldots & \gcd(1, n) \\       \gcd(2,1) & \gcd(2,2) & \ldots & \gcd(2, n) \\       \vdots & \vdots & & \vdots \\       \gcd(n,1) & \gcd(n,2) & \ldots & \gcd(n, n)     \end{array}\right| = \varphi(1) \varphi(2) \cdots \varphi(n) \]

Here gcd(i, j) is the greatest common divisor of i and j, and φ(n) is Euler’s phi function, the number of positive integers less than or equal to n and relatively prime to n.

The more general version of Smith’s determinant replaces gcd(i, j) above with f( gcd(i, j) ) for an arbitrary function f.

As a hint at a proof, you can do column operations on the matrix to obtain a triangular matrix with φ(i) in the ith spot along the diagonal.

Source: TAOCP vol 2, section 4.5.2, problem 42.

On the compulsive reading of news

“Remind me … to write a popular article on the compulsive reading of news. The theme will be that most neuroses and some psychoses can be traced to the unnecessary and unhealthy habit of daily wallowing in the troubles and sins of five billion strangers.”

Robert Heinlein, Stranger in a Strange Land

Too many objects

Around 1990, object oriented programming (OOP) was all the buzz. I was curious what the term meant and had a hard time finding a good definition. I still remember a description I saw somewhere that went something like this:

Object oriented programming is a way of organizing large programs. … Unless your program is fairly large, you will not see any difference between object oriented and structured programming.

The second sentence is no longer true. OOP is not just a high-level organizational style. Objects and method calls now permeate software at the lowest level. And that’s where things went wrong. Software developers got the idea that if objects are good, more objects are better. Everything should be an object!

For example, I had a discussion with a colleague once on how to represent depth in an oil well for software we were writing. I said “Let’s just use a number.”

double depth;

My suggestion was laughed off as hopelessly crude. We need to create depth objects! And not just C++ objects, COM objects! We couldn’t send a double out into the world without first wrapping it in the overhead of an object.

Languages like C# and Java enforce the everything-is-an-object paradigm. You can’t just write a function; you have to write member functions of an object. This leads to a proliferation of “-er” classes that do nothing but wrap a function. For example, suppose you need a function to solve a quadratic equation. You might make it the Solve method on a QuadraticEquationSolver object. That’s just silly. as John Carmack said,

Sometimes, the elegant implementation is a function. Not a method. Not a class. Not a framework. Just a function.

Languages are changing. You can create anonymous functions in C#, for example. You can even create a named function, by creating an anonymous function first and saving it to a named variable. A little wonky, but not too bad.

I imagine when people say OOP is terrible, they often mean that OOP as commonly practiced now goes too far.

Related posts:

Software to slice bread
You wanted a banana but you got a gorilla holding the banana
Wrapping a function in a burkha

Consulting update

Here’s a quick update for those who might be interested in what I’m up to.

These days I’m primarily working on two large projects, one that’s mathematical modeling and other that’s data exploration. I also have a couple smaller projects going on, one in software process improvement and another mathematical modeling project.

I really enjoy what I’m doing. I’ve worked on variety of interesting projects, and that’s important to me. And I’m spending less time now looking for work and more time doing work. (You can never stop looking for work, but for now I can afford to spend less time doing so than I did at first.)

 

Golden strings and the rabbit constant

Golden strings are analogous to Fibonacci numbers, except one uses concatenation rather than addition.

Start with s1 = “1” and s2 = “10”. Then define sn = sn-1 + sn-2 where “+” means string concatenation.

The first few golden strings are

  • “1”
  • “10”
  • “101”
  • “10110”
  • “10110101”

The length of sn is Fn+1, the n+1st Fibonacci number. Also, sn contains Fn 1’s and Fn-1 0’s. (Source: The Glorious Golden Ratio).

If we interpret the sn as the fractional part of a binary number, the sequence converges to the rabbit constant R = 0.7098034428612913…

It turns out that R is related to the golden ratio φ by

R = \sum_{i=1}^\infty 2^{-\lfloor i \phi \rfloor}

where ⌊i φ⌋ is the largest integer no greater than iφ.

Here’s a little Python code to print out the first few golden strings and an approximation to the rabbit constant.

from sympy.mpmath import mp, fraction

a = "1"
b = "10"
for i in range(10):
    b, a = b+a, b
    print(b)

n = len(b)
mp.dps = n
denom = 2**n
num = int(b, 2)

rabbit = fraction(num, denom)
print(rabbit)

Note that the code sets the number of decimal places, mp.dps, to the length of the string b. That’s because it takes up to n decimal places to exactly represent a rational number with denominator 2n.

Related posts:

Oscillating Fibonacci ratios
Recognizing numbers

Three properties of real-world graphs

From Graph Theory in the Information Age by Fan Chung:

Empirically, most real-world graphs have the following properties:

  • sparsity — The number of edges is within a constant multiple of the number of vertices.
  • small world phenomenon — Any two vertices are connected by a short path. Two vertices having a common neighbor are more likely to be neighbors.
  • power law degree distribution — The degree of a vertex is the number of its neighbors. The number of vertices with degree j (or having j neighbors) is proportional to j
    for some fixed constant β.

The seven color map theorem

The famous four color theorem says that any flat map can be colored with four colors so that no two countries that touch at more than a point are the same color. The hard part is to show that four colors are sufficient; it’s easy to show that four colors are necessary.

It’s easier to prove generalizations of the four color theorem to more complex surfaces. These were settled decades before the original four color theorem.

For example, the seven color map theorem says that any map on a torus (doughnut) can be colored using seven colors, and there exists a map that requires seven colors.

Besides the seven color theorem for the torus, there’s an eight color theorem for a surface with two holes, a nine color theorem for a surface with three holes, etc. In fact, there’s an n color theorem for all n at least 7.

From the examples above, it looks like if a surface has g holes (g for genus, what topologists call these holes), the number of colors required is 6 + g. That’s true for g up to 6, but then it fails. The actual theorem is that a surface with g holes requires

\left\lfloor \frac{7 + \sqrt{1+48g}}{2}\right\rfloor

colors where ⌊ x ⌋ is the largest integer no greater than x.

Because the expression above flattens out as a function of g, it will produce all integers greater than 6, and will produce some several times. For example, a map on a surface with 6 holes requires 12 colors, but so does a map on a surface with 7 holes.

Source: Four Colors Suffice: How the Map Problem Was Solved

Some things can’t be done slowly

Keith Perhac mentioned in a podcast that a client told him he accomplished more in three days than the client had accomplished in six months. That sounds like hyperbole, but it’s actually plausible.

Sometimes a consultant can accomplish in a few days what employees will never accomplish, not because the consultant is necessarily smarter, but because the consultant can give a project a burst of undivided attention.

Some projects can only be done so slowly. If you send up a rocket at half of escape velocity, it’s not going to take twice as long to get where you want it to go. It’s going to take infinitely longer.

Related post: A sort of opposite of Parkinson’s law

21st Century C

I ran across a copy of 21st Century C this afternoon. I hadn’t heard of the book, but the title was intriguing.  I wrote more C in the 20th century than the 21st, so my ideas regarding C (sans ++) are out of date. (I’ve written a fair amount of C++ this century, but I have only written C under duress and with difficulty.)

I’ve only skimmed through the book so far, but one thing I like about it is that the first 100 pages are devoted to tools, not the C language per se. There’s a lot more to using any language than the language itself, and I find it harder to learn about tools than languages. It’s hard to know what tools to learn, and what features of those tools to learn first.

No data on the need to bring data

The preface to Elements of Statistical Learning opens with the popular quote

In God we trust, all others bring data. — William Edwards Deming

The footnote to the quote is better than the quote:

On the Web, this quote has been widely attributed to both Deming and Robert W. Hayden; however Professor Hayden told us that he can claim no credit for this quote,and ironically we could find no “data” confirming that Deming actually said this.

Emphasis added.

The fact that so many people attributed the quote to Deming is evidence that Deming in fact said it. It’s not conclusive: popular attributions can certainly be wrong. But it is evidence.

Another piece of evidence for the authenticity of the quote is the slightly awkward phrasing “all others bring data.” The quote is often stated in the form “all others must bring data.” The latter is better, which lends credibility to the former: a plausible explanation for why the more awkward version survives would be that it is what someone, maybe Deming, actually said.

The inconclusive evidence in support of Deming being the source of the quote is actually representative of the kind of data people are likely to bring someone like Deming.

 

Syzygy

Syzygy must be really valuable in some word games. Such an odd little word.

I’ve run into the word syzygy in diverse contexts and wondered what the meanings had in common. According to the Online Etymology Dictionary, the word comes from

Greek syzygia “yoke, pair, union of two, conjunction”

It is used in biology to denote a pairing of chromosomes. Jung uses it to denote a pairing of opposites.

In astronomy it refers to an alignment of three objects in a gravitational system. In math it denotes an alignment of sorts, a linear combination of module generators that sums to 0.

 

Bayes : Python :: Frequentist : Perl

Bayesian statistics is to Python as frequentist statistics is to Perl.

Perl has the slogan “There’s more than one way to do it,” abbreviated TMTOWTDI and pronouced “tim toady.” Perl prides itself on variety.

Python takes the opposite approach. The Zen of Python says “There should be one — and preferably only one — obvious way to do it.” Python prides itself on consistency.

Frequentist statistics has a variety of approaches and criteria for various problems. Bayesian critics call this “adhockery.”

Bayesian statistics has one way to do everything: write down a likelihood function and prior distribution, then add data and compute a posterior distribution. This is sometimes called “turning the Bayesian crank.”

Triangular numbers and simplices

A couple weeks ago I posted a visual proof that

1 + 2 + 3 + \cdots + n = {n+1 \choose 2}

This says that the nth triangular number equals C(n+1, 2), the number of ways to choose two things from a set of n + 1 things.

I recently ran across a similar proof here. A simplex is a generalization of a triangle, and you can prove the equation above by counting the number of edges in simplices.

A 0-simplex is just a point. To make a 1-simplex, add another point and connect the two points with an edge. A 1-simplex is a line segment.

To make a 2-simplex, add a point not on the line segment and add two new edges, one to each vertex of the line segment. A 2-simplex is a triangle.

To make a 3-simplex, add point above the triangle and add three new edges, one to each vertex of the triangle. A 3-simplex is a tetrahedron.

Now proceed by analogy in higher dimensions. To make an an n-simplex, start with an n-1 simplex and add one new vertex and n new edges. This construction shows that the number of edges in an n simplex is 1 + 2 + 3 + … + n.

Another way to count edges is to note that an n-simplex has n+1 vertices and an edge between every pair of vertices. So an n simplex has C(n+1, 2) edges. So C(n+1, 2) must equal 1 + 2 + 3 + … + n.

How to subscribe to a Twitter account via RSS now

Twitter turned off their RSS support last month. This page gives several ways to create new RSS feeds for Twitter accounts.

Update (October 27, 2014): Here is a cost-free and ad-free Android app that is an RSS feed generator for Twitter.

The easiest solution is to create an RSS feed via rss4twitter. Another possibility is to use BazQux RSS reader. Finally, a couple server-side solutions are given here.

Here are links to RSS feeds for my daily tip accounts that were created using rss4twitter.

Math:

AlgebraFact (Algebra, number theory, miscellaneous)
ProbFact (Probability)
Diff_eq (Differential equations)
StatFact (Statistics)
TopologyFact (Topology and geometry)
AnalysisFact (Analysis: real, complex, functional, etc.)

Computing:

CompSciFact (Computer science and programming)
UnixToolTip (Unix command line tools, Emacs, etc.)
SciPyTip (Scientific computing and Python)
RegexTip (Regular expressions)
TeXtip (TeX, LaTeX, and typography)

 

Top five posts this year

These posts have been the most popular for the first half of 2013:

 

Hacking debt
About a deficit of time spent hacking, not tricks for getting out of financial debt.

Extreme syntax
Lisp and Perl take opposite approaches to syntax and both have their advantages.

The weight of code
Some source code used to have physical weight. Code still has metaphorical weight.

Which Unicode characters can you depend on?
Which characters have widespread font support? Not many.

Why j for imaginary unit?
An advantage to using j for √-1 even if you’re not an electrical engineer.