When We Add Up Each Part of the Puzzle, They’re All Lies

Wherein we again look small — at the parts of the pieces — to try and find a larger pattern

THE WEEKLY CHALLENGE – PERL & RAKU #149 TASK 1

---

“…Many things have a plurality of parts and are not merely a complete aggregate but instead some kind of a whole beyond its parts…”

— Aristotle

---

Fibonacci Digit Sum

Submitted by: Roger Bell_West

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

Example

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

On the Subject of Number Theory

The land of Number Theory is such a weird and unstable place. Unwilling or unable to leave well enough alone, its adherents look for new footholds by alighting from one known position to another, spanning uncharted distances in the process, hoping to construct a bridge between distant lands and trying not to fall off the edge of the world.

In other words, a quite common approach to new discovery is to take two seemingly unrelated ideas and then slam them together to see if some new type of connection can be inferred from the collision. In this it shares certain aspects with experimental particle physics and college-student breakfast food choices after an all-night bender.

The cross-product mashups entertained can sometimes on the surface seem ridiculous, but its important to keep our eye on the ball: we’re ultimately looking for deeper truths in the mathematics that connects all things, so there will be connections everywhere we look — some obvious, some not. It’s finding these hidden parallels and symmetries that become the purview of Number Theory. And if we don’t look, we’ll surely never find them.

So, you know… anything goes. You never know what you might find out there when by definition you can’t see it. In this scenario we have two fairly mainstream ideas: summing the individual digits of a number and the venerable Fibonacci sequence. On the face of it I can see no obvious connection between the two.

Method

The definition of the sequence requested is not exactly new; it has an entry in the Online Encyclopedia of Integer Sequences, albeit without a large number of accompanying references and commentary.

A028840

Numbers k such that sum of digits of k is a Fibonacci number.

As mentioned, there isn’t a whole lot listed to flush out our knowledge on the subject. But no matter: I wasn’t there to look up an algorithm anyway, and we’re only checking now after the fact, because I got curious.

So let’s go back in time.

It seems to construct the sequence we’ll need a couple of bits of logic: a function that sums digits and a function that can tell us whether or not a number is a Fibonacci number. The first can be a straightforward examination of the digits composing a number, but the second sounds more complicated, as we’re dealing with an infinite sequence.

It turns out that isn’t though: on further consideration we find a twelve digit number can only maximally sum to 108, so we really aren’t talking about very many Fibonacci numbers at all. Eleven, to be exact, for any value up to (and including) one trillion. If we fill every digit in our candidate with a 9 we really can’t sum any higher, and so this sets an upper bound.

So how do we get our list?

As we’re working with so few Fibonaccis, perhaps we could make a list from all the numbers that can be assembled from every integer partition of each of the 11 Fibonacci numbers. You know, an active, constructive approach. For example, for the number 5, we have the partitions

5

4 + 1

3 + 2

3 + 1 + 1

2 + 2 + 1

2 + 1 + 1 + 1

1 + 1 + 1 + 1 + 1

which in turn can be arranged to yield the numbers

5, 41, 14, 32, 23, 311, 131, 113, 221, 212, 122, 2111, 1211, 1121, 1112, and 11111.

Not bad so far. But then again it’s early days. The 7 partitions of 5 yield 16 values. By the time we get to 8 we have 128 values. We seem to be exponentially expanding.

The problem with this approach is that we create far more numbers in a sparse pattern than we need for the limited portion of the sequence we can conclude to be complete. Using the same method we used above to place a upper bound on the highest Fibonacci number required — by filling the available digits with 9s — when we create the sequence up to 999 the maximum sum can only be 18, and the maximum Fibonacci number we will be able to sum to will have to be 13. For the Fibonacci number 13, however, we create such numbers as 1231231, which is quite a bit more than 1000.

In fact for the number 13, we construct over 3000 extra values. And it only gets worse from there.

