The 51st Little Piece of String

Wherein we open the drawer and show off our collection of strings too short to keep…

THE WEEKLY CHALLENGE – PERL & RAKU #150 TASK 1

---

“Yes! I’m me! I am careful and logical and I look up things I dont understand! When I hear people use the wrong words, I get edgy! I am good with cheese. I read books fast! I think! And I always have a piece of string! Thats the kind of person I am!“
— Terry Pratchett

---

Fibonacci Words

Submitted by: Mohammad S Anwar

You are given two strings having same number of digits, $a and $b.

Write a script to generate Fibonacci Words by concatenation of the previous two strings. Finally print 51st digit of the first term having at least 51 digits.

Example:

    Input: $a = '1234' $b = '5678'
    Output: 7

    Fibonacci Words:

    '1234'
    '5678'
    '12345678'
    '567812345678'
    '12345678567812345678'
    '56781234567812345678567812345678'
    '1234567856781234567856781234567812345678567812345678'

    The 51st digit in the first term having at least 51 digits '1234567856781234567856781234567812345678567812345678' is 7.

On the Subject of Fibonacci Words

The Fibonacci sequence is defined by what is known as a “recurrence relation“. This means that elements previously defined in the sequence reoccur later, as components in the formula for making new elements, according to certain rules of construction. Thus it follows that values at points in the sequence cannot generally be known until the required previous values they are contingent on have themselves been constructed. A time-line is inferred. On the face of it an ordering becomes necessary; to evaluate an arbitrary n-th member of the sequence we need to work backwards recursively, defining the component parts, and their components, as required until we arrive at known values and can return back up the line.

The recurrence relation of the Fibonacci numbers is

F(n) = F(n-1) + F(n-2)

but this is not the only recurrence relation that can exist, and many variations have been explored. This, as they say, is just the tip of the iceberg.

In the simplest recurrence form, a new element is a function of the value for the single preceding element, such as each element is twice the previous. The Fibonacci numbers use the sum of the two previous elements, which makes them considerably more interesting in their properties.

The specific Fibonacci sequence works forward from the starting values (0,1) but other initial conditions can be used with the same recurrence to create variant sequences. Altering the coefficients of the components is another option, as is changing the operation acting on them. Continuing, we could also use three or more elements, or select not the elements immediately proceeding but rather some other combination of placements relative to the new value.

One interesting quality about these sequences is how the recursive definition relates to such other mathematical ideas such as series expansions and generating functions. The fact that, recursive definition notwithstanding, the n-th element of the Fibonacci sequence can be directly calculated in what is known as a closed-form expression, using a function of n alone, reveals deep connections between linear recurrence relations and linear differential equations. That expression, by the way, is known as Binet’s formula.

This generalized branching out from the original, specific definition of the Fibonacci numbers ultimately brings us to the idea that we needn’t even require numbers to apply a recurrence relation. The method of construction is the essential pattern: that this is made from that and that, and those things are themselves assembled from smaller components, all according to a defined set of rules that remain the same independent of scale. The one-millionth term is computed from the previous two, in the same way the third term is. If we use strings instead of numbers, and in a manner analogous to addition concatenate the strings, merging them together to make one long string, we have what is known as a sequence of Fibonacci Words. If the initial conditions specify that the strings have equal length, as is the case here, than the lengths of the strings composed will follow the Fibonacci sequence, with the values multiplied by the word length.

The term “Fibonacci word” is often used for the closely-defined sequence using the two binary digits (0,1) as initializers and applying concatenation. This task takes a broader approach, allowing any equal-length strings of digits for the starting values.

---

Unary notation, using one less digit than binary, can be thought of as moving around piles of sticks. Starting with the two “words” of a single thing and nothing, the resulting sequence, viewed as numbers in unary notation, is not just similar to but is the Fibonacci sequence.

Starting with a null, empty string (using ” for this lack of a character) we initialize with

(”, 1)

Once we start generating new values we get

”, 1, 1, 11, 111, 11111, 11111111, …

As we can see the count of the 1s shows the Fibonacci sequence in unary:

0, 1, 1, 2, 3, 5, 8, …

Method

We will still use decimal notation of the sequence index, and construct the terms the same way, only applying the string concatenation operator instead of adding the values.

Because this operation is not commutative, we need to specify that F(n) = F(n-2) • F(n-1). That is, the order of original creation will be maintained in the construction of new strings.

Because our indexing is 0-based the 51st character is located at index 50.

PERL 5 SOLUTION

We are asked for the various strings produced in the sequence, and once we find a member with 51 or more characters to present the 51st character found. So we will start from our given kernel and make new elements, noting the length of each along the way until we find one long enough.

As we need to report the strings created when we’re done we’ll keep them all this time. This is likely to cause memory problems in a general-purpose solution but the limitations on the problem-space make that irrelevant to the task at hand. We could address this by printing out strings as we form them, offloading the “memory” to the output — be it a written page or terminal window — and making it someone else’s problem. Then we would only need to keep the previous two strings in a buffer. This approach might make it more practical to answer such questions as “what is the 50th element”, which for the example given will have 50 billion or so digits.

But again, we’re not going to do that.

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

my $zero = shift // qw( 1234 );
my $one  = shift // qw( 5678 );

my @F = ($zero, $one);

while (length $F[-1] < 51) {
    push @F, $F[-2] . $F[-1]
}

say "the words generated, with a helpful guide:\n";
say $_ for @F;
say '';

say "0123456789" x 6;
say (map {"$_         "} (' ', 1..5));
say '';

say "start string 0: ", $zero;
say "start string 1: ", $one;


say qq(\nthe 51st character in the first term long enough to have one is "), 
        (substr $F[-1], 50, 1), q(")

Results

the words generated, with a helpful guide:

1234
5678
12345678
567812345678
12345678567812345678
56781234567812345678567812345678
1234567856781234567856781234567812345678567812345678

012345678901234567890123456789012345678901234567890123456789
          1         2         3         4         5         

start string 0: 1234
start string 1: 5678

the 51st character in the first term long enough to have one is "7"

raku solution

In Raku the syntax is a little different but the action remains unchanged. The ability to embed arbitrary code blocks in a here doc makes formatting the output considerably easier, and that’s ultimately where the analysis is performed, in a collection of anonymous blocks within a template. Which is pretty cool, if you ask me.

unit sub MAIN ( $zero = 'abcdefg', $one = 'tuvwxyz' ) ;

my @F = $zero, $one;


while @F[*-1].chars < 51 {
    @F.push: @F[*-2] ~ @F[*-1];
}


say qq:to/END/;
    the words generated, with a helpful guide:

    {@F.join: "\n"}

    {("0123456789" xx 6).join}
    {(' ', |(1..5)).join: '         '}

    start string 0: $zero
    start string 1: $one

    the 51st character in the first term long enough to have one is "{@F[*-1].substr(50, 1)}"
    END

---