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

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

HINWEIS: Dies ist eine schwierigere Variante des [[http://projecteuler.net/index.php?section=problems&id=114|Problem 114]].

Eine Reihe mit der Länge n Einheiten enthält rote Blöcke der Mindestlänge m so, dass zwischen zwei roten Blöcken immer mindestens ein schwarzes Quadrat liegt. Die roten Blöcke dürfen verschiedene Längen haben. (Siehe Bild beim Problem 114.)

Die Füll-Funktion F(m,n) soll die Anzahl verschiedener Möglichkeiten darstellen, in denen die Reihe gefüllt werden kann. 

Zum Beispiel sind F(3,29) = 673135 und F(3,30) = 1089155.

Das bedeutet, für m=3 ist ersichtlich, dass n = 30 der kleinste Wert ist, für den die Füll-Funktion eine Anzahl ergibt, die eine Million überschreitet. In der gleichen Weise findet man, dass F(10,56) = 880711 und F(10,57) = 1148904 ist, so das n = 57 der kleinste Wert ist, bei dem die Füll-Funktion zum ersten mal eine Anzahl von über eine Million Möglichkeiten anzeigt. 

Für m = 50 finde den kleinsten Wert n für den die Füll-Funktion zum ersten mal eine Anzahl von einer Million Möglichkeiten übersteigt.

**Antwort: Finde es selbst heraus mit Forth**  ;-)


----

Eine Lösung mit **gforth** (ist in 170 Millisecunden gelaufen):

<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>