Attractive Leonardo Numbers with Raku

by Arne Sommer

Attractive Leonardo Numbers with Raku

Published 31. December 2019. Updated 3. January 2020

 

Welcome to this 50th article in my Perl6/Raku blog!

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


Challenge #41.1: Attractive Numbers

Write a script to display attractive number between 1 and 50.

A number is an attractive number if the number of its prime factors is also prime number.

The number 20 is an attractive number, whose prime factors are 2, 2 and 5. The total prime factors is 3 which is also a prime number.

Several of the weekly challenges has touched prime numbers, and we sort of computed the divisors in challenge #8.1. This version does things in a slightly different way, just for fun.

Let us start with the divisors:

File: divisors
unit sub MAIN (Int $limit = 50);                          # [1]

for 1 .. $limit -> $current                               # [2]
{
  say "$current: with divisors: { divisors($current) }";  # [2]
}

sub divisors (Int $number is copy)                        # [3]
{
  return (1) if $number == 1;                             # [4]
  return ($number) if $number.is-prime;                   # [5]

  my @divisors;                                           # [6]

  for 2 .. ($number -1) -> $candidate                     # [7]
  {
    next unless $candidate.is-prime;                      # [8]
  
    while ($number %% $candidate)                         # [9]
    {
      @divisors.push: $candidate;                         # [9a]
      $number div= $candidate;                            # [9b]
    }
    if $number.is-prime                                   # [10]
    {
      @divisors.push: $number;                            # [10a]
      last;                                               # [10b]
    }
  }
  return @divisors;                                       # [11]
}

[1] We can override the default limit (0f 50) if we want to.

[2] For each integer from 1 to the upper limit, print the number and its divisors.

[3] This one returns a list of the divisors for the given number. Note «is copy», as we change the value (in [9b]).

[4] Return «(1)» if the number is 1.

[5] Return the number, if it is a prime number. (Note that «1» is not a prime number, so the previous line is required.)

Note that (1) is not a list with one element, but a single value. The parens are the grouping operator, nothing more. The comma is the list (creating) operator (so (1,) is a list with one element). The non-list return value doesn't matter here, as the receiving code stringifies the result. (Note that assigning a scalar to an array also works, e.g. my @array = 1 gives an array with one element.) [Added 3. Jan 2020]

[6] We collect the divisors here.

[7] We loop through the integers from 2 up to the number itself (not including it).

[8] Skip non-prime numbers.

[9] As long as the number is divisible by the candidate (i.e. that it is a divisor of the number), add the candidate to the list of divisors [9a] and remove the divisor from the number. Note the loop as the divisors can come several times, e.g. «27» has three divisors: «3», «3» and «3».

[10] If the number (after we have removed some divisors) is a prime number, add it ot the list of divisors [10a] and exit the loop [10b].

[11] Return the divisors.

Note that the upper limit in [7] could just as well have been written as «Inf», as «last» (in [10b]) does the actual loop termination before we come to the number itself. We can actually replace lines [7] and [8] with «for (^Inf).grep(*.is-prime) -> $candidate».

Running it:

$ raku divisors
1: with divisors: 1
2: with divisors: 2
3: with divisors: 3
4: with divisors: 2 2
5: with divisors: 5
6: with divisors: 2 3
7: with divisors: 7
8: with divisors: 2 2 2
9: with divisors: 3 3
10: with divisors: 2 5
11: with divisors: 11
12: with divisors: 2 2 3
13: with divisors: 13
14: with divisors: 2 7
15: with divisors: 3 5
16: with divisors: 2 2 2 2
17: with divisors: 17
18: with divisors: 2 3 3
19: with divisors: 19
20: with divisors: 2 2 5
21: with divisors: 3 7
22: with divisors: 2 11
23: with divisors: 23
24: with divisors: 2 2 2 3
25: with divisors: 5 5
26: with divisors: 2 13
27: with divisors: 3 3 3
28: with divisors: 2 2 7
29: with divisors: 29
30: with divisors: 2 3 5
31: with divisors: 31
32: with divisors: 2 2 2 2 2
33: with divisors: 3 11
34: with divisors: 2 17
35: with divisors: 5 7
36: with divisors: 2 2 3 3
37: with divisors: 37
38: with divisors: 2 19
39: with divisors: 3 13
40: with divisors: 2 2 2 5
41: with divisors: 41
42: with divisors: 2 3 7
43: with divisors: 43
44: with divisors: 2 2 11
45: with divisors: 3 3 5
46: with divisors: 2 23
47: with divisors: 47
48: with divisors: 2 2 2 2 3
49: with divisors: 7 7
50: with divisors: 2 5 5

That looks correct.

On to the challenge, then:

File: attractive-numbers
unit sub MAIN (Int $limit = 50, :$verbose);        # [1]

