## 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:
h := head ifEmpty:  ifNotEmpty: [Number readFrom: head base: b].
t := tail ifEmpty:  ifNotEmpty: [Number readFrom: tail base: b].
nh := head size.
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).

We have no such ready made infinity, nor lazy collections...
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:).