Tuesday 1 September 2009

I was recently reading an interesting blog posted by Rick Regan at Exploring Binary
talking about the binary expansion of base ten numbers that are made up of repeating nines...

"I discovered a cool property of positive integers of the form 10n-1, that is, integers made up of n digits of 9s: they have binary representations that have exactly n digits of trailing 1s. For example, 9,999,999 in decimal is 100110001001011001111111 in binary. "

Rick went on to show that this must always be the case with some pretty simple algebra. He noticed that the part of the number preceding the repeating ones is the binary for 5n-1... ok here is a simple example... 102-1 =99 in base ten and in base two that is 1100011,.... the two repeating 1's at the end have a value of 22-1, the 11000 in front is the binary expression for 24 or 52-1.
Rick showed that 10n-1 can always be expressed as
(5n – 1) 2n + (2n – 1)...

It occurred to me as I read his blog, that we could also expres 10n-1 as

2n (5n) - 5n + 5n-1 by adding and subtracting 5n instead of 2n

Regrouping that as (2n-1 )5n +( 5n-1) shows that when expressed in base five, 10n -1 will begin with 2n-1 base five followed by a string of n fours,

9 [5] = 1 4

99[5]= 344

999[5]= 12444


A similar event happens (I think, but do not prove) for any (pq)n -1 if p and q are (relatively?) Prime when expressed in base p or base q
... for example instead of 10n-1, if we used 6n-1 we would get
2n(3n) - 2n+2n-1 In base two that would show up as the base two number for 3n followed by a string of n ones.

For example 63-1 in base two is 11010111. The front part, 11010, is 26 or 33-1 in base ten, and then followed by three ones..

We could do the same switch to express it in base three.
The same number (63-1) in base three would give 21222, with 21 in front being the base three for 7 or 23-1 and then followed by a string of three twos..

If you want to explore binary problems, he Rick also has a convertor on his web page to go between decimal and binary. Of course you can always use Wolfram-alpha [I have a little "alpha" gadget on my I-google page to keep it handy]... By writing "convert 315 base 8 to base 3" it gave me 211213.

As a side note, I find that using alternate bases helps lots of kids really get a feel for polynomials they never had before (and perhaps a deeper understanding of the decimal system they thought they had fully mastered. Quickly students, can you see why 11010111 in base two would be 3113 in base four?


Anonymous said...

Re: "Ends in 4s": Nice! I like the algebra. But to show that the base 5 representation has EXACTLY n trailing 4s, you also need to show that the low order digit in the base 5 representation of 2^n - 1 is never 4. I think this is true based on some values I tried: 2^n - 1 in base 5 seems to always end in either 0, 1, 2, or 3 (corresponding to when 2^n - 1 in base 10 ends in 5, 1, 7, or 3, respectively). You'll have to prove it though. (Yes, there's a mod 5 thing going on there, but I think you have to go back and prove that 2^n - 1 in decimal always ends in 5, 1, 7, or 3.)

Re: Your relatively prime conjecture: I have not thought about it yet.

Re: Wolfram Alpha vs my converter. My converter is more limited in that it only does decimal/binary conversions, but it is arbitrary precision and will thus handle bigger/smaller numbers than Wolfram Alpha.

BTW, there's a typo in your post: you say 2n instead of 2^n in the sentence that starts "Rick showed that...".

Pat's Blog said...

thanks, I hope the typo is corrected.
Now, about the 2^n -1, the binary expansion of 2^n-1 will always be a string of ones, so we can prove that any power of 2^n -1 mod five will NOT have a remainder of four..because the sequence of modulii start at 1 (for 2^1-1) and each new value increases the power by one.
We know that the powers of 2 (beyond 2^0) proceed with base five modulii of 2, then 4, then 3, then 1.... and then repeats this same cycle....
so if we start at one, we can anticipate the sequence of base five modulii by seeing that they too will loop, 1+2---> 3
3+ 4 ---> 2
2+3----> 0
0+1 --->1
and we are back to the start...
so it is the first value plus the rhythm of modulus of the sequence of powers of two that guarentee they will always be some number other than four.