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

## Post a Comment