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: Ben Bacarisse <ben.usenet@bsb.me.uk>
Newsgroups: comp.lang.ada
Subject: Re: project euler 29
Date: Mon, 18 Sep 2023 01:16:19 +0100
Organization: A noiseless patient Spider
Message-ID: <8734zcl4j0.fsf@bsb.me.uk>
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>
	<87ediwl7oq.fsf@bsb.me.uk> <87zg1kpcjh.fsf@nightsong.com>
MIME-Version: 1.0
Content-Type: text/plain
Injection-Info: dont-email.me; posting-host="4a1f049c3c0d7d3aa42e2e5e10f8a54b";
	logging-data="643104"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/SGt11WrJM/gu8BofXctTyY6bUSD9leB4="
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/28.2 (gnu/linux)
Cancel-Lock: sha1:bxVD6sBPf+hJjS5KJmeY8mLbzBs=
	sha1:/BblLvuSBXWQj0OWqRs+rnC0TCw=
X-BSB-Auth: 1.9382678f80c36cfff3d0.20230918011619BST.8734zcl4j0.fsf@bsb.me.uk
Xref: news.eternal-september.org comp.lang.ada:65673
List-Id: <comp.lang.ada>

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.