===== Project Euler - Problem 115 =====

From [[http://projecteuler.net/index.php?section=problems&id=115|here]]

NOTE: This is a more difficult version of [[http://projecteuler.net/index.php?section=problems&id=114|problem 114]].

A row measuring n units in length has red blocks with a minimum length of m units placed on it, such that any two red blocks (which are allowed to be different lengths) are separated by at least one black square.

Let the fill-count function, F(m, n), represent the number of ways that a row can be filled.

For example, F(3, 29) = 673135 and F(3, 30) = 1089155.

That is, for m = 3, is can be seen that n = 30 is the smallest value for which the fill-count function first exceeds one million.

In the same way, for m = 10, it can be verified that F(10, 56) = 880711 and F(10, 57) = 1148904, so n = 57 is the least value for which the fill-count function first exceeds million.

**For m = 50, find the least value of n for which the fill-count function first exceeds one million**.

**Answer: Find out yourself running forth!**  ;-)


----

A solution with **gforth** (run in 0.170 seconds):

<code forth>
#! /usr/bin/gforth

Create X 1000 cells allot  \ allocate X[1000]

50      constant M
1000000 constant L
0       value    R

: solve
    1 X !
    1
    begin
        0 over cells X + !
        dup M > if
            dup M - 0 do
                dup M - i - X i cells + @ * over cells X + dup @ rot + swap !
            loop
        then
        dup cells X + @ R + to R
        1+
        R L >
    until
    ." Solution is " 2 - . cr
;

solve
bye
</code>