for 1 .. $limit -> $current                        # [2]
{
  my @divisors = divisors($current);               # [2]
  my $elems    = @divisors.elems;                  # [2]

  say ": $current: Divisors: { divisors($current) } Elements: $elems"
    if $verbose;                                   # [3]

  say "$current is an attractive number (with divisors: @divisors[])"
    if $elems.is-prime;                            # [4]
}

sub divisors (Int $number is copy)                 # [5]
{
  ...
}

[1] I have added verbose mode, to make it easier to see what is going on (and debug).

[2] The same as in the «divisors» program.

[3] Verbose output everything; the number, the divisors, and the divisor count.

[4] We have an attractive number if the divisor count is a prime number.

[5] The same as in the «divisors» program.

Running it:

$ raku attractive-numbers
4 is an attractive number (with divisors: 2 2)
6 is an attractive number (with divisors: 2 3)
8 is an attractive number (with divisors: 2 2 2)
9 is an attractive number (with divisors: 3 3)
10 is an attractive number (with divisors: 2 5)
12 is an attractive number (with divisors: 2 2 3)
14 is an attractive number (with divisors: 2 7)
15 is an attractive number (with divisors: 3 5)
18 is an attractive number (with divisors: 2 3 3)
20 is an attractive number (with divisors: 2 2 5)
21 is an attractive number (with divisors: 3 7)
22 is an attractive number (with divisors: 2 11)
25 is an attractive number (with divisors: 5 5)
26 is an attractive number (with divisors: 2 13)
27 is an attractive number (with divisors: 3 3 3)
28 is an attractive number (with divisors: 2 2 7)
30 is an attractive number (with divisors: 2 3 5)
32 is an attractive number (with divisors: 2 2 2 2 2)
33 is an attractive number (with divisors: 3 11)
34 is an attractive number (with divisors: 2 17)
35 is an attractive number (with divisors: 5 7)
38 is an attractive number (with divisors: 2 19)
39 is an attractive number (with divisors: 3 13)
42 is an attractive number (with divisors: 2 3 7)
44 is an attractive number (with divisors: 2 2 11)
45 is an attractive number (with divisors: 3 3 5)
46 is an attractive number (with divisors: 2 23)
48 is an attractive number (with divisors: 2 2 2 2 3)
49 is an attractive number (with divisors: 7 7)
50 is an attractive number (with divisors: 2 5 5)

With verbose mode:

$ raku attractive-numbers --verbose
: 1: Divisors: 1 Elements: 1
: 2: Divisors: 2 Elements: 1
: 3: Divisors: 3 Elements: 1
: 4: Divisors: 2 2 Elements: 2
4 is an attractive number (with divisors: 2 2)
: 5: Divisors: 5 Elements: 1
: 6: Divisors: 2 3 Elements: 2
6 is an attractive number (with divisors: 2 3)
: 7: Divisors: 7 Elements: 1
: 8: Divisors: 2 2 2 Elements: 3
8 is an attractive number (with divisors: 2 2 2)
: 9: Divisors: 3 3 Elements: 2
9 is an attractive number (with divisors: 3 3)
: 10: Divisors: 2 5 Elements: 2
10 is an attractive number (with divisors: 2 5)
: 11: Divisors: 11 Elements: 1
: 12: Divisors: 2 2 3 Elements: 3
12 is an attractive number (with divisors: 2 2 3)
: 13: Divisors: 13 Elements: 1
: 14: Divisors: 2 7 Elements: 2
14 is an attractive number (with divisors: 2 7)
: 15: Divisors: 3 5 Elements: 2
15 is an attractive number (with divisors: 3 5)
: 16: Divisors: 2 2 2 2 Elements: 4
: 17: Divisors: 17 Elements: 1
: 18: Divisors: 2 3 3 Elements: 3
18 is an attractive number (with divisors: 2 3 3)
: 19: Divisors: 19 Elements: 1
: 20: Divisors: 2 2 5 Elements: 3
20 is an attractive number (with divisors: 2 2 5)
: 21: Divisors: 3 7 Elements: 2
21 is an attractive number (with divisors: 3 7)
: 22: Divisors: 2 11 Elements: 2
22 is an attractive number (with divisors: 2 11)
: 23: Divisors: 23 Elements: 1
: 24: Divisors: 2 2 2 3 Elements: 4
: 25: Divisors: 5 5 Elements: 2
25 is an attractive number (with divisors: 5 5)
: 26: Divisors: 2 13 Elements: 2
26 is an attractive number (with divisors: 2 13)
: 27: Divisors: 3 3 3 Elements: 3
27 is an attractive number (with divisors: 3 3 3)
: 28: Divisors: 2 2 7 Elements: 3
28 is an attractive number (with divisors: 2 2 7)
: 29: Divisors: 29 Elements: 1
: 30: Divisors: 2 3 5 Elements: 3
30 is an attractive number (with divisors: 2 3 5)
: 31: Divisors: 31 Elements: 1
: 32: Divisors: 2 2 2 2 2 Elements: 5
32 is an attractive number (with divisors: 2 2 2 2 2)
: 33: Divisors: 3 11 Elements: 2
33 is an attractive number (with divisors: 3 11)
: 34: Divisors: 2 17 Elements: 2
34 is an attractive number (with divisors: 2 17)
: 35: Divisors: 5 7 Elements: 2
35 is an attractive number (with divisors: 5 7)
: 36: Divisors: 2 2 3 3 Elements: 4
: 37: Divisors: 37 Elements: 1
: 38: Divisors: 2 19 Elements: 2
38 is an attractive number (with divisors: 2 19)
: 39: Divisors: 3 13 Elements: 2
39 is an attractive number (with divisors: 3 13)
: 40: Divisors: 2 2 2 5 Elements: 4
: 41: Divisors: 41 Elements: 1
: 42: Divisors: 2 3 7 Elements: 3
42 is an attractive number (with divisors: 2 3 7)
: 43: Divisors: 43 Elements: 1
: 44: Divisors: 2 2 11 Elements: 3
44 is an attractive number (with divisors: 2 2 11)
: 45: Divisors: 3 3 5 Elements: 3
45 is an attractive number (with divisors: 3 3 5)
: 46: Divisors: 2 23 Elements: 2
46 is an attractive number (with divisors: 2 23)
: 47: Divisors: 47 Elements: 1
: 48: Divisors: 2 2 2 2 3 Elements: 5
48 is an attractive number (with divisors: 2 2 2 2 3)
: 49: Divisors: 7 7 Elements: 2
49 is an attractive number (with divisors: 7 7)
: 50: Divisors: 2 5 5 Elements: 3
50 is an attractive number (with divisors: 2 5 5)

