RogerBW's Blog

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.