OT: recurring decimals!



#2

Casio have recently updated some of their basic scientific calculators: the FX-83 ES and FX-85 ES have become the FX-83/5 GT Plus. Amongst other features, the new models allow the entry of recurring decimals, and will display results in this format as well!

I'm not sure if this is really of any practical use, but it is fun to play with! Does anyone know if this has been done before on a calculator?

Nigel


#3

I don't think this has ever been used in a calculator, but I wrote a library (for the Ruby programming language) that handles recurring decimals:

(look for "Repeating Numerals" in the documentation)

#4

Although exact rational arithmetic could be useful, I can't think of much use for these.

Still, it demonstrates that there is still innovation in the calculator industry.


- Pauli

#5

I doubt that it's of much practical use, but it is fun to think about.


Repeating fractions are like

a . b1...bn c1...cm

in other words

a + (b + c / (10m - 1)) / 10n

(e.g., 1 / 12 = 0.083, so a = 0, b = 8, c = 3, n = 2, and m = 1)

which is clearly a rational number.


It's not a very efficient way to represent rational numbers;
the repeating-fraction representation of a rational number p / q can have up to q - 1 repeating digits.

What I find interesting here is that this means that for any integer q, there must be a number 10r - 1, where r < q, that is divisible by q.


I think I'm starting to understand why some people find number theory interesting. :-)


Edited: 28 Apr 2010, 9:26 p.m.


#6

Quote:
It's not a very efficient way to represent rational numbers; the repeating-fraction representation of a rational number p / q can have up to q - 1 repeating digits.

From some work I did on this in college....

All 'q' that have q-1 repeating digits (i.e., the maximum number of digits in the repetitions) are prime numbers -- call these maximal primes. (Of course, not all prime numbers have the maximal number of digits.)

Here's the interesting thing I found and I'm sure is well know somewhere out there.... but it wasn't to me in 1974 when I figured this out for a math class project and later proved it.

If you look at the digits in one repetition of a maximal prime you'll find that it's a perfectly flat distribution. For example: 1/181 is a repeating with 180 digits in the repetition. Each digit 0 though 9 occurs exactly 18 times in this sequence. Furthermore each double digit 00 to 99 occurs exactly 1 or 2 times. This is true for all number bases, naturally. In other words, the frequency of each number within one repetition is as close to the average as possible.

After I conjectured this I wrote one of my first computer programs to prove this to be the case for numbers up to 1 million. Then I came up with a simple proof. I researched it some and couldn't find any prior reference to it, but never tried to published this. (I was just a freshman in college who would have listened.)

Anyway, it made for a fun computer program to write if nothing else.
This is easily doable on almost any HP calculator with indirect storage registers, BTW. This might make a good little programming challenge!

-Katie


#7

If q is a maximal prime, all the possible remainders 1...q-1 will occur during the long division, each exactly once per cycle, and so the digits generated for base b are floor(b/q), floor(2*b/q), ..., floor((q-1)*b/q), which trivially leads to a perfectly flat distribution of the digits 0...b-1.

The double-digit phenomenon seems a little trickier to explain. Maybe analyze the problem in terms of base b2 instead of base b? Hmmm...

UPDATE: Generalized from base 10 to base b.


Edited: 1 May 2010, 12:50 a.m.

#8

What makes a prime number q a maximal prime?


One way q can fail to be a maximal prime is when it divides the base. For example, 5 is a maximal prime in base 2, because 1/5 = 0.00112, but in base 10, 1/5 isn't even a repeating fraction.

What about 11 in base 10? 1/11 = 0.09, only 2 repeating digits... why not 10?

Any prime q that does not divide the base b is guaranteed to divide some number bn-1, where n <= q. This must be true because long division is basically a state machine whose only state is the most recent remainder, which must be less than q (because p mod q < q, always) and greater than 0 (because otherwise the fraction wouldn't repeat), so the repeating part of the fraction is at most q-1 digits long. Discarding any non-repeating part, any fraction with r repeating digits can be represented as a rational number whose denominator is br-1, so q must divide br-1.

My conjecture: a prime number q is a maximal prime in base b if and only if it does not divide b, and does not divide any bn-1, where n < q.


In base 10, the number 11 fails this test because it divides the number 99, which is b2-1, and 2 < 11.


#9

It seems that for bases b, where b is a square, there are no maximal primes.


Try this program:

#include <stdio.h>

int main(int argc, char *argv[]) {
int a, b, bsq, base, d, r;
if (argc < 2 || sscanf(argv[1], "%d", &base) != 1) {
fprintf(stderr, "Usage: %s base\n", argv[0]);
return 1;
}
a = 1;
while (1) {
next_a:
a += 2;
b = 1;
bsq = 1;
while (1) {
b += 2;
bsq += (b - 1) << 2;
if (a < bsq)
break;
if (a % b == 0)
goto next_a;
}
r = 1;
d = 0;
while (1) {
d++;
r = r * base % a;
if (r == 0)
goto next_a;
if (r == 1) {
if (d == a - 1)
printf("%d\n", a);
goto next_a;
}
}
}
return 0;
}

Save it as maxprimes.c, compile it, and run it like

./maxprimes <base>

#10

I haven't run your code yet, but that's an interesting find. I don't have an intuitive enough sense of number theory to see why that should be.

As to the matter of number distribution in the repeating series of a maximal price. It's not just single and double digit numbers that have a flat distribution it's all numbers. So if you had a repeating decimal with a period of 10,000 digits all 1 digit numbers would occur 1000 times, all 2 digit numbers would occur 100 times, all 3 digit numbers would occur 10 times. and 4 digit numbers would occur once. I agree that the proof isn't interesting, but this characteristic is, I think.

-Katie


#11

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.


Possibly Related Threads...
Thread Author Replies Views Last Post
  wp34s Adding decimals to fractions Norman Dziedzic 11 1,229 05-06-2011, 02:25 AM
Last Post: Walter B
  HP 20S recurring key identification Andrew 5 675 11-22-2010, 03:19 PM
Last Post: Walter B
  PI Decimals calculation on HP41c Philippe 12 1,183 05-04-2005, 09:01 AM
Last Post: Marc
  floating Decimals HP 12c Marge 5 634 10-19-2004, 11:00 PM
Last Post: Karl Schneider
  convert fractions to decimals? Buried Alive 2 434 08-29-2004, 06:59 AM
Last Post: Buried Alive
  Strange recurring HP41CX at $440 on eBay sergio 13 1,306 08-27-2003, 10:06 AM
Last Post: Axel Poqué
  41CV Need my decimals back Jen 2 433 12-20-2001, 03:47 AM
Last Post: thibaut.be

Forum Jump: