' Zeckendorf number representation
DECLARE FUNCTION ToZeckendorf$ (N%)
' The maximum Fibonacci number that can fit in a
' 32 bit number is Fib&(45)
CONST MAXFIBINDEX% = 45, TRUE% = -1, FALSE% = 0
DIM SHARED Fib&(1 TO MAXFIBINDEX%)
Fib&(1) = 1: Fib&(2) = 2
FOR I% = 3 TO MAXFIBINDEX%
  Fib&(I%) = Fib&(I% - 1) + Fib&(I% - 2)
NEXT I%
FOR I% = 0 TO 20
  SixChars$ = SPACE$(6)
  RSET SixChars$ = ToZeckendorf$(I%)
  PRINT USING "### "; I%; : PRINT SixChars$
NEXT I%
END

FUNCTION ToZeckendorf$ (N%)
  ' returns the Zeckendorf representation of N% or "?" if one cannot be found
  IF N% = 0 THEN
    ToZeckendorf$ = "0"
  ELSE
    Result$ = ""
    FPos% = MAXFIBINDEX%
    Rest% = ABS(N%)
    ' Find the first non-zero Zeckendorf digit
    WHILE FPos% > 1 AND Rest% < Fib&(FPos%)
      FPos% = FPos% - 1
    WEND
    ' If we found a digit, build the representation
    IF FPos% >= 1 THEN ' have a digit
      SkipDigit% = FALSE%
      WHILE FPos% >= 1
        IF Rest% <= 0 THEN
          Result$ = Result$ + "0"
        ELSEIF SkipDigit% THEN ' we used the previous digit
          SkipDigit% = FALSE%
          Result$ = Result$ + "0"
        ELSEIF Rest% < Fib&(FPos%) THEN ' cannot use the digit at FPos%
          SkipDigit% = FALSE%
          Result$ = Result$ + "0"
        ELSE ' can use this digit
          SkipDigit% = TRUE%
          Result$ = Result$ + "1"
          Rest% = Rest% - Fib&(FPos%)
        END IF
        FPos% = FPos% - 1
      WEND
    END IF
    IF Rest% = 0 THEN
      ToZeckendorf$ = Result$
    ELSE
      ToZeckendorf$ = "?"
    END IF
  END IF
END FUNCTION