Re: project euler 29

[Paul Rubin <no.email@nospam.invalid>]

Francesc Rocher <francesc.rocher@gmail.com> writes:
> Also, do you have a different approach to solve this 29th problem?

I see two natural approaches: 1) use bignums--it didn't occur to me to
not use them until this discussion.  2) Notice that a**b == c**d exactly
when the two sides have the same prime factorization, and the factors
of a**b are just the factors of a repeated b times, so you can count up
the distinct tuples of factors.

Method #2 is efficient (since a,b,c,d are all < 100) and doesn't use
bignums, but it is a fair amount of code to write unless you have
convenient libraries at hand for factorization and can easily count sets
of distinct tuples.  I guess there are fancier approaches possible too,
that avoid searching 100**2 combinations, but 100**2 is just 10000 which
is small.

Certainly both are easier to do if your language or libraries has
convenient features for dealing with variable sized objects like
bignums, or sets of tuples.  The bignum approach is less efficient but
it is much easier to code.  The Python expression

  len(set(a**b for a in range(2,101) for b in range(2,101))) 

takes around 25 msec to compute on my old slow laptop.

I will look at your Ada solution!