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?

Thursday, June 14, 2012

put in one's place

Consider, if you will, the question "What is the last digit of 4316 * 12  + 511?"

One way to quickly answer "what is the last digit?" questions like this is to realize that you don't need to do the full calculation - only the last digits of each number in the problem contribute to the last digit in the answer. So, you just need to calculate 6 * 2 + 1 and look at the last digit of that, which is 3.

When can we use this short-cut? With impunity when only multiplication and addition of positive Integers are involved - here only digits-in-the-ones-place of the inputs affect the digit-in-the-ones-place of the output. If you throw multiplication's tricky partner division into the mix, then I think that all bets are off (digits in all places affect the ones position in the result when you divide). However, we can still proceed with caution when  subtraction and negative Integers are in play: if we get a negative along the way while we are looking at the ones place, we need to pause and see if we should have "borrowed" from the tens place that we were ignoring.

For example, what is the last digit of (91536 - 648) * 12? Ignoring everything except the last digits in the original problem we have (6 - 8) * 2 = ( -2 ) * 2. At this point, we need to stop and realize that instead of keeping the -2 we should have borrowed from the tens position of  91536, giving us an 8 in the ones position, so we should have (8) * 2 = 16, so the last digit of (91536 - 648) * 12 is 6.

PS: The rest of the Peanuts cartoon featuring Peppermint's inventive rules for arithmetic can be found here.

Wednesday, June 6, 2012

more simple-yet-complex fractals


I'm back to playing around with fractals that are generated by looking at complex points that stay bounded when (repeatedly) plugged into a simple quadratic expression, as described here and here. I liked the pictures that came out, so I thought I would post them. :)

As mentioned previously, I'm using Processing for this, but now am using a Processing plugin for Eclipse (I'm currently using proclipsing, but I think there are other plugins available). I'm guessing that few people will be pleased doing this - people who like Processing's simplified view of Java may be intimidated by Eclipse, while hard-core Java programmers would likely not see much benefit in using Processing's library (I'm likely selling Processing short in thinking this -  I only have used a small bit of Processing and don't have a full appreciation for what it does).  But I like the simple API and model that Processing provides, and much prefer using a real IDE and writing most code outside the PApplet class. So, right now, I'm liking it just fine and would recommend it to anyone who thinks they might have similar preferences.