Sunday, July 8, 2018

Nearest Neighbors (Word Game)

Using the word aced, we could create the word acceded by starting with the letter a and successively choosing nearest-neighbor letters. We are allowed to choose a given letter twice in succession if we want to make a double letter.

The animation shows how to get from aced to acceded:



We will consider the leftmost letter and rightmost letter in a word to be nearest neighbors, as if the word were wrapped around the outside of a cardboard paper-towel tube. So for example, using the word nose, we could create the word oneness by starting with the letter o and successively choosing nearest-neighbor letters (and doubling letters from time to time as needed).

The animation shows how to get from nose to oneness:



Here are some puzzles of this type. In each puzzle, use the given word to create a new word of the indicated length by successively choosing nearest-neighbor letters and doubling letters where needed. Note: the puzzles are listed in alphabetical order by the solution word.

named →  __  __  __  __  __  __  __  __

piles →  __  __  __  __  __  __  __  __

rage →  __  __  __  __  __  __

tinges →  __  __  __  __  __  __  __  __  __

damned →  __  __  __  __  __  __  __  __

tine →  __  __  __  __  __  __  __  __

lesion →  __  __  __  __  __  __  __  __  __

pyre →  __  __  __  __  __  __  __

peso →  __  __  __  __  __  __  __  __  __

rite →  __  __  __  __  __  __  __

siesta →  __  __  __  __  __  __  __  __

noise →  __  __  __  __  __  __  __

fate →  __  __  __  __  __  __  __

atom →  __  __  __  __  __  __

rest →  __  __  __  __  __  __  __

flower →  __  __  __  __  __  __  __  __

swing →  __  __  __  __  __  __  __  __





Sunday, July 1, 2018

Four by Jennifer Egan


This past winter I spent a quiet week in Montreal. The weather was scrumptiously awful, and in the snowbound cafés of Old Montreal I got a lot of reading done, including two novels by Jennifer Egan: 2011's A Visit from the Goon Squad, which won the Pulitzer Prize, and last year's Manhattan Beach, which had been well reviewed in NYRB and which a lot of friends seemed to be reading. As usual I lost various belongings in taxis / cafés / hotel, so that in total by the end of the vacation I had actually bought two copies of Goon Squad and three copies of Manhattan Beach. Returning from Montreal, I immediately read two more Egan novels, 2011's Look at Me and 2006's The Keep.

I would recommend reading any of the four books. I might not recommend reading all of them, however, because—a credit to the author—these novels differ so much that any given reader likely has a best choice or two, depending on taste. Below, some notes on the novels with links to professional reviews if you'd like to follow up. (Reviews may have spoilers.)


Manhattan Beach. The most purely pleasurable book among the four. Many reviewers have sensed hidden depths in its themes and construction, but even its apparent depths are engrossing. I enjoyed its genre-play and its fresh, beautiful language. If I end up rereading Manhattan Beach, it will be so I can better understand the role of the protagonist's sister—the author's treatment of whom is one of the places where she most powerfully departs from narrative convention and cliché. Read a review. Buy it on Amazon.






Look at Me. Egan flirts with "being Egan" by including a private detective character, but this book is more of a standard 'serious novel' committed to realism and genrelessness. I dog-eared some pages to mark passages of lovely language, but not as many as in the other books. There's an unforgettable scene in which the protagonist is returning to modeling for the first time…those half-dozen pages are as good as writing gets. Read a review. Buy it on Amazon.







The Keep. The horror elements of this book were delicious. If, as a teenager, you had played a nasty prank on a cousin, leaving him trapped deep in a pitch-dark cave during a family picnic, after which he was forever changed, would you accept your cousin's invitation later in life to help him renovate a crumbling castle in Europe? I think not, and I can already hear you shouting "GET OUT!" at the main character when he arrives at the castle gate. But as good as Egan's sense of the macabre may be, she isn't confined by it; larger themes emerge in the book, including themes of isolation and being part of a modern society in which we are always reachable. Read a review. Buy it on Amazon.




A Visit from the Goon Squad. The most artistically daring of the four. For the most part, A Visit from the Goon Squad presents as a competent version of the Great American Novel (told from inside the music industry as it evolves from the Punk/youth vinyl era to the corporate digital age), but there comes a point suddenly when you find yourself reading dozens of pages in the form of Powerpoint slides! And then Egan pushes the ending out past the present to make the book partly a work of speculative fiction. There are some crazy and impressive choices here. Don't expect the book to cater to you. Read a review. Buy it on Amazon.




Having read four books by an author in one year, the temptation is irresistible to draw comparisons and make generalizations. I noticed for example that Egan favors a novel structured in Parts, with the final Part sometimes surprisingly brief. She doesn't mind introducing new characters late in the novel, even letting them take major roles in the final phases of the plot. Both proclivities can make for an unsatisfying ending to a book. On the other hand, a magically satisfying ending is essential only in a piece of escapist literature (and when I hear people complaining about endings, I wonder if they view all reading as escapist).

Egan wants to use words in a slantwise fashion, and this is mostly successful but not always. The prose is rocky in the opening pages of A Visit from the Goon Squad, but then Egan finds her groove. Manhattan Beach is dense with gorgeous similes and metaphors. At bath time, the body of a palsied child with its "unexpected twists" is "beautiful in its strange way, like the inside of an ear." Passages about diving offer long passages of aria-intense, finely wrought description.

There are bits of science or scientific perspective in all four of the books I read, as for example when a battleship is viewed as "a skyscraper turned on its side"; this is the kind of surprising shift in perspective that we often encounter when studying physics, as for example when the atmosphere is viewed as an ocean of air. Sometimes, events in these books occur in the near future; the extrapolations of current technology work well at a thematic level, but the concrete details can be clunky or corny—lacking in the kind of sexy geist that pervades William Gibson's work.

