Given an input

`$N`

, generate the first`$N`

numbers for which the sum of their digits is a Fibonacci number.

```
f(20)=[0, 1, 2, 3, 5, 8, 10, 11, 12, 14, 17, 20, 21, 23, 26, 30, 32, 35, 41, 44]
```

This is sequence A028840 in The On-Line Encyclopedia of Integer Sequences.

We need to do two things: given a number, find the sum of its digits, and given a number, check whether that number if a Fibonacci number.

The first taks is similar to what was needed in week 133, so we can reuse the code.

First, we create a method which, given a (non-negative) integer, returns the sum of its digit. We do this by getting the digits one at a time, from the right, using modulus and integer division:

```
sub digitsum ($number) {
my $sum = 0;
my $base = 10;
while ($number > 0) {
use integer;
$sum += $number % $base;
$number /= $base;
}
return $sum;
}
```

To check whether a number is a Fibonacci number, we keep a hash which
contains Fibonacci numbers. If we have a number `N`

of which we want
to know whether it's a Fibonacci number, we first check what the largest
number in our hash is. If it's less than `N`

, we generate successive
numbers until we reach or exceed `N`

. Then we do a simple look up.

```
sub is_fib ($n) {
state $fib = {0 => 1, 1 => 1};
state $fib_prev = 0;
state $fib_last = 1;
while ($fib_last < $n) {
($fib_prev, $fib_last) = ($fib_last, $fib_prev + $fib_last);
$$fib {$fib_last} = 1;
}
$$fib {$n}
}
```

We can then print the numbers in a simple loop:

```
while (<>) {
for (my ($k, $N) = (0, 0 + $_); $N > 0; $k ++) {
$N --, print "$k " if is_fib digitsum $k
}
print "\n";
}
```

Find the full program on GitHub.

bc doesn't have hashes. So, we keep the generated Fibonacci numbers in an array. Once we have generated enough, we will do a binary search to see whether the input number is a Fibonacci or not.

```
fib_prev = 1
fib_last = 1
fib [0] = 0
fib [1] = 1
fib_count = 2
define is_fib (n) {
auto t, min, max
while (fib_last < n) {
t = fib_last
fib_last = fib_prev + fib_last
fib_prev = t
fib [fib_count] = fib_last
fib_count = fib_count + 1
}
min = 0
max = fib_count
while (min < max) {
mid = (min + max) / 2
if (fib [mid] == n) {
return (1)
}
if (fib [mid] < n) {
min = mid + 1
} else {
max = mid
}
}
return (0)
}
```

Find the full program on GitHub.

For our Scheme solution, we use a recursive solution to calculate the sum of the digits of a number:

```
(define (digit_sum n)
(define base 10)
(if (= n 0) 0 (+ (modulo n base) (digit_sum (floor/ n base)))))
```

To check if a number is a Fibonacci number, this time, we're not storing numbers generated so far. We use pure recursion:

```
(define (_is_fib n prev last)
(cond ((= n prev) #t)
((< n prev) #f)
(else (_is_fib n last (+ last prev)))))
(define (is_fib n) (_is_fib n 0 1))
```

Since recursion is the name of the game in Scheme, we use recursion for the loop which prints out the numbers:

```
(define (digit_fib k n)
(cond ((= n 0) #f)
((is_fib (digit_sum k))
(begin (format #t "~d " k) (digit_fib (+ k 1) (- n 1))))
(else (digit_fib (+ k 1) n))))
```

Here, `k`

is the first number to check, and `n`

is the amount of
numbers we still want to check. The main program (also recursive)
looks like this:

```
(define (main)
(define n (read-line))
(define k 0)
(if (not (eof-object? n))
(begin
(digit_fib 0 (string->number n))
(newline)
(main))))
```

Find the full program on GitHub.

We also have implementations, all similar to the Perl one, in:

AWK, Bash, C, Go, Java, Lua, Node.js, Pascal, Python, R, Ruby, and Tcl.