I’ve been doing the Weekly
Challenges. The
latest
involved a check-digit function and more number reversals. (Note that
this is open until 14 August 2022.)
Task 1: Damm Algorithm
You are given a positive number, $n
.
Write a script to validate the given number against the included
check digit.
The Damm algorithm is
really interesting: its actual procedure is simple, a digit-by-digit
table lookup based on the previous intermediate result (or 0) and the
present digit, but the cleverness is in the table, constructed such
that any single-digit error or adjacent-digit transposition will
change the result.
For language with sloppy string/number types this is nearly trivial,
as here in Perl:
sub damm($n) {
my @tab = (
[0,3,1,7,5,9,8,6,4,2],
[7,0,9,2,1,5,4,8,6,3],
[4,2,0,6,8,7,1,3,5,9],
[1,7,5,0,9,8,3,4,2,6],
[6,1,2,3,0,4,5,9,7,8],
[3,6,7,4,2,0,9,5,8,1],
[5,8,6,9,7,2,0,1,3,4],
[8,9,4,5,3,6,2,0,1,7],
[9,4,3,8,6,1,7,2,0,5],
[2,5,8,1,4,3,6,7,9,0],
);
my $c = 0;
foreach my $digit (split '',$n) {
$c = $tab[$c][$digit];
}
return $c;
}
sub checkdamm($n) {
return (damm($n)==0)?1:0;
}
(I use two separate functions because, although checkdamm
is the
only one required, I can easily picture wanting to know the actual
checksum too.)
Where types do exists, as in JavaScript, it gets a little more fiddly:
for (let digit of n.toString().split("")) {
c = tab[c][parseInt(digit)];
}
I do rather like the PostScript though.
/damm {
1 dict begin
/tab [
[0 3 1 7 5 9 8 6 4 2]
[7 0 9 2 1 5 4 8 6 3]
[4 2 0 6 8 7 1 3 5 9]
[1 7 5 0 9 8 3 4 2 6]
[6 1 2 3 0 4 5 9 7 8]
[3 6 7 4 2 0 9 5 8 1]
[5 8 6 9 7 2 0 1 3 4]
[8 9 4 5 3 6 2 0 1 7]
[9 4 3 8 6 1 7 2 0 5]
[2 5 8 1 4 3 6 7 9 0]
] def
[ exch
{
dup 0 gt {
dup 10 mod exch
10 idiv
} {
pop
exit
} ifelse
} loop
] reverse 0 exch {
tab 3 -1 roll get exch get
} forall
end
} bind def
Task 2: Palindromic Prime Cyclops Numbers
Write a script to generate first 20 Palindromic Prime Cyclops Numbers.
A cyclops number is a number with an odd number of digits that has a
zero in the center only.
Sequence A136098 at the OEIS.
As I see it this is a filtering process. For each integer, starting at
1:
- check that it contains no zeroes
- turn it into a palindromic cyclops (i.e
ABC
→ ABC0CBA
, and
increasing ABC always leads to increasing the palindrome)
- check that for primality (using code I've already written)
I could also reject candidates that started with 5 or an even number,
since the cyclops will end with that and it won't be prime, but when I
tried this it was slower than simply letting them fall into the
primality test and be rejected there.
(Or I could turn the whole thing inside-out to generate a sequence of
primes and test them for being palindromic cyclops numbers, but while
I haven't checked I strongly suspect this would be less efficient.)
So in PostScript:
/ppc {
4 dict begin
/ct exch def
[
/fh 0 def
{
Increment the candidate number.
/fh fh 1 add def
/q true def
Check for zeroes.
fh {
dup 0 gt {
dup 10 mod 0 eq
{
/q false def
pop
exit
} {
10 idiv
} ifelse
} {
pop
exit
} ifelse
} loop
If no zeroes, duplicate (and because PostScript strings are always
references, make a copy with dup length string cvs
)
q {
[ fh cvss dup dup length string cvs reverse (0)
exch ] () strjoin cvi
And check for primality; if true, leave it on the stack, which is our
output array.
dup isprime {
/ct ct 1 sub def
ct 0 le {
exit
} if
} {
pop
} ifelse
} if
ct 0 le {
exit
} if
} loop
]
end
} bind def
More conventionally in Kotlin:
fun ppc(ct: Int): List<Int> {
var o = ArrayList<Int>()
var fh = 0
while (o.size < ct) {
fh += 1
var t = fh
var q = false
while (t > 0) {
if (t % 10 == 0) {
q = true
break
}
t /= 10
}
if (q) {
continue
}
val sfh = fh.toString()
val c = (sfh + "0" + sfh.reversed()).toInt()
if (isprime(c.toLong())) {
o.add(c)
}
}
return o
}
Full code on
github.
Comments on this post are now closed. If you have particular grounds for adding a late comment, comment on a more recent post quoting the URL of this one.