RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved more numerical series. (Note that this is open until 19 June 2022.)

Task 1: Brilliant Numbers

Write a script to generate first 20 Brilliant Numbers.

I.e. numbers with exactly two prime factors, of the same (base-10) length. So what I want to do is generate all the primes of a length, multiply them together pairwise, and if I don't have enough values add one to the length and do it again. I use a technique similar to the one in #167 two weeks ago, generating each set of length-N primes as a group. Python:

def brilliant(ct):
  base = 1
  out = set()
  while True:

Generate one digit-count's worth of primes (e.g. 1..9, 10..99, etc.)

    pl = [x for x in genprimes(base * 10) if x >= base]

Doubly iterate over the range, for each distinct multiplicative combination.

    for ai in range(len(pl)):
      for bi in range(ai,len(pl)):
        out.add(pl[ai] * pl[bi])

If I've got enough results, leave and process them.

    if len(out) >= ct:
      break

Otherwise, add a digit and continue.

    base *= 10

Convert the results into a list, sort it, and return the first ct entries of it.

  o = list(out)
  o.sort()
  return o[0:ct]

Task 2: Achilles Numbers

Write a script to generate first 20 Achilles Numbers.

These are numbers which are powerful (prime factorisation has no terms of power = 1) but imperfect (are not a perfect power, i.e. have no integer roots).

This can be resolved purely by looking at the exponents of the prime factorisation:

• there must be at least two terms

• the lowest term must be at least 2

• the greatest common divisor of the terms is 1

I already have prime factorisation code, and indeed for the languages that don't have it built in (most of them) a gcd function. Raku:

sub achilles($ct) {

Initialise output list and candidate.

    my @o;
    my $n = 1;
    while (True) {

Increment candidate.

        $n++;

Get the list of exponents.

        my @pv = primefactor($n).values;

If there are at least two terms, and

        if (@pv.elems > 1 &&

the lowest term is at least 2, and

            min(@pv) >= 2 &&

the gcd is 1 (using the syntax for a built-in infix operator)

            @pv.reduce(&infix:<gcd>) == 1) {

then this is a valid Achilles number. If we have enough, exit.

            push @o,$n;
            if (@o.elems >= $ct) {
                last;
            }
        }
    }
    return @o;
}

Full code on github.