Solution to a puzzle from a few months ago

I never posted a solution to this puzzle, and today one of my students asked me about it.

The puzzle was to find all three-digit numbers that, when multiplied by their successor, give a number concatenated with itself.

So of course when you concatenate a three-digit number x with itself, you get 1001x. So the question becomes: when is k(k+1) a multiple of 1001?

1001 is 7 times 11 times 13. k and k+1 have no prime factors in common, so we have to have that some subset of 7, 11, and 13 are prime factors of k, and the rest are prime factors of k + 1. Furthermore these are going to be proper subsets; if we have that 7, 11, and 13 are prime factors of k and none of those are prime factors of k+1, or vice versa, then we get that k doesn't in fact have three digits.

So we can have the following six situations:

(1) k is a multiple of 7 and k + 1 is a multiple of 143;

(2) k is a multiple of 11 and k + 1 is a multiple of 91;

(3) k is a multiple of 13 and k + 1 is a multiple of 77;

(4) k is a multiple of 77 and k + 1 is a multiple of 13;

(5) k is a multiple of 91 and k + 1 is a multiple of 11;

(6) k is a multiple of 143 and k + 1 is a multiple of 7.

In each case we can then use the Chinese remainder theorem to find k. Let's consider the first case: we have that k ≡ 0 (mod 7), k ≡ -1 (mod 11), k ≡ -1 (mod 13).

The CRT tells us that the solution to the system of congruences

k ≡ a₇ (mod 7), k ≡ a₁₁ (mod 11), k ≡ a₁₃ (mod 13)

is

k ≡ a₇(143)(143^-1)₇ + a₁₁(91)(91^-1)₁₁ + a₁₃ (77)(77^-1)₁₃ (mod 1001)

where I'm using (a^-1)_b to stand for the inverse of a mod b. The other solutions differ from this by multiples of 1001. We can find the inverses by brute force:

(143^-1)₇ = (3^-1)₇ = 5, (91^-1)₁₁ = (3^-1)₁₁ = 4, (77^-1)₁₃ = (12^-1)₁₃ = 12.

So we finally get

k ≡ 715 a₇ + 364 a₁₁ + 924 a₁₃ (mod 1001).

Now, the case (1) corresponds to a₇ = 0, a₁₁ = -1, a₁₃ = -1; so we get

k ≡ 0 - 364 - 924 (mod 1001)

and so we get the solution k = -364 - 924 + (2)(1001) = 714. Indeed (714)(715) = 510510. (714 and 715 are a Ruth-Aaron pair.) The other five situations lead to, respectively, k = 363, 923, 77, 637, 286 and k(k+1) = 132132, 852852, 6006, 406406, 82082.

A puzzle about splitting up numbers into groups

A puzzle from David Radcliffe: "Split {1,2,...,16} into two groups of the same size having equal sums, equal sums of squares, and equal sums of cubes."

Solution: one group is A, D, E, G, J, K, M, P; the other is B, C, E, H, I, L, N, O. (I've replaced each number with the corresponding letter of the English alphabet to obscure things a bit.)

Here's how I found this. It's often useful to look at cubes mod 9, because any cube of an integer is either a multiple of 9, one less than a multiple of 9, or one more than a multiple of 9. These cases correspond to the integer itself being a multiple of 3, one less than a multiple of 3, or one more than a multiple of 3. So 1³ + 2³ + 3³ is a multiple of 9; so are 4³ + 5³ + 6³, ..., 13³ + 14³ + 15³. Since 16³ is one more than a multiple of 9, so is the sum of the first sixteen cubes, which we'll call N.

We want to find eight integers in 1, ..., 16 that have sum of cubes equal to N/2. Now, if N is congruent to 1 mod 9, then N/2 is congruent to 5 mod 9. This means it's relatively far from a multiple of 9, so a lot of the numbers that are one more than a multiple of 9 are going to have to go into the same group. In particular, each group must contain either five more 1 mod 3 than 2 mod 3 integers, or four more 1 mod 3 than 2 mod 3 integers. Keeping in mind the limited supplies -- we only have six integers in our set congruent to 1 mod 3, and five each congruent to 0 and 2 mod 3, the only possible groups are:

≅ 0 (mod 3)	≅ 1 (mod 3)	≅ 2 (mod 3)
3	5	0
1	6	1
4	0	4
2	1	5

Furthermore we either have a group of the type given in the first row and one of the type given in the fourth row, or one of the second-row type and one of the third-row type, in order to meet the supply restrictions.

But it's not possible to have a group of the first-row type and a group of the fourth-row type. Let's consider a group of the fourth-row type -- that is, it has two multiples of three, one number that's one more than a multiple of three, and five that are one less than a multiple of three. The five that are one less than a multiple of three must be 2, 5, 8, 11, and 14. The square of each of these is one more than a multiple of three, so 2² + 5² + 8² + 11² + 14² is congruent to 2 mod 3. Call the other three members of this group x, y, and z. From the table above, two of these are multiples of 3.

But the square of every integer is either 0 mod 3 (if it's a multiple of 3) or 1 mod 3 (if it's not a multiple of 3) and so the sum of the first sixteen squares is 2 mod 3. So each group must have sum of squares congruent to 1 mod 3. The five integers that we've already put in the group have squares summing to 2 mod 3; thus x² + y² + z² is also 2 mod 3, contradicting the fact that exactly one of x, y, and z is not a multiple of 3.

So we must have groups of the type in the second row and of the type in the third row. Let's look at the group of the second-row type. It contains all six integers in {1, 2, ..., 16} congruent to 1 mod 3 -- that's 1, 4, 7, 10, 13, and 16. By symmetry the other two elements -- call them t and u -- must sum to 17. Furthermore the sum of the first 16 squares is (16)(16+1)(2×16+1)/6 = 1496; so the sums of the squares in each group must be 1496/2 = 748. 1²+4²+7²+10²+13²+16² = 591 and so we must have t² + u² = 748 - 591 = 157. So we need two integers that sum to 17, with squares summing to 157; solve the quadratic t² + (17-t)² = 157 to get t = 6 or t = 11, and correspondingly u = 11 or u = 6.

So if there's any way at all to do what we were asked, it's with one group being 1, 4, 6, 7, 10, 11, 13, 16 -- and this checks out.

Of course, it would be trivial to write a program to check this...

A cute number theory puzzle

Today's MAA number of the day, when multiplied by its successor, gives a number concatenated with itself. (Like 455 * 539 = 245245, except 539 isn't the successor of 455.)

Puzzle: find all such three-digit numbers. (The fact that I'm phrasing it this way should indicate to you that there's more than one.)

Meta-puzzle: generalize this. (I have some generalizations in mind.)

The Calkin-Wilf shirt

You can actually buy a shirt with the Calkin-Wilf tree on it. I probably should buy it, if only so I can wear it when I inevitably give a talk on this subject again, either as a stand-alone talk (I've done it twice) or when I teach it in a class.

This is an infinite binary tree of rational numbers. It has 1/1 at the root, and the children of r/s are r/(r+s) and (r+s)/s. It turns out that this tree contains every positive rational number exactly once, giving an explicit enumeration of the rational numbers.

Also -- and this is what's really surprising to me -- let f(n) be the number of ways to write n as a sum of powers of 2, where no power of 2 can be used more than twice. Then (f(0), f(1), f(2), ...) = (1,1,2,1,3,2,3,1,4,3,5,2,5,3,4,...). The sequence of numbers f(n)/f(n+1) are the rational numbers in that tree, in the order which they appear if you traverse each level from left to right.

I learned about the shirt from this mathoverflow thread, where Richard Stanley gives the theorem of the previous paragraph as an example of a theorem with an "unexpected conclusion".

See the original paper by Calkin and Wilf. I've mentioned it before here and here. I think I first heard of this paper from Brent Yorgey's series of posts expanding upon the paper, or perhaps from Mark Dominus' blog. (Somewhat coincidentally, Yorgey and Dominus both live in Philadelphia. I claim this is coincidence, even though Wilf is at Penn, because I don't think either of them heard about the paper from Wilf.)

