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.

Using generating functions to prove that the only sequences which are their own sequence of running averages are the constant sequences

Here's a problem that occurred to me yesterday: consider a sequence of real numbers a₀, a₁, a₂, ... . Let b_k = (a₀ + a₁ + ... + a_k)/(k+1) be the average of the first (k+1) of the a_i. When is a sequence equal to its own sequence of averages? That is, if we see a bunch of numbers, when is it true that every number we see is the average of all the numbers we've seen so far?

Of course the answer is the constant sequences. But can we prove this using generating functions?

It turns out we can. If we have

f(z) = a₀ + a₁ z + a₂ z² + ...

then

f(z)/(1-z) = a₀ + (a₀ + a₁)z + (a₀ + a₁ + a₂) z^2 + ... = b₀ + 2b₁ z + 3b₂ z^2 + ...

and let's call the right-hand side here g(z). What can we do to g(z) to transform it into

h(z) = b₀ + b₁ z + b₂ z² + ... ?

Well, a linear operator that takes the function (of z) z^k to the function (of z) z^k/(k+1) could be applied to g in order to get h. Clearly this is related to integration. In fact the operator

I φ(z) = (1/z) ∫₀^z φ(s) ds

does the trick. So we have

h(z) = I g(z) = (1/z) ∫₀^z f(s)/(1-s) ds.

But remember that we wanted the generating function h of the averages to be just the generating function f of the original sequence. So this gives

f(z) = (1/z) ∫₀^z f(s)/(1-s) ds

and this is in fact a differential equation. Multiply through by z and differentiate both sides to get

z f'(z) + f(z) = f(z)/(1-z).

A bit of rearranging gives

f'(z)/f(z) = 1/(1-z)

and we recognize that the left-hand side is the derivative of log f(z). Integrating both sides gives

log f(z) = log(1-z) + C

where C is a constant of integration, and finally we get f(z) = e^C/(1-z). But this is just the generating function of a constant sequence.

The quadratic equation, Dr. Seuss style

I've been busy, but here's a quick one: The quadratic equation, Dr. Seuss style, by Katie Benedetto. My favorite stanza:

Each value there was, well she renamed each one
Claiming that nice names would make this more fun.
“Variables, well, they’re whatever we wish
So like one, two, red, blue, I’ll call this one “fish”!

This is the antidote to if the IRS had discovered the quadratic formula.

Some thoughts on the mathematics of tax withholding

Here's a question of some practical importance: let's say that I make $2,000 in each of the first six months of the year, and $4,000 in each of the second six months. Will I have more or less tax withheld than if I make $3,000 every month?

(This is inspired by the fact that I taught this summer, and was paid for doing so, but because of the way my contract is written, my pay for the academic year is spread out over twelve months. As a result I got extra-large paychecks over the summer, partially for the work I was doing in the summer and partially for work that I had already done in the previous academic year or will be doing in the next academic year.)

For those not familiar with the US tax system: if your net pay is X you don't get a check for X, but for some smaller amount, because various taxes are withheld. Chief among these is the federal income tax. Now, the federal income tax is not a flat tax, but a progressive tax -- if your income is higher then you pay a larger percentage of your income in tax. Tax returns have to be filled out on a yearly basis, but most people get paid more often than yearly. So the amount of tax withheld is determined, based on the amount of the paycheck and the period that the paycheck is for, in such a way that the total amount of tax withheld is somewhere near the amount that you're expected to owe. (Most Americans actually end up overpaying through this system, and get a small refund back at tax-filing time.)

So say that if you make 36x per year, then your taxes will be f(36x). Then you'd expect that if you make 3x in a given month, you will have f(36x)/12 withheld, for a total of f(36x) over the course of the year.. If instead you make 2x in each of six months and 4x in each of six months, then in each of the months in which you make 2x tax will be withheld as if you make 24x per year, and in each month in which you make 4x tax will be withheld as if you make 48x per year. So total withholding will be

6f(24x)/12 + 6f(48x)/12

or, simplifying, [f(24x) + f(48x)]/2. Call this T'. Is this less than or greater than f(36x), which we'll call T?

We can easily see that T' ≥ T if and only if

f(48x)-f(36x) ≥ f(36x) - f(24x).

That is, T' ≥ T if and only if the amount of extra tax owed when you go from $36,000 to $48,000 is more than the extra amount owed when you go from $24,000 to $36,000. But since marginal tax rates are increasing -- since the tax is progressive -- this is true.

More generally, given progressive taxation, withholding is smallest for a given annual income if that income is spread out exactly evenly throughout the year. This is a consequence of Jensen's inequality. The more unevenly spread out the earnings are, the more money will be withheld.

In reality this is slightly more complicated because there are tax brackets, which are reflected in the withholding formulas, so f is actually piecewise linear (see page 36 of this IRS publication). For example, a single person paid between $883 and $3,050 per month (after subtracting withholding allowances) will have $70.80 + .15(x-$883) withheld from a paycheck of x; a single person paid between $3,050 and $7,142 will have $395.85 + .25(x-$3050) withheld. (Note that putting $3,050 into either of these formulas gives $395.85; the amount withheld is a continuous function of the amount earned.) So if every paycheck is under $3,050, or if every paycheck is over $3,050, then the amount withheld ends up being the same no matter how the pay is distributed. But a person who makes, say, $3,000 in each of two months will have $388.35 withheld from each, for a total of $766.70; a person who makes $2,000 in one month and $4,000 in another will have $238.35 withheld from the first and $633.35 withheld from the second, for a total of $871.70 withheld.

I had known all this intuitively before this afternoon but I'd never bothered to actually write down why it is...

This all applies to people who make varying amounts in differing pay periods from a single job. People who have multiple jobs can be burnt in the withholding process because we have progressive taxation; if you make x in each of two jobs you have less withheld than if you make 2x in a single job. If that's you, be careful.

(I'm not an accountant. None of this should be taken as financial advice.)

God tweets about playing dice

There's a book coming out in November, The Last Testament: A Memoir by God. "God" tweets at TheTweetOfGod, and "He" just twote:

Do you ever lose when you play cards?" Remember Einstein! I play not cards, but dice. And I never lose. The dice are loaded. And so am I.

There you have it, folks. The title of this blog is correct.

867-5309

The number 8,675,309 is the title of a song. It is also a prime number, and as far as I can tell, it's the largest prime number to appear in a song title. According to this list of songs with numbers in the title from Wikipedia (which is currently in the "Wikilists" space because it was deleted from mainstream Wikipedia, larger numbers in song titles are: 9 million, 30 million, 93 million, 100 million, 1 billion, 1 trillion, 1 quadrillion, 1 googolplex, infinity minus one, and infinity.

I'm not surprised to see that most of these are "round numbers", simply because they're easier to say; in particular by inspection they are not prime, since they're all multiples of large powers of 10. But I'm wondering if anybody out there has written a song titled, say, "six billion and one".

(No fair going out and writing such a song.)

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...