I’ve been doing the Weekly
Challenges. The
latest
involved an unusual binary encoding and indexing into a multiplication
table. (Note that this is open until 5 December 2021.)
Task 1: Number Divisors
Write a script to find lowest 10 positive integers having exactly 8
divisors.
For a test case, this can easily be checked against the
OEIS.
I always feel a bit lost when I have to factorise, but not
prime-factorise. (Of course one can build a list of all divisors by
starting with a list of prime factors, but I already knew I was going
to use a similar pattern with a bitmask in task #2 so I did it the
straightforward way. That's how I'd approach it with larger numbers,
though.)
I did this in two steps, because "count the number of factors of a
number" seems as though it might be something usefully reusable later.
Here's the Raku.
sub factorcount($n) {
if n==1 then let's not faff about with special cases deeper into the
code; just drop out now.
if ($n==1) {
return 1;
}
We start with two factors: 1 and N.
my $f=2;
If the number is a perfect square, it has one more factor, √N.
my $s=floor(sqrt($n));
if ($s*$s == $n) {
$s--;
$f+=1;
}
Any other factors will be in pairs, so we test them exhaustively up to
just below √N.
for (2..$s) -> $pf {
if ($n % $pf == 0) {
$f+=2;
}
}
return $f;
}
With that toolkit function, I write a wrapper to do the test case (in
this case with the parameters 10,8).
sub divisors($count,$n) {
my $nn=$n;
my @a;
my $t=0;
while ($nn) {
$t++;
if (factorcount($t)==$count) {
push @a,$t;
$nn--;
}
}
return @a;
}
All the other languages follow basically the same approach.
Task 2: Like Numbers
You are given positive integers, $m
and $n
.
Write a script to find total count of integers created using the
digits of $m
which is also divisible by $n
.
Repeating of digits are not allowed. Order/Sequence of digits can't
be altered. You are only allowed to use (n-1) digits at the most.
For example, 432 is not acceptable integer created using the digits
of 1234. Also for 1234, you can only have integers having no more
than three digits.
This got most fiddly in Rust, where converting back and forth between
numbers and strings is a Major Undertaking. The other languages all
take it quite lightly; some like indexing into strings better than
others. (One could break down the input number with modulus and
division, but string conversion is probably easier, even in Rust.) In
Python:
def likenumber(source,factor):
So we get the input number into an array of single-digit values
(converting each one just once), and get the length because we'll be
using that later. And start the counter.
s=[int(i) for i in str(source)]
m=len(s)
n=0
I'll use a bitmask pattern to flip each digit in and out of
consideration. All-digits-set is not allowed, so I cut one off the
test range. (Neither is no-digits-set of course.) And I'll build up
the candidate number one digit at a time.
for mask in range(1,(1<<m)-1):
c=0
for di in range(m):
if mask & 1<<di:
c=c*10+s[di]
if c % factor == 0:
n+=1
return n
For the PostScript version, it seemed easier to index into the string
and do the conversion on the fly. Slower that way, but nobody's going
to be running PostScript for speed. (I must write an array-unshift to
go with the array-push I already have. And pop/shift for that matter,
so that I can do clean FIFOs and LIFOs.)
/likenumber {
/factor exch def
/source exch def
/s source i2s def
/m s length def
/n 0 def
1 1 1 m bitshift 2 sub {
/mask exch def
/c 0 def
0 1 m 1 sub {
/di exch def
mask 1 di bitshift and 0 gt {
/c c 10 mul s di get cvi add def
} if
} for
c factor mod 0 eq {
/n n 1 add def
} if
} for
n
} bind def
Full code on
github.