What do these yellow boxes hide?

This image features the distinctive yellow-on-black styling used in the Star Wars opening crawl. Each item on the left of the image can be seen to be the name of a planet or a moon appearing in the Star Wars movies.

These clues and the title points us towards an integer sequence named after the English architect and author Richard Padovan (born 1935). The first three integers in the Padovan sequence are $$P_0 = P_1 = P_2 = 1$$. Each subsequent integer $$P_i$$ ($$i > 2$$) is computed as $$P_i = P_{i-3} + P_{i-2}$$. This yields the following sequence:

1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, 49, 65, 86, 114, 151, 200, …

The right side of the image shows secret coordinates encoding where the planets and moons are hiding in the Padovan sequence. To find its whereabouts, we first convert the name of a planet or a moon into its codename (a sequence of digits) by

• replacing each letter in the name with its position in the alphabet  (A=1, B=2, C=3, …, Z=26)

• keeping each digit in the name

• removing any other character

This conversion does not distinguish between uppercase and lower case letters. For example, Jedha becomes 105481 (the concatenation of 10, 5, 4, 8 and 1), D'Qar becomes 417118, Yavin 4 becomes 251229144, and Vandor-1 becomes 22114415181.

To illustrate how secret coordinates encode where planets and moons are hiding in the Padovan sequence, let's consider the first row featuring the moon Jedha, whose name corresponds to codename 105481. The first Padovan number to contain the digit sequence 105481 happens to be Padovan number $$P_{1738}$$ (indicated by #1738 in the secret coordinates). This particular Padovan number has 213 digits (the last number in the secret coordinates). If we then look at digits 94 to 99 (inclusive) of this 213-digit number (with the digits of an integer numbered from left to right starting from 1), we find that they read 105481 — precisely the codename corresponding to Jedha. For completeness, these are all 213 digits of Padovan number $$P_{1738}$$, with the relevant digits highlighted:

12856476872761368826412337124665816290845154237897141297537926654958720697804863
44210240740411054817800354360406301836700438227598098235590634907743866551613564
61510516579625400073487473896151762076073846053430017

In other words, the secret coordinates #1738, 94-99 of 213 can be summarized as: the number preceded by the pound sign (#, in this case #1738) denotes a particular Padovan number (in this case $$P_{1738}$$) and the rest of the secret coordinates (in this case 94-99 of 213) indicates which digits must be extracted from the Padovan number to obtain the codename corresponding to the name (in this case 105481=Jedha).

To decode the fourth line (where the yellow box covers the name), the secret coordinates to the right (#10090, 1060-1066 of 1233) correspond to codename 1512571. Although there are multiple names mapping to this codename, only one candidate matches with a Star Wars moon or planet — namely planet Olega (15-12-5-7-1).

The yellow boxes appearing on the final row of the image present a tougher challenge still, as we must determine which Padovan number to use. We already reveal that the first box hides the name Kef Bir, whose codename 11562918 appears for the first time in Padovan number $$P_{29772}$$. This Padovan number has 3636 digits, with the digits from codename 11562918 appearing for the first time from position 1295 up to and including position 1302. This yields secret coordinates #29772, 1295-1302 of 3636.

Assignment

• Write a function padovan_number that takes an integer $$n \in \mathbb{N}$$ (int). The function must return Padovan number $$P_n$$ (int).

  Tip

  By definition, the first three Padovan numbers are $$P_0 = P_1 = P_2 = 1$$.

  To compute Padovan number $$P_n$$ for $$n > 2$$, you must also compute all previous Padovan numbers $$P_0, P_1, \ldots, P_{n-1}$$. After all, each Padovan number $$P_i$$ is computed from two previous Padovan numbers: $$P_i = P_{i-3} + P_{i-2}$$.

  Padovan number $$P_3$$ is computed from the first two Padovan numbers: $$P_3 = P_0 + P_1$$. This does not require Padovan number $$P_2$$. However, you do need $$P_2$$ to compute the next Padovan number, because $$P_4 = P_1 + P_2$$.

  So you don't have to keep track of all the previous Padovan numbers. It is sufficient to keep track of the last three Padovan numbers that were computed in order to compute the next Padovan number. The video below shows step by step how Padovan number $$P_{10}$$ can be computed.

  

• Write a function digits that takes three integers $$n, a, b \in \mathbb{N}$$ (int). The function must return the integer (int) formed by extracting the digits from position $$a$$ up to and including position $$b$$ from Padovan number $$P_n$$, where positions of digits in Padovan number $$P_n$$ are numbered from left to right starting from 1.

• Write a function codename that takes a name (str). The function must return the codename (str) corresponding to the given name. No distinction should be made between uppercase and lowercase letters when determining the codename.

• Write a function coordinates that takes a name (str). The function must return the secret coordinates (str) that encode where the codename corresponding to the given name appears for the first time in the Padovan sequence.

  Tip

  Intuitively, you might be tempted to call the function padovan_number when implementing the function coordinates. However, this will be far too slow. If you have already calculated Padovan numbers $$P_1, P_2, \ldots, P_n$$, use a faster method to calculate the next Padovan number $$P_{n+1}$$.

Example

>>> padovan_number(10)
12
>>> padovan_number(20)
200
>>> padovan_number(30)
3329
>>> padovan_number(40)
55405

>>> digits(1738, 94, 99)
105481
>>> digits(3103, 355, 360)
205208
>>> digits(4757, 167, 172)
417118
>>> digits(10090, 1060, 1066)
1512571

>>> codename('Jedha')
'105481'
>>> codename("D'Qar")
'417118'
>>> codename('Yavin 4')
'251229144'
>>> codename('Vandor-1')
'22114415181'

>>> coordinates('Jedha')
'#1738, 94-99 of 213'
>>> coordinates('Teth')
'#3103, 355-360 of 379'
>>> coordinates("D'Qar")
'#4757, 167-172 of 581'
>>> coordinates('Olega')
'#10090, 1060-1066 of 1233'

Epilogue

In 2012 an online petition urged the Obama administration to build a Death Star like the one in Star Wars.

The campaign amassed 25 000 signatures, enough to require an official response. It fell to Paul Shawcross — chief of the Science and Space Branch at the Office of Management and Budget — to reject the project. He gave three reasons:

• The construction of the Death Star has been estimated to cost more than $850 000 000 000 000 000. We're working hard to reduce the deficit, not expand it.

• The Administration does not support blowing up planets.

• Why would we spend countless taxpayer dollars on a Death Star with a fundamental flaw that can be exploited by a one-man starship?