RogerBW's Blog

The Weekly Challenge 141: Binary and Tabular 30 November 2021

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.

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.

Search
Archive
Tags 1920s 1930s 1940s 1950s 1960s 1970s 1980s 1990s 2000s 2010s 3d printing action aeronautics aikakirja anecdote animation anime army astronomy audio audio tech aviation base commerce battletech beer boardgaming book of the week bookmonth chain of command children chris chronicle church of no redeeming virtues cold war comedy computing contemporary cornish smuggler cosmic encounter coup covid-19 crime cycling dead of winter doctor who documentary drama driving drone ecchi economics espionage essen 2015 essen 2016 essen 2017 essen 2018 essen 2019 essen 2022 existential risk falklands war fandom fanfic fantasy feminism film firefly first world war flash point flight simulation food garmin drive gazebo genesys geocaching geodata gin gkp gurps gurps 101 gus harpoon historical history horror hugo 2014 hugo 2015 hugo 2016 hugo 2017 hugo 2018 hugo 2019 hugo 2020 hugo 2022 hugo-nebula reread in brief avoid instrumented life javascript julian simpson julie enfield kickstarter kotlin learn to play leaving earth linux liquor lovecraftiana lua mecha men with beards museum music mystery naval noir non-fiction one for the brow opera parody paul temple perl perl weekly challenge photography podcast politics postscript powers prediction privacy project woolsack pyracantha python quantum rail raku ranting raspberry pi reading reading boardgames social real life restaurant reviews romance rpg a day rpgs ruby rust science fiction scythe second world war security shipwreck simutrans smartphone south atlantic war squaddies stationery steampunk stuarts suburbia superheroes suspense television the resistance the weekly challenge thirsty meeples thriller tin soldier torg toys trailers travel type 26 type 31 type 45 vietnam war war wargaming weather wives and sweethearts writing about writing x-wing young adult
Special All book reviews, All film reviews
Produced by aikakirja v0.1