QIBs and days - fun tasks for a sunny day

QIBs

Today's first 'fun task' (as Gabor puts it) is: Write a script to convert a given number (base 10) to quater-imaginary base number and vice-versa.

Quater-imaginary base numbers - henceforth qibs - are numbers written in the base 2i. So 123, for example means 1 x (2i)^2 + 2 x 2i + 3 = - 4 +4i + 3 = -1 + 4i.

I thought at first that I could just translate the Wikipedia explanation into Perl, but that turned out quite tricky.  I also though about using Math::Complex, but decided - probably wrongly - that it wasn't worth the effort of relearning its rather unfamiliar syntax.

So I wrote my own functions to_qib and from_qib. It wasn't that hard though perhaps not as much fun as I might have hoped. I confined myself to complex numbers with integer coefficients, which means the qibs either end in .0 or .2.

The length of qibs increases quite rapidly and my rather clunky way of adding them means that my code won't handle them over 18 digits before the point - but a little tweaking could probably cure that.

Working days

The task is described as: 'Write a script to find the time that occurs $duration business hours after $timestamp. For the sake of this task, let us assume the working hours are 9am to 6pm, Monday to Friday. Please ignore timezone too.'

This is a task which I have often had to address as a project manager: Fred has a workpackage estimated to take 200 hours. If he starts now, when should he finish?  Of course in real life there are complications - bank holidays, annual leave, sick leave, distractions, overtime and so on. However, again in real life, precision is not required, not least because the 200 hour estimate is probably far from exactly correct.

But today's task demands, I think, precision. After a few false starts my submitted algorithm looks like this.

We start with $timestamp and $duration. Let's assume that $timestamp falls within the working week (so not 2am on a Saturday, for example).  A little thought suggests that it would be much easier if $timestamp were 9am on a Monday. So here goes:

Move $timestamp back to 9am on the preceding Monday, and increase $duration by the number of working hours we've moved it back. That will be 9 hours for every full day plus the time span between 9am and $timestamp.  So for example, if $timestamp is 11:00 on Wednesday, we are increasing duration by 18 hours for Monday and Tuesday plus 2 hours on Wednesday.

We could then:
- divide $duration by 45 (working hours per week) to get a number of full weeks
- divide the remainder by 9 to get the number of extra days (9 hrs per day)
- and the remainder is the time period after 9am on the date that results

All that date arithmetic can easily be done using the epoch date (the seconds from 01.01.1970 used by Unix), remembering that a day is 24 * 60 * 60 seconds.

But it doesn't quite work.

It doesn't quite work because of daylight saving time. If the $duration takes us over the date when the clocks go back or forward, we'll be out by an hour. Can we rely on 'Please ignore timezone too' to ignore that?

Being of a cautious frame of mind, I adapted my algorithm slightly. Instead of just working with the epoch date, I treated the date and the time-of-day separately. I have a function date10add which takes a date (eg 2022-12-25) and adds an integer number of calendar days, and I used that to move forward by the full weeks and extra days from my algorithm above. As the working day is always 9 hours, even on the days the clocks change, we don't need to worry about that.

There is a slight anomaly to my algorithm. If the $duration ends at 6pm, the algorithm will give 9am on the next working day as the answer. This is of course strictly correct, but perhaps not what is expected. 

Damm and Cyclops

Damm algorithm

Take care to spell that correctly.

The Damm algorithm takes a sequence of n digits and results in a check digit, m. If the check digit is appended to the original sequence, applying the Damm algorithm to the new sequence of n+1 digits results in a check digit of 0.

The algorithm uses a weakly totally anti-symmetric quasigroup of order 10. I'm sure we're all familiar with those, but in case we don't have one to hand, Wikipedia has kindly purloined one from Dr Damm's PhD thesis, and luckily Mohammad has used that one for his example.

Armed with the quasigroup and holding it in Perl's simulation of a two-dimensional array, the algorithm is very simple: start with an 'interim digit' of 0 and then replace the interim digit with the value in the 2D array at [$interim_digit, $digit] where $digit is successive digits of the supplied number.

We are given a number to test which already has the check digit appended, so if the final value of $interim_digit is zero, the check digit is correct - ie the original digit sequence is valid.  

We can check our working by taking a long string of digits, adding its check digit, and then verifying that swapping two digits or altering a single digit results in a non-zero result from the algorithm.

Even in my rather verbose programming style that's only 5 lines of code (apart from initialising the table).

Palindromic prime cyclops numbers

The Damm algorithm is useful: it could be (but isn't) used for ISBNs or any long and easily mistyped string of digits.

Usefulness is not a feature - so far as I know - for palindromic prime cyclops numbers, which are prime numbers with an odd count of digits with the only zero as the middle digit.

My first thought was to start at 100 and check every number for being a PPCN. This works, but isn't very efficient. My second thought was only to check numbers with an odd number of digits - so 100 to 999 and then 10000 to 99999 and so on. That was a little quicker.

However, my third and submitted algorithm looks like this:

Loop $j up from 1 to something huge.  $j is going to be just the digits to the left of the central zero. 

First we discard any $j that contains a zero. 

Now we create a candidate number which is the concatenation of $j, '0' and $j reversed. So that is palindromic and has a single 0 in the right place, and all that remains is to check that it's prime. I used Math::Prime::Util to do that rather than write yet another sieve of Eratosthenes.

So far as I know, Perl has no intrinsic function to reverse a string, but this works:

join('', reverse(split('', $j)))

- that is, split the digits of the number into an array, reverse the array, and then join them together again.  There may be faster methods, but using my (third) algorithm generates PPCNs up into the millions without noticeable delay.

More funny numbers - permutable and reversible

Permuted multiples

Write a script to find the smallest integer x such that x, 2x, 3x, 4x, 5x and 6x are permuted 

multiples of each other. For example, the integers 125874 and 251748 are permuted multiples of each other.

My immediate thought was that the answer is 142857, which I imagine most of us recognise as the repeating decimal sequence in 1/7 (and 2/7, 3/7 ... 6/7). So I could take a punt on a valid solution being:

say 142857;

But is there a smaller answer?  I spent some time thinking whether I could prove that there isn't, but failed. So I wrote a short script to test it, and indeed that is the right answer. 

I also ran the script up to a million and didn't find another answer, so perhaps it is unique?

Reversible numbers

We are looking for a number written as AB such that AB + BA has only odd digits.

The sum is clearly 10A + B + 10B + A, which is 11 (A + B).  

Clearly no single digit number will qualify, so all we need to do is look from 10 to 99 checking that 11 (A + B) doesn't contain [02468].  Three lines of code does it plus another two to present the output a la Mohammad.