If $n$ is a positive integer, a Leistra sequence is a sequence $a_{1}, a_{2}, a_{3}, \ldots, a_{n-1}, a_{n}$ with $n$ terms with the following properties:

(P1) Each term $a_{1}, a_{2}, a_{3}, \ldots, a_{n-1}, a_{n}$ is an even positive integer.

(P2) Each term $a_{2}, a_{3}, \ldots, a_{n-1}, a_{n}$ is obtained by dividing the previous term in the sequence by an integer between 10 and 50, inclusive. (For a specific sequence, the divisors used do not all have to be the same.)

(P3) There is no integer $m$ between 10 and 50, inclusive, for which $\frac{a_{n}}{m}$ is an even integer.

For example,

$\left|\begin{array}{c}\text { Leistra sequences } \\ \hline 1000,50,2 \\ 1000,100,4 \\ 3000,300,30,2 \\ 106\end{array}\right|$

| Not Leistra sequences | Reason |
| :---: | :---: |
| $1000,50,1$ | (P1) fails - includes an odd integer |
| $1000,200,4$ | (P2) fails - divisor 5 falls outside range $\left(\frac{1000}{200}=5\right)$ |
| $3000,300,30$ | (P3) fails - can be extended with $\frac{30}{15}=2$ |
| 104 | (P3) fails - can be extended with $\frac{104}{13}=8$ |

(a) Determine all Leistra sequences with $a_{1}=216$.

(b) How many Leistra sequences have $a_{1}=2 \times 3^{50}$ ?

(c) How many Leistra sequences have $a_{1}=2^{2} \times 3^{50}$ ?

(d) Determine the number of Leistra sequences with $a_{1}=2^{3} \times 3^{50}$.

(In parts (b) and (c), full marks will be given for a correct answer. Part marks may be awarded for an incomplete solution or work leading to an incorrect answer.)
(a) Consider a Leistra sequence with $a_{1}=216$.

In the sequence, $a_{2}$ must be an even integer of the form $a_{2}=\frac{a_{1}}{d}=\frac{216}{d}$ where $d$ is an integer between 10 and 50, inclusive.

Since $216=6^{3}=2^{3} \times 3^{3}$, the positive divisors of 216 are

$$
1,2,3,4,6,8,9,12,18,24,27,36,54,72,108,216
$$

From this list, the divisors of 216 that are between 10 and 50 are 12, 18, 24, 27, 36 .

The quotients when 216 is divided by these integers are $18,12,9,8,6$, respectively.

Since $a_{2}$ is even, then we can have $a_{2}=18$ (with $d=12$ ) or $a_{2}=12$ (with $d=18$ ) or $a_{2}=8$ (with $d=27$ ) or $a_{2}=6$ (with $d=36$ ).

If $a_{2}=18$, there is no possible $a_{3}$ since the only divisor of $a_{2}=18$ that is greater than 10 is 18 and this would give $a_{3}=1$ which is not even.

If $a_{2}=12$, there is no possible $a_{3}$ since the only divisor of $a_{2}=12$ that is greater than 10 is 12 and this would give $a_{3}=1$ which is not even.

If $a_{2}=8$ or $a_{2}=6$, there is no divisor larger than 10 .

This means that no Leistra sequence starting with $a_{1}=216$ can have more than two terms.

Therefore, there are four Leistra sequences with $a_{1}=216$, namely 216, 18 and 216, 12 and 216,8 and 216,6 .

(b) Consider a Leistra sequence with $a_{1}=2 \times 3^{50}$.

In the sequence, $a_{2}$ must be an even integer of the form $a_{2}=\frac{a_{1}}{d_{1}}=\frac{2 \times 3^{50}}{d_{1}}$ where $d_{1}$ is an integer between 10 and 50, inclusive.

Since $a_{1}$ includes only one factor of 2 and since $a_{2}$ must be even, $d_{1}$ cannot itself be even. Therefore, $d_{1}$ must be an odd divisor of $a_{1}=2 \times 3^{50}$ that is between 10 and 50, inclusive. The odd positive divisors of $a_{1}=2 \times 3^{50}$ are the integers of the form $3^{j}$ with $0 \leq j \leq 50$; in other words, the odd positive divisors of $a_{1}$ are powers of 3 .

The first few powers of 3 are $3,9,27,81$. The only such power between 10 and 50 is $3^{3}=27$. Therefore, the only possibility for $d_{1}$ is $d_{1}=3^{3}$ which gives $a_{2}=\frac{a_{1}}{d_{1}}=2 \times 3^{47}$.

The next term in the sequence is an even positive integer $a_{3}$ of the form $a_{3}=\frac{a_{2}}{d_{2}}$ where
$d_{2}$ is an integer between 10 and 50, inclusive. (While we can find divisors between 10 and 50 to divide out and still obtain an even integer, (P3) tells us that the sequence must continue.)

