RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved various sorts of numerical search. (Note that this is open until 23 January 2022.)

Task 1: Eban Numbers

Write a script to generate all Eban Numbers <= 100.

An Eban number is a number that has no letter 'e' in it when the number is spelled in English (American or British).

So we have the sequence in the OEIS, of course.

I could have written a number-to-words converter – but that's fairly standard library code, and it's not needed to solve the problem. So instead I wrote something much simpler. In Perl:

sub eban {
  my $mx=shift;

Two lookup tables: a true value if there's no e in the representation of that digit, in the units place or the tens place. ("zero" doesn't count.)

  my @units=(1,0,1,0,1,0,1,0,0,0);
  my @tens=(1,0,0,1,1,1,1,0,0,0,0);
  my @out;

For each digit (tens and units), check whether its word-representation is allowable. (So for 17 I'm actually testing "ten-seven".) For 100, the "first digit" is 10. 0 has to be special-cased because "zero" has an e but that doesn't prevent "thirty" from being valid.

  foreach my $i (0..$mx) {
    if ($tens[int($i/10)] && $units[$i%10] && $i != 0) {
      push @out,$i;
    }
  }
  return \@out;
}

Task 2: Cardano Triplets

Write a script to generate first 5 Cardano Triplets.

A triplet of positive integers (a,b,c) is called a Cardano Triplet if it satisfies the below condition.

which I won't try to include as an image, but in short:

cube root of (a + b * sqrt(c)) plus cube root of (a - b * sqrt(c)) = 1

Extracting roots is hard computational work, and uses floating point which is just generally a bad idea. So let's not do that. There are a couple of useful rearrangements we can make: first here to get a simpler formula linking a, b and c, and further here building a parametric version. Another demonstration that spending minutes doing algebra can save milliseconds of runtime.

Here's the Rust version:

fn cardano(ct: u32) -> Vec<[u32;3]> {
    let mut out: Vec<[u32;3]>=Vec::new();
    let mut k=0;
    let mut cn=0;
    loop {

Using the parametric identity, generate values for a and for b²c. Now we just have to break down that latter number into its b² and c parts.

        let a=3*k+2;
        let b2c=(k+1)*(k+1)*(8*k+5);

Set up a cheaty way of generating b² by increments.

        let mut b=0;
        let mut b2=0;
        let mut inc=1;
        loop {
            b += 1;
            b2 += inc;
            inc += 2;

Now to be fair I could probably just have set b2=b*b each time through the loop and not taken much longer, but… eh, never mind. If b² is higher than b²c then c is less than 1 and we won't get any more valid solutions by increasing b.

            if b2 > b2c {
                break;
            }

If b²c is evenly divisible by b² then c is an integer and we have a solution, in which case add it to the list and leave if we have enough. Otherwise, keep looping.

            if b2c % b2 == 0 {
                out.push([a,b,b2c/b2]);
                cn += 1;
                if cn >= ct {
                    break;
                }
            }
        }
        if cn >= ct {
            break;
        }
        k += 1;
    }
    out
}

No floating point, no problem.

Full code on github.