God plays dice

I had a wonderful vacation in Vienna and Budapest in May.  (Vienna is entirely irrelevant to this story.)

My wife every so often talks about taking a trip to Poland for no particular reason. (Readers: why do I want to visit Poland?)

So I started looking through Wikitravel to answer the above question, and every so often it mentions a price. I need to get the exchange rate to put it in context. So I type “usd to pln” into Google:

In the chart, it looks like the zloty has been appreciating against the dollar. Is that because the dollar has been going down or because the zloty has been going up? Well, let’s see if the forint has made the same move. Type “usd to huf” into Google:

It has! Hmm, I guess the dollar isn’t doing so well in the past few months. You might wonder why I checked the exchange rate for Hungarian forints and not for euros. The reason is because I know the forint was trading at around 275-280 to the dollar in May, whereas I can’t remember what the euro was. It looks like it was around $1.15 US but I used “vacation math” and just treated prices in euros as if they were in US dollars.

And then because I like typing random things into Google, try “pln to huf”:

Is there some currency arbitrage opportunity? Of course not, the math works out perfectly:

Can you even directly trade zloty for forint, or would you end up going via some major currency anyway?

Also, somewhere in Budapest you can see this:

and here’s a closeup of the text at the bottom:

A transcription of the text (sorry if I have introduced any errors):

A Rubik-kocka bármely keverés utan legfeljebb 20 tekerésből kirakható, de az osszetettsége miatt osszesen 43252003274489856000-féle eltérő állás hozható létre. “Mindig van megoldas és nem is csak egy!”(Rubik Ernő)

I do not read Hungarian (nor any language related to it, because there are very few such languages) but I know what this says. I suspect some of you do too.

This week’s “Riddler Classic” puzzle, from FiveThirtyEight:

From Itay Bavly, a chain-link number problem:

You start with the integers from one to 100, inclusive, and you want to organize them into a chain. The only rules for building this chain are that you can only use each number once and that each number must be adjacent in the chain to one of its factors or multiples. For example, you might build the chain:

4, 12, 24, 6, 60, 30, 10, 100, 25, 5, 1, 97

You have no numbers left to place after 97, leaving you with a finished chain of length 12.

What is the longest chain you can build?

It turns out this question is literally as old as I am. Carl Pomerance wrote a paper On the longest simple path in the divisor graph, C. Pomerance, Proc. Southeastern Conf. Combinatorics, Graph Theory, and Computing, Boca Raton, Florida, 1983, Cong. Num. 40 (1983), 291–304. The result of this paper is that if is the length of the longest chain in , then . That is, as gets large, we can’t “use up” a constant fraction of the integers. This paper was dedicated to Erdos on his seventieth birthday.

But the paper is not constructive. The natural thing to do is to think of this as a graph-theory problem. Construct a graph with vertices latex a$ to if . But finding the longest path in a graph is NP-hard.

For example, with this graph appears as follows:

and you can see that 7 is going to cause something of a problem. If we just avoid it we can find the path

9, 3, 6, 1, 4, 8, 2, 10, 5

so . You can also see something of the structure of this problem – numbers which share prime factors cluster together in the graph, and we end up putting numbers with the same prime factors together in the sequence. Here all the multiples of three are at the beginning, all the multiples of two in the middle, and all the multiples of five at the end.

In fact , which we can figure out by arguing around 7. We can’t have a path that has 7 in the middle because 7 has degree 1 in this graph, so if 7 occurs at all it must occur at the start or the end. Without loss of generality let’s say we have a path that starts with 7, of length 10 We must have 7, 1, and then a path in this graph that goes through all eight vertices:

but such a path clearly doesn’t exist – if it existed it would have to go between the two vertices of degree 1, which are 9 and 5, but one can’t navigate properly around 2.

So what to do? I know nothing better than trial and error. We can quickly build the following path of length 30:

64, 32, 96, 48, 16, 8, 24, 72, 36, 12, 4, 2, 6, 18, 54, 27, 9, 81, 3, 1, 5, 15, 45, 90, 30, 10, 60, 20, 40, 80

which basically zig-zags through the 3-smooth numbers (that is, numbers with all factors 2 and 3) and then the numbers you get if you multiply those by 5. Then we want to insert little excursions out along different primes. For example between 3 and 1 we can insert

3, 51, 17, 68, 34, 1

which is essentially the path 3, 1, 4, 2 multiplied by 17. Doing a few of these insertions gives a length-49 sequence

64, 32, 96, 48, 16, 8, 24, 72, 36, 12,
4, 84, 28, 7, 14,
2, 88, 44, 22, 11, 99, 33, 66,
6, 18, 54, 27, 9, 81,
3, 51, 17, 68, 34,
1, 38, 76, 19, 95,
5, 15, 45, 90, 30, 10, 60, 20, 40, 80

where I’ve bolded the newly inserted bits, which go “out along” the primes 7, 11, 17, and 19 respectively. (Don’t ask me what happened to 13.) We can keep hacking away at this, for example sticking some multiples of 25 in between 5 and 15 to get

64, 32, 96, 48, 16, 8, 24, 72, 36, 12,
4, 84, 28, 7, 14,
2, 88, 44, 22, 11, 99, 33, 66,
6, 18, 54, 27, 9, 81,
3, 51, 17, 68, 34,
1, 38, 76, 19, 95,
5, 100, 50, 25, 75, 15, 45, 90, 30, 10, 60, 20, 40, 80

Since there are no 13s in here, let’s put them in. One way to do this is in the second line, which we can replace with the second and third lines here:

64, 32, 96, 48, 16, 8, 24, 72, 36, 12,
4, 56, 14, 42, 21, 84, 28,
7, 91, 13, 39, 78, 26, 52,
2, 88, 44, 22, 11, 99, 33, 66,
6, 18, 54, 27, 9, 81,
3, 51, 17, 68, 34,
1, 38, 76, 19, 95,
5, 100, 50, 25, 75, 15, 45, 90, 30, 10, 60, 20, 40, 80

and this has length 62. Things get trickier now – the idea becomes to look for numbers that aren’t in the sequence but have all their factors small. 63 isn’t in the sequence and it feels insertable, and if we replace 27, 9, 81, 3 with 27, 81, 9, 63, 3 we can do it. A few more little moves like this get us up to length 67:

64, 32, 96, 48, 16, 8, 24, 72, 36, 12,
4, 84, 28, 56, 14, 98, 49,
7, 91, 13, 39, 78, 26, 52,
2, 88, 44, 22, 11, 99, 33, 66,
6, 18, 54, 27, 81,
9, 63, 21, 42,
3, 51, 17, 68, 34,
1, 38, 76, 19, 95,
5, 80, 40, 20, 100, 50, 25, 75,
15, 45, 90, 30, 60, 10, 70, 35

which is the solution I submitted.

The “missing” numbers now are

23 29 31 37 41 43 46 47 53 55 57 58 59 61 62 65 67 69 71 73 74 77 79 82 83 85 86 87 89 92 93 94 97

and you can see what the basic problem ends up being.  All of these have at least one prime factor that’s greater than or equal to 11. Can we squeeze any of these in? In particular 55 and 77 seem like they could be inserted along this basic route, although I can’t figure out how.

The Metropolitan Museum of Art (New York) has an exhibit Picturing Math: Selections from the Department of Drawings and Prints, running from January 31 to May 8.  I was in New York mid-January, and I may have reason to be there again in June or July, so this seems like they’re setting their schedules to toy with me.  Fortunately, you can “view exhibition objects” at their web site or you can look at this article about the exhibit by Allison Meier for Hyperallergic.

I live in Georgia’s sixth congressional district.  As you may have heard, we’re having a special election to replace Tom Price, the new secretary of health and human services.  Price was a popular incumbent, but Trump barely scraped out a win in this district, so there’s a lot of national attention on this race.  And even if there weren’t, Georgia has a system for special elections where everyone will run in a primary (on April 18), and if nobody gets 50% of the vote (which there won’t), then there will be a runoff between the top two candidates on June 20.

And I do mean everyone.  There are 11 declared Republican candidates and 5 declared Democrats.    What little polling there’s been indicates that we should end up with a standard partisan election in June, with Karen Handel (former Secretary of State of Georgia and former candidate for Governor and Senator) for the Republicans, and Jon Ossoff, former congressional aide, current maker of investigative films, and person who is younger than me and therefore unelectable due to things he posted on Facebook, for the Democrats.

But this post is not about politics.  It’s about yard signs.  If I’m not mistaken – and I very well may be mistaken – I’m seeing more yard signs than I did for the presidential election.  Now, I live in an American suburb, which means that there are houses on main roads that people pass by,  and there are houses in subdivisions that nobody drives by unless they live in the subdivision. And I’m noticing that yard signs seem to be more prevalent on the main roads.

