Peter
Peter Campbell Smith

Fibonacci sums
and unique digits squares

Weekly challenge 149 — 24 January 2022

Week 149: 24 Jan 2022

Task 1

Task — Fibonacci digit sum

Given an input $N, generate the first $N numbers for which the sum of their digits is a Fibonacci number.

Examples


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

Analysis

It's easy to see that such numbers are quite common, so scanning up from 0 will work quickly enough. So only two functions are required:

sum_of_digits($j)
is_a_fibonacci_number($k)

The first of these doesn't need a sub as it can be done in one line of Perl:

$s = eval(join('+', split(//, $j)))

The 'split' splits the number into an array of digits, the 'join' joins them together with plus signs, and the 'eval' evaluates the string of plusses.

The Fibonacci series is easy to extend, so let's start with just (0, 1), and when we are testing a number for being in the series, we'll extend the series far enough that the last member is more than the number we're testing.

And there you have it.

Try it 

Try running the script with any input:



example: 30

Script


#!/usr/bin/perl

# Peter Campbell Smith - 2022-01-24
# PWC 149 task 1

use v5.28;
use strict;
use warnings;
use utf8;

my ($n, $i, @fibs, @results);

$n = 20;

@fibs = (0, 1);   # initial fibonacci series
@results = ();

# count up until we have the required quantity of results
for ($i = 0; $#results < $n - 1; $i++) {
    push(@results, $i) if is_a_fib(eval(join('+', split(//, $i))));   # see note above
}

say qq[\nf($n) = (] . join(', ', @results) . ')';

sub is_a_fib {
    
    # returns true if the argument is a fibonacci number
    
    my ($arg, $i);
    $arg = $_[0];
    
    # make sure @fibs is long enough
    while ($arg > $fibs[$#fibs]) {
        $fibs[$#fibs + 1] = $fibs[$#fibs] + $fibs[$#fibs - 1];   # add one fib to @fibs
    }
    
    # check if $arg is in @fibs
    for ($i = $#fibs; $i >= 0; $i--) {
        return 1 if $arg == $fibs[$i];
    }
    return 0;
}
        



Output


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

 

Any content of this website which has been created by Peter Campbell Smith is in the public domain