Re: project euler 29

[Ben Bacarisse <ben.usenet@bsb.me.uk>]

Paul Rubin <no.email@nospam.invalid> writes:

> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>>> Also, do you have a different approach to solve this 29th problem?
>>
>> Yes, but it's not in Ada.  I implemented an equality test for a^b ==
>> c^d.
>
> Oh interesting, based on a comment in Francesc's code, I think I see a
> method to do it without the auxiliary array, at a small increase in
> runtime cost.  Basically given a and b, you can find their prime factors
> and easily enumerate the combinations x,y with a**b==x**y and
> 1 <= x,y <= 100.  You can label each "equivalence class" by the (a,b)
> with the smallest possible a.
>
> So you just loop through 1 <= a,b <= 100 and count only the a,b pairs
> where a is the smallest a for its equivalence class.  I might see if I
> can code this, which should also let me describe it more concisely.

This is likely to be fast which is why I wanted to compile Francesc's to
try it out.  Mind you, a naive a^b == c^d test gives pretty good
performance for the kind of range requested.

-- 
Ben.