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

	Am on Problem 27 now. Loads of fun. I'm coding in Python, and I think I
had only one problem that failed to find an answer within a minute.

	I know basic number theory, and some of these problems are doing a good
job of keeping that information fresh in my head.

	If anyone attempts these, my recommendation is to scan at least the
first two pages of each problem's threads in the forums and see how
others did it - I picked up on a number of cool ideas from there.
	
-- 
Lisa: Oedipus killed his father and married his mother.
Homer: Who payed for THAT wedding?


                    /\  /\               /\  /
                   /  \/  \ u e e n     /  \/  a w a z
                       >>>>>>mue### [at] nawazorg<<<<<<
                                   anl

Post a reply to this message

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