 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
It's very fun indeed. Amazing to see the compact solutions in assembly (!) or
haskell. Also amazing to see your carefully crafted algorithm full of loops
being beaten to death by far more performant, short and classy pure math
ones...
programmers forgot being mathematicians long ago... :P
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Mueen Nawaz wrote:
> Hi,
>
> Just found this a few days ago. It's apparently been around for years,
> so some of you may know about it:
>
> http://projecteuler.net/index.php?section=about
I'm noticing that I can do some of these problems without a computer.
Number 5 would take a while with pen and paper, but it is simple the LCM
of the numbers from 2 to 20 (16 * 9 * 5 * 7 * 11 * 13 * 17 * 19).
There is a simple formula for the sum of the squares, and for the square
of the sums (which happens to be equal to the sum of the cubes), so
number six is straightforward as well.
The others are time-consuming to the point that a computer makes it easier.
Regards,
John
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
John VanSickle wrote:
> I'm noticing that I can do some of these problems without a computer.
Yes - particularly a bunch of the early ones, although I found at least
one problem in the 20's that I did by hand.
--
In an Astronomy class (toward an Astronomy major, not that gen-ed crap)
the professor did not tell us we would have to remember constants, and
he asked them as questions. They were short questions, and weren't worth
a lot.
One of them was: What is the orbital period of Saturn? (2 pts/100)
I started thinking about Bode's law and the possibility I could
calculate it from an approximate radius I would get from that law... if
I could remember it. But when you expect a 72% to be an A on a test, you
have bigger fish to fry.
Then I got it. It was right, it should work, and no one would have to be
nailed to anything.
I wrote: One Saturn-Year
I didn't get credit for it. A couple years later a sophomore was telling
me about this funny question he had in the same class. He showed it to
me. It read:
What is the orbital period of Saturn? (Do not put one Saturn-Year)
I was so right that it had to be guarded against. Yet those were 2
points I would never have.
(as told by SetupWeasel on Slashdot)
/\ /\ /\ /
/ \/ \ u e e n / \/ a w a z
>>>>>>mue### [at] nawaz org<<<<<<
anl
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Mueen Nawaz wrote:
> Hi,
>
> Just found this a few days ago. It's apparently been around for years,
> so some of you may know about it:
>
> http://projecteuler.net/index.php?section=about
Coming back to it, the first one is easily done without a computer.
The sum of the numbers in any range that are divisible by 3 or 5 is
equal to the sum of the numbers that are divisible by three, plus the
sum of the numbers that are divisible by five, minus the sum of the
numbers that are divisible by 15.
Our given range is from 1 to 999, so:
(3+999)*333/2 + (5+995)*(199)/2 - (15+990)*66/2 = 233168.
I used a calculator for the multiplying and adding here.
Regards,
John
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
I'm mostly stalled at 43%, I've seen several
problems that are easy enough to express
solutions to that are none-the-less difficult
to compute in any reasonable amount of time.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Tim Attwood wrote:
> I'm mostly stalled at 43%, I've seen several
> problems that are easy enough to express
> solutions to that are none-the-less difficult
> to compute in any reasonable amount of time.
Some of the questions state an iterative problem for which there is a
direct solution.
For instance, the second problem looks iterative, but there is a direct
formula for any member of the Fibonacci series, there is a direct
formula for the sum of a power series, and the even-valued members of
the Fibonacci series occur at every third position starting with 0.
When you put that together, the sum is
(1/sqrt(5) * ( (phi^(n+3)-1)/(phi-1) - ((1-phi)^(n+3)-1)/(1-phi-1) )
where n is equal to the index of the highest even-valued member of the
Fibonacci series that is below one million. It turns out that n is 30
in this case, and therefore the sum is 5702886.
Regards,
John
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
John VanSickle <evi### [at] hotmailcom> wrote:
> For instance, the second problem looks iterative, but there is a direct
> formula for any member of the Fibonacci series
> (1/sqrt(5) * ( (phi^(n+3)-1)/(phi-1) - ((1-phi)^(n+3)-1)/(1-phi-1) )
hmm, did you find out the formula for yourself or looked it up somewhere? Most
of the fun in solving these puzzles is coming up with solutions by yourself...
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
I've heard the name meantioned many times. (It comes up *a lot* on the
various Haskell mailing lists, Haskell IRC channel, Haskell wiki, etc.)
I have no idea what it actually is though. (Apparently some kind of set
of maths-related challenges.) This is the first time I've seen an actual
URL...
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> Some of the questions state an iterative problem for which there is a
> direct solution.
>
> For instance, the second problem looks iterative, but there is a direct
> formula for any member of the Fibonacci series, there is a direct formula
> for the sum of a power series, and the even-valued members of the
> Fibonacci series occur at every third position starting with 0. When you
> put that together, the sum is
>
> (1/sqrt(5) * ( (phi^(n+3)-1)/(phi-1) - ((1-phi)^(n+3)-1)/(1-phi-1) )
>
> where n is equal to the index of the highest even-valued member of the
> Fibonacci series that is below one million. It turns out that n is 30 in
> this case, and therefore the sum is 5702886.
Well, this is one of the first few, I got it to calculate in about 12s with
a simple summation, so I didn't bother to find a formula, though I'm
not really suprised that such a formula exists.
Many of the solutions need to exceed double precision, which is
leading to things like re-implementing power functions, and square roots.
Like problem 78, I've discovered Watson's congruence on partition
function P, and narrowed the number of candidate answers to 147,
but the generating function
P(n,k) = P(n-1,k-1)+P(n-k,k)
is running out of memory on my machine, so the answer probably
lies in implementing accurately Hardy and Ramanujan's asymptotic
solution.
P(n) ~ (1/(4*n*(sqrt 3))) * (e^(pi*(sqrt (2*n/3))))
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Tim Attwood escribió:
>> (1/sqrt(5) * ( (phi^(n+3)-1)/(phi-1) - ((1-phi)^(n+3)-1)/(1-phi-1) )
> P(n,k) = P(n-1,k-1)+P(n-k,k)
> P(n) ~ (1/(4*n*(sqrt 3))) * (e^(pi*(sqrt (2*n/3))))
O_o
Maybe I should stay away from the complex problems then.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
nemesis wrote:
> John VanSickle <evi### [at] hotmailcom> wrote:
>> For instance, the second problem looks iterative, but there is a direct
>> formula for any member of the Fibonacci series
>> (1/sqrt(5) * ( (phi^(n+3)-1)/(phi-1) - ((1-phi)^(n+3)-1)/(1-phi-1) )
>
> hmm, did you find out the formula for yourself or looked it up somewhere? Most
> of the fun in solving these puzzles is coming up with solutions by yourself...
Not too hard if you've studied difference equations (they also go by
another name - forgot what it was).
The Fibonacci sequence is a simple difference equation: Linear,
homogeneous and constant coefficients. If this sounds like what you may
have learned in differential equations, it's because they can be solved
in almost the same way. Basically, assume a solution of the form a^n,
plug it into the Fibonacci equation and calculate the possible values of
a. You'll get two, and any linear combination of those two will satisfy
the equation. Plug in the initial conditions, and you've solved it.
To get the partial sum of a Fibonacci sequence, note that it is just
the difference of two geometric sums. A little alteration in indices
gives you the sum of just the even terms.
Having said all this, I just wrote a program to calculate it. One of
the people on the forums had a neat solution: For large n, the ratio of
two successive Fibonacci numbers is phi, the Golden Ratio. So his code
just started with 2, multiplied by phi^3 (as we only want the even
numbers), and rounded to the nearest integer after each iteration.
--
Best file compressor around: DEL *.* (100% compression)
/\ /\ /\ /
/ \/ \ u e e n / \/ a w a z
>>>>>>mue### [at] nawazorg<<<<<<
anl
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v7 wrote:
> I've heard the name meantioned many times. (It comes up *a lot* on the
> various Haskell mailing lists, Haskell IRC channel, Haskell wiki, etc.)
> I have no idea what it actually is though. (Apparently some kind of set
> of maths-related challenges.) This is the first time I've seen an actual
> URL...
Well, now you know!
A lot of people solve them using Haskell, obviously. You should try the
problems. They'll tickle both your Haskell and your mathematical side.
--
Best file compressor around: DEL *.* (100% compression)
/\ /\ /\ /
/ \/ \ u e e n / \/ a w a z
>>>>>>mue### [at] nawazorg<<<<<<
anl
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> A lot of people solve them using Haskell, obviously. You should try the
> problems. They'll tickle both your Haskell and your mathematical side.
According to the statistics page on Project Euler there's about
three times as many people using C/C++ as Haskell, and about
twice as many using Python as Haskell.
The average user rating for Haskell users is a bit higher than
for Python and C users though =)
And you have to like how it has x% genius at the top of the
page, it's almost as good as when Bookworm squeals
"fantastic"
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Tim Attwood wrote:
> According to the statistics page on Project Euler there's about
> three times as many people using C/C++ as Haskell, and about
> twice as many using Python as Haskell.
In other words, C++ is many times more popular than Haskell. This is not
news. ;-)
> The average user rating for Haskell users is a bit higher than
> for Python and C users though =)
In other words, most of the people rating them are other Haskell users. :-D
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
nemesis wrote:
> John VanSickle <evi### [at] hotmailcom> wrote:
>> For instance, the second problem looks iterative, but there is a direct
>> formula for any member of the Fibonacci series
>> (1/sqrt(5) * ( (phi^(n+3)-1)/(phi-1) - ((1-phi)^(n+3)-1)/(1-phi-1) )
>
> hmm, did you find out the formula for yourself or looked it up somewhere? Most
> of the fun in solving these puzzles is coming up with solutions by yourself...
I looked up the formula for a member of the Fibonacci series (I keep
forgetting the 1/sqrt(5) constant), but once I had that I figured out
the rest on my own.
Regards,
John
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible wrote:
>> The average user rating for Haskell users is a bit higher than
>> for Python and C users though =)
>
> In other words, most of the people rating them are other Haskell users. :-D
No - you misunderstood. A person's user rating is related to how many
problems he/she has solved. So the average Haskell user has solved more
than the average C user, and roughly about the same as the average
Python user...
--
Isn't it counterproductive to have incandescent bulbs in a fridge?
/\ /\ /\ /
/ \/ \ u e e n / \/ a w a z
>>>>>>mue### [at] nawazorg<<<<<<
anl
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Mueen Nawaz wrote:
> Invisible wrote:
>>> The average user rating for Haskell users is a bit higher than
>>> for Python and C users though =)
>> In other words, most of the people rating them are other Haskell users. :-D
>
> No - you misunderstood. A person's user rating is related to how many
> problems he/she has solved. So the average Haskell user has solved more
> than the average C user, and roughly about the same as the average
> Python user...
Aaahhhh... So Haskell programmers are either bigger nerds or have more
free time than C programmers? ;-)
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> Aaahhhh... So Haskell programmers are either bigger nerds or have more
> free time than C programmers? ;-)
C(++) programmers probably have real software to write ;-)
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
"Tim Attwood" <tim### [at] comcastnet> wrote:
> According to the statistics page on Project Euler there's about
> three times as many people using C/C++ as Haskell, and about
> twice as many using Python as Haskell.
OTOH, most C++ solutions I've seen in the forum are the trivial, straightforward
loopy and slow performant solutions, using pretty much the same obvious
algorithm. Many Haskell solutions came up with amazingly concise and creative
algorithms.
but I was really impressed with the assembly and math solutions...
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
nemesis wrote:
> "Tim Attwood" <tim### [at] comcastnet> wrote:
>> According to the statistics page on Project Euler there's about
>> three times as many people using C/C++ as Haskell, and about
>> twice as many using Python as Haskell.
>
> OTOH, most C++ solutions I've seen in the forum are the trivial, straightforward
> loopy and slow performant solutions, using pretty much the same obvious
> algorithm. Many Haskell solutions came up with amazingly concise and creative
> algorithms.
>
> but I was really impressed with the assembly and math solutions...
Math solutions FTW!
(E.g., problem 1, I wrote something that loops over the numbers 1 to 100
finding those that fit the divisibility requirements and summing them.
Somebody else managed to produce a closed-form *formula* for the answer.
Beat that!)
The few Haskell solutions I've seen look unecessarily wordy - like they
were written by somebody just learning Haskell. But then, the Haskell
Wiki has a section devoted to Project Euler, and most solutions there
look rather childish and unperformant too, so...
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
John VanSickle wrote:
> Tim Attwood wrote:
>> I'm mostly stalled at 43%, I've seen several
>> problems that are easy enough to express
>> solutions to that are none-the-less difficult
>> to compute in any reasonable amount of time.
>
> Some of the questions state an iterative problem for which there is a
> direct solution.
>
> For instance, the second problem looks iterative, but there is a direct
> formula for any member of the Fibonacci series, there is a direct
> formula for the sum of a power series, and the even-valued members of
> the Fibonacci series occur at every third position starting with 0. When
> you put that together, the sum is
>
> (1/sqrt(5) * ( (phi^(n+3)-1)/(phi-1) - ((1-phi)^(n+3)-1)/(1-phi-1) )
It turns out that this formula is wrong. The correct formula is:
1/sqrt(5) *
( (phi^(n+3)-1)/(phi^3-1) - ((1-phi)^(n+3)-1)/((1-phi)^3-1) )
Regards,
John
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
nemesis wrote:
> "Tim Attwood" <tim### [at] comcastnet> wrote:
>> According to the statistics page on Project Euler there's about
>> three times as many people using C/C++ as Haskell, and about
>> twice as many using Python as Haskell.
>
> OTOH, most C++ solutions I've seen in the forum are the trivial, straightforward
> loopy and slow performant solutions, using pretty much the same obvious
> algorithm. Many Haskell solutions came up with amazingly concise and creative
> algorithms.
I admit that for the C++ solutions I've been resorting to brute force,
but for these problems I'm not aware of any solution that avoids the
brute force approach. For instance, in the problem for summing the
prime numbers less than one million, I'm not aware of any theorem which
calculates such a sum for any range without testing each odd number for
primality and then adding the primes.
It could be that the C++ coders either aren't aware of the
computationally less-expensive solutions, or they simply assume that the
relative efficiency of C++ (save counter-arguments for another thread,
please) enables them to not worry about computational efficiency.
Regards,
John
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
John VanSickle <evi### [at] hotmailcom> wrote:
> For instance, in the problem for summing the
> prime numbers less than one million, I'm not aware of any theorem which
> calculates such a sum for any range without testing each odd number for
> primality and then adding the primes.
http://en.wikipedia.org/wiki/Prime-counting_function
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp wrote:
> John VanSickle <evi### [at] hotmailcom> wrote:
>> For instance, in the problem for summing the
>> prime numbers less than one million, I'm not aware of any theorem which
>> calculates such a sum for any range without testing each odd number for
>> primality and then adding the primes.
>
> http://en.wikipedia.org/wiki/Prime-counting_function
I didn't read all of it, but it's not obvious how helpful that would
be...other than getting an idea of the number of primes under a million.
When you get that many then you can stop (assuming the estimate is good
enough).
I'm not aware of any better way to do this than to simply get all the
primes under a million and add them up. The only variation is how one
obtains all the primes. You could use a Sieve method, or do what many
people did: Test each odd number by dividing it by all possible primes
less than sqrt(number). For all the prime problems, I was using a sieve,
but apparently for a lot of problems (all so far?), simply testing by
dividing appears to be faster. I think the sieve wins out once you the
numbers get large enough, though.
--
Diplomacy - the art of letting someone have your way.
/\ /\ /\ /
/ \/ \ u e e n / \/ a w a z
>>>>>>mue### [at] nawazorg<<<<<<
anl
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v7 wrote:
> (E.g., problem 1, I wrote something that loops over the numbers 1 to 100
> finding those that fit the divisibility requirements and summing them.
> Somebody else managed to produce a closed-form *formula* for the answer.
> Beat that!)
Not particularly hard. You have a formula for the sum of all integers
from 1 to 100. And one for the sum of all multiples of 3 till 100. Ditto
for multiples of 5. Now just subtract the sum of all multiples of 15.
> The few Haskell solutions I've seen look unecessarily wordy - like they
> were written by somebody just learning Haskell. But then, the Haskell
> Wiki has a section devoted to Project Euler, and most solutions there
> look rather childish and unperformant too, so...
I do stuff in Python. Even though some manage to solve whole problems
with one line solutions, it is generally frowned upon in the Python
community if it gets challenging to read: They generally perform about
the same as more readable code.
So perhaps those Haskell users were converts from Python...
--
Diplomacy - the art of letting someone have your way.
/\ /\ /\ /
/ \/ \ u e e n / \/ a w a z
>>>>>>mue### [at] nawazorg<<<<<<
anl
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
John VanSickle wrote:
> I admit that for the C++ solutions I've been resorting to brute force,
> but for these problems I'm not aware of any solution that avoids the
> brute force approach. For instance, in the problem for summing the
> prime numbers less than one million, I'm not aware of any theorem which
> calculates such a sum for any range without testing each odd number for
> primality and then adding the primes.
I've done brute force for a bunch, but at times I try to find
shortcuts. Sometimes the resulting program is even slower, but I suspect
it'll scale better.
Also, while a brute force solution in C/C++ may run in under a minute,
it occasionally will not in Python. So I'm forced to think of ways to
speed it up. I frequently find a "better" solution than mine in the
forums, though.
--
Diplomacy - the art of letting someone have your way.
/\ /\ /\ /
/ \/ \ u e e n / \/ a w a z
>>>>>>mue### [at] nawazorg<<<<<<
anl
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Mueen Nawaz <m.n### [at] ieeeorg> wrote:
> Warp wrote:
> > John VanSickle <evi### [at] hotmailcom> wrote:
> >> For instance, in the problem for summing the
> >> prime numbers less than one million, I'm not aware of any theorem which
> >> calculates such a sum for any range without testing each odd number for
> >> primality and then adding the primes.
> >
> > http://en.wikipedia.org/wiki/Prime-counting_function
> I didn't read all of it, but it's not obvious how helpful that would
> be...
I didn't mean for it to be an answer to the problem but as an interesting
thing to read about the subject.
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Mueen Nawaz wrote:
> John VanSickle wrote:
>> I admit that for the C++ solutions I've been resorting to brute force,
>> but for these problems I'm not aware of any solution that avoids the
>> brute force approach. For instance, in the problem for summing the
>> prime numbers less than one million, I'm not aware of any theorem which
>> calculates such a sum for any range without testing each odd number for
>> primality and then adding the primes.
>
> I've done brute force for a bunch, but at times I try to find
> shortcuts. Sometimes the resulting program is even slower, but I suspect
> it'll scale better.
>
> Also, while a brute force solution in C/C++ may run in under a minute,
> it occasionally will not in Python. So I'm forced to think of ways to
> speed it up. I frequently find a "better" solution than mine in the
> forums, though.
It's interesting how many elaborate problems requiring multiple nested
loops and filtering take only about 10 instructions in assembly... (!)
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Currently for each problem, you either get the answer right or you get
it wrong. I think it would be nice if you could check intermediate parts
of the calculation. (E.g., is 103 a prime number? Is 187 an abundant
number? etc.)
On the other hand, I suppose they don't want to give too much data away,
otherwise you could just "solve" the problem by asking the Project Euler
website a sufficient number of questions. ;-)
Currently it seems the "ratings" are simply based on what fraction of
the problems you've solved. I think it would be nice if I get a bigger
score for solving problems that few other people have solved.
I'd kinda like to make my own website like Project Euler. However, I had
a look, and to get hosting that gives you server-side scripting and a
database is 5x the price of what I'm currently paying. :-S I can't
really afford that kind of money...
I suppose the alternative is to set up a Linux box in my house and host
a website from there [again]. But it's rather annoying when you're
playing a clan match and suddenly somebody hits your website and you
can't play properly any more. :-S
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible wrote:
> Currently for each problem, you either get the answer right or you get
> it wrong. I think it would be nice if you could check intermediate parts
> of the calculation. (E.g., is 103 a prime number? Is 187 an abundant
> number? etc.)
Well, for all but one of the problems I've worked on, the definitions
in the problem statements are fairly unambiguous.
Besides, for things like those, you can use Google to get a list of
primes, abundant numbers, etc. But be "careful", sometimes a good Google
search will get you the very answer to the question being asked.
> On the other hand, I suppose they don't want to give too much data away,
> otherwise you could just "solve" the problem by asking the Project Euler
> website a sufficient number of questions. ;-)
True - almost. If you submit too many answers in a short period of
time, the Web site blocks you for a while.
> I'd kinda like to make my own website like Project Euler. However, I had
> a look, and to get hosting that gives you server-side scripting and a
> database is 5x the price of what I'm currently paying. :-S I can't
> really afford that kind of money...
The weakened Dollar may help you there.<G>
What price are you talking about. You definitely can get it for under
$10/mo, and if your needs aren't too stringent, probably $5/mo is not
hard to find.
The tricky part is making the problems interesting enough for people to
come. A number of problems on the Project Euler site *may* lead you into
some interesting number theory topics...
--
I considered atheism but there weren't enough holidays.
/\ /\ /\ /
/ \/ \ u e e n / \/ a w a z
>>>>>>mue### [at] nawazorg<<<<<<
anl
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Mueen Nawaz wrote:
> Invisible wrote:
>> Currently for each problem, you either get the answer right or you get
>> it wrong. I think it would be nice if you could check intermediate parts
>> of the calculation. (E.g., is 103 a prime number? Is 187 an abundant
>> number? etc.)
>
> Well, for all but one of the problems I've worked on, the definitions
> in the problem statements are fairly unambiguous.
Well, for "find the millionth prime number" or something, there's not
much to check. But when the problem is "sum all the primes below 1
million", it might be nice to know, for example, how many primes there
are. (Or rather, be able to ask "are there 722 primes?" and get a yes/no
answer.)
[BTW, I'm damn-well *sure* there used to be a site that tells you
whether a number is prime, and what the Nth prime number is, and how
many primes there are below N. Google can no longer find it though...]
>> On the other hand, I suppose they don't want to give too much data away,
>> otherwise you could just "solve" the problem by asking the Project Euler
>> website a sufficient number of questions. ;-)
>
> True - almost. If you submit too many answers in a short period of
> time, the Web site blocks you for a while.
I know what *would* be nice - if the site would keep a list of the
answers you've already tried which turned out to be wrong! (So many
off-by-one bugs...)
>> I'd kinda like to make my own website like Project Euler. However, I had
>> a look, and to get hosting that gives you server-side scripting and a
>> database is 5x the price of what I'm currently paying. :-S I can't
>> really afford that kind of money...
>
> The weakened Dollar may help you there.<G>
>
> What price are you talking about. You definitely can get it for under
> $10/mo, and if your needs aren't too stringent, probably $5/mo is not
> hard to find.
My current host wants £15/month - which works out as £31/month. For my
current package (static HTML only) it's only £5/month.
> The tricky part is making the problems interesting enough for people to
> come. A number of problems on the Project Euler site *may* lead you into
> some interesting number theory topics...
I don't know - almost all of the problems seem to be a case of "write
this brute-force search algorithm so it doesn't take all day". Very few
problems appear to possess an elegant mathematical solution. For example:
- Find the 10,001st prime number. Well, sure, there's only one possible
way to do that. You can't know whether a given prime is the 10,001st or
not without finding all 10,000 primes below it! Brute-force search,
plain and simple.
- Take this file full of data, generate some numbers from it, find the
highest one. Well, again, no mathematics involved. It's a trivial search
problems. Just gotta write a program fast enough.
- Find a number having some highly obscure property. Well you can
probably use elegant mathematics to elimatine a few classes of
possibilities, but it still comes down to a simple search in the end.
A few of the problems admit an elegant mathematical solution. The thing
with Pythagorean triples, or finding the sum of numbers or the number of
combinations or something. Slightly more involve some actual maths
somewhere. But most seem to just involve blindly searching as fast as
possible. It's not very interesting, but I like seeing my score
increase. :^)
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> A few of the problems admit an elegant mathematical solution. The thing
> with Pythagorean triples, or finding the sum of numbers or the number of
> combinations or something. Slightly more involve some actual maths
> somewhere. But most seem to just involve blindly searching as fast as
> possible. It's not very interesting, but I like seeing my score increase.
> :^)
Oh I think it is pretty interesting. In real life you often need to get
results as quickly as possible. Part of the skill is being able to decide
quickly whether it's better to spend 1 minute coding and waiting 10 minutes,
or spending 10 minutes doing some math and then only having to wait 1 second
for the answer.
And then another skill is being able to decide *what* to use to get the
answer (C++, Excel, Haskell, calculator, pencil etc).
There should be a timer that starts the moment you open the problem for the
first time, and that is stopped when you submit the correct answer. Not
sure how you would stop people cheating though.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
scott wrote:
> There should be a timer that starts the moment you open the problem for
> the first time, and that is stopped when you submit the correct answer.
> Not sure how you would stop people cheating though.
Or a counter for the number of incorrect results you submitted. ;-)
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> [BTW, I'm damn-well *sure* there used to be a site that tells you whether
> a number is prime, and what the Nth prime number is, and how many primes
> there are below N. Google can no longer find it though...]
The Prime Pages probably has something like that.
http://primes.utm.edu/index.html
You can get the first 15 million primes in files.
There's also an open challenge from the EFF to
calculate a billion digit prime number, with a prize
of $250,000.
http://w2.eff.org/awards/coop.php
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible wrote:
>> Well, for all but one of the problems I've worked on, the definitions
>> in the problem statements are fairly unambiguous.
>
> Well, for "find the millionth prime number" or something, there's not
> much to check. But when the problem is "sum all the primes below 1
> million", it might be nice to know, for example, how many primes there
> are. (Or rather, be able to ask "are there 722 primes?" and get a yes/no
> answer.)
That'd make it easier to solve, though.
> My current host wants £15/month - which works out as £31/month. For my
That's an interesting currency conversion you have there...
Unless you have a good reason to stick with them, simply dump them and
ask around for recommendations of cheaper and better hosts. I'm
currently paying a bit less than you are (albeit that's because I paid
in advance), and I get probably much more than what you want.
(I use Dreamhost - often maligned, but more than satisfies my needs and
wants and I can't find similarly priced alternatives that do).
> I don't know - almost all of the problems seem to be a case of "write
> this brute-force search algorithm so it doesn't take all day". Very few
> problems appear to possess an elegant mathematical solution. For example:
>
> - Find the 10,001st prime number. Well, sure, there's only one possible
> way to do that. You can't know whether a given prime is the 10,001st or
> not without finding all 10,000 primes below it! Brute-force search,
> plain and simple.
>
> - Take this file full of data, generate some numbers from it, find the
> highest one. Well, again, no mathematics involved. It's a trivial search
> problems. Just gotta write a program fast enough.
I'm assuming that these two are just prepping you up for more difficult
(but related) problems later on. Certainly if someone has trouble
generating 10001 primes, he won't get too far.
> - Find a number having some highly obscure property. Well you can
> probably use elegant mathematics to elimatine a few classes of
> possibilities, but it still comes down to a simple search in the end.
That's sort of the point. Take Problem 43:
"The number, 1406357289, is a 0 to 9 pandigital number because it is
made up of each of the digits 0 to 9 in some order, but it also has a
rather interesting sub-string divisibility property.
Let d1 be the 1st digit, d2 be the 2nd digit, and so on. In this way, we
note the following:
* d2d3d4=406 is divisible by 2
* d3d4d5=063 is divisible by 3
* d4d5d6=635 is divisible by 5
* d5d6d7=357 is divisible by 7
* d6d7d8=572 is divisible by 11
* d7d8d9=728 is divisible by 13
* d8d9d10=289 is divisible by 17
Find the sum of all 0 to 9 pandigital numbers with this property."
A REAL brute force solution is simple to write, but do you really want
to check over a billion numbers? (I'm guessing anyone who got this far
would not even realize the search space is that big - they'll
automatically optimize).
Now with some thought you can bring that number down to something very
manageable. You could then code it and be happy, or think more and try
to reduce the search space even more. The more you do this, the more
"painful" it is to code. So then you take on the challenge of writing
the code in a "nicer" way so that it doesn't look like an ugly hack.
I just went halfway and coded it. I felt bad about that after looking
at the solutions. There were some really simple ways to reduce the
search space _much_ further - on the other hand I did a simplification
few thought of - but the ones I missed negated the need for mine.
Now some people simply solved this on paper (some of those did use a
calculator to help, though).
The point of the problems is not to solve it _entirely_ mathematically
(although if you can, that's wonderful). It's to use math to make the
problem more tractable (even if it _can_ be done under a minute via
brute force). And for me, it's also a challenge to write the code
somewhat nicely.
The last problem I worked on (in the 40's) was somewhat brute force and
took over 40 minutes. Haven't had time to think about it much since
then, but I look forward to bringing that down. I have a few ideas on
making the algorithm faster which may suffice, but before I had obtained
the solution, I noticed some mathematical properties which I suspected
held true in general (but couldn't prove it). After computing the
solution, I find the answer does satisfy my hypothesis, and now I don't
want to simply speed up the algorithm, but rather explore my hypothesis
and "speed" it up that way.
Which is why I enjoy a number of the problems...
> A few of the problems admit an elegant mathematical solution. The thing
> with Pythagorean triples, or finding the sum of numbers or the number of
> combinations or something. Slightly more involve some actual maths
> somewhere. But most seem to just involve blindly searching as fast as
> possible. It's not very interesting, but I like seeing my score
> increase. :^)
I assume that it'll demand more math thought as you get higher. Many
(most?) have not impressed me as much in that regard thus far. But heck,
it was fun anyway!
--
As a child my family's menu consisted of two choices: "Take it, or leave
it."
/\ /\ /\ /
/ \/ \ u e e n / \/ a w a z
>>>>>>mue### [at] nawazorg<<<<<<
anl
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Mueen Nawaz wrote:
> Invisible wrote:
>> Well, for "find the millionth prime number" or something, there's not
>> much to check. But when the problem is "sum all the primes below 1
>> million", it might be nice to know, for example, how many primes there
>> are. (Or rather, be able to ask "are there 722 primes?" and get a yes/no
>> answer.)
>
> That'd make it easier to solve, though.
Well yes - but do you have any idea how frustrating it is to spend hours
trying to make your program work when you don't even know what part is
broken? Knowing which part is broken doesn't tell you how to fix it, it
just tells you which part needs fixing...
(Also, a number of questions give insufficient detail to figure out what
the correct answer is.)
>> My current host wants £15/month - which works out as £31/month. For my
>
> That's an interesting currency conversion you have there...
OK, £15/month = $31/month. Sheesh, the symbols are right next to each
other...
> Unless you have a good reason to stick with them, simply dump them and
> ask around for recommendations of cheaper and better hosts.
I've asked many times. Nobody ever recommends anything.
My current host (1&1) charges quite a low price for serving just static
HTML, which is mainly what I want. However, if you decide you want CGI,
they suddenly want to charge a lot more.
(I hate Perl, and PHP would probably be the same. I'd probably want to
do my CGI scripting in Haskell - and by the looks of it, the only way to
do *that* is to go for a virtual server package rather than a simple web
hosting package. That's A LOT of extra complexity, and it's expensive.)
[BTW, I find it interesting that all hosting packages offer MySQL or SQL
Server, but none offer PostgreSQL...]
> I'm
> currently paying a bit less than you are (albeit that's because I paid
> in advance), and I get probably much more than what you want.
>
> (I use Dreamhost - often maligned, but more than satisfies my needs and
> wants and I can't find similarly priced alternatives that do).
Well, I'll have a look...
>> I don't know - almost all of the problems seem to be a case of "write
>> this brute-force search algorithm so it doesn't take all day". Very few
>> problems appear to possess an elegant mathematical solution.
>
> I'm assuming that these two are just prepping you up for more difficult
> (but related) problems later on. Certainly if someone has trouble
> generating 10001 primes, he won't get too far.
True, I guess.
>> - Find a number having some highly obscure property. Well you can
>> probably use elegant mathematics to elimatine a few classes of
>> possibilities, but it still comes down to a simple search in the end.
>
> That's sort of the point. Take Problem 43:
Actually I didn't - mainly because I don't know what "pandigital" means.
> A REAL brute force solution is simple to write, but do you really want
> to check over a billion numbers? (I'm guessing anyone who got this far
> would not even realize the search space is that big - they'll
> automatically optimize).
>
> Now with some thought you can bring that number down to something very
> manageable. You could then code it and be happy, or think more and try
> to reduce the search space even more. The more you do this, the more
> "painful" it is to code. So then you take on the challenge of writing
> the code in a "nicer" way so that it doesn't look like an ugly hack.
I did see one problem that was solved by a human with pen and paper in
under 30 seconds. Just move some algebra around and it tells you the
answer. But most seem to require a machine.
(Many involve prime numbers - and as we all know, it is impossible to
know anything about prime numbers. You just gotta compute them all the
long way...)
> The point of the problems is not to solve it _entirely_ mathematically
> (although if you can, that's wonderful). It's to use math to make the
> problem more tractable (even if it _can_ be done under a minute via
> brute force). And for me, it's also a challenge to write the code
> somewhat nicely.
Personally, I find that as you come up with better algorithms it gets
*easier* to code, not harder. ;-) Maybe that's just because I use
Haskell... The Mathematica solutions are similarly easy.
>> A few of the problems admit an elegant mathematical solution. The thing
>> with Pythagorean triples, or finding the sum of numbers or the number of
>> combinations or something. Slightly more involve some actual maths
>> somewhere. But most seem to just involve blindly searching as fast as
>> possible. It's not very interesting, but I like seeing my score
>> increase. :^)
>
> I assume that it'll demand more math thought as you get higher. Many
> (most?) have not impressed me as much in that regard thus far. But heck,
> it was fun anyway!
Well, it's a challenge I guess. I doubt I'll ever reach 100% though...
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> Well yes - but do you have any idea how frustrating it is to spend hours
> trying to make your program work when you don't even know what part is
> broken? Knowing which part is broken doesn't tell you how to fix it, it
> just tells you which part needs fixing...
> I've asked many times. Nobody ever recommends anything.
A friend of mine uses http://www.ipowerweb.com/ and recommended me to use if
I ever needed a website. A quick look shows that they offer 300 GB with
Perl/MySQL/PHP/CGI-BIN/etc for $4.95 / month if you get the 12 month
package.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
scott wrote:
>> I've asked many times. Nobody ever recommends anything.
>
> A friend of mine uses http://www.ipowerweb.com/ and recommended me to
> use if I ever needed a website. A quick look shows that they offer 300
> GB with Perl/MySQL/PHP/CGI-BIN/etc for $4.95 / month if you get the 12
> month package.
TY. I'll check it out later...
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible escribió:
> (I hate Perl, and PHP would probably be the same. I'd probably want to
> do my CGI scripting in Haskell - and by the looks of it, the only way to
> do *that* is to go for a virtual server package rather than a simple web
> hosting package. That's A LOT of extra complexity, and it's expensive.)
Find a Haskell interpreter written in PHP or Perl.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Nicolas Alvarez wrote:
> Find a Haskell interpreter written in PHP or Perl.
Good luck with that idea. ;-)
(Small hint: Aside from research projects and experimental
implementations, there are only 2 working Haskell compilers in the
world... and only 1 of those isn't written in Haskell.)
You would probably write a program that fakes it convincingly though...
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible wrote:
>>> Well, for "find the millionth prime number" or something, there's not
>>> much to check. But when the problem is "sum all the primes below 1
>>> million", it might be nice to know, for example, how many primes there
>>> are. (Or rather, be able to ask "are there 722 primes?" and get a yes/no
>>> answer.)
>>
>> That'd make it easier to solve, though.
>
> Well yes - but do you have any idea how frustrating it is to spend hours
> trying to make your program work when you don't even know what part is
> broken? Knowing which part is broken doesn't tell you how to fix it, it
> just tells you which part needs fixing...
I don't see it being an issue for this problem.
Write a program that sums all primes below n. You can test it for n=100
by hand. Unless you're using a weird algorithm, it should work for any
n, unless you have overflow, which I suspect you don't worry about in
Haskell, anyway.
There's a reason most problems come with at least one example: To test
your code. It helps, but do you realize how difficult it is to implement
what you're asking? How is the site owner supposed to guess what
questions are useful for you?
> (Also, a number of questions give insufficient detail to figure out what
> the correct answer is.)
Can you give me an example? I haven't come across any thus far.
> I've asked many times. Nobody ever recommends anything.
Well, Scott's friend recommended one. Looks fine, but I'll point out
that the $4.99/mo is only for the first year. I already said I use
Dreamhost. You have to pay a year in advance, but they give you over 90
days to cancel.
My recommendation about features (I actually have many, but this is
often overlooked): Make sure they provide you SSH/Telnet access.
Midnight Commander installed would be a bonus (must for me).
> (I hate Perl, and PHP would probably be the same. I'd probably want to
> do my CGI scripting in Haskell - and by the looks of it, the only way to
> do *that* is to go for a virtual server package rather than a simple web
> hosting package. That's A LOT of extra complexity, and it's expensive.)
You may want to try Django (Python) or Ruby on Rails. In which case
make sure the hosting company allows it (as opposed to "supporting" it).
I don't want to code PHP either. However, having a webserver allows me
to install PHP web software (gallery, blog, wiki, CMS, and much more).
Which I use very frequently.
> [BTW, I find it interesting that all hosting packages offer MySQL or SQL
> Server, but none offer PostgreSQL...]
Some do. A number of web software you may want to install may still
require MySQL, though.
>> That's sort of the point. Take Problem 43:
>
> Actually I didn't - mainly because I don't know what "pandigital" means.
Google it.
They actually explain it (albeit poorly) in the first problem they use it.
> Personally, I find that as you come up with better algorithms it gets
> *easier* to code, not harder. ;-) Maybe that's just because I use
> Haskell... The Mathematica solutions are similarly easy.
For me, that happens after more thought. Initially any advanced idea I
come up with after a first attempt is ugly. Then I abstract a little and
it gets nicer.
--
As a child my family's menu consisted of two choices: "Take it, or leave
it."
/\ /\ /\ /
/ \/ \ u e e n / \/ a w a z
>>>>>>mue### [at] nawazorg<<<<<<
anl
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Mueen Nawaz wrote:
>> (Also, a number of questions give insufficient detail to figure out what
>> the correct answer is.)
>
> Can you give me an example? I haven't come across any thus far.
6 is not an amicable number because it's only amciable with itself. This
was not made clear anywhere, and it took an absurd amount of time to
figure out why my working program was producing the "wrong" answer.
There were several others like that... I don't remember which now.
> My recommendation about features (I actually have many, but this is
> often overlooked): Make sure they provide you SSH/Telnet access.
> Midnight Commander installed would be a bonus (must for me).
I wouldn't use Telnet if you paid me. SSH though... (And presumably SSH
means you can use SFTP too? I wonder if there are tools to synchronise
folders over SFTP...)
>> Personally, I find that as you come up with better algorithms it gets
>> *easier* to code, not harder. ;-) Maybe that's just because I use
>> Haskell... The Mathematica solutions are similarly easy.
>
> For me, that happens after more thought. Initially any advanced idea I
> come up with after a first attempt is ugly. Then I abstract a little and
> it gets nicer.
...or that, yes. ;-)
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> 6 is not an amicable number because it's only amciable with itself. This
> was not made clear anywhere,
Ermm, it says in the question that:
If d(a) = b and d(b) = a, where a (doesn't equal) b, then a and b are an
amicable pair and each of a and b are called amicable numbers.
Seems pretty clear that 6 is not an amicable number to me...
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
scott wrote:
>> 6 is not an amicable number because it's only amciable with itself.
>> This was not made clear anywhere,
>
> Ermm, it says in the question that:
>
> If d(a) = b and d(b) = a, where a (doesn't equal) b, then a and b are an
> amicable pair and each of a and b are called amicable numbers.
>
> Seems pretty clear that 6 is not an amicable number to me...
Interesting. I don't remember that being there... (And the comments in
the forum indicated that I wasn't the only person to get this wrong.)
Maybe they changed it or something...
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible wrote:
> I wouldn't use Telnet if you paid me. SSH though... (And presumably SSH
> means you can use SFTP too? I wonder if there are tools to synchronise
> folders over SFTP...)
Yes, generally SSH implies SFTP.
And I'd be surprised if you can't synchronize using SFTP. I don't
really do that, though - I just use Subversion (which they provide...).
You don't HAVE to use SSH - but I think if you can use UNIX, you should
get it - much easier editing files that way.
--
Do Not Attempt to Traverse a Chasm in Two Leaps...
/\ /\ /\ /
/ \/ \ u e e n / \/ a w a z
>>>>>>mue### [at] nawazorg<<<<<<
anl
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Mueen Nawaz wrote:
> Invisible wrote:
>> I wouldn't use Telnet if you paid me. SSH though... (And presumably SSH
>> means you can use SFTP too? I wonder if there are tools to synchronise
>> folders over SFTP...)
>
> Yes, generally SSH implies SFTP.
>
> And I'd be surprised if you can't synchronize using SFTP. I don't
> really do that, though - I just use Subversion (which they provide...).
>
> You don't HAVE to use SSH - but I think if you can use UNIX, you should
> get it - much easier editing files that way.
Most of my HTML is machine-generated. ;-)
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Mueen Nawaz <m.n### [at] ieeeorg> wrote:
> And I'd be surprised if you can't synchronize using SFTP.
I think the most common tool for synchronization (if we don't go to
versioning systems) in unix is rsync. It can copy files using ssh, so it
should be as secure.
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible wrote:
...
> I wouldn't use Telnet if you paid me. SSH though... (And presumably SSH
> means you can use SFTP too? I wonder if there are tools to synchronise
> folders over SFTP...)
...
I think that should be possible with sshfs and rsync:
http://en.wikipedia.org/wiki/SSHFS
http://en.wikipedia.org/wiki/Rsync
--
Tor Olav
http://subcube.com
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Tor Olav Kristensen <tor### [at] TOBEREMOVEDgmailcom> wrote:
> Invisible wrote:
> ...
> > I wouldn't use Telnet if you paid me. SSH though... (And presumably SSH
> > means you can use SFTP too? I wonder if there are tools to synchronise
> > folders over SFTP...)
> ...
>
> I think that should be possible with sshfs and rsync:
It seems that ssh and rsync are sufficient.
"rsync Tips & Tricks":
http://sial.org/howto/rsync/
"Using rsync over ssh":
http://www.oreilly.com/pub/h/38
rsync manual:
http://samba.anu.edu.au/ftp/rsync/rsync.html
Here's an excerpt from that manual:
"Once installed, you can use rsync to any machine that you can
access via a remote shell (as well as some that you can access
using the rsync daemon-mode protocol). For remote transfers, a
modern rsync uses ssh for its communications, but it may have
been configured to use a different remote shell by default,
such as rsh or remsh.
You can also specify any remote shell you like, either by
using the -e command line option, or by setting the RSYNC_RSH
environment variable.
Note that rsync must be installed on both the source and
destination machines."
--
Tor Olav
http://subcube.com
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Damnit, this Project Euler metadiscussion isn't even a metadiscussion
about Project Euler! o_O
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
