Fibonacci Squared Again
with Raku and Perl

by Arne Sommer

Fibonacci Squared Again with Raku and Perl

[168] Published 6. February 2022.

This is my response to the Perl Weekly Challenge #150.

Challenge #150.1: 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.

Example 1: 
    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.

File: fibonacci-words 
#! /usr/bin/env raku

subset DigitStr where * ~~ /^<[0..9]>+$/;                 # [1]
unit sub MAIN (DigitStr $a, DigitStr $b, :v(:$verbose));  # [1]

my $fw := ($a, $b, * ~ * ... *);                          # [2]

for ^Inf -> $index                                        # [3]
{
 my $current = $fw[$index];                               # [4]
      
  say ": { $index +1 }: $current" if $verbose;

  if $current.chars >= 51                                 # [5]
  {
    say $current.substr(50, 1);                           # [6]
    last;                                                 # [6a]
  }
}

[1] A custom type allowing digits only. Note that the \d regex will match any Unicode character that has a numeric digit property, so explisitly allowing the digits 0-9 is the thing.

[2] The sequence. The first two values as specified in $a and $b, and then we concatenate the two newest values to get the next one.

[3] Iterate over the numbers from 0 and up,

[4] and use that number as index in the Fibonacci sequence.

[5] Do we have enough digits?

[6] if so, print the 51st digit (at index 50, as they are zero based), and exit [6a].

Running it: 

$ ./fibonacci-words 1234 5678
7

$ ./fibonacci-words -v 1234 5678
: 1: 1234
: 2: 5678
: 3: 12345678
: 4: 567812345678
: 5: 12345678567812345678
: 6: 56781234567812345678567812345678
: 7: 1234567856781234567856781234567812345678567812345678
7

We can make the program a little shorter:

File: fibonacci-words-while 
#! /usr/bin/env raku

subset DigitStr where * ~~ /^<[0..9]>+$/;

unit sub MAIN (DigitStr $a, DigitStr $b);

for ($a, $b, * ~ * ... *) -> $current
{
  if $current.chars >= 51
  {
    say $current.substr(50, 1);
    last;
  }
}

Running it gives the expected result: 

$ ./fibonacci-words-while 1234 5678
7

A Perl Version

This is straight forward translation of the Raku version(s), with verbose mode. Perl does not have sequences, but we can use the $a and $b variables to hold the last two values while we loop away (just as we did last week for the normal Fibonacci sequence; see Fibonacci Square with Raku and Perl).

File: fibonacci-words-perl 
#! /usr/bin/env perl

use strict;
use warnings;
use feature 'say';

use Getopt::Long;

my $verbose =  0;

GetOptions("verbose" => \$verbose);

my $a = $ARGV[0] || 1234;
my $b = $ARGV[1] || 5678;
my $i = 4;

die 'Please specify digits only for $a' unless $a =~ /^\d+$/;
die 'Please specify digits only for $b' unless $b =~ /^\d+$/;

say ": 1: $a" if $verbose;
say ": 2: $b" if $verbose;

($a, $b) = ($b, $a . $b);

say ": 3: $b" if $verbose;

while (length($b) < 51)
{
  ($a, $b) = ($b, $a . $b);  
  say ": " . $i++ . ": $b" if $verbose;
}

say substr($b, 50, 1);

Running it gives the same result as the Raku version: 

$ ./fibonacci-words-perl 1234 5678
7

$ ./fibonacci-words-perl -v 1234 5678
: 1: 1234
: 2: 5678
: 3: 12345678
: 4: 567812345678
: 5: 12345678567812345678
: 6: 56781234567812345678567812345678
: 7: 1234567856781234567856781234567812345678567812345678
7

Challenge #150.2: Square-free Integer

Write a script to generate all square-free integers <= 500.

In mathematics, a square-free integer (or squarefree integer) is an integer which is divisible by no perfect square other than 1. That is, its prime factorization has exactly one factor for each prime that appears in it. For example, 10 = 2 ⋅ 5 is square-free, but 18 = 2 ⋅ 3 ⋅ 3 is not, because 18 is divisible by 9 = 3**2.

Example: 
The smallest positive square-free integers are
1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 26, 29, 30, ...

Let us start with the hard part, the Prime Factors. This is a case of code reuse, as we did just that in Challenge #123.1 Ugly Numbers; see Ugly Points with Raku and Perl, which is also a case of code reuse of the «factors» procedure from the program with the same name in my Centenary Sequences with Raku Part 5 - Divisors and Factors article. (Scroll down to sequence #065).

The rest of the program is quite easy to set up:

File: square-free-integers 
#! /usr/bin/env raku

