Forth-eV Wiki

From here

NOTE: This is a more difficult version of 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):

#! /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