NAVINDRA UMANEE

I came across Google's billboard challenge the other day. The most interesting part of the problem, to me, seemed to be how to calculate the digits of e to the required precision.

In particular, I thought it would be interesting to view the problem from a `stream' point of view, a concept I had come across several years ago as an undergraduate student.

Why not generate the digits of e on the fly, as and when needed, with no arbitrary limit as to the precision? My goal was to formulate the answers to the two problems as:

(filter-stream prime? (ten-consecutive-digits-stream (e-stream)))
(filter-stream sum-49? (ten-consecutive-digits-stream (e-stream)))

Elegantly expressed in Scheme, e-stream generates the infinite digits of e, which are then passed on to ten-consecutive-digits-stream which constructs another infinite stream consisting of sequences of ten consecutive digits of e. Finally, filter-stream applies the required test (either for primality or for the condition that all the digits in the number sum to 49) and generates an infinite stream consisting of all the possible results.

Of course, e-stream itself should be constructed from another infinite stream, the reciprocals of factorials, itself constructed from the infinite stream of factorials.

Was this feasible?

In my personal implementation, I ended up straying from this ideal due to a practical compromise. My most recent solution looks like:

(define ten-e-stream (ten-consecutive-digits-stream (e-stream 10000)))
(define prime-stream (filter-stream prime? ten-e-stream))
(define sum-49-stream (filter-stream sum-49? ten-e-stream))

Since the results of stream computations are memoized, using the named ten-e-stream instead of creating new streams for each solution allows us to avoid many redundant recomputations. This is simply an implementation improvement over my original formulation.

The compromise is that I now decide beforehand the maximum precision that e-stream will yield. In the above case, only up to 10000 digits of e can be generated by the stream. They will, however, be generated on the fly as and when required as opposed to being pre-computed.

The reason for the compromise is that I chose to use Scheme's bignum representation for the digits of e; having the maximum desired precision in advance simplifies the implementation and improves performance by allowing us to use the results of previous computations.

A possible approach towards generating a proper infinite stream would be by using rationals (implemented as a pair of bignums) to represent e, providing as much precision as required. Although I have yet to implement or test this approach, I hope that Google will offer me a job in the meanwhile.