Using a similar argument, $d_{2}=3^{3}$ and so $a_{3}=2 \times 3^{44}$.

Since each subsequent term $a_{i}$ is found by dividing its previous term by an integer, then each $a_{i}$ is itself a divisor of $a_{1}$ which means the divisors of each $a_{i}$ are a subset of the divisors of the original $a_{1}$.

In this case, this means that the only divisor that we will ever be able to use in this sequence is $3^{3}$ and we must divide this out until we can no longer do so.

This means that the Leistra sequence continues in the following way:

$$
2 \times 3^{50}, 2 \times 3^{47}, 2 \times 3^{44}, \ldots, 2 \times 3^{8}, 2 \times 3^{5}
$$

where the last term listed is the 16th term so far.

We can again divide out a factor of $3^{3}$ to obtain

$$
2 \times 3^{50}, 2 \times 3^{47}, 2 \times 3^{44}, \ldots, 2 \times 3^{8}, 2 \times 3^{5}, 2 \times 3^{2}
$$

The last term is now 18 ; as in (a), the sequence cannot be continued.

Therefore, with $a_{1}=2 \times 3^{50}$, the sequence is completely determined without choice, and so there is exactly 1 Leistra sequence with $a_{1}=2 \times 3^{50}$.

(c) Consider Leistra sequences with $a_{1}=2^{2} \times 3^{50}$.

The divisors that can be used to construct the Leistra sequence are divisors of $2^{2} \times 3^{50}$ that leave an even quotient.

Since $a_{1}$ includes 2 factors of 2 , these divisors can thus include 0 or 1 factor of 2 in order to preserve the parity of the quotient.

This means that the divisors are of the form $3^{j}$ or $2 \times 3^{j}$ and are between 10 and 50, inclusive.

From (b), the only possible divisor of the form $3^{j}$ in this range is $3^{3}=27$.

Also, the integers of the form $2 \times 3^{j}$ with $j=1,2,3$ are $6,18,54$, and so the only possible divisor in the desired range is 18 .

This means that this Leistra sequence can only use the divisors 27 and 18 . We note further that the divisor 18 can be used at most once, otherwise the remaining quotient (and thus next term) would be odd.

Suppose that the divisor 18 is not used.

Using a similar argument to (b), this gives the sequence

$$
2^{2} \times 3^{50}, 2^{2} \times 3^{47}, 2^{2} \times 3^{44}, \ldots, 2^{2} \times 3^{8}, 2^{2} \times 3^{5}, 2^{2} \times 3^{2}
$$

The last term in this list is $2^{2} \times 3^{2}=36$. This term cannot be the final term in the sequence because $\frac{36}{18}=2$, and so if 36 were the final term, (P3) would be violated.

Thus, the sequence cannot use 27 as its only divisor and must use 18 at least once and at most once (thus exactly once).

Therefore, any Leistra sequence beginning with $a_{1}=2^{2} \times 3^{50}$ must use the divisor 18 exactly once and the divisor 27 a number of times.

If the sequence above is extended by using the divisor 18 to generate a final term, we obtain

$$
2^{2} \times 3^{50}, 2^{2} \times 3^{47}, 2^{2} \times 3^{44}, \ldots, 2^{2} \times 3^{8}, 2^{2} \times 3^{5}, 2^{2} \times 3^{2}, 2
$$

In this case, the sequence uses the divisor $3^{3}=27$ a total of 16 times and the divisor 18 once.

The divisor $3^{3}=27$ cannot be used 17 times, since $\left(3^{3}\right)^{17}=3^{51}$ and we cannot divide 3 out of $2 \times 3^{50}$ a total of 51 times and still obtain an integer quotient.

Also, since $\left(3^{3}\right)^{15} \times\left(2 \times 3^{2}\right)=2 \times 3^{47}$ and $\frac{2^{2} \times 3^{50}}{2 \times 3^{47}}=2 \times 3^{3}$, the divisor $3^{3}=27$ has to be used more than 15 times, since if it used only 15 times, the sequence must be continued by dividing again by 27 .

Therefore, the Leistra sequences starting with $a_{1}=2^{2} \times 3^{50}$ all have 18 terms, and are generated by dividing 16 times by 27 and 1 time by 18 . Any order of these divisors will generate a sequence of even integers, and so will generate a Leistra sequence.

There are 17 ways of arranging these 17 divisors as there are 17 places to choose to place the 18 and the remaining places are filled with the 27s.

Since there are 17 ways of arranging the divisors, there are 17 Leistra sequences with $a_{1}=2^{2} \times 3^{50}$.

(d) Consider Leistra sequences with $a_{1}=2^{3} \times 3^{50}$.