unit sub MAIN (Int $limit where $limit > 0 = 500;                        # [1]

say (1 .. $limit).grep( { factors($_).repeated.elems == 0 }).join(", "); # [2]

sub factors ($number is copy)
{
  return (1)       if $number == 1;
  return ($number) if $number.is-prime;

  my @factors;

  for (2 .. $number div 2).grep( *.is-prime) -> $candidate
  {
    while $number %% $candidate
    {
      @factors.push: $candidate;
      $number /= $candidate;
    }
  }

  return @factors;
}

[1] Specify another limit if 500 does not suit you.

[2] Hold on to the elemenst that have repeated factors (with grep) and print them. The repeated method removes the first instance of the values, giving us a list of repetitions (after the first one). Slapping on .elems == 0 takes care of the rest.

See docs.raku.org/routine/repeated for more information about repeated.

Running it: 

$ ./square-free-integers
1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 26, 29, 30, 31, 33,\
34, 35, 37, 38, 39, 41, 42, 43, 46, 47, 51, 53, 55, 57, 58, 59, 61, 62, 65,\
66, 67, 69, 70, 71, 73, 74, 77, 78, 79, 82, 83, 85, 86, 87, 89, 91, 93, 94,\
95, 97, 101, 102, 103, 105, 106, 107, 109, 110, 111, 113, 114, 115, 118, 119,\
122, 123, 127, 129, 130, 131, 133, 134, 137, 138, 139, 141, 142, 143, 145,\
146, 149, 151, 154, 155, 157, 158, 159, 161, 163, 165, 166, 167, 170, 173,\
174, 177, 178, 179, 181, 182, 183, 185, 186, 187, 190, 191, 193, 194, 195,\
197, 199, 201, 202, 203, 205, 206, 209, 210, 211, 213, 214, 215, 217, 218,\
219, 221, 222, 223, 226, 227, 229, 230, 231, 233, 235, 237, 238, 239, 241,\
246, 247, 249, 251, 253, 254, 255, 257, 258, 259, 262, 263, 265, 266, 267,\
269, 271, 273, 274, 277, 278, 281, 282, 283, 285, 286, 287, 290, 291, 293,\
295, 298, 299, 301, 302, 303, 305, 307, 309, 310, 311, 313, 314, 317, 318,\
319, 321, 322, 323, 326, 327, 329, 330, 331, 334, 335, 337, 339, 341, 345,\
346, 347, 349, 353, 354, 355, 357, 358, 359, 362, 365, 366, 367, 370, 371,\
373, 374, 377, 379, 381, 382, 383, 385, 386, 389, 390, 391, 393, 394, 395,\
397, 398, 399, 401, 402, 403, 406, 407, 409, 410, 411, 413, 415, 417, 418,\
419, 421, 422, 426, 427, 429, 430, 431, 433, 434, 435, 437, 438, 439, 442,\
443, 445, 446, 447, 449, 451, 453, 454, 455, 457, 458, 461, 462, 463, 465,\
466, 467, 469, 470, 471, 473, 474, 478, 479, 481, 482, 483, 485, 487, 489,\
491, 493, 494, 497, 498, 499

Looking good.

Perl

This is a straight forward translation of the Raku version. Perl does not have a «repeated» function, but «List::MoreUtils::duplicates» works fine.

File: square-free-integers-perl 
#! /usr/bin/env perl

use strict;
use warnings;
use feature 'say';
use feature 'signatures';
no warnings 'experimental::signatures';

use Math::Prime::Util 'is_prime';
use List::MoreUtils 'duplicates';

my $limit = $ARGV[0] || 500;

die "Please specify a positive integer" unless $limit =~ /^[1-9]\d*$/;

my @result = grep { ! duplicates factors($_) } (1 .. $limit);

say join(", ", @result);

sub factors ($number)
{
  return (1)       if $number == 1;
  return ($number) if is_prime($number);

  my @factors;

  for my $candidate (grep { is_prime($_) } 2 .. $number / 2)
  {
    while ($number % $candidate == 0)
    {
      push(@factors, $candidate);
      $number /= $candidate;
    }
  }
    
  return @factors;
}

Running it gives the same result as the Raku version: 

$ ./square-free-integers-perl
1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 26, 29, 30, 31, 33,\
34, 35, 37, 38, 39, 41, 42, 43, 46, 47, 51, 53, 55, 57, 58, 59, 61, 62, 65,\
66, 67, 69, 70, 71, 73, 74, 77, 78, 79, 82, 83, 85, 86, 87, 89, 91, 93, 94,\
95, 97, 101, 102, 103, 105, 106, 107, 109, 110, 111, 113, 114, 115, 118, 119,\
122, 123, 127, 129, 130, 131, 133, 134, 137, 138, 139, 141, 142, 143, 145,\
146, 149, 151, 154, 155, 157, 158, 159, 161, 163, 165, 166, 167, 170, 173,\
174, 177, 178, 179, 181, 182, 183, 185, 186, 187, 190, 191, 193, 194, 195,\
197, 199, 201, 202, 203, 205, 206, 209, 210, 211, 213, 214, 215, 217, 218,\
219, 221, 222, 223, 226, 227, 229, 230, 231, 233, 235, 237, 238, 239, 241,\
246, 247, 249, 251, 253, 254, 255, 257, 258, 259, 262, 263, 265, 266, 267,\
269, 271, 273, 274, 277, 278, 281, 282, 283, 285, 286, 287, 290, 291, 293,\
295, 298, 299, 301, 302, 303, 305, 307, 309, 310, 311, 313, 314, 317, 318,\
319, 321, 322, 323, 326, 327, 329, 330, 331, 334, 335, 337, 339, 341, 345,\
346, 347, 349, 353, 354, 355, 357, 358, 359, 362, 365, 366, 367, 370, 371,\
373, 374, 377, 379, 381, 382, 383, 385, 386, 389, 390, 391, 393, 394, 395,\
397, 398, 399, 401, 402, 403, 406, 407, 409, 410, 411, 413, 415, 417, 418,\
419, 421, 422, 426, 427, 429, 430, 431, 433, 434, 435, 437, 438, 439, 442,\
443, 445, 446, 447, 449, 451, 453, 454, 455, 457, 458, 461, 462, 463, 465,\
466, 467, 469, 470, 471, 473, 474, 478, 479, 481, 482, 483, 485, 487, 489,\
491, 493, 494, 497, 498, 499

And that's it.

Links
 About me
 Keyword Index
Raku Courses
 Beginning Raku (book)
 RSS Feed
 Code (zip)
Reddit Comments