Perl Weekly Challenge 149: Fibonacci Digit Sum

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.