[VA] Short & Sweet Math Challenge #24: "2019 Spring Special 5-tier"

[Valentin Albillo]

       
Hi, all:
       
First of all, thanks to all 5 of you who contributed to this thread so far, namely Albert Chan, Paul Dale, J-F Garnier, Oulan and Gerson W. Barbosa, your efforts and interest are much appreciated (and also thanks for not using CODE sections as I requested).

A week has elapsed and now I'll post my original solutions and comments to the different tiers discussed, one at a time, beginning with Tier 1:

Tier 1 - The Challenge:

We'll call  Homage Number  to any 10-digit positive integers which are multiples of 271, divisible by 41 and further their digits are all distinct. Write a program that takes no inputs but simply finds out and outputs just how many Homage Numbers there are.

My original solution:

This tier was expressly created to be really easy so anyone interested could write code to solve it without much trouble. Matter of fact, as Albert Chan realized, it can be solved by hand with just a little thinking. The key is to realize that 41 and 271 are coprime, so every Homage number should be divisible by both and thus by their product, which is 41 * 271 = 11,111.

Also, being a 10-digit number and having all its digits distinct means that its digits are 0, 1, 2, 3, ... , 9 in some order and thus their sum is 1 + 2 + 3 + ... + 9 = 45, which is divisible by 9 so each Homage number has to be divisible by 9 too. As 9 is coprime to 41 and 271, each Homage number N must be divisible by their product, i.e., by 41 * 271 * 9 = 99,999.

Now let's split N into two 5-digit parts, A, B, like this: N = 100,000*A + B, which must be a multiple of 99,999, so subtracting 99,999*A from it the resulting value: 100,000*A + B - 99,999*A = A + B must be a multiple of 99,999 too and, as both A and B are 5-digit long, i.e., less than 100,000, that multiple must be 99,999 itself. Now, considering their individual digits we have:

       A + B = abcde + uvxyz = 99999

and thus all 5 pairs of digits must comply with a + u = b + v = ... = e + z = 9.

Now, there are 5! permutations of the 5 pairs, so 120 permutations in all, but each of the 5 pairs has 2 possible orderings, say (a,u) and (u,a), so 2⁵ = 32 variations for each of the 120 permutations and thus there are 120 * 32 = 3,840 potential Homage numbers in all.

However, only 9 out of 10 begin with a non-zero digit (numbers beginning with a 0 aren't 10-digits numbers) and so finally there are 3,840 * 9/10 = 3,456 Homage Numbers.

What if we can't or won't engage on such math reasoning ? Well, that's where our trusty HP calc will take away all the drudgery and work out the solution by itself, doing all the work for us in mere seconds and saving our neurons for better endeavours. In my case, this little 2-liner for the HP-71B (fits in just 1 line too) will scan the whole range at steps of 99,999, increasing the count each time the corresponding number happens to have all its 10 digits different:

       1   DESTROY ALL @ C=0 @ D=99999 @ FOR N=D*CEIL(10^9/D) TO 10^10-1 STEP D
       2   C=C+NOT SPAN("0123456789",STR$(N)) @ NEXT N @ DISP C

          >RUN
                 3456

so there are 3,456 Homage Numbers in all.

That's it. Affordable, as promised. In the next days I'll post my solutions for the subsequent tiers.

V.