The divisors that can be used to construct the Leistra sequence are divisors of $2^{3} \times 3^{50}$ that leave an even quotient.

Since $a_{1}$ includes 3 factors of 2 , these divisors can thus include 0,1 or 2 factors of 2 in order to preserve the parity of the quotient.

From (c), these divisors are 18 and 27 along with any divisors of the form $2^{2} \times 3^{j}$ that are between 10 and 50, inclusive.

Since the integers of the form $2^{2} \times 3^{j}$ with $j=0,1,2,3$ are $4,12,36,108$, the possible divisors in the desired range are 12 and 36 .

Thus, these Leistra sequences are generated using the divisors $27,18,12$, and 36 . To count the number of Leistra sequences, we count the number of ways of arranging the possible divisors, noting that at most 2 factors of 2 can be included amongst the set of divisors used and at most 50 factors of 3 can be included amongst the set of divisors used.

Looking at the number of factors of 2 , we can see that either (i) the divisors are all odd, (ii) one divisor of 12 is used, (iii) one divisor of 36 is used, (iv) two divisors of 18 are used, or (v) one divisor of 18 is used. Any other combination of the even divisors will not satisfy the conditions of Leistra sequences.

Case 1: 27 only

Note that $27^{16}=\left(3^{3}\right)^{16}=3^{48}$ which is a divisor of $a_{1}$.

Since $27=3^{3}$, we cannot use 17 or more $27 \mathrm{~s}$, as $a_{1}$ includes only 50 factors of 3 .

Also, we cannot use 15 or fewer 27 s, as the sequence can be continued by dividing by another 27.

Since $\frac{a_{1}}{\left(3^{3}\right)^{16}}=\frac{2^{3} \times 3^{50}}{3^{48}}=2^{3} \times 3^{2}$, then the sequence cannot use just 27 s since we could continue the sequence that did by dividing by 12 , for example.

Therefore, there are no sequences in this case.

Case 2: 27 and 12

The divisor 12 can only be used once, otherwise too many factors of 2 would be removed. Since $12 \times 27^{15}=2^{2} \times 3^{46}$ and $12 \times 27^{16}=2^{2} \times 3^{49}$ and $12 \times 27^{17}=2^{2} \times 3^{52}$, then the divisor of 27 must be used exactly 16 times. (If 27 is used 17 times, too many 3s are removed; if 27 is used 15 times, the sequence can be extended by dividing by 27 again. If 27 is used 16 times, the quotient is $\frac{2^{3} \times 3^{50}}{2^{2} \times 3^{49}}=2 \times 3=6$ which ends the sequence.)

Therefore, Leistra sequences can be formed by using exactly 16 divisors equal to 27 and 1 divisor equal to 12 .

Since these divisors can be used in any order, there are 17 such sequences, as in (c).

Case 3: 27 and 36

The divisor 36 can only be used once, otherwise too many factors of 2 would be removed.

Since $36 \times 27^{15}=2^{2} \times 3^{47}$ and $36 \times 27^{16}=2^{2} \times 3^{50}$ and $36 \times 27^{17}=2^{2} \times 3^{53}$, then the divisor of 27 must be used exactly 16 times.

Therefore, Leistra sequences can be formed by using exactly 16 divisors equal to 27 and 1 divisor equal to 36.

Since these divisors can be used in any order, there are 17 such sequences, as in (c).

Case 4: 27 and two 18s

Note that 18 cannot be used more than two times and that 18 cannot be combined with 12 or 36 , otherwise the remaining quotient would be either odd or not an integer.

Since $18^{2} \times 27^{14}=2^{2} \times 3^{46}$ and $18^{2} \times 27^{15}=2^{2} \times 3^{49}$ and $18^{2} \times 27^{16}=2^{2} \times 3^{52}$, then the divisor of 27 must be used exactly 15 times.

Therefore, Leistra sequences can be formed by using exactly 15 divisors equal to 27 and 2 divisors equal to 18.

There are $\left(\begin{array}{c}17 \\ 2\end{array}\right)=\frac{17 \times 16}{2}=136$ ways of choosing 2 of the 17 positions in the sequence of divisors for the 18s to be placed. The remaining spots are filled with $27 \mathrm{~s}$.

Therefore, there are 136 such sequences.

Case 5: 27 and one 18

Since $18 \times 27^{15}=2 \times 3^{47}$ and $18 \times 27^{16}=2 \times 3^{50}$ and $18 \times 27^{17}=2 \times 3^{53}$, then the divisor of 27 must be used exactly 16 times, leaving a final term of $2^{2}=4$.

As in Case 2 and Case 3, there are 17 such sequences.

Having considered all possibilities, there are $17+17+136+17=187$ Leistra sequences with $a_{1}=2^{3} \times 3^{50}$.