July 13, 2011

I am not entirely sure why, however a couple of days ago the following search keywords were used to access one or more articles on this blog:

the sum of 1+2+3+4...+98+99+100

The above request I found to be a bit interesting, and there is a 50/50 chance that the person found the right answer to the sum of the numbers between 1 and 100.

If you had to solve this problem with the help of Oracle Database, how would you accomplish the task? If it helps, I think that I recall that the mathematical notation representing the problem posed by the searcher is as follows:

Would your answer be any different if the person needed to know the sum of the numbers between 6 and 105:

What about generalizing the problem even further:

Think about the problem before scrolling down. How many unique solutions are able to produce the answer?

–

–

–

–

–

–

–

–

–

–

–

–

–

–

–

–

–

–

–

–

–

–

–

–

–

–

————————————

If you think about the problem, in its simplist form it is really just a matter of repeatedly adding the set of the highest and lowest unmatched numbers (all of those results should be the same, otherwise your calculator needs new batteries) and then multiplying by the number of pairs (1/2 as many numbers are in the sequence to be summed):

01 + 100 = 101 02 + 99 = 101 03 + 98 = 101 04 + 97 = 101 05 + 96 = 101 ... 50 + 51 = 101

So, the general formula is:

`(max - min + 1) / 2 * (min + max)`

And the SQL statements to produce the results:

SELECT (100 - 1 + 1) /2 * (1 + 100) FROM DUAL; SELECT (105 - 6 + 1) /2 * (6 + 105) FROM DUAL;

————————————

–

–

–

–

–

–

–

–

–

–

–

–

For now, ignore the above section. How many ways can this particular problem be solved with the help of Oracle Database? Are there any built-in functions that will help?

Enrique Aviles(07:23:51) :select sum(x)

from (select rownum x from dual connect by level <= y)

where r between x and y

Enrique Aviles(07:46:09) :Correction:

Declare x and y as number variables.

Charles Hooper(14:49:12) :Enrique,

The first solution that I thought about is similar to what you posted, and then I started wondering… what if the lower number is not 1, but instead some other number. I abandoned my solution that was similar to your solution before sliding the CONNECT BY portion of the query into an inline view as you did:

Those are the expected values.

Raj(07:31:04) :One way of solving it mathematically is applying this formula => (n * (n + 1)) / 2

So in this case it will be ((y – x + 1) * (y – x + 2)) / 2

Raj(07:42:07) :Above formula is incorrect. Instead it should be something like this.

Thanks

Charles Hooper(14:13:48) :Raj,

This is the output that I receive:

It appears that your PL/SQL block is producing the expected value (I assume that the first DBMS_OUTPUT is showing the value before correction).

Raj(03:11:54) :That’s correct. It was included just for my testing purpose.

Thanks

Mr Py(07:50:34) :Charles Hooper(14:03:10) :Mr Py,

Before testing, I thought that your example would fail for the same reason that a SQL statement would fail if the ROWNUM pseudo column is used in the WHERE clause – as testing shows, that was not the case. Unfortunately, it appears that the = sign just after the number 6 was lost during formatting of your comment:

Dom Brooks(08:34:14) :How long is a piece of string?

The number of variations on a theme would mean that there are soooo many “different” ways.

Two basic strategies though:

– one is to generate the formula as a string and get “something” to evaluate the formula “dynamically”

– other is to use various methods to iterate through the calculation.

Here are a couple I came up with:

Dom Brooks(08:35:22) :oops – made multiple mistakes in my formatting tags.

Charles Hooper(09:16:31) :I think that I was able to fix the formatting tags.

—

A lot of creative solutions so far. As indicated by the solutions provided so far, part of the point of this blog article (and the similar ones that are found on this blog) is not necessarily to provide the

mostefficient method to solve the problem. Rather, it is to demonstrate different techniques to arrive at the same answer – the most efficient method in any particular solution is not always the most efficient solution when faced with a similar problem. Additionally, part of the point of this blog article is to demonstrate new approaches to solving problems, and those new approaches when applied to completely different problems might be the only visible (possible) angle of attack.Dom’s two solutions used techniques that I was completely unfamiliar with – I see that I not only need to find some time to dig into the MODEL clause, but also XML related functions.

Dom Brooks(10:15:59) :> I think that I was able to fix the formatting tags

No – There were three – the second and the third have merged.

I’ll attempt a repost.

Doing an evaluation of a string forumla, i.e. generating then evaluating ‘1+2+3…’

Recursive With, not something I normally use:

One way of doing it with model:

