laurent_r

These are some answers to the Week 149 of the Perl Weekly Challenge organized by Mohammad S. Anwar.

Spoiler Alert: This weekly challenge deadline is due in a few days from now (on February 6, 2022 at 24:00). This blog post offers some solutions to this challenge, please don’t read on if you intend to complete the challenge on your own.

Task 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:

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.

So, Fibonacci words are similar to Fibonacci numbers, except that any value is generated by concatenating (instead of adding) the two previous values.

Since we can easily find how many digits we add each time through the iteration, there is certainly a way to find directly the requested digit without even computing the sequence’s words, but it is much simpler to iteratively compute the words and pick up the 51st digit once we have enough digits for that.

Fibonacci Words in Raku

Here, we use the sequence operator to generate a sequence of Fibonacci words. We stop the sequence with the *.chars >= 51 expression. We then just take the digit at index 50 (corresponding to position 51) of the last word.

use v6;

sub fibonacci (Int $a, Int $b where $a.chars == $b.chars) {
    my ($c, $d) = $a < $b ?? ($a, $b) !! ($b, $a);
    my @fib = $c, $d, * ~ * ... *.chars >= 51;
    # say @fib;
}
say (fibonacci 1234, 5678)[*-1].comb[50];

This script displays the following output:

$ raku ./Fibonacci_words.raku
7

Fibonacci Words in Perl

Same idea as above, except that we build the sequence of Fibonacci words with a for loop.

use strict;
use warnings;
use feature "say";

sub fibonacci {
    my ($a, $b) = @_;
    my @fib = $a < $b ? ($a, $b) : ($b, $a);
    for my $i (1..20) {
        push @fib, $fib[-2] . $fib[-1];
        next if length $fib[-1] < 51;
        say $fib[-1];
        return $fib[-1];
    }
}
say substr fibonacci(1234, 5678), 50, 1;

This script displays the following output:

$ perl ./Fibonacci_words.pl
1234567856781234567856781234567812345678567812345678
7

Task 2: Square-Free Integers

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 x 5 is square-free, but 18 = 2 x 3 x 3 is not, because 18 is divisible by 9 = 32.

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, ...

The first idea that might come to mind would be to perform prime factorization of all integers between 2 and 500, and to retain all those whose all exponents are 1. But that’s a lot of computing work, much of which is in fact useless. It is much better to try to divide the input integers by perfect squares. Why would you want to test twice division by 2 when it is enough to test once division by 4? Only six squares of prime numbers may occur in prime factorization of integers below 500: 4, 9, 25, 49, 121, 169. There are some other squares (such as 16, 36, 64, 81, 100, 144, 196, and 225), but these are not squares of prime numbers and numbers containing these squares will all have been found to contain squares when we test 4, 9, and 25.

Square-Free Integers in Raku

We first need to build a list of squares of prime numbers less than the square root of 500/2. For each integer between 1 and 500, we test whether any of the squares evenly divides that integer. A small easy optimization is that we can stop the process whenever we reach a square larger than the integer being tested.

my @squares = map { $_² }, grep {.is-prime}, 2..250.sqrt.Int;
# say @squares; # [4 9 25 49 121 169] squares of prime integers
NEXT_I: for 1..500 -> $i {
    for @squares -> $j {
        next NEXT_I if $i %% $j;
        last if $j > $i;
    }
    print "$i ";
}
say "\nDuration: ", now - INIT now;

This script displays the following output:

$ raku ./square-free.raku
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 289 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 361 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

Duration: 0.12648938

We compute and display the duration just to check that the program runs fast enough.

Square-Free Integers in Perl

This is the same idea as explained above. A slight change is that this program doesn’t test for primality of the numbers that will be squared, because anyone with only basic math knowledge can list prime numbers between 1 and 15. So we don’t need to compute them, we simply hard-code them.

use strict;
use warnings;
use feature "say";

my @squares = map { $_ * $_ } 2, 3, 5, 7, 11, 13;
# say "@squares"; # 4 9 25 49 121 169 - squares of prime integers
NEXT_I: for my $i (1..500) {
    for my $j (@squares) {
        next NEXT_I if $i % $j == 0;
        last if $j > $i;
    }
    print "$i ";
}
say " ";

This script displays the following output:

$ perl ./square-free.pl
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 289 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 361 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

Wrapping up

The next week Perl Weekly Challenge will start soon. If you want to participate in this challenge, please check https://perlweeklychallenge.org/ and make sure you answer the challenge before 23:59 BST (British summer time) on February 13, 2022. And, please, also spread the word about the Perl Weekly Challenge if you can.