RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved finding Pythagorean triples and prime numbers. (Note that this ends today.)

Task 1: Pythagoras Multiplied

You are given a positive integer n.

Find the number of all positive integer triplets (a, b, c) so that a^2 + b^2 = c^2 and a, b and c are integers <= n.

I can take some short cuts here.

We know there are no integer Pythagorean triangles with an hypotenuse less than 5. (I'm not just going to test-fit all the known triangles, though it could be done in this case; it always feels like cheating to build from someone else's list.)

The problem wants me to count (3, 4, 5) and (4, 3, 5) separately. But I can slice off half the search space. Can there be a triple such that a == b? I argue no: if these is, a² + b² = c² is equivalent to 2a² = c², and if we take the square root of each component in that last equation √2a = c. Which means a and c have an irrational ratio, and so cannot both be integers. Therefore for any given c I can just run my tester through a from 1 to c - 2, then within that through b from a + 1 up to c - 1, and count each success twice.

And if a² + b² > c² I can end the innermost (b) loop early because no later b will work with this a and c. (Except in Scala which doesn't let you break out of a loop.)

All right, this is still O(n³).

Furthermore I can cache the results of the squaring operations, both inside each loop and overall (by various methods depending on the language, or not at all if it turned out to be hard). Perhaps a squaring operation is not expensive enough to be worth caching, but it's a handy proof of concept.

Perl:

use Memoize;

memoize('squared');

sub squared($a) {
  $a * $a;
}

sub pythagorasmultiplied($n) {

Initialise the counter.

  my $ct = 0;

Loop over all possible values of c.

  foreach my $c (5 .. $n) {
    my $csquared = squared($c);

And then a inside that.

    foreach my $a (1 .. $c - 2) {
      my $asquared = squared($a);

And then b inside that.

      foreach my $b ($a + 1 .. $c - 1) {
        my $bsquared = squared($b);

Then do the testing.

        my $tot = $asquared + $bsquared;

If we've exceeded the value, drop out of the inner loop.

        if ($tot > $csquared) {
          last;
        }

If we've matched the value, count the triangle.

        if ($tot == $csquared) {
          $ct += 1;
        }
      }
    }
  }

The result is double the counter.

  $ct * 2;
}

Task 2: Prime Step

You are given a string with English alphabetic characters only.

What is the absolute difference of the sum of the ASCII values of the characters in the string to the nearest prime number?

The algorithm is apparent:

Step 1, find the target number.

Step 2, find a list of primes which spans the target.

Step 3, find from that list the two closest primes to the target, calculate the differences, and return the lower one.

With languages that have a readily available binary search on a sorted list (Rust, Python, Kotlin) I use it. Otherwise I just filter the list of primes, rather than mucking about with writing my own binary search and fiddling with special cases. (I haven't met a language with a two-way filter function, like the existing filter/grep/select but producing a second list with the non-matching elements. It wouldn't often be useful, but it would here.)

Rust:

fn primestep(a: &str) -> u32 {

Find the target value.

    let g = a.chars().map(|x| x as u32).sum::<u32>();

Generate a (sorted) list of primes that will span it. (I think the ratio of two successive primes is never as much as 2.) Using existing library code, see codeberg for the full thing.

    let pm = genprimes(g * 2);

Find the insertion point of the target value in that list. This can be either an Ok (we found this exact value) or an Err(x) (x is the place where the value should be inserted to keep the list sorted).

    let bs = pm.binary_search(&g);
    match bs {

If we had an exact match, the difference is zero.

        Ok(_) => 0,

Otherwise, calculate the difference between target and previous prime, and target and next prime, and return the lower.

        Err(ix) => min(g - pm[ix - 1], pm[ix] - g),
    }
}

As an example of the languages where I didn't have (or at least didn't find) a binary search, here's the Raku version, starting as before.

sub primestep($a) {
    my $g = $a.comb.map({$_.ord}).sum;
    my @pm = genprimes($g * 2);

Find all the values that are lower than or equal to the target, and take the last (highest) one.

    my $lo = @pm.grep({$_ <= $g})[*-1];

Find all the values that are greater than the target, and take the first (lowest) one.

    my $hi = @pm.grep({$_ > $g})[0];

Calculate the difference as before.

    min($g - $lo, $hi - $g);
}

Full code in all tagged languages is on codeberg.