Weekly Challenge

Challenge, My solutions

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

$ ./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.

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

$ ./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