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 Newsgroups: comp.lang.ada Subject: Re: project euler 29 Date: Sun, 17 Sep 2023 17:09:38 -0700 Organization: A noiseless patient Spider Message-ID: <87zg1kpcjh.fsf@nightsong.com> References: <874jjvmoi9.fsf@bsb.me.uk> <87sf7dltq0.fsf@bsb.me.uk> <87jzsplr49.fsf@bsb.me.uk> <715fe49a-47bc-46be-ae26-9ed89b38bcb5n@googlegroups.com> <87ediwl7oq.fsf@bsb.me.uk> MIME-Version: 1.0 Content-Type: text/plain Injection-Info: dont-email.me; posting-host="02e6da0e6d12432512a57a13e6ebb466"; logging-data="646671"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18ADWhWG/i/Qo7Z/yINFR/A" User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/27.1 (gnu/linux) Cancel-Lock: sha1:V1Fdk6wmCuXRgMpreGRnHqR5IK4= sha1:oytZRX9CpL2T+DWWbaLvMFEXuNI= Xref: news.eternal-september.org comp.lang.ada:65672 List-Id: Ben Bacarisse 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.