I’m not overly familiar with any of these techniques but these were the ones that immediately sprung to mind as ways to try to do just for fun and not, as you say, with performance in mind.

Charles Hooper(14:32:41) :Dom,

Interesting solutions. I had a bit of trouble generalizing the method using the MODEL clause so that it would not add the numbers 1 through x-1:

Can you see what I did wrong?

Charles Hooper(11:22:29) :Here is a fun method – divide the numbers into two groups, add the results, and count the number of pairs:

The above works fine until someone does something like the following, and introduces an un-even number of numbers:

So, we have to detect that the middle number was excluded. Let’s see, if there is a difference between the CEIL and FLOOR, something is missing:

So, if we multiply the result of the above by the middle number in between the low and high numbers, we can add that value to the previous result, like this:

Mark W. Farnham(11:49:39) :If you notice that the sum of the first and last numbers of a sequential list of integers is the same as the sum of the second and next to last number, and that this continues until either all the numbers are paired or if you have an odd number the unpaired number is exactly one-half of all the sums, then you have observed one of the derivations of the formula

(x+y)((y-x+1)/2)

and it doesn’t matter whether the list is an even or an odd number of integers. If both the end points are even or odd, the sum will be even, so one half the sum is still an integer, so no fractional parts, floors, or ceilings are needed. If one end point is even and the other is odd, you have have an integer number of pairs, so it doesn’t matter that the sum is odd.

Charles Hooper(13:36:32) :Mark,

Well stated.

I hid a similar answer in the article, but you explained the concept quite a bit better than I did. :-) Roughly half way through the string of

-characters at the bottom of this article is an odd blank area created by white text on a white background. If you highlight that area of the article, it should be possible to read my explanation for an immediate answer to the problem. It is a bit reassuring to see that someone else independently arrived at the same solution.—

With a problem like the one posed in this article, it is possible to think through the problem using logic, play what-if games if there are an even or odd number of elements, or something in between those extremes. I am a little surpised that no one has of yet showed a simple PL/SQL FOR loop.

Enrique Aviles(14:15:15) :Why do it in PL/SQL when you can do it with a single SQL? :-)

Radoslav Golian(14:29:35) :because PL/SQL (without SQL) is faster ;)

jgarry(15:22:47) :As long as you don’t get tripped up by those darn context switches…

Charles Hooper(13:57:31) :Enrique, Radoslav, Joel good points.

I was actually thinking something similar to what Enrique posted when I added the comment about a simple PL/SQL loop – it probably is not a good idea from a performance perspective to create a PL/SQL function to find the sum of the numbers from 1 to 100 (or x to y) and then return that value in a SQL statement. As Joel mentioned, the performance issues due to the unnecessary context switches can be problematic.

It might not have been 100% clear, but this blog post was looking for solutions to the problem that used Oracle Database to help find the answer to the problem. This time there was no restriction stating that the answer had to be retrieved with a SQL select statement. If you encountered the problem of having to calculate the sum of the numbers between x and y, and were in the middle of programming a PL/SQL function, it is more efficient to find the answer using just a PL/SQL FOR loop (or better yet just calculate the answer using the formulas provided in the comments) than it would be to incur a context switch and execute a SQL statement to calculate the answer. I was a bit surprised when I saw Radoslav’s comment above – yet he has a valid point that if the answer is needed as part of a PL/SQL routine, calculating the answer in that routine is more efficient.

Technically, the question posed by this blog article also did not restrict the use of Java to help calculate the answer, so there might be a couple of additional solutions.

Radoslav Golian(15:42:15) :Optimal solution is to find a closed form for that sum and use it as an algorithm..

Finding a closed form for that easy sum is trivial (http://www.jimloy.com/algebra/gauss.htm)

any SQL statement would be slower..

(edit CH: fixed the scrambled code by replacing x with X in the code section)Radoslav Golian(16:06:39) :I didn’t notice that Mark was faster than me :)

Gary Colbran(07:40:27) :What’s wrong with this ?

select (max(n)+min(n))/2*count(n) from (select level n from dual connect by level < 99);

Should work for any starting number, amount of numbers or increment.

select (max(n)+min(n))/2*count(n) from (select (level+x)*i from dual connect by level < y);

Charles Hooper(09:56:57) :Gary,

I appologize in advance if I am misunderstanding your comment – I think that you are asking how to fix the second SQL statement that you posted.

In the blog article, the following formula appeared in white letters (almost invisible):

That formula is logically equivalent to this one:

And the above formula is logically equivalent to the first SQL statement that you provided.

My sample SQL statement:

Your SQL statement with the same input numbers:

A minor adjustment to your second SQL statement: