RogerBW's Blog

The Weekly Challenge 144: Semiprime Ulam 21 December 2021

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.

See also:
Perl Weekly Challenge 139: Jort Primes

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 advent of code 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 cthulhu eternal cycling dead of winter doctor who documentary drama driving drone ecchi economics en garde espionage essen 2015 essen 2016 essen 2017 essen 2018 essen 2019 essen 2022 essen 2023 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 mpd 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 scala 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