Attractive Leonardo Numbers with Raku

by Arne Sommer

Attractive Leonardo Numbers with Raku

[50] 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.

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