In a parallel universe, Jennifer Egan might have become a science fiction author (see her tour de force short story "Black Box," which made my Year's Best List in 2014, and which, as I realized this year, is a coda to A Visit from the Goon Squad). But the universe we're in is better. With her command of language, her generational vision, and her artistic ambition, I wouldn't want Egan to belong to any genre other than her own.

Wednesday, June 27, 2018

Digital Pseudoprimes

In the previous post we considered prestidigital numbers—my term for numbers like 126 for which the digits can be arranged to produce a factorization (126 = 6·21). The opposite of a prestidigital number would be a number with no factorization that uses any of its digits. (In saying this, we are excluding the trivial factorization n = 1·n.) An example would be the number 14, whose only nontrivial factorization is 14 = 2·7. I'll call such numbers digital pseudoprimes. Another example would be 54, whose nontrivial factorizations all avoid the digits 5 and 4:

54 = 2·27 = 3·18 = 6·9

One could say that prime numbers are digitally pseudoprime, since prime numbers have no nontrivial factorization at all. But I'm more interested in composite cases, so let's go ahead and define a digital pseudoprime to be a composite number, none of whose nontrivial factorizations use any digits from the number. Equivalently, a digital pseudoprime is a composite number none of whose nontrivial divisors use any digits from the number.

Here are the first few digital pseudoprimes:

4, 6, 8, 9, 10, 14, 16, 18, 21, 27, 34, 38, 46, 49, 54, …

This sequence doesn't appear to be included in the Online Encyclopedia of Integer Sequences. There is a related sequence, A035139, but that sequence contains 40, for example, whereas 40 isn't digitally pseudoprime (40 = 4·10, also 40 = 2·20). I have submitted the sequence of digital pseudoprimes for review by the OEIS editors. If approved, it'll be sequence A316227.

The coolest digital pseudoprimes I have found so far are these, each of which has 8 distinct digits, leaving only two digits for the divisors:

248,629,501 = (337)(737,773)

321,810,649 = (557)(577,757).

(Both numbers have no other divisors; the four numbers in parentheses are all prime.)

The same kinds of questions that people ask about prime numbers could also be asked about digital pseudoprimes. For example,

1. Are there infinitely many digital pseudoprimes? [Update 6/29/2018: Suppose p is a prime number with its digits limited to 3 and 4. Then the digits of 2p are all 6s and 8s and 2p is a digital pseudoprime. This shows that if there are infinitely many primes with digits limited to 3 and 4, then there are infinitely many digital pseudoprimes. However, I doubt it's known if this is the case; it seems hard enough, as of 2016, to prove that there are infinitely many primes missing a single given digit. Note added 6/30/2018: It is enough if there are infinitely prime numbers p with digits in {2, 3, 4}; then the digits of 2p are all in {4, 6, 8} and 2p is a digital pseudoprime.]

2. Are there infinitely many consecutive pairs of digital pseudoprimes? Example: 107,887,106 and 107,887,107 are consecutive digital pseudoprimes.

Because digital pseudoprimes are defined in terms of their digits, being digitally pseudoprime is like a base-dependent version of primality. So some other questions arise:

4. If a number is digitally pseudoprime in one base, then could it be, or must it be, digitally pseudoprime in other bases?

5. The number 248,629,501 has 8 distinct digits and is digitally pseudoprime. Is there a digital pseudoprime with 9 distinct digits? [Update 6/28/2018: the answer is no. If all nontrivial divisors of a number use a single digit, then it isn't hard to show that the digit must be 1. But if all nontrivial divisors of n use only the digit 1, then n must also have the digit 1 in it (in at least the ones place). So if all nontrivial divisors of n use a single digit, n is not digitally pseudoprime.]


If these or other questions about digital pseudoprimes grab you, feel free to send in answers or put them in comments!

Tuesday, June 19, 2018

"Prestidigital" Numbers

On Father's Day I was messing around with numbers as follows. Let us call a whole number prestidigital if its digits can be arranged to provide a factorization. Here's an example: the number 1827 is prestidigital, because its digits can be arranged to form the numbers 21 and 87, which provide a factorization:

1827 = 21·87.

I'll call such a factorization a prestidigital factorization.

The name "prestidigital" is a play on the word "prestidigitation" (magic tricks). A prestidigital number has 'magic' digits, in the sense that they can be used to pull a factorization out of a hat.

Using a computer I found some exotic prestidigital numbers, including these two, both of which are ten-digit numbers in which every digit appears once:

1,024,739,856 = 3·7·8·642·9501

6,231,574,908 = 98754·63102.

You might try finding the smallest prestidigital number.

Is there a largest prestidigital number? I don't know. From this entry in the Online Encyclopedia of Integer Sequences, it follows that there are infinitely many prestidigital numbers. I might say more about that in a future post.

I also don't know if there is a There are prestidigital numbers with more than one distinct prestidigital factorization. For example, since 1827 is prestidigital via 21·87, then so is 18,270 prestidigital via 210·87 or 21·870. A less trivial example:

1395 = 15·93 = 5·9·31

Does there exist a prestidigital factorization with more than five factors? I haven't found one.

Update 6/21/2018: Here are some cases with six and seven factors:

15,598,328,492,687,040 = 60·524·723·801·898·954
1,694,536,975,878,000 = 73·89·601·604·750·958
133,998,561,647,490,168,000 = 510·606·681·740·933·940·981

I think I can show that:

   - a prestidigital factorization cannot have 1 as a factor.

   - a prestidigital factorization must have at least one factor with more than one digit.

   - an n-digit prestidigital number cannot consist of a single digit repeated n times.

But if I'm wrong about those things, let me know. Also, let me know if you discover anything else interesting!

Update 6/19/2018: I just googled "1827 number theory properties" and found an article about "vampire numbers," which are a special case of the above idea: http://mathworld.wolfram.com/VampireNumber.html. A vampire number by definition has an even number of digits, and the vampire factorization is two factors, each using half the digits of the vampire number. So 1827 = 21·87 is a vampire number and a prestidigital number, but 11,844 = 84·141 is a prestidigital number but not a vampire number. What I'm calling prestidigital numbers might be what has been called a "pseudovampire number." For more, here is OEIS A014575 and OEIS A020342.

Update 6/20/2018: Any single-digit factor in a prestidigital factorization of a prestidigital number N must be less than the leading digit of N. To see this in a formal way, imagine that 548,323,126 has the factorization (43)(612)(2)(835). (This isn't so, but pretending it is will show the idea.) Then

     1 = (pretend) 43·612·2·835/548,323,126 
       < 43·612·2·835/500,000,000
       < 43·612·5·835/500,000,000
       = 43·612·835/100,000,000
       < (100)(1000)(1000)/100,000,000
       = 1.

So 1 < 1, a contradiction.

Friday, June 15, 2018

Minimizing Rotational Inertia of A Curve


In the rotating apparatus below, a curve connects the green points. Thinking of the curve as a rigid body with uniform mass per unit length, determine the shape of the curve that minimizes its rotational inertia about the center of rotation.


I haven't seen this problem in any textbooks, perhaps because it isn't valuable as a real-world application. (In such an apparatus most of the inertia will be in the two arms, not in the curve, making optimization a task of doubtful importance.) However, the problem would be a good exercise for a graduate student in physics.

The best curve I can find is the one defined in polar coordinates by r = f(θ), where


and c ≈ 6.82843. Then the moment of inertia is about 0.61592 (in units where the two straight segments have unit length). Here's what the extremal curve looks like:


Here it is standing still:

As one would expect, the curve bends inward so that points on the curve are closer to the axis of rotation; this decreases rotational inertia. However, the curve doesn't bend so far inward that it becomes overlong and therefore overly massive (which would increase rotational inertia).

My calculation is here. It isn't a proof—for example, I haven't ruled out curves that can't be written in the form r = f(θ). But I'd be surprised if a better shape exists. Now if the angle π/4 were replaced by a much larger angle, then the best solution might travel along the arms; for example, if the angle were π, a straight angle, then surely the best curve is just a straight line from one green point to the other.

My strategy was direct—just set up the integral for the moment of inertia and then solve the resulting Euler-Lagrange differential equation for minimizing the integral. This wasn't hard to do symbolically, but there is a final numerical step at the end because the solution to the differential equation has a free parameter in it. (I can't remember having had that happen in a variational problem before.)

One final point of interest is that when transformed into Cartesian coordinates the extremal curve r = f(θ) is pretty close to part of the cubic curve 2.61x3 − 7.84xy2 = 1. Here is a global picture; see the PDF for details.




Wednesday, June 13, 2018

A Few Old-School Math Problems

Here are some nice short exercises from Algebra and Trigonometry (1960), by Edward A. Cameron (c. 1906–1992). I found this book in a used bookstore last year and finally leafed through it tonight.

  1. The sum of the digits of a three-digit number is 11. If 495 were subtracted from the number, the order of the digits would be reversed. If 27 were subtracted from the number, the units' digit and the tens' digit would be interchanged. Find the number.
  2. If the altitude of a certain triangle were increased by 2 inches and the base by 4 inches, the area would be increased by 32 square inches and the new base would be equal to the new altitude. Find the altitude and base of the original triangle.
  3. At the same instant two observers located 2 miles apart measure the angle of elevation of an airplane which is between them and directly over the line joining them. The two angles are 42°20' and 52°40'. Find the altitude of the airplane.

Wednesday, June 6, 2018

Crossing Strings - Another Look

In the original Crossing Strings problem, the attachment points for both of the strings and both of the posts were randomly chosen, and the resulting probability of crossing was ½. In a modified version of the problem, with the attachment points for one string biased in a certain way, the probability of crossing was 35/72.

In this post, I'll state a more general version of the problem and then provide an expression one can use to calculate the probability of a crossing when these more general conditions obtain. (Because, you know, you might need this someday.) We'll also consider an interesting special case. And if you stick with me to the end, there's a funny story about a mathematician.

Here's the more general version of the problem.
  • Two posts are divided into N equal-length sections. The sections of the left post are labeled D1, …, DN. The sections of the right post are labeled E1, …, EN.
  • On the left post, a green string has probability γLi of attaching to a point in section Di (and all attachment points in section Di are equally likely).
  • On the left post, a red string has probability ρLj of attaching to a point in section Dj (and all attachment points in section Dj are equally likely).
  • On the right post, a green string has probability γRk of attaching to a point in section Ek (and all attachment points in section Ek are equally likely).
  • On the right post, a red string has probability ρR of attaching to a point in section E (and all attachment points in section E are equally likely).
What is the probability that the strings cross?

Here is a diagram showing all the symbols for the case N = 4.


In the diagram, the green string attaches to the left post at a point in section D4; the probability of this is γL4. Note that γL1 + γL2 + γL3 + γL4 = 1, and similarly for the γR quantities and the ρL,R quantities. (These are probability distributions.)

The calculation I gave here can be straightforwardly generalized to produce the crossing probability in the general problem as follows: Probability of crossing =
\[ 2\left( \frac{1}{2}\sum_{n=1}^N{\gamma^{\rm L}_{n}\rho^{\rm L}_{n}} + \sum_{i < j}{\gamma^{\rm L}_{i}\rho^{\rm L}_{j}}\right)\left( \frac{1}{2}\sum_{m=1}^N{\gamma^{\rm R}_{m}\rho^{\rm R}_{m}} + \sum_{k>\ell}{\gamma^{\rm R}_{k}\rho^{\rm R}_{\ell}}\right)\,.\] I think this general expression is right…certainly it gives the correct results for the previous two versions of the problem. The problem in the original post corresponds to N = 1, γL1 = 1, ρL1 = 1, γR1 = 1, ρR1 = 1. Then the general expression becomes \[2\left(\frac{1}{2}\cdot 1\cdot 1 + 0\right)\left(\frac{1}{2}\cdot 1\cdot 1 + 0\right) = \frac{1}{2}\] as expected. The modified problem from the previous post corresponds to N = 2, γL1 = ⅓, γL2 = ⅔, γR1 = ⅓, γR2 = ⅔, ρL1 = ρL2 = ρR1 = ρR2 = ½. Then the general expression becomes
\[2\left(\frac{1}{2}\left(\frac{1}{3}\cdot\frac{1}{2}+\frac{2}{3}\cdot\frac{1}{2}\right) + \frac{1}{3}\cdot\frac{1}{2}\right)\left(\frac{1}{2}\left(\frac{1}{3}\cdot\frac{1}{2}+\frac{2}{3}\cdot\frac{1}{2}\right) + \frac{2}{3}\cdot\frac{1}{2}\right) = \frac{35}{72}\]
as expected.

A special case is interesting. If the colors are treated the same way on each post (meaning that γLm = ρLm ≡ πLm and γRm = ρRm ≡ πRm), then the probability of a crossing is ½ regardless of the probability distributions {πLm, πRm}. To see how this follows from the general expression, note that under the stated assumptions, the general expression becomes

\[ 2\left( \frac{1}{2}\sum_{n=1}^N{{\left[\pi^{\rm L}_{n}\right]}^2} + \sum_{i < j}{\pi^{\rm L}_{i}\pi^{\rm L}_{j}}\right)\left( \frac{1}{2}\sum_{m=1}^N{{\left[\pi^{\rm R}_{m}\right]}^2} + \sum_{k>\ell}{\pi^{\rm R}_{k}\pi^{\rm R}_{\ell}}\right)\]
\[ = 2\left(\frac{1}{2}\left(\sum_{n=1}^N{\pi^{\rm L}_{n}}\right)^{\!\!2}\,\right)\left( \frac{1}{2}\left(\sum_{m=1}^N{\pi^{\rm R}_{m}}\right)^{\!\!2}\,\right)\]
\[ = 2\left(\frac{1}{2}\cdot 1^2\right)\left( \frac{1}{2}\cdot 1^2\right)\]
\[ = \frac{1}{2}\,.\]

It wasn't obvious to me a priori that the probability of a crossing is ½ when colors are treated the same way (even when the posts are not treated the same way, and even when the probability distribution along a given post is non-uniform). Is it obvious in retrospect?*

I'm not sure "obvious" is the word I'd use, but I do believe it's possible to appreciate, without any algebra, why the answer to the color-symmetric problem has to be ½. Here's one way to explain it—you may have a better way.

To begin with, I think a natural way to imagine building a random configuration would be as follows:
  • Draw a green line from a randomly chosen left-hand point to a randomly chosen right-hand point, choosing the left-hand point according to the probability distribution for the left post and choosing the right-hand point according to the probability distribution for the right post.
  • Draw a red line from a randomly chosen left-hand point to a randomly chosen right-hand point, choosing the left-hand point according to the probability distribution for the left post and choosing the right-hand point according to the probability distribution for the right post. 
But we don't have to do things in this order. We could instead do things like so:
  • Mark a green endpoint on the left post, choosing randomly according to the probability distribution for the left post.
  • Mark a red endpoint on the left post, choosing randomly according to the probability distribution for the left post.
  • Mark a green endpoint on the right post, choosing randomly according to the probability distribution for the right post.
  • Mark a red endpoint on the right post, choosing randomly according to the probability distribution for the right post.
  • Draw segments connecting endpoints of the same color.
Nothing says green has to come before red. So another alternative would be:
  • Mark a red endpoint on the left post, choosing randomly according to the probability distribution for the left post.
  • Mark a green endpoint on the left post, choosing randomly according to the probability distribution for the left post.
  • Mark a red endpoint on the right post, choosing randomly according to the probability distribution for the right post.
  • Mark a green endpoint on the right post, choosing randomly according to the probability distribution for the right post.
  • Draw segments connecting endpoints of the same color.
Yet another approach:
  • Mark a red endpoint on the left post, choosing randomly according to the probability distribution for the left post.
  • Mark a green endpoint on the left post, choosing randomly according to the probability distribution for the left post.
  • Mark a green endpoint on the right post, choosing randomly according to the probability distribution for the right post.
  • Mark a red endpoint on the right post, choosing randomly according to the probability distribution for the right post.
  • Draw segments connecting endpoints of the same color.
Given the identical probabilities for green and red on either post, we could even do things this way (here is the version to pay attention to):
  • Mark an endpoint on the left post, choosing randomly according to the probability distribution for the left post. Label this endpoint A.
  • Mark another endpoint on the left post, choosing randomly according to the probability distribution for the left post. Label this endpoint B.
  • Toss a fair coin to decide which endpoint is red and which is green. This is a valid approach because on the left post, red and green endpoints are drawn from the same distribution. 
  • Mark an endpoint on the right post, choosing randomly according to the probability distribution for the right post. Label this endpoint X.
  • Mark another endpoint on the right post, choosing randomly according to the probability distribution for the right post. Label this endpoint Y.
  • Toss a fair coin to decide which endpoint is red and which is green.  This is a valid approach because on the right post, red and green endpoints are drawn from the same distribution.
  • Draw segments connecting endpoints of the same color.
Using this last method, I think it is apparent that following four configurations are equally likely:
  • A green segment AX and a red segment BY
  • A red segment AX and a green segment BY
  • A green segment AY and a red segment BX
  • A red segment AY and a green segment BX
Two of these configurations have a crossing, while two do not. So the probability of a crossing is 2 ÷ 4 or ½.

-----------------
 *At Harvard they used to tell a story about Serge Lang, the mathematician (probably the identical story has been told in lots of places about lots of people). During a lecture, Lang was writing on the board. When making a transition from one equation to the next, Lang said, "… and so, it's obvious that …" whereupon he wrote the next equation. A student's hand went up. "Professor Lang, is that really obvious?" Lang paused and stared at his equation. He kept staring. After staring for some time, he placed his chalk in the tray and walked out of the lecture room. Some minutes later, Lang returned. "Yes," he said, "it's very obvious."