Re: OT: recurring decimals! -- > Programming Challenge? Message #10 Posted by Thomas Okken on 1 May 2010, 4:13 p.m., in response to message #9 by Katie Wasserman
Regarding the nonexistence of maximal primes in square bases, I think I found a proof.
Say q is a maximal prime in base c2. The base-c2 representation of 1/q has q-1 repeating digits, by definition of what it means to be a maximal prime. The equivalent representation in base c would appear to have 2q-2 repeating digits, which would be impossible. However, we need to rule out the possibility that the base-c representation actually has fewer than 2q-2 repeating digits; for example, 1/5 = 0.14638 = 0.00112; if a number can be a maximal prime in base c3 and c, why would the same thing not also be possible in base c2 and c?
Let's say you have a repeating fraction with r repeating digits in base c. If you convert this to base cn, the repeating part in the new base can be at most n times shorter, if n divides r. If you call that the best case, the worst case is that gcd(r,n)=1, in which case the base-cn representation has exactly as many repeating digits as the base-c representation. The base-cn representation will never have more repeating digits than the base-c representation, because n repetitions of the base-c repeating section (with length r) will always fit exactly in r base-cn digits.
Returning to the base-c2 vs. base-c case, what this means is that for any repeating fraction that has r repeating digits in base c2, the base-c representation must have a repeating section that is either 2r or r digits long. For 1/q, with q being a maximal prime in base c2, the length in base c2 of the repeating section is q-1; in base c, the length of the repeating section would then have to be either 2q-2 or q-1. The former is impossible because 1/q can never have more than q-1 repeating digits in any base, and the latter is also impossible, because q-1 is even, so the repeating section in base c2 would be (q-1)/2 digits long, contradicting the claim that q is a maximal prime in base c2.
Hence, no number q can be a maximal prime in base c2, Q.E.D.
Note that I'm making the important assumption that primes are always odd. Of course the number 2 is the one exception to that rule, and 2 is, in fact, a maximal prime in any odd base, including square bases. :-)
Proving the flat distribution of groups of 2 or more digits is a harder nut to crack. I think one should start by looking at the remainders that generate one specific next digit, e.g. 1...(q-1)/b will generate 0, and then look at the distribution of the subsequent remainders 1%q...(q-1)/b%q. I think the idea is pretty straightforward but the devil is going to be in the details.
Edited: 1 May 2010, 4:21 p.m.
|