From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on
	ip-172-31-65-14.ec2.internal
X-Spam-Level: 
X-Spam-Status: No, score=-1.9 required=3.0 tests=BAYES_00,T_SCC_BODY_TEXT_LINE
	autolearn=ham autolearn_force=no version=3.4.6
Path: eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Paul Rubin <no.email@nospam.invalid>
Newsgroups: comp.lang.ada
Subject: Re: project euler 29
Date: Sun, 17 Sep 2023 15:54:12 -0700
Organization: A noiseless patient Spider
Message-ID: <874jjsquln.fsf@nightsong.com>
References: <beaa0494-5783-4130-b96f-1a5271466678n@googlegroups.com>
	<874jjvmoi9.fsf@bsb.me.uk>
	<a10a258f-8a3a-4017-bb30-8fe5629089ffn@googlegroups.com>
	<87sf7dltq0.fsf@bsb.me.uk> <87jzsplr49.fsf@bsb.me.uk>
	<715fe49a-47bc-46be-ae26-9ed89b38bcb5n@googlegroups.com>
MIME-Version: 1.0
Content-Type: text/plain
Injection-Info: dont-email.me; posting-host="02e6da0e6d12432512a57a13e6ebb466";
	logging-data="624102"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+cmFPp1MMsdUrYg0X2IU3q"
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/27.1 (gnu/linux)
Cancel-Lock: sha1:kxx0mr/Eo+tGS01Os6n3HzzWlPk=
	sha1:ZcfSxU2jTiYtL87cswah2lQFks8=
Xref: news.eternal-september.org comp.lang.ada:65670
List-Id: <comp.lang.ada>

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!