That looks correct as well.

A fun fact about attractive numbers: whilst prime factors are a major (or «prime») ingredient, the numbers themselves are not prime.

Challenge #41.2: Leonardo Numbers

Write a script to display first 20 Leonardo Numbers. Please checkout wiki page for more information.

For example:

L(0) = 1
L(1) = 1
L(2) = L(0) + L(1) + 1 = 3
L(3) = L(1) + L(2) + 1 = 5
and so on.

This looks familiar to the Fibonacci Sequence (which hasn't been used in any of the challenges so far), and we can use a Sequence here as well:

> my $leonardo := (1, 1, { $^a + $^b +1 } ... Inf);
################## A  B  #  C   ######### #  D  ##

The first number is 1 (#A), the second is (also) 1 (#B). Then the third, fourth and so on up to infinity (#D) number is the sum of the two previous numbers + 1 (#C).

Obtaining the first 20 numbers is as easy as:

> say $leonardo[^20];
(1 1 3 5 9 15 25 41 67 109 177 287 465 753 1219 1973 3193 5167 8361 13529)

As a one-liner (REPL, and on the command line):

> say (1, 1, { $^a + $^b +1 } ... Inf)[^20]
(1 1 3 5 9 15 25 41 67 109 177 287 465 753 1219 1973 3193 5167 8361 13529)
$ raku -e "say (1, 1, { $^a + $^b +1 } ... Inf)[^20]"
(1 1 3 5 9 15 25 41 67 109 177 287 465 753 1219 1973 3193 5167 8361 13529)

If you want a program, here it is:

File: leonardo
my $leonardo := (1, 1, { $^a + $^b +1 } ... Inf);

unit sub MAIN ($limit = 20);

say "$_: $leonardo[$_]" for ^$limit;

Running it:

$ raku leonardo
0: 1
1: 1
2: 3
3: 5
4: 9
5: 15
6: 25
7: 41
8: 67
9: 109
10: 177
11: 287
12: 465
13: 753
14: 1219
15: 1973
16: 3193
17: 5167
18: 8361
19: 13529

And with a user specified upper limit:

$ raku leonardo 50
0: 1
1: 1
2: 3
3: 5
4: 9
5: 15
6: 25
7: 41
8: 67
9: 109
10: 177
11: 287
12: 465
13: 753
14: 1219
15: 1973
16: 3193
17: 5167
18: 8361
19: 13529
20: 21891
21: 35421
22: 57313
23: 92735
24: 150049
25: 242785
26: 392835
27: 635621
28: 1028457
29: 1664079
30: 2692537
31: 4356617
32: 7049155
33: 11405773
34: 18454929
35: 29860703
36: 48315633
37: 78176337
38: 126491971
39: 204668309
40: 331160281
41: 535828591
42: 866988873
43: 1402817465
44: 2269806339
45: 3672623805
46: 5942430145
47: 9615053951
48: 15557484097
49: 25172538049

You can read more about the Fibonacci Numbers in my Beginning Raku book. (Look it up in the Index.) As procedures as well as sequences.

And that's it.