> 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

This would be a finite series. I think it is usually covered in calculus courses but some of the basics are discussed in earlier algebra courses. Here is a link to a brief summary on finite series. http://calculus.nipissingu.ca/tutorials/finiteseries.html

You can also start your way up from the basics in Khan's Academy.

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.

That is an outstanding explanation of the intuition behind that formula, and in ASCII no less! :)

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

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

Isn't sum(1...n) - sum(1...n-1) just n? (1+2+3+4+5 - (1+2+3+4) = 5). That should be a +, right?

This is an awesome visualization, by the way.

> Isn't sum(1...n) - sum(1...n-1) just n?

Yes. I meant n^2 = sum(1..n-1) + sum(1..n).

You may have a look at “The Magic of Math” [1]. I’m reading it right now and I am loving it. It contains a lot of interesting problems from arithmetics, algebra and geometry. They are well explained and show that math is about creative thinking and not about memorizing equations.

[1] https://www.amazon.com/Magic-Math-Solving-Figuring-Out/dp/04...

Honestly math is filled with cool stuff like this. In fact sometimes I wish I would have done a math minor or major at University instead of just a Computer Science major and Information Systems minor (I’m finishing my undergrad in the spring.)

Combinatorics is one of my favorite fields I always feel it has a lot of cool gems like that one and the proofs are often really intuitive. Combinatorics is all about counting things like the number of possible poker hands given a single deck or the number of ways you can seat 4 people around a table.

It was already mentioned below but, discrete math is another good one. Discrete math includes combinatorics, graph theory, set theory, logic, and number theory. All of these have really cool little tidbits of information. My Discrete Math course was my favorite class at university so far. One of the first random bits of information I learned in that class was that any number is divisible by 9 if the sum of it’s digits are divisible by 9 this was posed to us in one of our first homeworks to be proven or disproven and we were able to prove it using some algebra.

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.

Author(s)?

Not the same person but I guess he means the one by Graham, Knuth (yeah that one) and Patashnik.

Ronald L. Graham, Donald Ervin Knuth, Oren Patashnik

Discrete mathematics is the branch of math you're after.

This looks like it has some ok examples: https://www.tutorialspoint.com/discrete_mathematics/discrete...

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

I always understood it just by saying "Okay, if we take the last item and the first (so n+1), and then the second to last item and second item (so n-1 + 2 = n + 1), etc, we get to the middle in n/2 times. If it was odd, we have an extra n/2. But trying it out on a few series, and it's obvious it works out each way, odd or even, to n/2 * (n + 1).

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

That's the sum of all integers on the complex plane, solved using an analytical continuation of the Riemann zeta function at -1 (fwiw, by the same definition, the sum of 13, 26, 39...inf is also -1/12).

It's disingenuous to assert that is same as the sum of that infinite series without the associated caveats. By the definitions of infinite series that we all learned in calculus, that is a divergent series with no sum.

Edit: Wolfram Alpha[0] has a good graphic showing why this series converges to -1/12 (the one with the red line, drawing a peach-like shape). It also gives an intuition as to how complex numbers are influencing the results despite being omitted from the equation.

[0] http://mathworld.wolfram.com/RiemannZetaFunction.html

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.

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.

I do not have an formal math education, but I'm fairly sure what you quote is part of the Arithmetic Progression concept (the sum formula more specifically), so taking a look at the arithmetic branch of math might be a good idea.

Wikipedia[0], MathWords[1] and Brilliant[2] might be some good resources for you.

[0] https://en.wikipedia.org/wiki/Lists_of_mathematics_topics [1] http://www.mathwords.com/ [2] https://brilliant.org/

Here are some purely visual proofs of that fact: http://gauravkumar.tech/math/visual-proofs/sum-of-first-n-na...

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.

I'll check Daniel Shanks' book out. But the OP was interested in reaching a level where the proof of such summation is not `black magic` - at least that was my impression - which implies reaching a level considerably higher than the minimum... Hardy would be helpful, and is at a sufficiently higher level than future Project Euler questions he might encounter e.g. those involving continued fractions, or Diophantine equations, or even modular arithmetic etc.

Any arithmetic book on Sequence and Series will provide you with the basic toolset to derive the above.

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 <- [1..999], (mod x 3 == 0) || (mod x 5 == 0)]

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 threads, write a scheduler for that, implement message-passing concurrency, and do highly efficient multiplexed I/O in the style of asyncio.

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

Well years ago, I saw a discussion that put this in the context of python's generators being inspired by what was in Icon.

I'm just now looking at Icon code for the first time, but, to me, Python's list comprehension syntax looks more similar to Haskell's than Icon's.

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.

I don't think it's unreasonable to expect it. E.g. clang -O1 (https://godbolt.org/g/7qzSF9 ) is able to use the closed form for a sum on a simple C++ loop. It's not unreasonable that a language with deeper introspection could identify more closed forms. I agree that I don't think the Haskell maintainers would put this specific example in, but I wonder whether they could build it up from simpler primitives.

Haskell optimizer does not feature an arithmetic Oracle nor polynomial optimizer. It cannot even optimize Peano arithmetic much less a series.

This might be fixed some time or never. There is little push for ultimate performance and actually identifying arithmetic forms in recursive loops in the front-end is hard. (Heck it sometimes fails to tail optimize.)

I'd be interested to see how this weighs out in 5-10 years. Since there's no I/O here, I don't see why a clever compiler writer couldn't optimize this whole expression away at compile time, generating an executable just prints a constant.

What language is this?

It’s a Haskell list comprehension. You read it as:

The sum of x for x from one to 999 where x mod three is zero or x mod five is zero.

well, the bit in square brackets is a comprehension. `sum `is just ordinary function application.

Haskell

Oh cool!

I've been working with a continuation-pasing style variant of Joy (https://en.wikipedia.org/wiki/Joy_programming_language https://github.com/calroc/joypy) and tried it on the Project Euler problem 1: https://github.com/calroc/joypy/blob/master/docs/3.%20Develo...

I came up with a solution that generalizes to blocks of terms, but yours is much much nicer! Cheers!

""" Between 0 and 990 inclusive there are sixty-six "blocks" of seven terms each, starting with:

    [3 5 6 9 10 12 15]

And ending with:

    [978 980 981 984 985 987 990]

If we reverse one of these two blocks and sum pairs... """

The Advent of Code 2017 includes a puzzle involving a "spiral" memory grid and I had a similar thing where I was able to figure out a simple mathematical way to solve the puzzle: https://github.com/calroc/joypy/blob/master/docs/Advent%20of...

I'm not explaining it well 'cause I'm all excited to show it.

If you read the first paragraph of the website, "Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems."