Sunday, June 24, 2012

last-digit sequences

When you look at the last digits of an Integer sequence, you get a whole new Integer sequence. For example, if you look at the last digit of the sequence a_n = n^2 -n +1, you get the repeating last-digit sequence shown above (it has a period of 5). Neat thing: any sequence "like" this one will always have a repeating last-digit-sequence, and that last-digit-sequence will have a period of 1, 2, 5, or 10.

Here is another example that has a last-digit sequence with period 10:

Just looking at the last digits of powers of n provides other simple examples (see this old post).

Except when the terms are negative, last digits can be obtained by using modular arithmetic and working “modulo 10”, “ 54 mod 10” is 4, “12 mod 10” is 2, etc. So for the most part, instead of saying "last digit"  we can just say “mod 10” to get the last digits. When negatives are involved, the last digits can be found by “mod 10 – 10,” so without loss of generality we’ll just say "mod 10" when we want to grab the last digit of some number.

Let's look at sequences that you get from polynomials with Integer coefficients, a_n that are of this form:
It turns out that this kind of sequence modulo 10 repeats itself with a period that divides 10 - you can see this is true by proving that
This statement says that the sequence, mod 10, will repeat itself every 10th term - so its period must be a divisor of 10 in order for this to happen, which means its period must be 1, 2, 5 or 10.

One way to see this true is to consider any term  in the sum that defines a_n, and verify that when you sub in n +10, you'll get something that is congruent to n, modulo 10. This just requires ye-olde binomial theorem: all terms in the expansion except for one are congruent to zero mod 10 and just vanish:

These sequences sometimes also have nice symmetry in their last-digit sequences. When this symmetry happens you are able to find some value k where:
The value of k/2 provides you with an axis of symmetry for your sequence. For example, the first sequence shown above, a_n = n^2 -n +1, (this sequence is "Hogben's central polygonal numbers," mentioned here), there is a symmetry at = 3, so our k is 6.

Here's another similar observation about these kinds of sequences (those generated by polynomials with Integer coefficients) - their terms are either always even, always odd, or alternate between even and odd values (e.g. you won't get a sequence that goes "even, even, odd, .." or some combination other than the three possibilities mentioned). Can you see how you can show that this is true using similar arguments to the ones used here for last-digits?