Dates, and more recursively defined numbers

Last Sundays 

For task 1 we are asked to write a script to list the last Sunday of every month of a given year.

The first decision is which modules we're allowed to use, but in the interests of revealing the logic I only used timelocal_posix, which is the inverse of the built-in localtime (apart from a few irrelevant provisos).

It's a slightly awkward calculation. There can be 4 or 5 Sundays in a month, and that depends on the day of the week the month starts on and how many days there are in the month. So I hit on the idea of looking at the 12 months starting with the February of the given year.  If we take the 1st of each of these 12 months, we can construct the Unix time of noon like this:

$time = timelocal_posix(0, 0, 12, 1, $month, $year - 1900);

and then use timelocal to get the day of the week as $t[6] in:

@t = localtime($time);

Then, to get the last Sunday of the preceding month, if the 1st of the month is a Sunday ($t[6] == 0) we need to move back 7 days, or otherwise we just move back $t[6] days. To do that we subtract 86400 seconds for each day we're moving back, and then a final localtime gives us the desired date.

The vanilla version of timelocal works for nearby dates, but the Posix version can cover (at least) 1753 - 3999 in the Gregorian calendar.

Perfect totients

Task 2 requires to write a script to generate the first 20 Perfect Totient Numbers. To do this for a given number n, we first count the mutually prime lesser integers (including 1) with which it is mutually prime - or equivalently, those with which it has a greatest common divisor of 1.

Having got this count, we repeat the process on it - that is, count its lesser mutual primes, and so until we get to 1. Clearly it will always converge to 1, because the count of positive integers less than n will always be less than n.

So how to do this? First I wrote (borrowed, actually) a gcd function, and then wrote a totients_count function.  That's enough for the first few perfect totients, but as they get bigger it takes longer, so I had totients_count cache its results in an array, and checked for an answer there before calling totients_count again.

On my quite slow machine it took about 1.5 minutes to get the required 20 numbers.

Comments

Popular posts from this blog

Illuminating the Ulam

How to find palindromes quickly

Numbers in words and Cardano triplets