===== Project Euler - Problem 151 =====
From [[http://projecteuler.net/index.php?section=problems&id=151|here]]
A printing shop runs 16 batches (jobs) every week and each batch requires a sheet of special colour-proofing paper of size A5.
Every Monday morning, the foreman opens a new envelope, containing a large sheet of the special paper with size A1.
He proceeds to cut it in half, thus getting two sheets of size A2.
Then he cuts one of them in half to get two sheets of size A3 and so on until he obtains the A5-size sheet needed for the first batch of the week.
All the unused sheets are placed back in the envelope.
{{ http://projecteuler.net/project/images/p_151.gif }}
At the beginning of each subsequent batch, he takes from the envelope one sheet of paper at random.
If it is of size A5, he uses it.
If it is larger, he repeats the 'cut-in-half' procedure until he has what he needs and any remaining sheets are always placed back in the envelope.
**Excluding the first and last batch of the week, find the expected number of times (during each week) that the foreman finds a single sheet of paper in the envelope.**
Give your answer rounded to six decimal places using the format x.xxxxxx .
**Answer: Find out yourself running forth! ;-)**
----
A solution using **gforth**:
#! /usr/bin/gforth
: p151 { a5 a4 a3 a2 -- F: res }
0.0e { F: res }
a5 a4 a3 a2 + + + { W: left }
1 left = a5 1 <> and if 1.0e to res then
a5 0 > if a5 1- a4 a3 a2 recurse a5 s>d d>f f* res f+ to res then
a4 0 > if a5 1+ a4 1- a3 a2 recurse a4 s>d d>f f* res f+ to res then
a3 0 > if a5 1+ a4 1+ a3 1- a2 recurse a3 s>d d>f f* res f+ to res then
a2 0 > if a5 1+ a4 1+ a3 1+ a2 1- recurse a2 s>d d>f f* res f+ to res then
left 0 > if res left s>d d>f f/ to res then
res
;
1 1 1 1 p151
." The answer is " 6 set-precision f. cr
bye
Runtimes:
luca@tux-laptop:~/tmp$ time ./p151.fth
The answer is not given here, but was checked ok in project euler.
real 0m0.087s
user 0m0.084s
sys 0m0.004s