# IBM Research Ponder This (June Challenge)

This was the challenge in last month's 'IBM Reseach Ponder This'. I just cannot get my head around the solution posted. Can someone explain further?

Challenge

Find a rational number (a fraction of two integers) that satisfies the following conditions:

1)Its denominator is five digits long and all of them are different.

2)In the infinite decimal representation, every digit occurs an equal number of times in the digits from one billion to two billion places to the right of the decimal point (inclusive), except for the last digit in the denominator, which occurs twice as often as the other nine digits.

3)Its numerator contains as few different digits as possible.

Update 6/4: To clarify the problem, here is an example: 5/17 = 0.294117647058823529411764705882... and in the 11 digit in the places 20-30 after the decimal point the digit 7 (the last digit of the demonimator) appears twice as many times as the digit 4, but not twice as many as the digit 9 (which does not appear there at all).

Solution

The way to have one digit appear twice as many times as the other nine is to set a period of 11 digits. To do that, we need the fraction to be X/99999999999. Factoring the denominator leads us to 21649 as the denominator, and looking at the possible numerators we find that 639/21649 solves the first two conditions. To get fewer number of distinct digits, 646/21649 may seem to be the best solution (there are only two different digits), but using improper fractions, we can get the best solution: 333333/21649.

• Can you be more specific about what part you don't understand? – Nate Eldredge Jul 15 '13 at 20:12
• I didn't understand any part of the solution. I am looking for a more elaborate explanation. – The mach Jul 15 '13 at 20:50

A number with decimal notation $0.NPPPPPP...$, where $N$ and $P$ are groups of digits, is of the form $$\frac{N(10^R-1)+P10^{S+R}}{10^s(10^R-1)},$$ where $S$ is the length of $N$ and $R$ is the length of $P$.

First notice that to have a decimal expansion of period $r$ the denominator has to be a divisor of $10^S(10^r-1)$. Let $x$ be the number of times a digit different from the last in the denominator appears in the range 1B to 2B first digits of the decimal expansion. Then that special digit appears $2x$ each of the others appear $x$. So, $2x+x+x+x+x+x+x+x+x+x=2x+9x=11x=1B$.

I think they made a guess, that perhaps can be also proven if one works carefully, that since we want small numerator we may also want small denominator, and then a small period. Then they take $11$ as the period, $N=S=0$. So the denominator is a divisor of $10^{11}-1$. They find the only divisor of $10^{11}-1$ of $5$ digits and no repeated digits. That is that $21649$. Then, search for a numerator (make the computer do it).

For example, since they don't want repeated digits in the denominator then the factor $10^S$ must cancel out, pretty much completely. So the numerator must be divisible, at least, by $10^{S-1}$. So, $N$ must be divisible by $10^{S-1}$.

This entire question is strongly connected with a simple, yet profound observation: In a given base $b$, the rational numbers of the form $\frac{k}{b-1}$ have a repeating 'decimal' in the given base $b$ of length one, and in fact, for each $k$ in $\{1,...,b-2\}$, that the numeral of that repeated digit is $k$.

More generally, a repeated decimal of length $n$ (in base $b$) can always be expressed as $k/(b^n-1)$ for some natural number $0<k<b^n-1$. This is a consequence of Fermat's Little Theorem and a basic observation about the standard division algorithm (adapted to base $b$).

I made this observation when I was studying the question 'How long is the repeating part of the decimal expression of $1/n$ for any $n$ (in base $10$)?' and quickly generalized it to arbitrary base $b$ (it's a fairly well-known result from elementary number theory, as it turns out).