12 recent entries Archive:
Subtopics:
Comments disabled |
Tue, 28 Jul 2015 A few months ago I wrote an article here called an ounce of theory is worth a pound of search and I have a nice followup. When I went looking for that article I couldn't find it, because I thought it was about how an ounce of search is worth a pound of theory, and that I was writing a counterexample. I am quite surprised to discover that that I have several times discussed how a little theory can replace a lot of searching, and not vice versa, but perhaps that is because the search is my default. Anyway, the question came up on math StackExchange today:
OP opined no, but had no argument. The first answer that appeared was somewhat elaborate and outlined a computer search strategy which claimed to reduce the search space to only 14,553 items. (I think the analysis is wrong, but I agree that the search space is not too large.) I almost wrote the search program. I have a program around that is something like what would be needed, although it is optimized to deal with a few oddly-shaped tiles instead of many similar tiles, and would need some work. Fortunately, I paused to think a little before diving in to the programming.
For there is an easy answer. Suppose John solved the problem. Look at just one of the 7×11 faces of the big box. It is a 7×11 rectangle that is completely filled by 1×3 and 3×3 rectangles. But 7×11 is not a multiple of 3. So there can be no solution. Now how did I think of this? It was a very geometric line of reasoning. I imagined a 7×11×9 carton and imagined putting the small boxes into the carton. There can be no leftover space; every one of the 693 cells must be filled. So in particular, we must fill up the bottom 7×11 layer, and there is no point trying to fill any other layer until the bottom one is filled. So I started considering how to pack the bottommost 7×11×1 slice with just the bottom parts of the small boxes and quickly realized it couldn't be done; there is always an empty cell left over somewhere, usually in the corner. The argument about considering just one face of the large box came later; I decided it was clearer than what I actually came up with. I think this is a nice example of the Pólya strategy “solve a simpler
problem” from For a more interesting problem of the same sort, suppose you have six 2×2x1 slabs. It is possible to pack them into a 3×3x3 box? (There will, of course, be some space left over.)
Mystery of the misaligned lowercase ‘p’
I've seen this ad on the subway at least a hundred times, but I never noticed this oddity before: Specifically, check out the vertical alignment of those ‘p’s: Notice that it is not simply an unusual font. The height of the ‘p’ matches the other lowercase letters exactly. Here's how it ought to look: At first I thought the designer was going for a playful, informal logotype. Some of the other lawyers who advertise in the subway go for a playful, informal look. But it seemed odd in the context of the rest of the sign. As I wondered what happened here, a whole story unfolded in my mind. Here's how I imagine it went down: The ‘p’, in proper position, collided with the edge of the light-colored box, or overlapped it entirely, causing the serif to disappear into the black area. The designer (Spivack's nephew) suggested enlarging the box, but there was not enough room. The sign must fit a standard subway car frame, so its size is prescribed. The designer then suggested eliminating “LAW OFFICES OF”, or eliminating some of the following copy, or reducing its size, but Spivack refused to cede even a single line. “Millions for defense,” cried Spivack, “but not one cent for tribute!” Spivack found the obvious solution: “Just move the up the ‘p’ so it doesn't bump into the edge, stupid!” Spivack's nephew complied. “Looks great!” said Spivack. “Print it!”
I have no real reason to believe that most of this is true, but I find it all so very plausible. [ Addendum: Noted typographic expert Jonathan Hoefler says “I'm certain you are correct.” ]
[ Notice: I originally published this report at the wrong URL. I moved it so that I could publish the June 2015 report at that URL instead. If you're seeing this for the second time, you might want to read the June article instead. ] A lot of the stuff I've written in the past couple of years has been on Mathematics StackExchange. Some of it is pretty mundane, but some is interesting. I thought I might have a little meta-discussion in the blog and see how that goes. These are the noteworthy posts I made in April 2015. Languages and their relation : help is pretty mundane, but interesting for one reason: OP was confused about a statement in a textbook, and provided a reference, which OPs don't always do. The text used the symbol !!\subset_\ne!!. OP had interpreted it as meaning !!\not\subseteq!!, but I think what was meant was !!\subsetneq!!. I dug up a copy of the text and groveled over it looking for the explanation of !!\subset_\ne!!, which is not standard. There was none that I could find. The book even had a section with a glossary of notation, which didn't mention !!\subset_\ne!!. Math professors can be assholes sometimes. Is there an operation that takes !!a^b!! and !!a^c!!, and returns !!a^{bc}!! is more interesting. First off, why is this even a reasonable question? Why should there be such an operation? But note that there *is*an operation that takes !!a^b!! and !!a^c!! and returns !!a^{b+c}!!, namely, multiplication, so it's plausible that the operation that OP wants might also exist.But it's easy to see that there is no operation that takes !!a^b!! and !!a^c!! and returns !!a^{bc}!!: just observe that although !!4^2=2^4!!, the putative operation (call it !!f!!) should take !!f(2^4, 2^4)!! and yield !!2^{4\cdot4} = 2^{16} = 65536!!, but it should also take !!f(4^2, 4^2)!! and yield !!4^{2\cdot2} = 2^4 = 256!!. So the operation is not well-defined. And you can take this even further: !!2^4!! can be written as !!e^{4\log 2}!!, so !!f!! should also take !!f(e^{2\log 4}, e^{2\log 4})!! and yield !!e^{4(\log 4)^2} \approx 2180.37!!. They key point is that the representation of a number, or even an integer, in the form !!a^b!! is not unique. (Jargon: "exponentiation is not injective".) You can raise !!a^b!!, but having done so you cannot look at the result and know what !!a!! and !!b!! were, which is what !!f!! needs to do. But if !!f!! can't do it, how can multiplication do it when it multiplies !!a^b!! and !!a^c!! and gets !!a^{b+c}!!? Does it somehow know what !!a!! is? No, it turns out that it doesn't need !!a!! in this case. There is something magical going on there, ultimately related to the fact that if some quantity is increasing by a factor of !!x!! every !!t!! units of time, then there is some !!t_2!! for which it is exactly doubling every !!t_2!! units of time. Because of this there is a marvelous group homomophism $$\log : \langle \Bbb R^+, \times\rangle \to \langle \Bbb R ,+\rangle$$ which can change multiplication into addition *without*knowing what the base numbers are.In that thread I had a brief argument with someone who thinks that operators apply to expressions rather than to numbers. Well, you can say this, but it makes the question trivial: you can certainly have an "operator" that takes *expressions*!!a^b!! and !!a^c!! and yields the*expression*!!a^{bc}!!. You just can't expect to apply it to numbers, such as !!16!! and !!16!!, because those numbers are not expressions in the form !!a^b!!. I remembered the argument going on longer than it did; I originally ended this paragraph with a lament that I wasted more than two comments on this guy, but looking at the record, it seems that I didn't. Good work, Mr. Dominus.how 1/0.5 is equal to 2? wants a simple explanation. Very likely OP is a primary school student. The question reminds me of a similar question, asking why the long division algorithm is the way it is. Each of these is a failure of education to explain what division is actually doing. The long division answer is that long division is an optimization for repeated subtraction; to divide !!450\div 3!! you want to know how many shares of three cookies each you can get from !!450!! cookies. Long division is simply a notation for keeping track of removing !!100!! shares, leaving !!150!! cookies, then !!5\cdot 10!! further shares, leaving none. In this question there was a similar answer. !!1/0.5!! is !!2!! because if you have one cookie, and want to give each kid a share of !!0.5!! cookies, you can get out two shares. Simple enough. I like division examples that involve giving cookies to kids, because cookies are easy to focus on, and because the motivation for equal shares is intuitively understood by everyone who has kids, or who has been one. There is a general pedagogical principle that an ounce of examples are worth a pound of theory. My answer here is a good example of that. When you explain the theory, you're telling the student how to understand it. When you give an example, though, if it's the right example, the student can't help but understand it, and when they do they'll understand it in their own way, which is better than if you told them how. How to read a cycle graph? is interesting because hapless OP is asking for an explanation of a particularly strange diagram from Wikipedia. I'm familiar with the eccentric Wikipedian who drew this, and I was glad that I was around to say "The other stuff in this diagram is nonstandard stuff that the somewhat eccentric author made up. Don't worry if it's not clear; this author is notorious for that." In Expected number of die tosses to get something less than 5, OP calculated as follows: The first die roll is a winner !!\frac23!! of the time. The second roll is the first winner !!\frac13\cdot\frac23!! of the time. The third roll is the first winner !!\frac13\cdot\frac13\cdot\frac23!! of the time. Summing the series !!\sum_n \frac23\left(\frac13\right)^nn!! we eventually obtain the answer, !!\frac32!!. The accepted answer does it this way also. But there's a much easier way to solve this problem. What we really want to know is: how many rolls before we expect to have seen one good one? And the answer is: the expected number of winners per die roll is !!\frac23!!, expectations are additive, so the expected number of winners per !!n!! die rolls is !!\frac23n!!, and so we need !!n=\frac32!! rolls to expect one winner. Problem solved! I first discovered this when I was around fifteen, and wrote about it here a few years ago. As I've mentioned before, this is one of the best things about mathematics: not that it works, but that you can do it by whatever method that occurs to you and you get the same answer. This is where mathematics pedagogy goes wrong most often: it proscribes that you must get the answer by method X, rather than that you must get the answer by hook or by crook. If the student uses method Y, and it works (and if it is correct) that should be worth full credit. Bad instructors always say "Well, we need to test to see if the student knows method X." No, we should be testing to see if the student can solve problem P. If we are testing for method X, that is a failure of the test or of the curriculum. Because if method X is useful, it is useful because for some problems, it is the only method that works. It is the instructor's job to find one of these problems and put it on the test. If there is no such problem, then X is useless and it is the instructor's job to omit it from the curriculum. If Y always works, but X is faster, it is the instructor's job to explain this, and then to assign a problem for the test where Y would take more time than is available. I see now I wrote the same thing in 2006. It bears repeating. I also said it again a couple of years ago on math.se itself in reply to a similar comment by Brian Scott: If the goal is to teach students how to write proofs by induction, the instructor should damned well come up with problems for which induction is the best approach. And if even then a student comes up with a different approach, the instructor should be pleased. ... The directions **should not begin**[with "prove by induction"]. I consider it a failure on the part of the instructor if he or she has to specify a technique in order to give students practice in applying it.
The annoying boxes puzzle: solution
There are two boxes on a table, one red and one green. One contains a treasure. The red box is labelled "exactly one of the labels is true". The green box is labelled "the treasure is in this box."It's not too late to try to solve this before reading on. If you want, you can submit your answer here:
## Results
66.52% 300 red 25.72 116 not-enough-info 3.55 16 green 2.00 9 other 1.55 7 spam 0.44 2 red-with-qualification 0.22 1 attack 100.00 451 TOTAL One-quarter of respondents got
the right answer, that there is not enough information
given to solve the problem, Two-thirds of respondents said the
treasure was in the red box.
This is wrong. The treasure
is in the green box.
## What?Let me show you. I stated:
The labels are as I said. Everything I told you was literally true. The treasure is definitely not in the red box. No, it is actually in the green box. (It's hard to see, but one of the items in the green box is the gold and diamond ring made in Vienna by my great-grandfather, which is unquestionably a real treasure.) So if you said the treasure must be in the red box, you were simply mistaken. If you had a logical argument why the treasure had to be in the red box, your argument was fallacious, and you should pause and try to figure out what was wrong with it. I will discuss it in detail below.
## SolutionThe treasure is undeniably in the green box. However, correct answer to the puzzle is "no, you cannot figure out which box contains the treasure". There is not enough information given. (Notice that the question was not “Where is the treasure?” but “Can you figure out…?”)
## (Fallacious) Argument
Many people erroneously conclude that the treasure is in the red box,
using reasoning something like the following: |

Order What is the Name of this Book? with kickback no kickback |

Typically the truth or falsity of the labels
**is part of the puzzle conditions**. Here's a typical example,
which I took from Raymond Smullyan's What is the name of this
book? (problem 67a):

… She had the following inscriptions put on the caskets:Notice that the problem condition gives the suitor a certification about the truth of the labels, on which he may rely. In the quotation above, the certification is in boldface.

Gold Silver Lead THE PORTRAIT IS IN THIS CASKET THE PORTRAIT IS NOT IN THIS CASKET THE PORTRAIT IS NOT IN THE GOLD CASKET Portia explained to the suitor that of the three statements, at most one was true.Which casket should the suitor choose [to find the portrait]?

A well-constructed puzzle will always contain such a certification, something like “one label is true and one is false” or “on this island, each person always lies, or always tells the truth”. I went to _What is the Name of this Book?_ to get the example above, and found more than I had bargained for: problem 70 is exactly the annoying boxes problem! Smullyan says:

Good heavens, I can take any number of caskets that I please and put an object in one of them and then write any inscriptions at all on the lids; these sentences won't convey any information whatsoever.(Page 65)

Had I known that ahead of time, I doubt I would have written this post at all.

One respondent referred me to a similar post on lesswrong.

I did warn you all that the puzzle was annoying.

I started writing this post in October 2007, and then it sat on the shelf until I got around to finding and photographing the boxes. A triumph of procrastination!

*[Other articles in category /math/logic]
permanent link*

The annoying boxes puzzle

Here is a logic puzzle. I will present the solution on Friday.

There are two boxes on a table, one red and one green. One contains a treasure. The red box is labelled "exactly one of the labels is true". The green box is labelled "the treasure is in this box."Starting on 2015-07-03, the solution will be here.Can you figure out which box contains the treasure?

*[Other articles in category /math/logic]
permanent link*

In late April I served a residency at Recurse Center, formerly known as Hacker School. I want to write up what I did before I forget.

Recurse Center bills itself as being like a writer's retreat, but for programming. Recursers get better at programming four days a week for three months. There are some full-time instructors there to help, and periodically a resident, usually someone notable, shows up for a week. It's free to students: RC partners with companies that then pay it a fee if they hire a Recurser.

I got onto the RC chat system and BBS a few weeks ahead and immediately realized that it was going to be great. I am really wary about belonging to groups, but I felt like I fit right in at RC, in a way that I hadn't felt since I went off to math camp at age 14. Recurse Center isn't that different from math camp now that I think about it.

The only prescribed duty of a resident is to give a half-hour talk on Monday night, preferably on a technical topic. I gave mine on the history and internals of lightweight hash structures in programming languages like Python and Perl. (You can read all about that if you want to.)

Here's what else I did:

I gave a bunch of other talks: two on Git, one on calculating with continued fractions, one on how the Haskell type inferencer works, one on the topology of data types, one on the Unix process model, one on Alien Horrors from the Dawn of Unix. This was too many talks. I didn't have enough energy and time to prepare all of them properly. On the other hand, a lot of people were very complimentary about the talks and said they were very glad that I gave so many. Also, giving talks is a great way to get people familiar with you so that they won't be shy about talking to you or asking you to work with them. But I think I'll cut it down to one per day next time.

Alex Taipale was inspired by my hash talk to implement hashes synthetically in Python, and I paired with her on that for the first part and reviewed her code a couple of times after. It was really fun to see how she went about it.

Libby Horacek showed me around the text adventure game she wrote in Haskell. I had the first of several strokes of luck here. Libby had defined an input format to specify the room layout and the objects, and I observed that it was very similar to Asherah, a project that another Recurser, Michelle Steigerwalt, had done a couple of years before. I found this out because I read everyone's self-posted bio ahead of time and browsed the interesting-sounding links.

Aditya Mukerjee was implementing Git in Go. He wanted help deciphering the delta format. Later I paired with Aditya again and we debugged his implementation of the code that expanded the deltas back into complete files. I hadn't known any Go but it's easy to pick up.

Geoffrey Gilmore had read my ancient article on how to write a regex matcher. He had written his own implementation in Scala and wanted to show it to me. I didn't know any Scala but the code was very clear. Geoffrey had worked out a clever way to visualize the resulting finite automaton: his automaton object had a method that would dump out its graph in the "dot" language, and he could feed that to Graphviz to get it to draw the graph.

I had a conference with Ahmed Abdalla and Joel Burget about SML. The main question they wanted me to answer: Why might they want to look at SML instead of Haskell? This was a stroke of luck: I was unusually well-prepared to answer this question, having written many thousands of lines of SML since about 1993. My answer was unequivocally that there was no reason, SML was obsolete, because it had big problems which had never been solved, and Haskell had been introduced in part to solve, avoid, or finesse these problems.

For example, nobody knows how to incorporate references into a Hindley-Milner type system. SML has tried at least three methods for doing this over the years. They all suck, and none of them work right. Haskell avoids the whole issue: no references. If you want something like references, you can build a monad that simulates it locally.

I could probably write a whole blog article about this, so maybe another time.

Libby wanted to pair with me again. She offered me a choice: she was building an e-reader, controlled by a Raspberry Pi, and mounted inside an antique book that she had hollowed out. I would have been willing to try this, although I didn't know anything about Raspberry Pi. But my other choice was very attractive: she was reviving KiSS, an ancient Windows paper-doll app that had been current in the 1990s. people had designed hundreds or thousands of dolls and costumes, which were all languishing because nobody wanted to run the app any more. She wanted to reimplement the dress-up program in Javascript, and port the doll and clothing cels to PNG files. Here I had another stroke of luck. I was already familiar with the program, and I think I have even been into its source code at some point.

Libby had found that Gimp could load a KiSS cel, so we looked at the Gimp source code to figure out the file format. She had been planning to use

`libpng`

to turn the cel into a PNG, but I showed her a better way: convert it into a PPM file and feed to to`ppmtopng`

. This saved a lot of trouble! (I have written a little bit about this approach in the past.) Libby hacked in the Gimp code, grafting her PPM file writing code into the Gimp cel reading code in place of Gimp's internal pixmap operations. It worked!I talked to Chris Ball about his GitTorrent project. Chris wants to make a decentralized github that doesn't depend on the GitHub company or on their technical infrastructure. He spent a long time trying to make me understand why he wanted to do the project at all and what it was for. I think I eventually got it. It also transpired that Chris knows way more about BitTorrent than I do. I don't think I was much help to Chris.

Jesse Chen paired with me to fix the layout problems that have been troubling my blog for years. We redid the ancient table-based layout that I had inherited from Blosxom ten years ago, converting it mostly to CSS, and fixed a bunch of scrolling problems. We also fixed it to be legible on a phone display, which it previously wasn't. Thanks Jesse!

I had a discussion with Michelle Steigerwalt about big-

*O*notation and how you figure out what an algorithm's big-*O*-ness is, either from counting lines in the source code or the pseudocode, or from running the algorithm on different-size inputs and timing it. It's fun that you can do the static analysis and then run the program and see it produce the results you predicted.

There was a lot of other stuff. I met or at least spoke with around 90% of the seventy or so Recursers who were there with me. I attended the daily stand-up status meetings with a different group each time. I ate lunch and dinner with many people and had many conversations. I went out drinking with Recursers at least once. The RC principals kindly rescheduled the usual Thursday lightning talks to Monday so I could attend. I met Erik Osheim for lunch one day. And I baked cookies for our cookie-decorating party!

It was a great time, definitely a high point in my life. A thousand thanks to RC, to Rachel Vincent and Dave Albert for essential support while I was there, and to the facilitators, principals, and especially to the other Recursers.

*[Other articles in category /misc]
permanent link*

A lot of the stuff I've written in the past couple of years has been on math.StackExchange. Some of it is pretty mundane, but some is interesting. My summary of April's interesting posts was well-received, so here are the noteworthy posts I made in May 2015.

What matrix transforms !!(1,0)!! into !!(2,6)!! and tranforms !!(0,1)!! into !!(4,8)!!? was a little funny because the answer is $$\begin{pmatrix}2 & 4 \\ 6 & 8 \end{pmatrix}$$ and yeah, it works exactly like it appears to, there's no trick. But if I just told the guy that, he might feel unnecessarily foolish. I gave him a method for solving the problem and figured that when he saw what answer he came up with, he might learn the thing that the exercise was designed to teach him.

Is a “network topology'” a topological space? is interesting because several people showed up right away to say no, it is an abuse of terminology, and that network topology really has nothing to do with mathematical topology. Most of those comments have since been deleted. My answer was essentially: it is topological, because just as in mathematical topology you care about which computers are connected to which, and not about where any of the computers actually are.

Nobody constructing a token ring network thinks that it has to be a geometrically circular ring. No, it only has to be a

*topologically*circular ring. A square is fine; so is a triangle; topologically they are equivalent, both in networking and in mathematics. The wires can cross, as long as they don't connect at the crossings. But if you use something that isn't*topologically*a ring, like say a line or a star or a tree, the network doesn't work.The term “topological” is a little funny. “Topos” means “place” (like in “topography” or “toponym”) but in topology you don't care about places.

Is there a standard term for this generalization of the Euler totient function? was asked by me. I don't include all my answers in these posts, but I think maybe I should have a policy of including all my questions. This one concerned a simple concept from number theory which I was surprised had no name: I wanted !!\phi_k(n)!! to be the number of integers !!m!! that are no larger than !!n!! for which !!\gcd(m,n) = k!!. For !!k=1!! this is the famous Euler totient function, written !!\varphi(n)!!.

But then I realized that the reason it has no name is that it's simply !!\phi_k(n) = \varphi\left(\frac n k\right)!! so there's no need for a name or a special notation.

As often happens, I found the answer myself shortly after I asked the question. I wonder if the reason for this is that my time to come up with the answer is Poisson-distributed. Then if I set a time threshold for how long I'll work on the problem before asking about it, I am likely to find the answer to almost any question that exceeds the threshold shortly after I exceed the threshold. But if I set the threshold higher, this would

*still*be true, so there is no way to win this particular game. Good feature of this theory: I am off the hook for asking questions I could have answered myself. Bad feature: no real empirical support.how many ways can you divide 24 people into groups of two? displays a few oddities, and I think I didn't understand what was going on at that time. OP has calculated the first few special cases:

1:1 2:1 3:3 4:3 5:12 6:15

which I think means that there is one way to divide 2 people into groups of 2, 3 ways to divide 4 people, and 15 ways to divide 6 people. This is all correct! But what could the 1:1, 3:3, 5:12 terms mean? You simply can't divide 5 people into groups of 2. Well, maybe OP was counting the extra odd person left over as a sort of group on their own? Then odd values would be correct; I didn't appreciate this at the time.

But having calculated 6 special cases correctly, why can't OP calculate the seventh? Perhaps they were using brute force: the next value is 48, hard to brute-force correctly if you don't have a enough experience with combinatorics.

I tried to suggest a general strategy: look at special cases, and not by brute force, but try to

*analyze*them so that you can come up with a method for solving them. The method is unnecessary for the small cases, where brute force enumeration suffices, but you can use the brute force enumeration to check that the method is working. And then for the larger cases, where brute force is impractical, you use your method.It seems that OP couldn't understand my method, and when they tried to apply it, got wrong answers. Oh well, you can lead a horse to water, etc.

The other pathology here is:

I think I did what you said and I got 1.585times 10 to the 21

for the !!n=24!! case. The correct answer is $$23\cdot21\cdot19\cdot17\cdot15\cdot13\cdot11\cdot9\cdot7\cdot5\cdot3\cdot1 = 316234143225 \approx 3.16\cdot 10^{11}.$$ OP didn't explain how they got !!1.585\cdot10^{21}!! so there's not much hope of correcting their weird error.

This is someone who probably could have been helped in person, but on the Internet it's hopeless. Their problems are Internet communication problems.

Lambda calculus typing isn't especially noteworthy, but I wrote a fairly detailed explanation of the algorithm that Haskell or SML uses to find the type of an expression, and that might be interesting to someone.

I think Special representation of a number is the standout post of the month. OP speculates that, among numbers of the form !!pq+rs!! (where !!p,q,r,s!! are prime), the choice of !!p,q,r,s!! is unique. That is, the mapping !!\langle p,q,r,s\rangle \to pq+rs!! is reversible.

I was able to guess that this was not the case within a couple of minutes, replied pretty much immediately:

I would bet money against this representation being unique.

I was sure that a simple computer search would find counterexamples. In fact, the smallest is !!11\cdot13 + 19\cdot 29 = 11\cdot 43 + 13\cdot 17 = 694!! which is small enough that you could find it without the computer if you are patient.

The obvious lesson to learn from this is that many elementary conjectures of this type can be easily disproved by a trivial computer search, and I frequently wonder why more amateur mathematicians don't learn enough computer programming to investigate this sort of thing. (I wrote recently on the topic of An ounce of theory is worth a pound of search , and this is an interesting counterpoint to that.)

But the most interesting thing here is how I was able to instantly guess the answer. I explained in some detail in the post. But the basic line of reasoning goes like this.

Additive properties of the primes are always distributed more or less at random unless there is some obvious reason why they can't be. For example, let !!p!! be prime and consider !!2p+1!!. This must have exactly one of the three forms !!3n-1, 3n,!! or !!3n+1!! for some integer !!n!!. It obviously has the form !!3n+1!! almost never (the only exception is !!p=3!!). But of the other two forms there is no obvious reason to prefer one over the other, and indeed of the primes up to 10,000, 611 are of the type !!3n!! and and 616 are of the type !!3n-1!!.

So we should expect the value !!pq+rs!! to be distributed more or less randomly over the set of outputs, because there's no obvious reason why it couldn't be, except for simple stuff, like that it's obviously almost always even.

So we are throwing a bunch of balls at random into bins, and the claim is that no bin should contain more than one ball. For that to happen, there must be vastly more bins than balls. But the bins are numbers, and primes are not at all uncommon among numbers, so the number of bins

*isn't*vastly larger, and there ought to be at least some collisions.In fact, a more careful analysis, which I wrote up on the site, shows that the number of

*balls*is vastly larger—to have them be roughly the same, you would need primes to be roughly as common as perfect squares, but they are far more abundant than that—so as you take larger and larger primes, the number of collisions increases enormously and it's easy to find twenty or more quadruples of primes that all map to the same result. But I was able to predict this after a couple of minutes of thought, from completely elementary considerations, so I think it's a good example of Lower Mathematics at work.This is an example of a fairly common pathology of math.se questions: OP makes a conjecture that !!X!! never occurs or that there are no examples with property !!X!!, when actually !!X!! almost always occurs or

*every*example has property !!X!!.I don't know what causes this. Rik Signes speculates that it's just wishful thinking: OP is doing some project where it would be useful to have !!pq+rs!! be unique, so posts in hope that someone will tell them that it is. But there was nothing more to it than baseless hope. Rik might be right.

[ Addendum 20150619: A previous version of this article included the delightful typo “mathemativicians”. ]

*[Other articles in category /math/se]
permanent link*

[ This page originally held the report for April 2015, which has moved. It now contains the report for June 2015. ]

Is “smarter than” a transitive relationship? concerns a hypothetical "is smarter than" relation with the following paradoxical-seeming property:

most X's are smarter than most Y's, but most Y's are such that it is not the case that most X's are smarter than it.

That is, if !!\mathsf Mx.\Phi(x)!! means that most !!x!! have property !!\Phi!!, then we want both $$\mathsf Mx.\mathsf My.S(x, y)$$ and also $$\mathsf My.\mathsf Mx.\lnot S(x, y).$$

“Most” is a little funny here: what does it mean? But we can pin it down by supposing that there are an infinite number of !!x!!es and !!y!!s, and agreeing that most !!x!! have property !!P!! if there are only a finite number of exceptions. For example, everyone should agree that most positive integers are larger than 7 and that most prime numbers are odd. The jargon word here is that we are saying that a subset contains “most of” the elements of a larger set if it is

*cofinite*.There is a model of this property, and OP reports that they asked the prof if this was because the "smarter than" relation !!S(x,y)!! could be antitransitive, so that one might have !!S(x,y), S(y,z)!! but also !!S(z,x)!!. The prof said no, it's not because of that, but the OP want so argue that it's that anyway. But no, it's not because of that; there is a model that uses a perfectly simple transitive relation, and the nontransitive thing nothing but a distraction. (The model maps the !!x!!es and !!y!!s onto numbers, and says !!x!! is smarter than !!y!! if its number is bigger.) Despite this OP couldn't give up the idea that the model exists because of intransitive relations. It's funny how sometimes people get stuck on one idea and can't let go of it.

How to generate a random number between 1 and 10 with a six-sided die? was a lot of fun and attracted several very good answers. Top-scoring is Jack D'Aurizio's, which proposes a completely straightforward method: roll once to generate a bit that selects !!N=0!! or !!N=5!!, and then roll again until you get !!M\ne 6!!, and the result is !!N+M!!.

But several other answers were suggested, including two by me, one explaining the general technique of arithmetic coding, which I'll probably refer back to in the future when people ask similar questions. Don't miss NovaDenizen's clever simplification of arithmetic coding, which I want to think about more, or D'Aurizio's suggestion that if you threw the die into a V-shaped trough, it would land with one edge pointing up and thus select a random number from 1 to 12 in a single throw.

Interesting question: Is there an easy-to-remember mapping from edges to numbers from 1–12? Each edge is naturally identified by a pair of distinct integers from 1–6 that do not add to 7.

The oddly-phrased Category theory with objects as logical expressions over !!{\vee,\wedge,\neg}!! and morphisms as? asks if there is a standard way to turn logical expressions into a category, which there is: you put an arrow from !!A\to B!! for each proof that !!A!! implies !!B!!; composition of arrows is concatenation of proofs, and identity arrows are empty proofs. The categorial product, coproduct, and exponential then correspond to !!\land, \lor, !! and !!\to!!.

This got me thinking though. Proofs are properly not lists, they are trees, so it's not entirely clear what the concatenation operation is. For example, suppose proof !!X!! concludes !!A!! at its root and proof !!Y!! assumes !!A!! in more than one leaf. When you concatenate !!X!! and !!Y!! do you join all the !!A!!'s, or what? I really need to study this more. Maybe the Lambek and Scott book talks about it, or maybe the Goldblatt Topoi book, which I actually own. I somehow skipped most of the Cartesian closed category stuff, which is an oversight I ought to correct.

In Why is the Ramsey`s theorem a generalization of the Pigeonhole principle I gave what I thought was a terrific answer, showing how Ramsey's graph theorem and the pigeonhole principle are both special cases of Ramsey's hypergraph theorem. This might be my favorite answer of the month. It got several upvotes, but OP preferred a different answer, with fewer details.

There was a thread a while back about theorems which are generalizations of other theorems in non-obvious ways. I pointed out the Yoneda lemma was a generalization of Cayley's theroem from group theory. I see that nobody mentioned the Ramsey hypergraph theorem being a generalization of the pigeonhole principle, but it's closed now, so it's too late to add it.

In Why does the Deduction Theorem use Union? I explained that the English word actually has multiple meanings. I know I've seen this discussed in elementary logic texts but I don't remember where.

Finally, Which is the largest power of natural number that can be evaluated by computers? asks if it's possible for a computer to calculate !!7^{120000000000}!!. The answer is yes, but it's nontrivial and you need to use some tricks. You have to use the multiplying-by-squaring trick, and for the squarings you probably want to do the multiplication with DFT. OP was dissatistifed with the answer, and seemed to have some axe to grind, but I couldn't figure out what it was.

*[Other articles in category /math/se]
permanent link*

Want to work with me on one of these projects?

I did a residency at the Recurse Center last month. I made a profile page on their web site, which asked me to list some projects I was interested in working on while there. Nobody took me up on any of the projects, but I'm still interested. So if you think any of these projects sounds interesting, drop me a note and maybe we can get something together.

They are listed roughly in order of their nearness to completion, with the most developed ideas first and the vaporware at the bottom. I am generally language-agnostic, except I refuse to work in C++.

Or if you don't want to work with me, feel free to swipe any of these ideas yourself. Share and enjoy.

Linogram is a constraint-based diagram-drawing language that I think
will be better than prior languages (like `pic`

, Metapost, or, god
forbid, raw postscript or SVG) and very different from WYSIWYG drawing
programs like Inkscape or Omnigraffle. I described it in detail in
chapter 9 of Higher-Order
Perl
and it's missing only one or two important features that I can't quite
figure out how to do. It also needs an SVG output module, which I
think should be pretty simple.

Most of the code for this already exists, in Perl.

I have discussed Linogram previously in this blog.

Each angle of an orthogonal polygon is either 90° or 270°. All 4-sided orthogonal polygons are rectangles. All 6-sided orthogonal polygons are similar-looking letter Ls. There are essentially only four different kinds of 8-sided orthogonal polygons. There are 8 kinds of 10-sided orthogonal polygons:

There are 29 kinds of 12-sided orthogonal polygons. I want to efficiently
count the number of orthogonal polygons with *N* sides, and have the
computer draw exemplars of each type.

I have a nice method for systematically generating descriptions of all simple orthogonal polygons, and although it doesn't scale to polygons with many sides I think I have an idea to fix that, making use of group-theoretic (mathematical) techniques. (These would not be hard for anyone to learn quickly; my ten-year-old daughter picked them right up. Teaching the computer would be somewhat trickier.) For making the pictures, I only have half the ideas I need, and I haven't done the programming yet.

The little code I have is written in Perl, but it would be no trouble to switch to a different language.

[ Addendum 20150607: the orthogonal polygon sequence is now in OEIS! ]

I want to learn to build Android apps for my Android phone. I think a
good first project would be a utility where you put in a sequence of
letters, say `FBS`

, and it displays all the words that contain those
letters in order. (For `FBS`

the list contains "afterburners",
"chlorofluorocarbons", "fables", "fabricates", …, "surfboards".) I
play this game often with my kid (the letters are supplied by license
plates we pass) and we want a way to cheat when we are stumped.

My biggest problem with Android development in the past has been getting the immense Android SDK set up.

The project would need to be done in Java, because that is what Android uses.

Git is great, but its user interface is awful. The command set is obscure and non-orthogonal. Error messages are confusing. gi is a thinnish layer that tries to present a more intuitive and uniform command set, with better error messages and clearer advice, without removing any of git's power.

There's no code written yet, and we could do it in any language. Perl or Python would be good choices. The programming is probably easy; the hard part of this project is (a) design and (b) user testing.

I have a bunch of design notes written up about this already.

Twingler takes an example of an input data structure and and output data structure, and writes code in your favorite language for transforming the input into the output. Or maybe it takes some sort of simplified description of what is wanted and writes the code from that. The description would be declarative, not procedural. I'm really not at all sure what it should do or how it should work, but I have a lot of notes, and if we could make it happen a lot of people would love it.

No code is written; we could do this in your favorite language. Haskell maybe?

Bonus: Whatever your favorite language is, I bet it needs something like this.

I want a simple library that can render simple pixel graphics and detect and respond to mouse events. I want people to be able to learn to use it in ten minutes. It should be as easy as programming graphics on an Apple II and easier than a Commodore 64. It should not be a gigantic object-oriented windowing system with widgets and all that stuff. It should be possible to whip up a simple doodling program in Crapspad in 15 minutes.

I hope to get Perl bindings for this, because I want to use it from Perl programs, but we could design it to have a language-independent interface without too much trouble.

There are about 17 GUIs for Git and they all suck in exactly the same way: they essentially provide a menu for running all the same Git commands that you would run at the command line, obscuring what is going on without actually making Git any easier to use. Let's fix this.

For example, why can't you click on a branch and drag it elsewhere to rebase it, or shift-drag it to create a new branch and rebase that? Why can't you drag diff hunks from one commit to another?

I'm not saying this stuff would be easy, but it should be possible. Although I'm not convinced I really want to put ion the amount of effort that would be required. Maybe we could just submit new features to someone else's already-written Git GUI? Or if they don't like our features, fork their project?

I have no code yet, and I don't even know what would be good to use.

*[Other articles in category /prog]
permanent link*

Easy exhaustive search with the list monad

(Haskell people may want to skip this article about Haskell, because the technique is well-known in the Haskell community.)

Suppose you would like to perform an exhaustive search. Let's say for concreteness that we would like to solve this cryptarithm puzzle:

```
S E N D
+ M O R E
-----------
M O N E Y
```

This means that we want to map the letters `S`

, `E`

, `N`

, `D`

, `M`

,
`O`

, `R`

, `Y`

to *distinct* digits 0 through 9 to produce a five-digit
and two four-digit numerals which, when added in the indicated way,
produce the indicated sum.

(This is not an especially difficult example; my 10-year-old daughter Katara was able to solve it, with some assistance, in about 30 minutes.)

If I were doing this in Perl, I would write up either a recursive
descent search or a solution based on a stack or queue of partial
solutions which the program would progressively try to expand to a
full solution, as per the techniques of chapter 5 of *Higher-Order
Perl*. In Haskell, we can use the list monad to hide all the
searching machinery under the surface. First a few utility functions:

```
import Control.Monad (guard)
digits = [0..9]
to_number = foldl (\a -> \b -> a*10 + b) 0
remove rs ls = foldl remove' ls rs
where remove' ls x = filter (/= x) ls
```

`to_number`

takes a list of digits like `[1,4,3]`

and produces the
number they represent, 143. `remove`

takes two lists and returns all
the things in the second list that are not in the first list. There
is probably a standard library function for this but I don't remember
what it is. This version is !!O(n^2)!!, but who cares.

Now the solution to the problem is:

```
-- S E N D
-- + M O R E
-- ---------
-- M O N E Y
solutions = do
s <- remove [0] digits
e <- remove [s] digits
n <- remove [s,e] digits
d <- remove [s,e,n] digits
let send = to_number [s,e,n,d]
m <- remove [0,s,e,n,d] digits
o <- remove [s,e,n,d,m] digits
r <- remove [s,e,n,d,m,o] digits
let more = to_number [m,o,r,e]
y <- remove [s,e,n,d,m,o,r] digits
let money = to_number [m,o,n,e,y]
guard $ send + more == money
return (send, more, money)
```

Let's look at just the first line of this:

```
solutions = do
s <- remove [0] digits
…
```

The `do`

notation is syntactic sugar for

```
(remove [0] digits) >>= \s -> …
```

where “…” is the rest of the block. To expand this further, we need
to look at the overloading for `>>=`

which is implemented differently
for every type. The mote on the left of `>>=`

is a list value, and
the definition of `>>=`

for lists is:

```
concat $ map (\s -> …) (remove [0] digits)
```

where “…” is the rest of the block.

So the variable `s`

is bound to each of 1,2,3,4,5,6,7,8,9 in turn, the
rest of the block is evaluated for each of these nine possible
bindings of `s`

, and the nine returned lists of solutions are combined
(by `concat`

) into a single list.

The next line is the same:

```
e <- remove [s] digits
```

for each of the nine possible values for `s`

, we loop over nine value
for `e`

(this time including 0 but not including whatever we chose for
`s`

) and evaluate the rest of the block. The nine resulting lists of
solutions are concatenated into a single list and returned to the
previous `map`

call.

```
n <- remove [s,e] digits
d <- remove [s,e,n] digits
```

This is two more nested loops.

```
let send = to_number [s,e,n,d]
```

At this point the value of `send`

is determined, so we compute and
save it so that we don't have to repeatedly compute it each time
through the following 300 loop executions.

```
m <- remove [0,s,e,n,d] digits
o <- remove [s,e,n,d,m] digits
r <- remove [s,e,n,d,m,o] digits
let more = to_number [m,o,r,e]
```

Three more nested loops and another computation.

```
y <- remove [s,e,n,d,m,o,r] digits
let money = to_number [m,o,n,e,y]
```

Yet another nested loop and a final computation.

```
guard $ send + more == money
return (send, more, money)
```

This is the business end. I find `guard`

a little tricky so let's
look at it slowly. There is no binding (`<-`

) in the first line, so
these two lines are composed with `>>`

instead of `>>=`

:

```
(guard $ send + more == money) >> (return (send, more, money))
```

which is equivalent to:

```
(guard $ send + more == money) >>= (\_ -> return (send, more, money))
```

which means that the values in the list returned by `guard`

will be
discarded before the `return`

is evaluated.

If `send + more == money`

is true, the `guard`

expression yields
`[()]`

, a list of one useless item, and then the following `>>=`

loops
over this one useless item, discards it, and returns yields a list
containing the tuple `(send, more, money)`

instead.

But if `send + more == money`

is false, the `guard`

expression yields
`[]`

, a list of zero useless items, and then the following `>>=`

loops
over these zero useless items, never runs `return`

at all, and yields
an empty list.

The result is that if we have found a solution at this point, a list
containing it is returned, to be concatenated into the list of all
solutions that is being constructed by the nested `concat`

s. But if
the sum adds up wrong, an empty list is returned and `concat`

ed
instead.

After a few seconds, Haskell generates and tests 1.36 million choices for the eight bindings, and produces the unique solution:

```
[(9567,1085,10652)]
```

That is:

```
S E N D 9 5 6 7
+ M O R E + 1 0 8 5
----------- -----------
M O N E Y 1 0 6 5 2
```

It would be an interesting and pleasant exercise to try to implement
the same underlying machinery in another language. I tried this in
Perl once, and I found that although it worked perfectly well, between
the lack of the `do`

-notation's syntactic sugar and Perl's clumsy
notation for lambda functions (`sub { my ($s) = @_; … }`

instead of
`\s -> …`

) the result was completely unreadable and therefore
unusable. However, I suspect it would be even *worse* in Python
because of semantic limitations of that language. I would be
interested to hear about this if anyone tries it.

[ Addendum: Thanks to Tony Finch for pointing out the η-reduction I missed while writing this at 3 AM. ]

[ Addendum: Several people so far have misunderstood the question
about Python in the last paragraph. The question was not to implement
an exhaustive search in Python; I had no doubt that it could be done
in a simple and clean way, as it can in Perl. The question was to
implement *the same underlying machinery*, including the list monad
and its `bind`

operator, and to find the solution using the list
monad.

[ Peter De Wachter has written in with a Python solution that, while not using the list monad, I think clearly demonstrates that the problems I was worried about will not arise, at least for this task. I hope to post his solution in the next few days. ]

*[Other articles in category /prog/haskell]
permanent link*

Another use for strace (isatty)

(This is a followup to an earlier article describing an interesting use of `strace`

.)

A while back I was writing a talk about Unix internals and I wanted to
discuss how the `ls`

command does a different display when talking to
a terminal than otherwise:

`ls`

to a terminal`ls`

not to a terminalHow does `ls`

know when it is talking to a terminal? I expect that is
uses the standard POSIX function `isatty`

. But how does `isatty`

find
out?

I had written down my guess. Had I been programming in C, without
`isatty`

, I would have written something like this:

```
@statinfo = stat STDOUT;
if ( $statinfo[2] & 0060000 == 0020000
&& ($statinfo[6] & 0xff) == 5) { say "Terminal" }
else { say "Not a terminal" }
```

(This is Perl, written as if it were C.) It uses `fstat`

(exposed in
Perl as `stat`

) to get the mode bits (`$statinfo[2]`

) of the inode
attached to `STDOUT`

, and then it masks out the bits the determine if
the inode is a character device file. If so, `$statinfo[6]`

is the
major and minor device numbers; if the major number (low byte) is
equal to the magic number 5, the device is a terminal device. On my
*current* computers the magic number is actually 136. Obviously this
magic number is nonportable. You may hear people claim that those bit
operations are also nonportable. I believe that claim is mistaken.

The analogous code using `isatty`

is:

```
use POSIX 'isatty';
if (isatty(STDOUT)) { say "Terminal" }
else { say "Not a terminal" }
```

Is `isatty`

doing what I wrote above? Or something else?

Let's use `strace`

to find out. Here's our test script:

```
% perl -MPOSIX=isatty -le 'print STDERR isatty(STDOUT) ? "terminal" : "nonterminal"'
terminal
% perl -MPOSIX=isatty -le 'print STDERR isatty(STDOUT) ? "terminal" : "nonterminal"' > /dev/null
nonterminal
```

Now we use `strace`

:

```
% strace -o /tmp/isatty perl -MPOSIX=isatty -le 'print STDERR isatty(STDOUT) ? "terminal" : "nonterminal"' > /dev/null
nonterminal
% less /tmp/isatty
```

We expect to see a long startup as Perl gets loaded and initialized,
then whatever `isatty`

is doing, the write of `nonterminal`

, and then
a short teardown, so we start searching at the end and quickly
discover, a couple of screens up:

```
ioctl(1, SNDCTL_TMR_TIMEBASE or TCGETS, 0x7ffea6840a58) = -1 ENOTTY (Inappropriate ioctl for device)
write(2, "nonterminal", 11) = 11
write(2, "\n", 1) = 1
```

My guess about `fstat`

was totally wrong! The *actual* method is that
`isatty`

makes an `ioctl`

call; this is a device-driver-specific
command. The `TCGETS`

parameter says what command is, in this case
“get the terminal configuration”. If you do this on a non-device, or
a non-terminal device, the call fails with the error `ENOTTY`

. When
the `ioctl`

call fails, you know you don't have a terminal. If you do
have a terminal, the `TCGETS`

command has no effects, because it is a
passive read of the terminal state. Here's the successful call:

```
ioctl(1, SNDCTL_TMR_TIMEBASE or TCGETS, {B38400 opost isig icanon echo ...}) = 0
write(2, "terminal", 8) = 8
write(2, "\n", 1) = 1
```

The `B38400 opost…`

stuff is the terminal configuration; 38400 is the baud rate.

(In the past the explanatory text for `ENOTTY`

was the mystifying “Not
a typewriter”, even more mystifying because it tended to pop up when
you didn't expect it. Apparently Linux has revised the message to the
possibly less mystifying “Inappropriate ioctl for device”.

(`SNDCTL_TMR_TIMEBASE`

is mentioned because apparently someone decided
to give their `SNDCTL_TMR_TIMEBASE`

operation, whatever that is, the
same numeric code as `TCGETS`

, and `strace`

isn't sure which one is
being requested. It's possible that if we figured out which device was
expecting `SNDCTL_TMR_TIMEBASE`

, and redirected standard output to
that device, that `isatty`

would erroneously claim that it was a
terminal.)

[ Addendum 20150415: Paul Bolle has found that the
`SNDCTL_TMR_TIMEBASE`

pertains to the old and possibly deprecated OSS
(Open Sound System)
It is conceivable that `isatty`

would yield the wrong answer when
pointed at the OSS `/dev/dsp`

or `/dev/audio`

device or similar. If
anyone is running OSS and willing to give it a try, please contact me at `mjd@plover.com`

. ]

*[Other articles in category /Unix]
permanent link*

Another use for strace (groff)

The marvelous Julia Evans is always looking for ways to express her
love of `strace`

and now has written a zine about
it. I don't use
`strace`

that often (not as often as I should, perhaps) but every once
in a while a problem comes up for which it's not only just the right
thing to use but the *only* thing to use. This was one of those
times.

I sometimes use the ancient Unix drawing language
`pic`

. Pic has many
good features, but is unfortunately coupled too closely to the Roff
family of formatters (`troff`

, `nroff`

, and the GNU project version,
`groff`

). It only produces Roff output, and not anything more
generally useful like SVG or even a bitmap. I need raw images to
inline into my HTML pages. In the past I have produced these with a
jury-rigged pipeline of `groff`

, to produce PostScript, and then GNU
Ghostscript (`gs`

) to translate the PostScript to a PPM
bitmap, some PPM utilities to crop and
scale the result, and finally `ppmtogif`

or whatever. This has some
drawbacks. For example, `gs`

requires that I set a paper size, and
its largest paper size is A0. This means that large drawings go off
the edge of the “paper” and `gs`

discards the out-of-bounds portions.
So yesterday I looked into eliminating `gs`

. Specifically I wanted to
see if I could get `groff`

to produce the bitmap directly.

GNU `groff`

has a `-T`

*device* option that specifies the "output"
device; some choices are `-Tps`

for postscript output and `-Tpdf`

for
PDF output. So I thought perhaps there would be a `-Tppm`

or
something like that. A search of the manual did not suggest anything
so useful, but did mention `-TX100`

, which had something to do with
100-DPI X window system graphics. But when I tried this `groff`

only said:

```
groff: can't find `DESC' file
groff:fatal error: invalid device `X100`
```

The `groff -h`

command said only `-Tdev use device dev`

. So what
devices are actually available?

`strace`

to the rescue! I did:

```
% strace -o /tmp/gr groff -Tfpuzhpx
```

and then a search for `fpuzhpx`

in the output file tells me exactly
where `groff`

is searching for device definitions:

```
% grep fpuzhpx /tmp/gr
execve("/usr/bin/groff", ["groff", "-Tfpuzhpx"], [/* 80 vars */]) = 0
open("/usr/share/groff/site-font/devfpuzhpx/DESC", O_RDONLY) = -1 ENOENT (No such file or directory)
open("/usr/share/groff/1.22.2/font/devfpuzhpx/DESC", O_RDONLY) = -1 ENOENT (No such file or directory)
open("/usr/lib/font/devfpuzhpx/DESC", O_RDONLY) = -1 ENOENT (No such file or directory)
```

I could then examine those three directories to see if they existed, and if so find out what was in them.

Without `strace`

here, I would be reduced to groveling over the
source, which in this case is likely to mean trawling through the
`autoconf`

output, and that is something that nobody wants to do.

Addendum 20150421: another article about `strace`

. ]

[ Addendum 20150424: I did figure out how to prevent `gs`

from
cropping my output. You can use the flag `-p-P48i,48i`

to `groff`

to
set the page size to 48 inches (`48i`

) by 48 inches. The flag is
passed to `grops`

, and then resulting PostScript file contains

```
%%DocumentMedia: Default 3456 3456 0 () ()
```

which instructs `gs`

to pretend the paper size is that big. If it's
not big enough, increase `48i`

to `120i`

or whatever. ]

*[Other articles in category /Unix]
permanent link*