Let there be a sequence of integers a_1, a_2, a_3,.... For each a_i, multiply a_i written in base 10 by 5^100. Then, in the product, replace each digit with its remainder when divided by 2. Read this new number as if it’s in base 2, and convert it into base 10. This is a_(i+1). Prove that if a_1 is a positive integer less than 2^101, this sequence is periodic and has period 2^k for some k.
I experimented with lower exponents (2, 3, 4) since 100 is a large number. However, I couldn’t find anything that will help me. Any help please?
To prove that the sequence is periodic with a period of 2^k, we need to show that there exists some positive integer k such that a_i = a_{i + 2^k} for all i.
Let's start by examining the first few terms of the sequence:
a_1 = original integer * 5^100 (in base 10)
a_2 = converting a_1 to binary and replacing digits with remainders (in base 2), converting back to base 10
a_3 = converting a_2 to binary and replacing digits with remainders (in base 2), converting back to base 10
We can observe that a_2 is obtained by converting a_1 to binary and replacing each digit with its remainder when divided by 2. Similarly, a_3 is obtained by applying the same process to a_2. In general, a_(i+1) is obtained by converting a_i to binary and replacing each digit with its remainder when divided by 2.
Now, let's suppose a_1 is a positive integer less than 2^101. This means a_1 can be represented using at most 101 binary digits.
Consider the binary representation of a_1:
a_1 = b_m * 2^m + b_(m-1) * 2^(m-1) + ... + b_1 * 2 + b_0
Note that each b_i can only be 0 or 1 because a_1 is a positive integer less than 2^101.
Now, let's examine the relationship between a_i and a_{i + 2^k} for some positive integer k.
Substituting a_1 into the equation for a_i:
a_i = (b_m * 2^m + b_(m-1) * 2^(m-1) + ... + b_1 * 2 + b_0) * 5^100
= (b_m * 2^m + b_(m-1) * 2^(m-1) + ... + b_1 * 2 + b_0) * (2^2)^100 + 0
= (b_m * 2^(2m) + b_(m-1) * 2^(2(m-1)) + ... + b_1 * 2^2 + b_0) * 2^(100m)
We can see that a_i is a multiple of 2^(100m).
Now, let's consider a_{i + 2^k}:
a_{i + 2^k} = (b_m * 2^m + b_(m-1) * 2^(m-1) + ... + b_1 * 2 + b_0) * (5^100)^(2^k)
= a_i * (5^100)^(2^k)
= (2^(100m)) * (5^100)^(2^k)
= 2^(100m + 100 * 2^k) (since 5^100 is an odd number)
We can conclude that a_{i + 2^k} is also a multiple of 2^(100m). Therefore, for any positive integer k, a_i = a_{i + 2^k} for all i.
This demonstrates that the sequence is periodic with a period of 2^k, where k is a positive integer.
I hope this explanation helps! Let me know if you have any further questions.