Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Project Euler

projecteuler.net

Post reply on HN
Print view View original

71–80 of 172 posts

Re: Project Euler

#71

Post by danielbarla »

bhrgunatha wrote: post #53
sevensor wrote: post #38

After hearing about it for years, I decided to start working through Project Euler about two weeks ago. It really is much more about math than programming, although it's a lot of fun to take on the problems with a language that has tail call optimization because so many of the problems involve recurrence relations. I like that the problems are constructed in a way that usually punishes you for trying to use brute for…

My only real complaint is (according to my experience) unless you happen to understand some mathematical concept/s involved in the question, it's incredibly difficult to get some insight or clue for how to go about solving it. The forums are a fantastic resource once you already know how to solve the problem .

This is true, though there are recurring themes, and the forum discussion for previous problems often helps.

Re: Project Euler

#72

Post by opportune »

colejohnson66 wrote: post #41
toAnswerIt wrote: post #32

Earlier quoted context omitted.

to see it consider this: S = 1 + 2 + 3 + ... + n-1 + n + S = n + n-1 + n-2 + ...+ 2 + 1 = 2S = n+1 + n+1 + n+1 + ... + n+1 + n+1 every column sums to n+1

Random fact: this only works if the series is finite. Otherwise you end up with sum(1...inf) equaling -1/12.

This can be disproven by noting that the naturals are closed under addition.

The math involved in reaching this identity is akin to dividing by zero.

Re: Project Euler

#73

Post by bjoli »

sevensor wrote: post #38

After hearing about it for years, I decided to start working through Project Euler about two weeks ago. It really is much more about math than programming, although it's a lot of fun to take on the problems with a language that has tail call optimization because so many of the problems involve recurrence relations. I like that the problems are constructed in a way that usually punishes you for trying to use brute for…

I have found that for me, a classical musicians although somewhat mathematically inclined, most problems up to about problem 100 were solvable with my maths book and some helpful pointers.

I ended up spending too much time per problem (days to weeks) and then I got a kid, so that time is being spent on better things.

Re: Project Euler

#74

Post by srikz »

sevensor wrote: post #38

After hearing about it for years, I decided to start working through Project Euler about two weeks ago. It really is much more about math than programming, although it's a lot of fun to take on the problems with a language that has tail call optimization because so many of the problems involve recurrence relations. I like that the problems are constructed in a way that usually punishes you for trying to use brute for…

I think Exercism [1] is a better not-math-inclined coding challenge collection

[1]: http://exercism.io

Re: Project Euler

#75

Post by gordaco »

nhebb wrote: post #52
acscott wrote: post #40

Earlier quoted context omitted.

There's a legend, Gauss came up with that while an elementary student: http://www.nctm.org/Publications/Teaching-Children-Mathemati...

I came up with it too when I was in school. I was bored and staring at some tiles and noticed that for a square block of tiles with side = n, n^2 = sum(1...n) - sum(1...n-1). The funny thing is that, since then, I've looked at that formula several times and can't for the life of me figure out I got from the above formula to the the sum of the range formula. I guess younger me was smarter than current me.

You can arrive to the formula n^2 = sum(1..n) + sum(1..n-1) visually, separating a square into two triangles and fill them adding diagonals. Ok, that doesn't sound very informative, so let me show you an example.

Let's start with a 4x4 square:

OOOO

OOOO

OOOO

OOOO

Divide it into two triangles:

OOOO

OOO O

OO OO

O OOO

Note that one of the triangles has a side of (n-1) and other has a side of n. Now, let's see how many elements has each triangle. As I said, we can use diagonal lines. So the first diagonal has 1 element:

O

We then add the second diagonal, which has 2 elements (I'll use lower caps for the elements that were already present):

oO

O

The third one has 3 elements:

ooO

oO

O

And finally we add the last one:

oooO

ooO

oO

O

It's easy to see how this procedure can be extended to any triangle and to any square (which can be divided in two triangles).

So we can see that:

1) A triangle of side n has sum(1..n) elements.

2) A square of side n can be decomposed into a triangle of side n and another one of side (n-1).

3) Now you can use some basic algebra to determine the value of sum(n): if sum(n-1) + sum(n) = n^2, and sum(n-1) + n = sum(n), then 2·sum(n) = n^2+n, therefore sum(n) = (n^2+n)/2, or if you prefer, sum(n)=n·(n+1)/2.

Re: Project Euler

#76

Post by fantispug »

skierscott wrote: post #54
colejohnson66 wrote: post #41

Earlier quoted context omitted.

Random fact: this only works if the series is finite. Otherwise you end up with sum(1...inf) equaling -1/12.

Not true. Infinite sums are not defined for series that don’t converge, and sum(1..n) does not converge as n => infinity. Yes, you can play a nice trick with that sum if you ignore the fact that inf-inf is meaningless.

It depends on how you define the summation of infinite series. With the standard convergence type definitions you are correct. But it is possible to define this sum in a consistent way (e.g. Ramanujan summation or Riemann Zeta analytic continuation) as shown in Hardy's “Divergent Series”. The cost is that they have properties like rearranging the order of the terms gives a different result. Apparently this sum can come up in Quantum Field Theory when calculating vacuum force between two conducting plates.

Re: Project Euler

#77

Post by fantispug »

jackweirdy wrote: post #21
delibes wrote: post #9

Ah, memories. Back in 2010 I whinged to colleagues who were using their fancy functional languages to solve problem 1 inefficiently in 2 lines of code... " Project Euler problem 1 :- It helps to know the sum of (1 .. x) is 0.5 * n * (n+1). Multiples of 3 less than 1000 are (3 .. 999) == (1 .. 333) * 3 = 0.5 * 333 * 334 * 3 = 166833 Multiples of 5 less than 1000 are (5 .. 995) == (1 .. 199) * 5 = 0.5 * 199 * 200 * 5 =…

> It helps to know the sum of (1 .. x) is 0.5 * n * (n+1) This is cool. As someone out of full time education, and who dropped maths relatively early, where’s a good place to start learning some of this stuff? By stuff I mean things related to algebra and whatever the black magic I quoted is

I really like the book “Concrete Mathematics”. It might be a little hard going without much maths background, but it is filled with these kinds of tricks.

Re: Project Euler

#79

Post by archgoon »

http://rosalind.info (named after Rosalind Franklin) is similar, for bioinformatics. It has the advantage over Project Euler that it provides some background and hints to the solution to the problem it presents, plus an additional graph structure of concept dependencies.

Many of the bioinformatics problems are also pure Math and CS, so it's probably of broad interest beyond just an interest in biology.

Re: Project Euler

#80

Post by nhebb »

tomfitz wrote: post #56
nhebb wrote: post #52

Earlier quoted context omitted.

I came up with it too when I was in school. I was bored and staring at some tiles and noticed that for a square block of tiles with side = n, n^2 = sum(1...n) - sum(1...n-1). The funny thing is that, since then, I've looked at that formula several times and can't for the life of me figure out I got from the above formula to the the sum of the range formula. I guess younger me was smarter than current me.

That's a neat visualisation. n^2 = sum(1..n) - sum(1..n-1) = 2 sum(1..n-1) + n => n^2 - n = 2 sum(1..n-1) => n(n-1) = 2*sum(1..n-1) => sum(1..n-1) = n(n-1)/2 And you can rewrite that as... sum(1..n) = n(n+1)/2

That's it! Makes me realize how rusty at math I've gotten. :/
Post reply on HN