Arrival Pt. 2

Puzzle for the week of 5/25

Inspired by the Fiddler on the Proof (formerly The Riddler), X’s Puzzle Corner aims to produce a weekly puzzle for readers that enjoy math, probability, and algorithms. Please submit your solution! Solutions will be accepted until 11 pm the following Sunday after the puzzle is posted (in this case 6/1/25). While it isn’t required, I encourage you to opt to have your solution shared so that we all get the chance to see how others thought about and attempted the problem! The solution and submitted responses will be posted around Wednesday at 10 am.

I make no guarantees my solutions are correct! You are all smart people so please comment if you think I made a mistake!

---

The next few weeks will feature puzzles intended to set the scene and build into a fascinating result from the recent paper A Hyper-Catalan Series Solution to Polynomial Equations, and the Geode. I was tempted not to mention the paper as the influence, but it’s such an interesting result that I couldn’t resist. Just know that reading the paper will result in puzzle spoilers :)

---

Decades of patiently listening to the cosmos have finally paid off! The SETI project has detected a faint, repeating signal from a distant star system. Linguists and cryptographers are abuzz, believing it might be a fragment of an alien lullaby or a foundational counting sequence, due to its simple, recursive structure. Your puzzle this week is to help them understand it.

Each Signal is composed of a combination of pulses and phrases and is structured as follows:

• The most basic element is a "Pulse." It's a complete, indivisible unit, which we'll represent with a dot.

• More complex structures, called "Phrases," are formed by a specific modulator followed by a sequence of other complete signals (each of which can be a pulse or another phrase).

  • An Alpha-Modulator (symbol A): This modulator always precedes exactly two subsequent Signals. We can visualize this as A(Signal₁, Signal₂) or as a tree:

       A
     /   \
Signal₁  Signal₂

• • A Beta-Modulator (symbol B): This modulator always precedes exactly three subsequent signals. Visualized as B(Signal₁, Signal₂, Signal₃) or:

         B
      /  |   \
    /    |     \
   /     |      \
Signal₁ Signal₂ Signal₃

Examples of Signal Structures:

1. A simple Pulse: •

2. An Alpha-Phrase made of two Pulses: A(•, •)

3. A Beta-Phrase made of three Pulses: B(•, •, •)

4. A more complex Phrase: A(•, B(•, •, •)) (An Alpha-Phrase where the first Signal is a Pulse, and the second Signal is a Beta-Phrase containing three Pulses).

5. Another example: B(A(•,•), •, •) (A Beta-Phrase where the first Signal is an Alpha-Phrase, followed by two Pulses).

The "complexity" of a Signal can be defined by the number of modulators it contains. A pulse • has 0 complexity. A(•,•) has complexity 1, and A(•, B(•,•,•)) has complexity 2 (one A-Modulator and one B-Modulator).

---

Warm up: Harmonies & Echoes

The team is trying to catalogue the simplest signal structures. Remember, the order of subsequent Signals within a Phrase matters (e.g., if S₁ and S₂ are different structured Signals, A(S₁, S₂) is distinct from A(S₂, S₁)).

1. How many distinct signal structures have exactly two modulators in total? These two modulators can be any combination of Alpha or Beta types (e.g., two Alphas, or one Alpha and one Beta, or two Betas).

2. Do you recognize this number? Do these calculations feel familiar? (Hint)

---

Decoding The Signals

The xenolinguists are now trying to estimate the total computational decoding cost for the entire Lullaby language. This is a theoretical measure representing the sum of efforts required to decode every conceivable signal structure. Here's how the cost is modeled:

• A basic Pulse • is trivial to decode, having a computational cost of 1 unit.

• Decoding an Alpha-Modulator itself involves a certain overhead, represented by a cost factor A. The overall computational cost to decode a Phrase A(S₁, S₂) is a multiplicative function of this overhead and the costs of its sub-signals: A×(cost of S1​)×(cost of S2​).

• Similarly, a Beta-Modulator has a cost factor B, and a Phrase B(S₁, S₂, S₃) has an overall decoding cost of B×(cost of S1​)×(cost of S2​)×(cost of S3​).

Recall we want to compute the sum S of the individual decoding costs of all possible distinct signal structures. You’re about to start approximating S by enumerate all possibilities but the lead—on his way out for the evening—researcher tells you there’s a much easier way to compute S. You yell back in confusion, “How?” but he’s already gone. What was he talking about? In other words, can you find a simpler way to express and compute S(A,B)?

If you think you have it, you can always check by computing an approximation of S(A,B) with the first handful of terms in the infinite series representation.

Please submit your answers here. Please ask any questions in the comments.

---

Disclaimer: This puzzle was a tricky one for me. It’s a little bit of a departure from my previous puzzles. If you have a moment, I’d particularly like folks’ feedback in the comments on this puzzle and, more broadly, this series of puzzles based on the recent hyper-Catalan/polynomial solution paper I mention up top.

---

As an aside, this puzzle reminds me of the short story Story of Your Life by Ted Chiang. His entire collection of short stories are great. Highly recommend.