Ich habe ein Rechteck mit ganzzahligen Seitenlängen. Dieses Rechteck möchte ich nun in Quadrate zerlegen, die eine Zweierpotenz als Seitenlänge haben. Dabei sollen so wenige Quadrate wie möglich entstehen.

Als Beispiel betrachten wir ein 9 x 6-Rechteck. Ein solches Rechteck lässt sich wie folgt in zwei Quadrate der Seitenlänge 4, vier Quadrate der Seitenlänge 2 und sechs Quadrate der Seitenlänge 1 zerlegen:

Nun suche ich nach einer Möglichkeit, dies nicht zeichnerisch, sondern durch eine Formel oder einen Algorithmus (gerne in Pseudocode) zu bestimmen. Hat jemand eine Idee, wie man da vorgehen könnte? Meine bisherigen Ansätze waren nicht wirklich zielführend und sicherlich auch zu kompliziert gedacht...