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.
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.