Peter
Peter Campbell Smith

Fibonacci words
and round numbers

Weekly challenge 150 — 31 January 2022

Week 150: 31 Jan 2022

Task 1

Task — Fibonacci words

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.

Examples

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.

Analysis

This is a good example of a task where efficiency isn't an issue. You can probably generate a Fibonacci series up to the point where you run out of memory in milliseconds, and for the example above we only need 4 more terms to reach the 51 character length requested.

Even giving my vanilla algorithm with two starting strings which are 1 character long, and asking for the first term with 1000 characters you only need 14 terms beyond the two given ones.

And I could do the task as stated on paper in under 20 seconds!

Try it 

Try running the script with any input:



example: 1234, 56



example: 51

Script


#!/usr/bin/perl

# Peter Campbell Smith - 2022-01-31
# PWC 150 task 1

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

my ($a, $b, $index, $j, $test, @fib, @tests, $big, $length);

# sets of inputs to test ($a, $b, character index of interest)
@tests = (['1234', '5678', 51], ['12345678', '98765432', 159], ['1234567890', '1234567890', 1000]);

# loop over tests
for $test (@tests) {
    
    # get parameters
    ($fib[0], $fib[1], $index) = @$test;
    
    # create successive ternms of series until one is long enough
    $j = 1;
    while (1) {
        $j ++;
        $fib[$j] = $fib[$j - 2] . $fib[$j - 1];
        last if length($fib[$j]) >= $index;
    }
    
    # format the answer
    say qq[\nInput:  $fib[0], $fib[1]];
    $length = length($fib[$j]);
    $big = '';
    $big .= qq[$1\n] while $fib[$j] =~ m|(.{50})|g;
    $big .= substr($fib[$j], int($length / 50) * 50);
    say qq[Character $index is ] . substr($fib[$j], $index - 1, 1) . 
        qq[, term $j is $length characters long:\n$big];
}

Output


Input:  1234, 5678
Character 51 is 7, term 6 is 52 characters long:
12345678567812345678567812345678123456785678123456
78

Input:  12345678, 98765432
Character 159 is 7, term 7 is 168 characters long:
98765432123456789876543212345678987654329876543212
34567898765432123456789876543298765432123456789876
54329876543212345678987654321234567898765432987654
321234567898765432

Input:  1234567890, 1234567890
Character 1000 is 0, term 11 is 1440 characters long:
12345678901234567890123456789012345678901234567890
12345678901234567890123456789012345678901234567890
12345678901234567890123456789012345678901234567890
12345678901234567890123456789012345678901234567890
12345678901234567890123456789012345678901234567890
12345678901234567890123456789012345678901234567890
12345678901234567890123456789012345678901234567890
12345678901234567890123456789012345678901234567890
12345678901234567890123456789012345678901234567890
12345678901234567890123456789012345678901234567890
12345678901234567890123456789012345678901234567890
12345678901234567890123456789012345678901234567890
12345678901234567890123456789012345678901234567890
12345678901234567890123456789012345678901234567890
12345678901234567890123456789012345678901234567890
12345678901234567890123456789012345678901234567890
12345678901234567890123456789012345678901234567890
12345678901234567890123456789012345678901234567890
12345678901234567890123456789012345678901234567890
12345678901234567890123456789012345678901234567890
12345678901234567890123456789012345678901234567890
12345678901234567890123456789012345678901234567890
12345678901234567890123456789012345678901234567890
12345678901234567890123456789012345678901234567890
12345678901234567890123456789012345678901234567890
12345678901234567890123456789012345678901234567890
12345678901234567890123456789012345678901234567890
12345678901234567890123456789012345678901234567890
1234567890123456789012345678901234567890

 

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