## Friday, January 27, 2012

### Which fraction has these digits ?

 Sven Van Caekenberghe posted these nice example on Pharo mailing list:

1/9801 asScaledDecimal: 200.
1/998001 asScaledDecimal: 3000.

This also works with:
1/9801 printShowingDecimalPlaces: 200.

We could conjecture that 1/99980001 asScaledDecimal: 40000 should give a nice serie of digits too.
But if we want to form our own fraction, how can we construct it ?
Let us consider a fraction in interval ]0,1[
In "decimal" notation (I say decimal, but it is valid in any other base b), this fraction print in base b with a head composed of head size digits, and a repeated tail composed of tail size digits 0.head_tail_tail_tail...

For example, b := 10, head := '123' and tail := '40', will lead to (fraction asScaledDecimal: tail size * 3 + head size) = '0.123404040s9'

I once thought we could extend the syntax with such notation to denote infinite repetition:
fraction := 0.123(40).

But we didn't, so what is the value of the fraction?
Let us work with numbers rather than strings:
t := tail ifEmpty:  ifNotEmpty: [Number readFrom: tail base: b].
nt := tail size.

If we had infinite series (lazy one would be preferred), we could define:
positiveIntegers := 1 to: Integer infinity.
infiniteTail := (positiveIntegers collect: [:i | t / (b raisedTo: nt * i)]).
fraction := (infiniteTail + h) / (b raisedTo: nh).

But even with such objects, we cannot evaluate this infiniteTail that easily.
Really? If we shift it by tail size digits, we will obtain this number with same infiniteTail:
infiniteTail * (b raisedTo:  nt) = (t + infiniteTail).

From this property, it is easy to get:
infiniteTail :=  t / ((b raisedTo: nt) - 1).

If we want a leading head, we simply have to shift above fraction:
fraction := (t / ((b raisedTo: nt) - 1) + h) / (b raisedTo: nh).

So, let us reconstruct Sven example:
| base tail |
base := 10.
tail := ((0 to: 97) , #(99) inject: '' writeStream into: [:s :n | n printOn: s base: base length: 2 padded: true. s]) contents.
^(Number readFrom: tail base: base) / ((base raisedTo: tail size) - 1)
-> 1/9801

Good. Now, this expression won't lead to nice fraction for any tail...
If we want a fraction with numerator = 1, we need to find a divisor of the denominator 999....99. That's the nice thing with Sven example. I don't know how or where he found it, but I guess it'll be hard to be as elegant. Oh, maybe thanks to the extension to any base you can play with it too (you will need to implement printShowingDecimalPlaces:base:).