RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved some interesting mathematical sequences. (Note that this is open until 26 December 2021.)

Task 1: Semiprime

Write a script to generate all Semiprime number <= 100.

where a semiprime number is the product of exactly two primes.

I did this in two steps: (1) get all the relevant prime numbers (sieve of Eratosthenes), (2) multiply them to get semiprimes. In Raku:

sub semiprime($mx) {
  my @primes;
  {

Make a list of candidate primes. (Use a lower ceiling here; if the semiprimes are going up to 100, we only need primes in the range 2..50.)

    my $mxx=floor($mx/2);
    my $primesh=(2..$mxx).SetHash;

Start with a test divisor.

    my $p=2;

If the square is higher than the maximum, bail out because there will be no more numbers to be removed.

    while ($p*$p <= $mxx) {

See whether this number is still regarded as plausibly prime. If it's not, we've already removed all its multiples from earlier passes.

      if ($primesh{$p}:exists) {

Start at number-squared, because again any smaller factors have been removed. (E.g. 5×2 and 5×3 were already removed when we did 2×5 and 3×5.)

        my $i=$p*$p;

Iterate deleting multiples of this number.

        while ($i <= $mxx) {
          $primesh{$i}:delete;
          $i += $p;
        }
      }

(All the non-Perl languages offer me some easy way of iterating on a range with a step; for example in Ruby

      (p*p..mxx).step(p) do |i|
        primesh.delete?(i)
      end

which I find easier to comprehend at a glance than the while-loop approach.)

Jump to the next plausible-prime (all the odd numbers after 2); I could generate candidates using the (6k-1,6k+1) loop I had for challenge 139 task 2, but given that all we're doing for each non-prime is a hash lookup this seems like optimisation enough. If this were performance-critical I'd write both versions and profile them. Maybe eventually I'll write a library function to generate all primes up to a set limit, with all the optimisations, in each language I use for these things.

      if ($p==2) {
        $p--;
      }
      $p+=2;
    }

Take the remaining list of primes, sort it, and drop it into an array.

    @primes=$primesh.keys.sort;
  }

That's part 1 done. Part 2 is quite similar in that it builds up an unordered list with deduplication. This time we start with an empty list:

  my $semiprimesh=SetHash();

Iterate over the primes.

  for 0..@primes.end -> $i {

Iterate from this prime to the end of the list (so we'll multiply a number by itself, but we don't calculate both a×b and b×a).

    for $i..@primes.end -> $j {

Calculate the product, and store if it's within the maximum value. (Otherwise bail out of the inner loop, since we know @primes is sorted, so all values calculated in the rest of this loop would also be too high.)

      my $t=@primes[$i]*@primes[$j];
      if ($t <= $mx) {
        $semiprimesh{$t}++;
      } else {
        next;
      }
    }
  }

Get it out as a list.

  return $semiprimesh.keys.map({$_+0}).sort;
}

This works in PostScript too (using a dict in place of the Set).

Task 2: Ulam Sequence

You are given two positive numbers, $u and $v.

Write a script to generate Ulam Sequence having at least 10 Ulam numbers where $u and $v are the first 2 Ulam numbers.

where the next entry in an Ulam sequence is the lowest number larger than the previous entry, that can be made by summing exactly one combination of previous entries. (Yes, that Ulam.)

I used a sieving algorithm. sieve[0] is the sieve value for candidate number 1, etc. I'll show this one in Kotlin.

fun ulam(u: Int, v: Int, ccount: Int): ArrayList<Int> {
    var ulams=arrayListOf<Int>(u,v)
    var sieve=ArrayList<Int>()
    var uc=v
    while (ulams.size < ccount) {

Extend the sieve list with zeroes until it's large enough to account for the next number (which can't be higher than the sum of the last two numbers found). (Several languages have ways of generating a list of a set number of zeroes; it's quite possible Kotlin does too and I simply haven't found it yet.)

        for (i in sieve.size..uc+ulams[ulams.size-2]) {
            sieve.add(0)
        }

For each number in the candidate space (from the most recent up to the sum of the most recent two), add 1 to its sieve value – i.e. increment the number of ways of constructing it. (If it's constructible from an earlier pair of numbers, we'll have checked that on a previous pass.)

        for (i in 0..ulams.size-2) {
            sieve[uc + ulams[i] - 1] += 1
        }

Then look through the sieve list: the first sieve entry we find with a value of 1 (i.e. which has exactly one possible construction) is the next number in the sequence.

        for (i in uc..sieve.size-1) {
            if (sieve[i] == 1) {
                uc=i+1
                ulams.add(uc)
                break
            }
        }
    }
    return ulams
}

And because I am a glutton for punishment I've added Lua to the languages I'm doing this in. (As with Ruby, it's the language needed for code that runs within something I already work with – in this case Tabletop Simulator – so I want to get some facility with it on a "proper" system before I try to get things working in a restricted environment.) The main weirdness is that it really wants you to start your array indices at 1… and its arrays are hashes really. Not fast, but readily embeddable, which is its point.

Full code on github.