project euler 29

[CSYH (QAQ)]

Hello, everyone.
Now this time, I am facing trouble for problem #29.
As I know integer type is for 32 bits. but for this problem as me to find out the 2 ** 100 and even 100 ** 100.
I used python to get the answer correctly in 5 minutes.

context = []
for a in range(2,101):
for b in range(2,101):
context.append(a**b)
len(list(set(context)))

I know the algorithm is easy, but I am pretty interesting how to calculate a large like it. And thanks for the help from problem 26, your discussions come my every working hour.

for this problem I want to know how to know is there an easy way to store a large number like 100 ** 100, and how do U make a similar function like "set(context)" to delete the duplicated value in a vector.
Thanks
From CSYH(QAQ)

[Jeffrey R.Carter]

On 2023-09-15 11:03, CSYH (QAQ) wrote:
>
> for this problem I want to know how to know is there an easy way to store a large number like 100 ** 100, and how do U make a similar function like "set(context)" to delete the duplicated value in a vector.

You will need an unbounded-integer pkg. If you want to write portable code in a
standard language, then you can write Ada 12 using a library such as
PragmARC.Unbounded_Numbers.Integers
(https://github.com/jrcarter/PragmARC/blob/Ada-12/pragmarc-unbounded_numbers-integers.ads).
This will compile with both GNAT and ObjectAda.

If you want to write non-portable code in a non-standard, Ada-like language,
then you can use the GNAT language, which is mostly Ada 12 with some Ada 23
features, one of which is the Ada-23 standard package
Ada.Numerics.Big_Numbers.Big_Integers
(http://www.ada-auth.org/standards/22aarm/html/AA-A-5-6.html). This can only be
compiled with GNAT. Note that, unlike PragmARC.Unbounded_Numbers.Integers,
GNAT's implementation of Ada.Numerics.Big_Numbers.Big_Integers is not truly
unbounded. I don't know if it will hold 101 ** 101 without modification.

You can store the results directly in a set from the standard library to avoid
duplicate values. If I understand your Python (probably not), you would want to
output the result of Length for the resulting set.

--
Jeff Carter
"I didn't squawk about the steak, dear. I
merely said I didn't see that old horse
that used to be tethered outside here."
Never Give a Sucker an Even Break
103

[Ben Bacarisse]

"CSYH (QAQ)" <sche...@asu.edu> writes:

> Now this time, I am facing trouble for problem #29. As I know integer
> type is for 32 bits. but for this problem as me to find out the 2 **
> 100 and even 100 ** 100. I used python to get the answer correctly in
> 5 minutes.
>
> context = []
> for a in range(2,101):
> for b in range(2,101):
> context.append(a**b)
> len(list(set(context)))
>
> I know the algorithm is easy, but I am pretty interesting how to
> calculate a large like it.

Most of the Project Euler problems have solutions that are not always
the obvious one (though sometimes the obvious one is the best). You
can, of course, just use a big number type (or write your own!) but this
problem can be solved without having to use any large numbers at all.

--
Ben.

[Jeffrey R.Carter]

On 2023-09-15 11:03, CSYH (QAQ) wrote:

> As I know integer type is for 32 bits. but for this problem as me to find out the 2 ** 100 and even 100 ** 100.

I missed this the first time.

No, you don't know that Integer is 32 bits. ARM 3.5.4 (21)
[http://www.ada-auth.org/standards/aarm12_w_tc1/html/AA-3-5-4.html] requires

"In an implementation, the range of Integer shall include the range –2**15+1 ..
+2**15–1."

There are compilers for which Integer is less than 32 bits, so assuming
otherwise is not portable. I know a lot of people don't care about portability,
but I've also seen projects that spent large sums porting code that they thought
didn't have to be portable. The cost of writing portable code is usually much
smaller than the cost of porting non-portable code.

Of course, you can always declare your own integer type with whatever range is
appropriate for your problem, though the compiler doesn't always have to accept
it. I don't know any compiler that doesn't accept 32-bit integer declarations,
nor any targeting 64-bit platforms that doesn't accept 64-bit integers. But
you're unlikely to find a compiler that will accept

range 2 .. 101 ** 101

In King (https://github.com/jrcarter/King) the compiler must accept all integer
type declarations.

[Keith Thompson]

"Jeffrey R.Carter" <spam.jrc...@spam.acm.org.not> writes:
[...]

> can only be compiled with GNAT. Note that, unlike
> PragmARC.Unbounded_Numbers.Integers, GNAT's implementation of
> Ada.Numerics.Big_Numbers.Big_Integers is not truly unbounded. I don't
> know if it will hold 101 ** 101 without modification.

It only has to hold 100 ** 100. The Python code in the parent uses the
expression `range(2,101)`. Python's range() function yields a range
that includes the first bound and excludes the second bound.

--
Keith Thompson (The_Other_Keith) Keith.S.T...@gmail.com
Will write code for food.
void Void(void) { Void(); } /* The recursive call of the void */

[Francesc Rocher]

El dia divendres, 15 de setembre de 2023 a les 17:42:43 UTC+2, Ben Bacarisse va escriure:

> "CSYH (QAQ)" <sche...@asu.edu> writes:
>
> > Now this time, I am facing trouble for problem #29. As I know integer
> > type is for 32 bits. but for this problem as me to find out the 2 **
> > 100 and even 100 ** 100. I used python to get the answer correctly in
> > 5 minutes.

> Most of the Project Euler problems have solutions that are not always
> the obvious one (though sometimes the obvious one is the best). You
> can, of course, just use a big number type (or write your own!) but this
> problem can be solved without having to use any large numbers at all.

Please take a look at this solution: https://github.com/rocher/alice-project_euler-rocher/blob/main/src/0001-0100/p0029_distinct_powers.adb
It's not using any big numbers library.

---
Francesc Rocher

[Ben Bacarisse]

Why?

--
Ben.

[Ben Bacarisse]

That came over as rather curt. I meant what is it about the code that
you are drawing my attention to -- its particular use of Ada, its
structure, the algorithm, the performance...? What (and where) is
Euler_Tools?

--
Ben.

[Francesc Rocher]

El dia dissabte, 16 de setembre de 2023 a les 23:56:11 UTC+2, Ben Bacarisse va escriure:

Well, I was sending the answer to the thread, not to anyone in particular.

I simply thought that, since you mention that this can be solved without having to use
big numbers, people in this group could be interested in seeing how. My solution to this
problem dates back to earlier this year, when I solved the first 30 problems of Project
Euler.

Euler_Tools is a repository of functions that I'm collecting while solving new problems
of Project Euler. In case you want to take a look, https://github.com/rocher/euler_tools

Also, do you have a different approach to solve this 29th problem?

BR
---
Francesc Rocher

[Paul Rubin]

Francesc Rocher <frances...@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!

[Ben Bacarisse]

Francesc Rocher <frances...@gmail.com> writes:

> El dia dissabte, 16 de setembre de 2023 a les 23:56:11 UTC+2, Ben Bacarisse va escriure:
>> Ben Bacarisse <ben.u...@bsb.me.uk> writes:
>>
>> > Francesc Rocher <frances...@gmail.com> writes:
>> >
>> >> El dia divendres, 15 de setembre de 2023 a les 17:42:43 UTC+2, Ben Bacarisse va escriure:
>> >>> "CSYH (QAQ)" <sche...@asu.edu> writes:
>> >>>
>> >>> > Now this time, I am facing trouble for problem #29. As I know integer
>> >>> > type is for 32 bits. but for this problem as me to find out the 2 **
>> >>> > 100 and even 100 ** 100. I used python to get the answer correctly in
>> >>> > 5 minutes.
>> >>
>> >>> Most of the Project Euler problems have solutions that are not always
>> >>> the obvious one (though sometimes the obvious one is the best). You
>> >>> can, of course, just use a big number type (or write your own!) but this
>> >>> problem can be solved without having to use any large numbers at all.
>> >>
>> >> Please take a look at this solution:
>> >> https://github.com/rocher/alice-project_euler-rocher/blob/main/src/0001-0100/p0029_distinct_powers.adb
>> >
>> > Why?
>> That came over as rather curt. I meant what is it about the code that
>> you are drawing my attention to -- its particular use of Ada, its
>> structure, the algorithm, the performance...? What (and where) is
>> Euler_Tools?
>
> Well, I was sending the answer to the thread, not to anyone in
> particular.

I see.

> I simply thought that, since you mention that this can be solved
> without having to use big numbers, people in this group could be
> interested in seeing how. My solution to this problem dates back to
> earlier this year, when I solved the first 30 problems of Project
> Euler.
>
> Euler_Tools is a repository of functions that I'm collecting while
> solving new problems of Project Euler. In case you want to take a
> look, https://github.com/rocher/euler_tools

I was more interested to see if I could compile your code to compare
timings etc, but I don't know how to put the pieces together.

> 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.

--
Ben.

[Paul Rubin]

Ben Bacarisse <ben.u...@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.

[Ben Bacarisse]

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.

[Paul Rubin]

Ben Bacarisse <ben.u...@bsb.me.uk> writes:
>> 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.

> 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.

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.

[Ben Bacarisse]

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.

--
Ben.

[Francesc Rocher]

> > 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

[Ben Bacarisse]

Francesc Rocher <frances...@gmail.com> writes:

>> > 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,

I thought so.

> 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?

Well I just stored the unique pairs found so far. It's not very
efficient, but perfectly fast enough for a,b in [2, 100].

> If anyone is interested, for performance comparison or whatever reason, I can
> provide a stand alone version.

I am curious, but only if it's not too much work.

--
Ben.

[Francesc Rocher]

> I am curious, but only if it's not too much work.

Pre-condition: alr must be installed in your system.
Then, three simple steps:

1. this: git clone g...@github.com/rocher/euler_tools
or: git clone https://github.com/rocher/euler_tools
2. cd euler_tools/examples
3. alr build

Included examples are problems 26 (discussed in a different thread) and 29.

BR
---
Francesc Rocher

[Ben Bacarisse]

Francesc Rocher <frances...@gmail.com> writes:

>> I am curious, but only if it's not too much work.
>
> Pre-condition: alr must be installed in your system.
> Then, three simple steps:
>
> 1. this: git clone g...@github.com/rocher/euler_tools
> or: git clone https://github.com/rocher/euler_tools
> 2. cd euler_tools/examples
> 3. alr build

Thanks. The https clone worked but I got

$ git clone g...@github.com/rocher/euler_tools
fatal: repository 'g...@github.com/rocher/euler_tools' does not exist

from the first.

--
Ben.

[Paul Rubin]

Ben Bacarisse <ben.u...@bsb.me.uk> writes:
> $ git clone g...@github.com/rocher/euler_tools
> fatal: repository 'g...@github.com/rocher/euler_tools' does not exist

Try the https link instead. You may need to enroll an ssh public key on
github for the other way to work. Also maybe try euler_tools.git
instead of just euler_tools. I'm in the middle of something right now
but can check on it tonight if you don't have any luck and if Francesc
doesn't get back to you.

[comp.lang.ada]

> > $ git clone g...@github.com/rocher/euler_tools
> > fatal: repository 'g...@github.com/rocher/euler_tools' does not exist

Typo: it should be g...@github.com:rocher/euler_tools
As Paul said, it requires having a github account configured with an ssh key.

BR
---
Francesc Rocher

[comp.lang.ada]

> Typo: it should be g...@github.com:rocher/euler_tools

Damn it! The server modifies the address!!
It should say, without spaces: git [at] github.com:rocher/euler_tools

BR
---
Francesc Rocher

[Ben Bacarisse]

Paul Rubin <no.e...@nospam.invalid> writes:

> Ben Bacarisse <ben.u...@bsb.me.uk> writes:
>> $ git clone g...@github.com/rocher/euler_tools
>> fatal: repository 'g...@github.com/rocher/euler_tools' does not exist
>
> Try the https link instead.

I said it worked in the text just prior to the part you quoted!

--
Ben.