And can anything nice be said about the number of ways to write n as a sum of powers of 3, where no power of 3 can be used more than three times?

Is zero even?

Did you know that there are actually things to say about whether zero is even or odd (from Wikipedia)? Obviously it is, but the math-ed folks have seriously looked at this.

I found this via a comment by John Thacker at The Volokh Conspiracy. There's a poll there; right now 2% of people have said 0 is odd, 51% even, 43% both, 4% neither. I can kind of understand what's going on with people saying "neither" (perhaps they're getting this from some elementary-school notions), but how is 0 odd?

My answer: yes, zero is even, because it's twice an integer.

(Or because the identity permutation on n letters is an element of the alternating group A_n -- I've been thinking about permutations a lot lately. But if you understand that, you probably are like me, think zero is even, and didn't even think there was anything to discuss.)

Incidentally, sometime recently -- I forget the context -- I saw something that referred to the Gaussian integer a+bi as "uneven" if and only if a and b had different parity.

A number-theoretic tangent for your Saturday afternoon

You may know that 1001 has a simple prime factorization, namely 1001 = (7)(11)(13).

And of course 1000 has a simple prime factorization, namely 1000 = (2³)(5³).

The natural question to ask at this point, to me, is "how often does this happen?" Of course one has to define "this". One question is "how often are there two consecutive numbers that have all their prime factors less than or equal to 13?" There seem to be finitely many, and after I compiled a list I googled a few numbers from it and discovered that David Rusin had also done so. In case you're wondering why I conjecture there are finitely many: the number of integers less than n with all prime factors at most 13 is proportional to (log n)⁶. (The exponent 6 comes from the fact that there are six primes which are 13 or less.) So the "probability" (in the usual heuristic number-theoretic sense) that a given number n is "13-smooth" is the derivative of this, and thus of the order of (log n)⁵/n. The "probability" that two consecutive numbers are "13-smooth" is on the order of the square of this "probability", i. e. (log n)¹⁰n^-2, and the integral of that from, say, 2 to infinity converges. Nothing is special about 13 here; there should be finitely many pairs of consecutive "p-smooth numbers" where p is any prime.

(Rusin's list, by the way, was something he compiled to illustrate how one might calculate logarithms; since 1000 ~ 1001, we can take common logs and get 3 ~ log(7) + log(11) + log(13). Given enough relations like this one can solve for the logarithms themselves.)

Alternatively, we can define the "roughness" of n as (log p)/(log n) where p is the largest prime factor of n. I call it "roughness", not "smoothness", because if it's smaller than the corresponding number is smoother, i. e. has comparatively small prime factors. This naturally compensates for the size of the number; if I recall correctly the proportion of numbers less than n with roughness less than r approaches some limit (a function of r) as n goes to infinity. (I only dabble in analytic number theory so I can't provide a source off the top of my head.)

It seems reasonable then that there should be a similar limit for pairs of consecutive numbers. Then empirically it seems that the probability that n and n+1 both have roughness at most (log 13)/(log 1001) is about 1 in 250. The pairs of numbers that are "at least as round" as (1000, 1001) in this sense are

(80, 81), (224, 225), (1000, 1001), (1715, 1716), (2079, 2080), (2400, 2401), ...

and it seems like about one in 230 pairs of consecutive numbers have this property (4291 in the first million). As is often the case, the interesting thing is that the limiting probability appears to exist and be neither zero nor one.


Postscript: I know some readers will be offended by my use of "probability" in this number-theoretic sense, because the prime factorization of a number is hardly a random object! But I'm a probabilist; this is how I think.

Plats diviseurs, or how the French cut cakes

Apparently in France they have an interesting solution to cake-cutting problems -- a plate with markings on the rim for the proper place to cut into 3, 5, 6, 7, or 9 slices, called the plat diviseur. See also here. You can buy them here; the site is in French. Some especially ornate examples are due to Paul Urfer, who appears to be the original inventor.

I found out about these from The Number Warrior, Jason Dyer. Unfortunately I have no use for one of these, because I live alone, in a small apartment where I couldn't reasonably have enough people over to need a whole cake, and so I do not buy a whole cake at once.

I suspect I have some French readers. Have you seen these before?

A number-theoretic coincidence

An interesting little tidbit from Tanya Khovanova: consider the Pythagorean triple 3² + 4² = 5², in which all three numbers are consecutive, and another similar coincidental-seeming equation 10² + 11² + 12² = 13² + 14². These are the first two elements of a sequence of similar equations, with k+1 squares on the left-hand side and k squares on the right-hand side, which she presents there.

Still perhaps coincidental is the fact that 3² + 4² = 5² and 3³ + 4³ + 5³ = 6³. Of course once you see these it's tempting to check if 3⁴ + 4⁴ + 5⁴ + 6⁴ = 7⁴. (It doesn't.) In fact, for n ≥ 4,

3ⁿ + 4ⁿ + ... + (n+2)ⁿ < (n+3)ⁿ

and here's a proof. I'll prove it for n ≥ 5. It suffices to show that

(3/(n+3))ⁿ + (4/(n+3))ⁿ + ... + ((n+2)/(n+3))ⁿ < 1.

Call the left-hand side f(n). But the last term on the right-hand side is decreasing in n, and for n ≥ 5, is at most 16807/32768 (its value at 5). Now, we can write the left-hand side of the above inequality as

((n+2)/(n+3))ⁿ (1 + ((n+1)/(n+2))ⁿ + (n/(n+2))ⁿ + ... + (3/(n+2))ⁿ)

and each term in the second factor is at most ((n+1)/(n+2))ⁿ times the previous one. So we have

(1 + ((n+1)/(n+2))ⁿ + (n/(n+2))ⁿ + ... + (3/(n+2))ⁿ) > (1 + r + r² + r³ + ...)

where r = ((n+1)/(n+2))ⁿ. Of course the right-hand side of the previous inequality is 1/(1-r). r is positive and decreasing in n, so 1/(1-r) is as well. Since n ≥ 5, 1/(1-r) is bounded above by its value at 5, which is 16807/9031. Thus for n ≥ 5,

f(n) < (16807/32768)(16807/9031)

and the right-hand side is easily checked to be less than 1.

For n = 4 this proof doesn't work, because I threw away a bit too much in bounding the sum of a finite series by the sum of an infinite one, but it's easy to check.

In fact, f(n) approaches 1/(e-1) as n goes to infinity.

Edit (8:41 pm):: See also The Everything Seminar.

A puzzle

2²⁹, expressed in base 10, is a nine-digit number. All nine of its digits are different. Find the digit that is missing without explicitly calculating 2²⁹. (Thanks to Kate for this one; a solution is there, so don't look until you've thought about it.)

When do you learn that the rationals are countable, and the reals aren't?

I'm currently teaching a course "Ideas in Mathematics" in our summer session. This is a course generally taken by students not in technical fields; quickly speaking, my syllabus is some basic number theory, different notions of infinity, some bits of geometry (polyhedra, letting them know that there is such a thing as non-Euclidean geometry, etc.), fractals and chaos, and a smattering of probability. This is a course that's not a prerequisite for anything and the students aren't going into fields where they'll need math, so I, like a lot of other people teaching this class, take the approach of showing them that "math is beautiful" rather than that "math is useful".

