Totient numbers on a Sunday
Tags: perl, python, theweeklychallenge
Published: 2022-07-31 12:38:02

# Weekly Challenge

[Challenge](https://theweeklychallenge.org/blog/perl-weekly-challenge-175/), [My solutions](https://github.com/manwar/perlweeklychallenge-club/tree/master/challenge-175/sgreen)

## Task 1: Last Sunday

### Task

Write a script to list Last Sunday of every month in the given year.

### My solution

Date math is hard, although not as hard as date and time calculations. As a quick [refresher](https://en.wikipedia.org/wiki/Gregorian_calendar), the days, months and year as we know it was introduced in October 1582 by Pope Gregory XIII as a modification of, and replacement for, the Julian calendar. Both solutions I've provided have assumed the Georgian Calendar since the beginning of time, and thus will give wrong results for old dates.

In my solution, I use the [date module](https://docs.python.org/3/library/datetime.html#datetime.date) from datetime. For the specified year, I calculate the last day of each month (first day of the  month + 1 month - 1 day). I also obtain the day of the week (where Monday is 1 and Sunday is 7). Finally, I substrate the day of the week from the last day to produce the last Sunday. I use `% 7` so we don't subtract seven days if the last day is a Sunday.

For my Perl solution, I use the [Date::Calc module](https://metacpan.org/pod/Date::Calc). As this has a `Days_in_Month` function. We can calculate the last day of the month a little easier. Unlike the Python solution, the functions don't result in an object. This has pros and cons.

### Examples

```bash
$ ./ch-1.py 
2022-01-30
2022-02-27
2022-03-27
2022-04-24
2022-05-29
2022-06-26
2022-07-31
2022-08-28
2022-09-25
2022-10-30
2022-11-27
2022-12-25
```

## Task 2: Perfect Totient Numbers

### Task

Write a script to generate first 20 [Perfect Totient Numbers](https://en.wikipedia.org/wiki/Perfect_totient_number).

### My solution

I may have over engineered this solution. My first attempt took nearly four minutes to run. My final solution took 4½ seconds in Python and 13 seconds in Perl.

This means that I need to go into some detail about my solution. Lets start at the beginning. I define three global variables: `primes` (list), `factors` (dict of sets) and `totient` (dict of integers). These are mainly used for caching results of numbers we already have calculated.

I then have three functions to populate each variable. All of them take a number as an input. The `is_prime` number will add to the `primes` list if the number is a prime. This is done by checking if the number is divisible by any already found primes with no remainder. The `get_factors` function returns a set of prime numbers that make up the number. For example for the number 18, it would return a set of `{2, 3}` (being 2 × 3 × 3).

The `get_totients` function will return the number of integers between 1 and the number that have a relative prime of 1 (in other words, the greatest common divisor of that number is 1). As the `get_factors` function returns sets, we can use the intersection method to see if there is a common prime.

Next, we have the `is_ptn` function. This calculates the number of relative primes (using the `get_totients` function) of the number, and does this recursively in a while loop until we reach 1. Finally we compare the total with the original number and return True if they match, or False otherwise.

Finally, we have the `main` function which is the usual wrapper for this type of challenge. We have a `solutions` list, and an incrementing while loop that continues until we have 15 numbers.

The Perl code is roughly equivalent. It will use the [state](https://perldoc.perl.org/functions/state) function rather than global variables where appropriate, and the none function when comparing two arrays. I suspect this is the main difference in performance between the two sets of code.

### Examples

```bash
$ ./ch-2.py 
3, 9, 15, 27, 39, 81, 111, 183, 243, 255, 327, 363, 471, 729, 2187, 2199, 3063, 4359, 4375, 5571

$ ./ch-2.pl 
3, 9, 15, 27, 39, 81, 111, 183, 243, 255, 327, 363, 471, 729, 2187, 2199, 3063, 4359, 4375, 5571
```