Pseudorandom Sequence

Rand48 is a pseudorandom number generator used by some programming languages. It generates a sequence from any given integer $0 \le a_0 < 2^{48}$ using the rule $a_n = (25214903917 \cdot a_{n - 1} + 11) \bmod 2^{48}$. Let $b_n = \lfloor a_n / 2^{16} \rfloor \bmod 52$. The sequence $b_0, b_1, \dots$ is translated to an infinite string $c = c_0c_1\dots$ via the rule: $0 \rightarrow$ a, $1\rightarrow$ b, $\dots$, $25 \rightarrow$ z, $26 \rightarrow$ A, $27 \rightarrow$ B, $\dots$, $51 \rightarrow$ Z. For example, if we choose $a_0 = 123456$, then the string $c$ starts with: "bQYicNGCY$\dots$". Moreover, starting from index $100$, we encounter the substring "RxqLBfWzv" for the first time. Alternatively, if $c$ starts with "EULERcats$\dots$", then $a_0$ must be $78580612777175$. Now suppose that the string $c$ starts with "PuzzleOne$\dots$". Find the starting index of the first occurrence of the substring "LuckyText" in $c$.

To solve this problem, first, we need to convert letters to numbers that we can use when applying the Rand48 equation. Using the provided conversion rules, the string “PuzzleOne” turns into $(41, 50, 56, 56, 37, 28, 40, 31, 38)$. Similarly, “LuckyText” is turned into $(37, 50, 37, 45, 32, 40, 31, 58, 41)$.

Next, since we’re dealing with modular arithmetic, we want to find an inverse of our multiplier ($25214903917$) to allow us to undo the operation. The inverse will be $(25214903917)^{-1} \mod 2^{48} = 36468348860117 \mod 2^{48}$.

Next is finding the initial value of $a$, $a_0$, given that the string starts with “PuzzleOne”. We’re given an example of how to do this: “EULERcats” corresponds to $a_0 = 78580612777175$. By extending this example to our string “PuzzleOne”, we find the following equation to get the initial value of $a$:

$a_0 = 36468348860117 \cdot ((41 \cdot 2^{40}) + (50 \cdot 2^{32}) + (56 \cdot 2^{28}) + (56 \cdot 2^{24}) + (37 \cdot 2^{20}) + (28 \cdot 2^{16}) + (40 \cdot 2^{12}) + (31 \cdot 2^{8}) + 38) \mod 2^{48}$

After calculating $a_0$, we will use the provided rule to generate the sequence of $a$. $a_n = (25214903917 \cdot a_{n – 1} + 11) \bmod 2^{48}$.

Let’s now find when the sequence $b$ first equals to $(37, 50, 37, 45, 32, 40, 31, 58, 41)$ (which corresponds to “LuckyText”). Since we’re given that “RxqLBfWzv” corresponds to the $100^{th}$ index, we will use our sequence $a$, calculate $b_n$ and check when it first equals our “LuckyText”. We keep doing this until we get the expected sequence.

This is a laborious process and it might take time as the sequence will be extensive (larger than $2^{48}$ values). Unfortunately, since we don’t know in which length this sequence will appear, the exact computations cannot be provided here. It may be more feasible to find the solution programmatically, using a programming language to automate the calculations and find the indices.

More Answers: