Posts

PWC 177

PWC 177 Challenge 1 (Damm Algorithm) This challenge requires implementing the Damm algorithm which uses an extra check digit to catch errors in entering digits in a numeric code, especially the common transposition errors. In terms of programming, this is a simple matter of setting up a lookup table and then looking it up. I implement two subroutines, closely following the howto in the wikipedia page. "get_check_digit" calculates a check digit for a given number, and "validate" checks if a number is correct based on the extended number including a check digit. In Perl 5 and Raku, I indulge my atavistic leanings by setting up the lookup table as a flat list of strings. In Julia, it is easy to implement it as a matrix. This algorithm is useful enough to have its own CPAN module: Algorithm::Damm Here is my Perl 5 script. Here is my Raku script. Here is my Julia script. Challenge 2 (Palindromic Prime Cyclops) This challenge requires looking for the first 20 positive in

PWC 176

PWC 176 Challenge 1 (Permuted multiples) We are asked to find the smallest number x such that x , 2 x, 3 x , 4 x , 5 x and 6 x all have the same digits in common (not in the same order obviously) and no other digits. The answer is 142857.    I started with Raku. Looping through the integers, for each multiple, 2x, 3x etc., I used comb to get a list of digits and then sort to get them sorted and then gist to stringify them, and then compared this to the combed, sorted and stringified original number x. This translates easily to both Perl 5 and Julia. In Perl 5 I used a sub to do the equivalent of combing and sorting and then joined the array back into an Int. Here is my Raku script Here is my Perl 5 script Here is my Julia script   Here it is as a Raku one-liner:   raku -e '(1 .. 200_000).grep({$_.comb.sort.gist eq (6*$_).comb.sort.gist}).grep({$_.comb.sort.gist eq (5*$_).comb.sort.gist}).grep({$_.comb.sort.gist eq (4*$_).comb.sort.gist}).grep({$_.comb.sort.gist eq (3*$_).comb.s

PWC 175

PWC 175 Challenge 1 -- Last Sunday Challenge 1 asks us to find the last Sunday of every month in a particular year, say 2022. This is easy to do in Perl thanks to the Date::Manip suite of modules, which bristles with options, including a straightforward way to do this. The specific module useful here is Date::Manip::Recur With this module it's as easy as saying: $date_recur_object -> parse( " last Sunday of every month in 2022 " ); which is exactly what I do. In Raku, it's a bit more difficult, but still easy via Raku's excellent and well-documented built-in Date objects. Pretty much a matter of looping through the last 10 days of each month, picking up the Sundays in that stretch, and then keeping the last Sunday. Julia is similar to Raku in its Dates handling, except that the Dates are not built-in, but a short library call away. I could have translated my Raku script line-for-line to Julia, but I have the minor difference that I used multiple dispatch in R

PWC #174

PWC #174 Challenge 1 (Disarium Numbers) For challenge 1, we are tasked to find the first 19 disarium numbers . These are base-ten positive integers "abc..." such that a^1+b^2+c^3 ... = abc... (I don't know how to type Math in this blog platform, so I use something like Excel formula syntax, with which readers should be familiar) For example, 518 is a disarium number, because 5+1^2+8^3 = 518.  There are only 20 disarium numbers, with the 20th being a 20-digit monster. The first 10 are mechanically the single-digit numbers from 0 through 9. The 19th is a 7-digit number around 2.6 million. I used a brute-force approach of just going through all the numbers from 0 to 3_000_000, and selecting the ones which meet the disarium condition. But a more efficient strategy exists, which I sketch below, but did not implement in most of my scripts. The brute force approach is fast enough for the first 19 items. More efficient (but largely unused) algorithm Consider if we want to find al

PWC #173

PWC #173 Challenge 1 (Esthetic numbers) Esthetic numbers are numbers in which consecutive digits are either one less or one more than the (previous or next) other digit. For example, 5_654 is an esthetic number but 120 is not. We are asked to find a function that tells us whether a particular input number is esthetic or no. This seems like a good candidate for a regex solution, but I wound up just looping through the characters in the number (as a string) and checking if the next character was one more or less. If not, then it is not esthetic, otherwise it is. I also check that the input is numeric (otherwise not esthetic). In Perl and Raku, I check for and drop the "_" character used as a thousands separator. I have not considered single-digit numbers, the algorithm assumes the number is at least two digits (easy to fix, but I'll leave it). The internet tells me that single-digit numbers are esthetic by convention. My if condition is unnecessarily clunky, I check separa

PWC #172

PWC #172 Challenge 1 (Prime Partition) The challenge calls for finding a set of n prime numbers that add up to a given number m .  CAVEAT: I have not quite followed the instructions, which require the set of primes to be distinct ("No duplicates"). My solutions also find repeated primes. Thus, the challenge gives the expected prime partition where m =19 and n =3 as: (3,5,11) where 3+5+11=19. My programs also turn up: (3,3,13) and (5,7,7). My discussion below is therefore for the somewhat different problem that allows duplicates. My bad for not reading the instructions carefully enough, but hopefully the somewhat different problem and solution is still interesting. Though usually with prior challenges, I started in Perl 5, and my Raku programs have mostly been adapted from the Perl 5 version, this time, I started in Raku.  Raku offers the combination operator, which can be used to efficiently(?) search through all combinations of items, such as an array of prime numbers. I

PWC #171

PWC #171 Challenge 1 Odd Abundant Numbers Abundant numbers are whole numbers (positive integers) where the sum of all the whole-number divisors is greater than the number itself (where the summation includes both prime and non-prime divisors and the number 1, but not the number itself) . They contrast with perfect numbers, where this sum exactly equals the number, and deficient numbers, where this sum is less than the number. We are asked to find the first 20 odd abundant numbers. I use the Math::Factor::XS package in Perl 5. This has the "factors" function which returns an array of all the factors of a number including non-prime factors (but excluding 1 and the number itself). Perl 5 does not have a ready-made sum function to sum over an array, but it is trivial to write one, along with another convenience function to print an array. We then loop over the odd numbers using a C-style for loop (for my $n=1;;$n+=2), calculating the sum of factors (remembering to add 1), and