```
From: Paul Rubin <no.email@nospam.invalid>
Subject: Re: project euler 29
Date: Sun, 17 Sep 2023 15:54:12 -0700 [thread overview]
Message-ID: <874jjsquln.fsf@nightsong.com> (raw)
In-Reply-To: 715fe49a-47bc-46be-ae26-9ed89b38bcb5n@googlegroups.com
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!
```

next prev parent reply other threads:[~2023-09-17 22:54 UTC|newest]Thread overview:23+ messages / expand[flat|nested] mbox.gz Atom feed top 2023-09-15 9:03 project euler 29 CSYH (QAQ) 2023-09-15 9:50 ` Jeffrey R.Carter 2023-09-15 18:04 ` Keith Thompson 2023-09-15 15:42 ` Ben Bacarisse 2023-09-16 10:07 ` Francesc Rocher 2023-09-16 20:59 ` Ben Bacarisse 2023-09-16 21:56 ` Ben Bacarisse 2023-09-17 18:56 ` Francesc Rocher2023-09-17 22:54 ` Paul Rubin [this message]2023-09-17 23:08 ` Ben Bacarisse 2023-09-18 0:09 ` Paul Rubin 2023-09-18 0:16 ` Ben Bacarisse 2023-09-18 5:16 ` Paul Rubin 2023-09-18 11:31 ` Ben Bacarisse 2023-09-18 13:04 ` Francesc Rocher 2023-09-18 14:20 ` Ben Bacarisse 2023-09-18 16:55 ` Francesc Rocher 2023-09-18 19:22 ` Ben Bacarisse 2023-09-18 19:38 ` Paul Rubin 2023-09-18 19:52 ` comp.lang.ada 2023-09-18 19:56 ` comp.lang.ada 2023-09-18 20:01 ` Ben Bacarisse 2023-09-15 16:34 ` Jeffrey R.Carter

replies disabled

This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox