Let there be a sequence of integers where a_1 is less than 2^101. For each a_i, multiply a_i by 5^100 in base 10, replace each digit with its remainder mod 2, and read that number in binary. Switch it to base 10 and call this number a_(i+1). Show that for any a_1 less than 2^101, the sequence is periodic and has period 2^n for some n.
what do you mean by "switch it to base 10"?
Do you mean read that string of 1's and 0's as a base-10 number,
or convert it to base 10?
I suggest you start with a smaller exponent, and see what happens if it is 2,3,4 etc.
5^100 is very large to work with.
I mean that you read it in base 2 and convert it to base 10. I looked at small exponents and I’m stuck. Any help please and thank you.
To show that the sequence is periodic and has a period of 2^n for some n, we need to analyze the pattern that occurs when we follow the given process.
Let's start by understanding the given process step by step.
1. Start with a given integer, a_1, which is less than 2^101.
2. Multiply a_1 by 5^100. This is essentially shifting the binary representation of a_1 to the left by 100 places because 5^100 is equivalent to (2^2 * 5^2)^100, which can be simplified to 2^200 * 25^100, and 25 is 2^2 * 5.
3. Replace each digit of the resulting number with its remainder mod 2. This step effectively converts the number to its binary representation, as in the binary representation, the only possible remainders when dividing by 2 are 0 and 1.
4. Read this binary representation in base 10. This step converts the number back to base 10.
5. We call this resulting number a_(i+1) and repeat the same process (steps 2-4) to obtain a_(i+2), a_(i+3), and so on.
Now, let's observe the pattern in this process:
Since we are replacing each digit of the number with its remainder mod 2, every digit in the resulting number will be either 0 or 1. This means that the new generated numbers a_(i+1), a_(i+2), a_(i+3), and so on will be binary numbers.
Moreover, since we are multiplying by 5^100, which is a fixed value and does not change with each iteration, the rate at which each digit of the number changes will also be fixed. This implies that the pattern of digits in the binary representation of the resulting numbers will repeat after a certain number of iterations.
Now, let's consider the maximum possible length of the sequence (the period).
The length of the binary representation of a number n is given by ⌊log₂(n)⌋ + 1. In our case, a_(i+1) is a binary number, and its length is given by ⌊log₂(a_(i+1))⌋ + 1.
Since we are replacing each digit with its remainder mod 2, each digit will be either 0 or 1. This means that the maximum value of a_(i+1) will be when all the digits are 1, which is equivalent to 2^k - 1, where k is the number of digits.
Therefore, the maximum length of the sequence (the period) will be when a_(i+1) = 2^k - 1, where k is the number of digits in a_(i+1).
To calculate the maximum value of a_(i+1), we need to find the maximum number of digits (k) that a_(i+1) can have.
From step 2, we know that we multiply a_i by 5^100, which effectively shifts the binary representation of a_i to the left by 100 places. Thus, the maximum number of digits in a_(i+1) will be the maximum number of digits in a_i + 100.
Since a_1 is less than 2^101, it has a maximum of 101 digits in its binary representation. Therefore, the maximum number of digits in a_(i+1) will be 101 + 100 = 201.
So, the maximum value of a_(i+1) = 2^201 - 1.
Now, let's look at the pattern in the binary representation of a_(i+1) as we iterate through the process.
When we multiply a_(i+1) by 5^100, we are effectively shifting the binary representation of a_(i+1) to the left by 100 places. Considering the maximum value of a_(i+1) we calculated earlier (2^201 - 1), it means that we are shifting a maximum 201-digit binary number to the left by 100 places.
Let's consider the two extreme cases: when a_(i+1) = 2^201 - 1 and when a_(i+1) = 0 (which will occur when a_i = 0).
When a_(i+1) = 2^201 - 1, the next binary representation will be obtained by shifting it to the left by 100 places. Since it was already the maximum number (all 1s), shifting it will simply bring back the zeros at the beginning. Therefore, a_(i+2) will be a number with the same binary representation as a_(i+1).
When a_(i+1) = 0, it will remain 0 after shifting it to the left by 100 places.
These two extreme cases demonstrate that the pattern of digits in the binary representation of a_(i+1) will repeat after 2^n iterations, where n is the number of digits in a_(i+1). In our case, n = 201.
Therefore, for any a_1 less than 2^101, the given sequence is periodic and has a period of 2^201.