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

51–60 of 172 posts

Re: Project Euler

#51

Post by bunderbunder »

racer-v wrote: post #30
bunderbunder wrote: post #10

Earlier quoted context omitted.

The best point to be made from this isn't that it's more computationally efficient. It's that, compared to something like sum [x | x which is really just bluntly translating the question into a programming language and letting it take care of the rest, your approach involves some actual insight into the underlying math.

Right. We don't actually know whether this Haskell code is less efficient - that depends entirely on the implementation.

Compared to grandparent's method of calculation (9 multiplications, 3 additions, no comparisons, no iteration), the Haskell code is almost certainly less efficient. I can't imagine the Haskell maintainers would spend time on an optimization that is so impractically purpose-specific.

Re: Project Euler

#52

Post by nhebb »

acscott wrote: post #40
jackweirdy wrote: post #21

Earlier quoted context omitted.

> 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

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.

Re: Project Euler

#53

Post by bhrgunatha »

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.

Re: Project Euler

#54

Post by skierscott »

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.

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.

Re: Project Euler

#55

Post by sixstringtheory »

tedmiston wrote: post #49
mathattack wrote: post #35

Earlier quoted context omitted.

His point is correct. There are usually efficient and inefficient ways to attack each problem. It's better to solve the math problem first, before the coding problem.

Only when the scale truly matters is the most efficient algorithm the best choice though. For a lot of problems, especially in early stage startups, the brute force solution is more than sufficient and avoids premature optimization. Having perfect algorithms for everything comes with an opportunity cost in startup land that isn't aligned with whether or not your business succeeds most of the time. (This really only a…

Some problems simply will never return the result if you brute force it. I've run a brute-force solver and written the elegant approach while I waited for a result that'd never come.

Most of the elegant solutions do exist in libraries out there, but the point is to pass down the underlying knowledge.

I don't think it's really fair to liken something like mathematics to the startup world, something that has all sorts of nondeterministic factors involved.

Re: Project Euler

#56

Post by tomfitz »

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.

That's a neat visualisation.

n^2 = sum(1..n) - sum(1..n-1) = 2sum(1..n-1) + n

=> n^2 - n = 2sum(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

Re: Project Euler

#57

Post by oldandtired »

kccqzy wrote: post #44
bunderbunder wrote: post #10

Earlier quoted context omitted.

The best point to be made from this isn't that it's more computationally efficient. It's that, compared to something like sum [x | x which is really just bluntly translating the question into a programming language and letting it take care of the rest, your approach involves some actual insight into the underlying math.

You can do the same in Python, which steals Haskell’s list comprehension. By the way doesn’t the original problem say exclude multiples of 15? IMO Python’s generators and coroutines are one of its most useful yet least appreciated features. Being able to suspend a function, resume it, get values from it, send values or exceptions to it is a highly powerful feature. You can use them to implement user-space cooperative…

and Python got this from....? (which language)

Re: Project Euler

#59

Post by EpiMath »

somezero wrote: post #48
jackweirdy wrote: post #21

Earlier quoted context omitted.

> 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

Read G.H. Hardy's Introduction to Number Theory, Then possibly A Course of Pure Mathematics, also by him. Note that the level for which you're aiming, is a level wherein such summation is much closer to triviality, than it is to `black magic` - whatever that means.

If you mean Hardy and Wright's Introduction to the Theory of Numbers, I agree it is excellent, but you can solve the great majority of the project Euler problems without going to quite that level. I particularly enjoyed Daniel Shank's Solved and Unsolved Problems in Number Theory but even that goes beyond what is necessary.

Re: Project Euler

#60

Post by kccqzy »

oldandtired wrote: post #57
kccqzy wrote: post #44

Earlier quoted context omitted.

You can do the same in Python, which steals Haskell’s list comprehension. By the way doesn’t the original problem say exclude multiples of 15? IMO Python’s generators and coroutines are one of its most useful yet least appreciated features. Being able to suspend a function, resume it, get values from it, send values or exceptions to it is a highly powerful feature. You can use them to implement user-space cooperative…

and Python got this from....? (which language)

Well Python got it from Haskell. I thought I made it clear enough.

See https://docs.python.org/3/howto/functional.html

Post reply on HN