So today I'm showing my students that the rationals are countable, first by the standard proof and then by the superior Calkin-Wilf proof. I find the Calkin-Wilf proof aesthetically superior because the "standard" proof, in my opinion, is "really" a proof that the set of pairs of natural numbers is countable; we then just cross off the pairs which aren't in lowest terms as a sort of afterthought. As a result, it's difficult to answer questions like "what's the 1000th rational number in the `standard' enumeration?". Then I will show them that the reals are uncountable, using Cantor's diagonalization argument.

While preparing today's class, I realized that I don't know when I learned that the rationals are countable and the reals are uncountable. Is this even part of the "standard" curriculum for math majors? These feel like facts that I have always known; presumably I picked them up from some popular mathematics book at an early age. Do any of you remember when you learned this?

Odd periods in continued fractions

Here's a question. Why is the period of the quotients in the continued fraction of N^1/2 "usually" even? For example, if N runs over the ninety non-squares less than 100, then only 20 times does the continued fraction expansion of N^1/2 have an odd period. Of the 992 non-squares less than 1024, 157 have an odd period. Of the 9900 squares less than 10⁴, 1322 have an odd period. This is a sign that something is going on under the hood -- naively you'd expect half the periods to be odd.

Arnold has observed this, but only empirically; I first observed it from this problem from Project Euler.

The period of the continued fraction of N^1/2 is odd if and only if x² - Ny² = -1 has solutions in integers. All such integers, it turns out, have no prime factors congruent to 3 mod 4, which is pretty rare for large numbers. (The number of positive integers less than N with no prime factors congruent to 3 mod 4 is about N(log N)^-1/2.) For integers having no prime factors congruent to 3 mod 4, though, a paper of Etienne Fouvry and Jurgen Kluners shows that asymptotically at least 52% of such numbers have odd period, and at most two-thirds do.

The Calkin-Wilf tree on Wikipedia

The Calkin-Wilf tree now has a Wikipedia page. This is an infinite binary tree with rational numbers at the nodes, such that it contains each rational number exactly once. In the sequence of rational numbers that one gets from breadth-first traversal of the tree,

1/1, 1/2,2/1, 1/3, 3/2, 2/3, 3/1, 1/4, 4/3, 3/5, 5/2, 2/5, 5/3, 3/4, 4/1, ...

the denominator of each number is the numerator of the next; furthermore the sequence of denominators (or of numerators) actually counts something. Plus, there are some interesting pictures that come from plotting these sequences, and some interesting probabilistic properties (see arXiv:0801.0054 for some of the probabilistic stuff, although I actually just found it and haven't read it thoroughly) I've given a talk about this; one day I'll write down some version of it. This is one of my favorite mathematical objects.

It looks like we've got David Eppstein to thank for this. It was introduced in this article by Calkin and Wilf.

The large sieve and its applications

You should vote at thebookseller.com for Emmanuel Kowalski's The Large Sieve and its Applications, which has been shortlisted for the "Diagram Prize for Oddest Book Title of the Year". (Apparently "large sieve" sounds like it has something to do with cooking, if you're not a mathematician.)

Divisibility by 7

There's a pretty well-known test for divisibility by seven that came up over coffee today. Namely, to check if a number written in base 10 is divisible by 7, remove the last digit; then subtract twice that digit from the "rest" of the number. The input is divisible by 7 if and only if the output is; since this test makes numbers smaller, that's fine.

For example, 4728402 is divisible by 7. Why? Remove the last digit (2) and subtract its double (4) from the "rest" of the number, giving 472840 - 4 = 472836. Repeating, we get:
47283 - 12 = 47271
4727 - 2 = 4725
472 - 10 = 462
46 - 4 = 42
4 - 4 = 0
which is divisible by 7. (The number isn't special in any way; I just pressed a bunch of number keys and multiplied by 7 to create it.)

But I'd never seen a proof that this works. Here's a quick one. We want to show that 10k + m is divisible by 7 if and only if k - 2m is.

Say 10k + m is divisible by 7. Then 3k+m is, so 10k+m - 3(3k+m) = k-2m is.
Conversely, say k-2m is divisibile by 7. Then 3(k-2m) + 7(k+m) = 10k+m is.

The square root of 3 and mock theta functions. (No, they're not connected.)

Mark Dominus writes about why it really isn't so mysterious that Archimedes had the approximation √3 = 265/153 (which is correct to four decimal places). Apparently historians of mathematics have been mystified by this. Dominus points out that tabulating n² and 3n² for the first few hundred integers would be enough. And it might even be enough to go up to 100 or so, observing where n² and 3m² are close to each other (which gives an approximation √3 ~ n/m), guess the pattern (it comes from the continued fraction of √3, but Archimedes didn't need to know that), and extrapolate. He suggests that's because the historians themselves weren't so good at arithmetic. Many of these historians date from the late 19th and early 20th century, after when mathematics generally turned more abstract and before computers existed, so it's plausible. If I were a historian I'd have something serious and insightful to say about this.

A more general question: if you're trying to work out the history of mathematics by examining the original sources, how important is it to be a good mathematician? I saw a lecture by George Andrews last week on Ramanujan's lost notebook; he and Bruce Berndt are working on an edited version of it (first volume, second volume, review of first volume in the October 2006 Bulletin of the AMS). Andrews happened to be looking through some papers at the library of Trinity College, Cambridge, when he came across these papers. The manuscript conventionally called "Ramanujan's lost notebook" consists of many pages of formulas and almost no words and is concerned with mock theta function; Andrews claims that he would not have recognized the significance of what he was looking at had he not wrote a PhD thesis on mock theta functions.

On birthdays

Yesterday, my age was a factorial.

Today, my age is a square.

This raises an interesting problem.

How could you guess the formula for the sum of the first n fifth powers?

The following three formulae are reasonably well known:

1 + 2 + 3 + ... + n = n(n+1)/2

1² + 2² + 3² + ... + n ² = n(n+1)(2n+1)/6

1³ + 2³ + 3³ + ... + n ³ = (n(n+1)/2)²

(The sums of first and second powers arise pretty often naturally; the sum of cubes is rare, but it's easy to remember because the sum of the first n cubes is the square of the sum of the first n natural numbers.)

The first member of this series I can't remember is the following:

1⁴ + 2⁴ + 3⁴ + ... + n ⁴ = n(n+1)(2n+1)(3n²+3n-1)/30

and generally, the sum of the first n kth powers is a polynomial of degree k+1.

I ran into these formulas, which I'd seen plenty of times before while perusing the book Gamma: Exploring Euler's Constant by Julian Havil, which I had heard of a few years ago, forgotten about, and then found while browsing the library shelves. (Also in German, under the title GAMMA: Eulers Konstante, Primzahlstrände und die Riemannsche Vermutung.) This is a most interesting book, at least if you're someone like me who pretends to know number theory but really doesn't.

Anyway, back to the main story. Say I wanted to know the sum of the first n fifth powers. Well, there's a general method for finding the formula of the first k powers; it involves the Bernoulli numbers. But let's say I didn't know that. Let's say somebody hands me the sequence

1, 33, 276, 1300, 4425, 12201, 29008, 61776, 120825, 220825

in which the nth term, s_n, is the sum 1⁵ + 2⁵ + ... + n⁵ -- but doesn't tell me that's where the sequence comes from -- and challenges me to guess a formula for it in "closed form". (Smart-asses who will say that there are infinitely many formulas are hereby asked to leave.) How would I guess it?

Well, it can't hurt to find factorizations for these numbers. And if you do that you get

1, 3¹ 11¹, 2² 3¹ 23¹, 2² 5² 13¹, 3¹ 5² 59¹, 3¹ 7² 83¹, 2⁴ 7² 37¹, 2⁴ 3³ 11¹ 13¹, 3³ 5² 179¹, 5² 11² 73¹

and this seems interesting; these numbers seem to have lots of small factors. Furthermore, a fair number of them seem to have one largeish prime factor, which I've bolded. (Yes, I realize, 11 times 13 isn't prime, but I actually did think of it as a large factor.) What are the large factors that I observe in these numbers? They are

?, 11, 23, ?, 59, 83, ?, 143, 179, ?

and the nth of these is easily seen to be 2n² + 2n - 1. (Some terms don't show up from inspection of the factorizations because they get "lost in the noise", as it were.)

From there the rest is pretty easy. We see that often (but not always), s_n is divisible by 2n² + 2n - 1. You can check that for n = 1, 2, ..., 10, the term s_n is always divisible by (2n² + 2n - 1)/3. So now consider the sequence t_n = s_n / ((2n² + 2n - 1)/3). The numbers t₁ through t₁₀ are

1, 9, 36, 100, 225, 441, 784, 1296, 2025, 3025

and I recognized that all of these are squares; in particular t_n = (n(n+1)/2)².

Putting everything together, I get the conjecture that the sum of the first n fifth powers

s_n = n²(n+1)²(2n²+2n-1)/12

which could be proven by induction, but actually writing out the proof is best left to undergrads.

The method here is reminiscent of Enumeration of Matchings: Problems and Progress by James Propp. In that article, Propp lists various unsolved problems in the enumeration of tilings, and conjectures that some of them might have answers which are given by simple product formulas, because actually counting the tilings in question gave numbers with nice prime factorizations.

Edit, 9:13 pm: of course this is not the only method, or even the best method; it's just the method I played around with this morning. See the comments for other methods.

Classification is hard, and libraries are not perfect

When I go to the library, even if it's just to get a specific book, I tend to browse a bit. I've found some interesting books this way.

So I was just there, and Anatomy of Integers, the proceedings of this conference, was shelved near the calculus textbooks. In particular, it was near various books that collect integrals. "Anatomy of integers" is a name that seems to be used for a certain branch of number theory that looks at the distribution of prime factors; for a nice introduction to the concept, see Andrew Granville's anatomy of integers and permutations. (This paper, still in development, talks about the analogy between the prime factorizations of integers and cycle structure of permutations. For example, the distribution of the number of cycles of a random permutation of {1, 2, ..., n} is approximately normal with mean and variance near log n; the Erdos-Kac theorem says that the distribution of the number of prime factors of a random integer less than or equal to eⁿ is asymptotically normal with mean and variance near log n. Lots of results about prime factorizations or about permutations seem to have counterparts in the other realm. Anyway, this isn't calculus! But it was with the calculus books.

Similarly, I found a book entitled Mathematical Essays: In Honor of Su Buchin, which was a volume of mathematical research articles in honor of the Chinese differential geometer Su Buchin, shelved with various books that consist of reflections by mathematicians on mathematics -- the sort of nontechnical writing that "essay" usually means.

Is there something wrong with Penn's library? Not at all. They were in the right place according to the Library of Congress Classification, but whoever does that classification seems to make the occasional error. Of course the reasons for these particular errors were obvious from the titles, which is why I spotted them. I am not sure if the classification is done by people who aren't familiar with mathematics; that would explain the integer/integral mistake, at least.

A quirk of electoral apportionment

I was curious: how will the electoral vote apportionment change between now and 2012? (Reapportionment is done after each census, and censuses take place in years divisible by 10; the apportionment takes effect the year after the census. Thus the 2004 and 2008 presidential elections were done under one apportionment, and the 2012, 2016, and 2020 elections will be done under another one.)

I don't know (my first attempt at programming the apportionment gave some really strange-looking results) but I wanted to share an amusing fact.

Each of the 50 states receives a number of electoral votes equal to its number of Representatives, plus two. So the question is really one of determining the number of Representatives that each state gets. The way this works is as follows. First, each state receives one seat. Then, let the populations of the states be P₁, P₂, ..., P₅₀; let

Q_i,j = P_i / (j(j-1))^1/2

for 1 ≤ i ≤ 50 and all positive integers j. Sort these numbers, and take the 385 largest of these numbers. Now state i (the state with population P_i) gets r = r_i representatives, where r is the unique integer such that Q_i,r is one of the 385 largest Q's, and Q_i,r+1 is not. (385 is 435-50; 435 is the number of seats in the House of Representatives, and 50 seats were already assigned in the previous step, one for each state.) Essentially, this assigns the seats in the House "in sequence", so we can speak of the 51st seat, 52nd seat, ..., 435th seat.

So what if there's a tie for 385th place in that ordering? This can occur, of course, if two states have the same population, and I bet some tiebreaker is written into the law. But what if two states have different populations, but after dividing by the square root factor, two of the Q_i,j are the same? Surprisingly, this can happen. Let P₁ = 6P₂. Then it's not hard to see Q_1,9 = Q_2,2; that is, state 1 gets its ninth seat "simultaneously with" state 2 getting its second seat. More generally, if

P₁ / (m(m-1))^1/2 = P₂ / (n(n-1))^1/2

then state 1 gets its mth seat simultaneously with state 2 getting its nth seat. Note that P₁/P₂ is rational. So a tie can only occur when (m(m-1)/n(n-1))^1/2 is rational; when does this happen?

When n = 2, this amounts to asking when (m(m-1)/2) is a square; this happens for m = 2, 9, 50, ... (the indices of the square-triangular numbers in the sequence of triangular numbers) So one state can receive its second seat at the same time another one gets its 9th seat, its 50th seat, ... if the larger state has 6, 35, ... times the population of the smaller one.

Somehow I doubt the law covering apportionment has a provision for this. I suspect the provision taken would be similar to what happens if there's a tie in an election; I know there are some jurisdictions that just flip a coin in that case.

Edit, 10:53 pm: Boris points out in the comments that somebody's done the projection. Texas gains 4, Florida and Arizona each gain 2; the Carolinas, Georgia, Utah, Nevada, and Oregon each gain 1. New York and Ohio each lose 2; Massachusetts, New Jersey, Pennsylvania, Michigan, Illinois, Minnesota, Iowa, Missouri, Louisiana, and California each lose 1. At first glance this shift seems like it would favor the Republicans in the presidential race; nine of the seats created are in states that voted for McCain in '08, and only two of the seats destroyed are. But I'm not sure about this analysis; states are made of people, so as a state's population grows or shrinks its political makeup changes as well. Maybe Nate Silver will have something to say about this?

Interesting fact of the day

The number of ways to write n as a sum of powers of 2, where each summand occurs at most three times, is (n/2) + 1 rounded down. See the 1983 Putnam exam, problem B2 (link goes to a solution, so don't go there if you want to think about the problem yourself!) I learned this from Bruce Reznick's paper "Some binary partition functions".

Of course, if we replace "three" by "one", the analogous problem is trivial -- it's just saying that the binary expansion of an integer is unique. If "three" is replaced by "two", we get an interesting sequence: let b(n) be the number of ways to write n as a sum of powers of two where each summansd occurs at most three times. So for example b(14) = 4, since we can write 14 as 8 + 4 + 2, 8 + 4 + 1 + 1, 8 + 2 + 2 + 1 + 1, or 4 + 4 + 2 + 2 + 1 + 1. I've alluded to this sequence before in comments. Starting with b(0), the sequence of b(n) is

1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, 1, 5, 4, 7, ...

and we can make rational numbers out of these by taking b(n)/b(n+1):

1/1, 1/2, 2/1, 1/3, 3/2, 2/3, 3/1, 1/4, 4/3, 3/5, 5/2, 2/5, 5/3, 3/4, 4/1, 1/5, 5/4, 4/7, ...

and it turns out this sequence includes each rational number exactly once! Neil Calkin and Herb Wilf wrote about this in their paper Recounting the rationals, which you should read. I first learned about this paper from Brent Yorgey's series of posts.