Is this true? It’s hard to count and drive at the same time – it’s easy enough to count the signs, but counting the houses is tricky, and without the denominator this would be worthless – and I wouldn’t have been able to get a large enough sample anyway.  But it seems to make sense.  I live on one of those roads that nobody drives down unless they live on it.  If I had a sign, who would see it?   I’m not much for putting up signs anyway, but if I were, I’d be more likely to if I lived on a road where the sign would have more effect. As it turns out, I’m not the only one. The paper Understanding Visible Political Participation: An Analysis of Yard Sign-Displays during the 2008 Presidential Election came up with a model to predict which properties display yard signs, and traffic volume (subjectively coded into six categories from “dead-end” to “major artery” does turn out to be significant.  I found out about this from a Slate article by Sasha Issenberg which rounds up a lot of the research on signs.

By the way, this is one of those things that’s very hard to Google, because the advice on  how to put up signs swamps the research on signs.  But the conventional wisdom seems to agree that signs on busier roads are more valuable.  One sign vendor writes (emphasis added):

1. The most effective way is to combine your dooknocking [sic] with your yard sign recruitment. Target the busiest streets for door to door work first, and for those people who are friendly, ask them if it would be okay to put a sign in the yard.

Perhaps this is why nobody bothers to canvass my neighborhood and offer me a sign.

The Hampshire College Summer Studies in Mathematics program has what it calls an “Interesting Test” that interested students are invited to take as part of their application. Their web page offers a sample of past test problems. One of these, under the heading “Problems which at first seem to lack sufficient information”, is as follows:

From the third term on, each term of the sequence of real numbers is the sum of the preceding two terms; that is, for . If , what is the sum of all the ten terms?

I’d heard this one before (though it’s hard to find a source for things like this – the cloesst I could find was this Math StackExchange question. The solution is as follows: we can write as linear combinations of . In particular we have , where the general term is (we’ll use this later). Here is the th Fibonacci number, where . Adding everything up we get

and doing those sums gives . But , and so the sum is just . For example, consider the sequence with :

which you can easily verify sums to 187. In the case where you actually have the whole sequence, this is a reasonably well-known “arithmetic trick” that one can show grade school children! The HCSSiM version, of course, doesn’t let you see the whole sequence.

But are there similar tricks to this with shorter or longer sequences? That’s usually the way with the Fibonacci numbers; facts about them tend to be parametrizable. A bit of experimentation shows us that with six terms we have

See for example the series ; its sum, 56, is four times its fifth term. And with fourteen terms we have

(I’ll leave you to come up with your own example.) It would appear that we have , where the are the Lucas numbers . Consider the sum of the first terms satisfying a Fibonacci recurrence:

Now we have and . These are both special cases of the identity givnen in Wikipedia, . So we have

.

So the sum of a fourteen-term Fibonacci sequence is equal to a multiple of the ninth term; the sum of a ten-term Fibonacci sequence, a multiple of the seventh term; the sum of a six-term Fibonacci sequence, a multiple of the fifth term. What of a sum of a two-term Fibonacci sequence? We get . Recall — the sum of the first two terms is, trivially, a multiple of the third term.

(I don’t claim this is original. Only that I had some fun thinking about it. That probably means I need to get a life.)

Terry Tao’s open thread for mathematicians on the immigration executive order, not exactly a follow-up to it ought to be common knowledge that Donald Trump is not fit for the presidency of the United States of America. Tao writes:

mathematical research is a transnational activity, in that the specific nationality of individual members of a research team or research community are (or should be) of no appreciable significance for the purpose of advancing mathematics.

Not surprisingly, then, given the current political situation, 90 percent of people identifying themselves as “mathematician” donating money to US political campaigns give to Democrats, according to analysis by Verdant Labs. Only 85 percent of those calling themselves “Professor of Mathematics” do.  One possible explanation is the those identifying as “professor of mathematics” identify more with their position as educators, and education doesn’t have the same “transnational” quality.

You can download the data from the FEC if you want! I suspect there’s something interesting in here… let’s see how my new laptop handles those twenty million records.

And please point me to interesting analysis of FEC data on campaign contributions that’s already been done! A couple things I’ve seen from the data science community:

• Someone named Gary did some analysis in November of 2015, for the 2016 presidential cycle as it had unfolded thus far in Ohio
• Verdant Labs has also looked at the politics of first names .

But there is surprisingly little out there, given that this is such an interesting data set!

If you want to do something more useful than navel-gazing at data, I recently came across Data for Democracy, and Moon Duchin is organizing a summer school on the geometry of redistricting, including some training in being an expert witness in gerrymandering cases. Will someone write the gerrymandr R package?

The Doomsday clock, of the Bulletin of the Atomic Scientists, is back in the news. It’s 11:57:30. It was 11:57; the thirty-second increment is unpresidented [sic]. The amount of time until midnight is supposed to indicate how close we are to, well, Doomsday.

I feel reasonably sure that I’ve seen somewhere a suggestion that the Doomsday clock could be calibrated such that the probability of Doomsday is proportional to the reciprocal of the time towards midnight. If I had to guess this is an idea of Douglas Hofstadter but I don’t have his books at hand right now. (This is annoyingly hard to Google, because the Doomsday argument gets in the way.)

Some people have objected to the thirty-second news as unnecessary fine-tuning. But in this reciprocal view that isn’t so strange; it corresponds to adjusting the probability of Doomsday from, say, one per thirty years to one per twenty-five years. There have been moves from five to six minutes before, to which this is proportional.  Also, the clock was at 11:57; it’s only been at 11:58 once before, after the US and Soviet Union did thermonuclear tests in close temporal proximity in 1953.  So unless they want to say it is literally the worst it has ever been, two and a half minutes to midnight it is.

Here’s the full statement of the Bulletin. They appear to be saving themselves some room:

The board’s decision to move the clock less than a full minute—something it has never before done— reflects a simple reality: As this statement is issued, Donald Trump has been the US president only a matter of days.

Let’s see what happens next year.