The actual combinatorics involve a convoluted path: taking what is known as the multiset permutations for every set of integer partitions with a maximum value of 9 per part in each, summed over the Fibonacci numbers up to some maximum value. This is of course a whole crazy discussion in itself, but going down that particular rabbit-hole of unexpected byways turns out to yield a very simple result: 2^n-1 numbers generated for each value n. Or ok, very close to this, as after a point we are no longer allowed multi-digit partitions: 12, for instance, can’t be broken down into 10 + 2 or just kept as 12. So 8 has 128 numbers that can constructed, and 13 has about 4076, not 4096. And 35 should have around 34,359,738,368, but I haven’t been able compute the exact number to check. In any case we will need to work with these values to construct all sequence elements up to a million or so. Even tossing out candidates that are obviously over our upper limit it’s still a lot of numbers to process. Furthermore, this strategy computes to a limit, when what we’ve been asked for is a number of values. We have no idea what limit to pick to compute our theoretical 1 million elements.

Yea thats not going to work very well at all.

Alternately we could start incrementing up from 1 and evaluating each candidate, until we’ve gathered enough numbers. With a pair of functions to sum the digits and to check whether or not the given value is a Fibonacci we should be good to go. Which is pretty much where we started before our little excursion.

PERL 5 SOLUTION

We have, as stated, two functions are required, to sum the digits and then check the result against a list of Fibonacci numbers. To sum the digits we use substr to examine each digit in turn and add them to a running tally. For the Fibonacci numbers we could just hard-code them in and refer to that, but instead we’re going to make no assumptions and use a state variable to construct the sequence to as many values as we need and keep the results around between subroutine calls. If we are asked to evaluate a number greater than the largest so far created, we simply make more until we have enough. Once each number is created it is also immediately added to a parallel lookup hash for easy random access to the individual elements in the sequence. It’s all rather a moot point of course, as this method can quickly compute the first 1,000,000 terms in the sequence (the 1,000,000th is 13380892), and the largest Fibonacci required for this is 54. But then again it’s self-adapting to whatever we throw at it and again, it’s always good to not make assumptions.

For those curious after our previous foray into a constructive solution, there are, in the end, 84645 values in the sequence less than 1 million. The largest is 1,000,000 itself, as this adds up to 1, or F₁.

use warnings;
use strict;
use utf8;
use feature ":5.26";
use feature qw(signatures);
no warnings 'experimental::signatures';

my $N = shift // 1000;
my $candidate;
my @out = (0);

while ( ++$candidate ) {
    push @out, $candidate if is_fib( digisum($candidate) );
    last if @out == $N;
}

local $" = ', ';
say "@out";

sub digisum ( $num ) {
    my $sum;
    $sum += substr $num, $_-1, 1 for (1..length $num);
    return $sum;   
}

sub is_fib ( $num ) {
    state @fibs = ( 0, 1 );
    state %fhash = map { $_ => undef } @fibs;
    while ( $fibs[-1]+$fibs[-2] <= $num ) {
        my $next = $fibs[-1]+$fibs[-2];
        push @fibs, $next;
        $fhash{$next} = undef;
    }
    return 1 if exists $fhash{$num};
    return 0;
}

0, 1, 2, 3, 5, 8, 10, 11, 12, 14, 17, 20, 21, 23, 26, 30, 32, 35, 41, 44, 49, 50, 53, 58, 62, 67, 71, 76, 80, 85, 94, 100, 101, 102, 104, 107, 110, 111, 113, 116, 120, 122, 125, 131, 134, 139, 140, 143, 148, 152

raku solution

The Raku solution shares many similarities, but also has a few remarkable differences. First off we can draw values from our hash lookup from a lazily-defined list, that will automatically make new values of the sequence whenever we need to. How cool is that? The digit summing step is so simplified using the method chain .comb.sum that I just went ahead and inlined it into a combined grep filter, working on another lazy list of potential candidates. The array slice postscript ultimately defines how many elements we need to create; the lazy evaluation continues until we have enough.

Logically it serves the same purpose as as an incrementing value in an infinite loop with an escape condition, but, you know, this is much cooler.

unit sub MAIN ( $N = 25 ) ;

sub is_fib ( $num ) {
    state @fibs = (0, 1, 1, * + * ... *);
    state %fh;
    state $n = 0;
    while @fibs[$n] < $num  {
        %fh{ @fibs[++$n] } = 1; 
    }

    return %fh{$num}:exists
        ?? 1
        !! 0
}

my  @out = (0, | grep { is_fib( $_.comb.sum ) }, (0..*) )[0..$N-1];
say @out;

---