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,FREEMAIL_FROM,
T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6
X-Received: by 2002:a05:620a:8d07:b0:76d:c79b:4bb8 with SMTP id rb7-20020a05620a8d0700b0076dc79b4bb8mr169208qkn.1.1695042261803;
Mon, 18 Sep 2023 06:04:21 -0700 (PDT)
X-Received: by 2002:a05:6808:17a3:b0:3a1:d419:9c64 with SMTP id
bg35-20020a05680817a300b003a1d4199c64mr3716486oib.5.1695042261462; Mon, 18
Sep 2023 06:04:21 -0700 (PDT)
Path: eternal-september.org!news.eternal-september.org!border-1.nntp.ord.giganews.com!nntp.giganews.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.lang.ada
Date: Mon, 18 Sep 2023 06:04:21 -0700 (PDT)
In-Reply-To: <87wmwnk9a9.fsf@bsb.me.uk>
Injection-Info: google-groups.googlegroups.com; posting-host=77.75.179.3; posting-account=ZswU3AoAAAA4QKiyoxEpA3Hh7ry7Cau3
NNTP-Posting-Host: 77.75.179.3
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> <87zg1kpcjh.fsf@nightsong.com> <8734zcl4j0.fsf@bsb.me.uk>
<87v8c8oyby.fsf@nightsong.com> <87wmwnk9a9.fsf@bsb.me.uk>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <7a98a430-a01d-41e7-80fe-bc2e1e1592d3n@googlegroups.com>
Subject: Re: project euler 29
From: Francesc Rocher
Injection-Date: Mon, 18 Sep 2023 13:04:21 +0000
Content-Type: text/plain; charset="UTF-8"
Xref: news.eternal-september.org comp.lang.ada:65676
List-Id:
> > But Francesc's program doesn't use that method. It only suggests it in
> > a comment. The program actually works by building a list, sorting it,
> > and counting the groups.
> I only looked briefly and thought it used the factor method to decide if
> the power is one that occurs earlier in the sequence. Two trivial
> things, starting with Answer as the full NxN count and then decrementing
> Answer made me think that was what it was doing.
Exactly, that's the point: to find if for a given base+exponent a**b there is an
equivalent x**y with 2 <= a < x <= 100 and 2 <= y <= 100, first a and b are
factored as a product of prime numbers. In case a has multiple times the same
factor, e.g. 27 = 3*3*3 = 3**3, then the exponent 3 is used as a new factor of the
exponent. Introducing this factor requires that the list of factors of b must be
sorted to find a new base x, a < x. Otherwise you could find x > 100 and consider
that there is no such pair x and y within the limits. That's the only reason the list
of factors is sorted when a new one is introduced.
Example:
27**100 = (3*3*3)**(2*2*5*5)
= (3**3)**(2*2*5*5)
= 3**(2*2*3*5*5)
= 9**(2*3*5*5)
= 81**(3*5*5)
= 81**75
On the other hand, the algorithm first assumes that all possible combinations of
a**b are unique, and then subtracts 1 each time x and y are found for a and b.
Implementing the equality operator for a**b = x**y is also an alternative algorithm.
Using it would require a loop for a in 2..99, b in 2..100, x in a+1..100 and y in 2..100.
Is this correct? Or are there other constraints?
Anyway, for big numbers, having the equality operator a**b = x**y with the factoring
method is a good idea.
Unfortunately, my Project Euler programs are prepared to be inserted into the new Alice
project, which is a (big) work in progress and cannot be compiled easily (it requires
Alire, Project Euler for Alice and my sources, which depend on the Euler Tools).
If anyone is interested, for performance comparison or whatever reason, I can
provide a stand alone version.
BR,
-- Francesc Rocher