comp.lang.ada
 help / color / mirror / Atom feed
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!  

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