THE SQL Server Blog Spot on the Web

Welcome to SQLblog.com - The SQL Server blog spot on the web Sign in | |
in Search

Louis Davidson

Sequence Table Tricks

Ok, so I am writing about the kinds of things you can do with a sequence table, and I have built the table, I have the typical kinds of things planned (like splitting a string, and for the next section, loading a calendar table) but I wanted to do something interesting.  And frankly, sometimes the path to solving a real problem starts with with solving an abstract problem, then reality often tosses you a problem that is really close to this.  Admittedly this might not be realistic in my case, but it is possible.

I have just recently watched the Futurama video "Bender's Big Score" and they have a little math lesson section on the video that was very interesting, but the thing that stuck in my mind was this reference back to a previous episode called the "Lesser of Two Evils".  The Bender look-alike named Flexo (they are both Bender units) start talking and have the following exchange:

Bender: Hey, brobot, what's your serial number?
Flexo: 3370318.
Bender: No way! Mine's 2716057!
Fry: I don't get it.
Bender: We're both expressible as the sum of two cubes!

So I figured, the sum of two cubes would be an interesting, and pretty easy abstract utilization of the sequence table.  Then I have found this reference also to "taxicab" numbers, where the goal is to discover the smallest value that can be expressed as the sum of three cubes in N different ways.

How hard is the query? Turns out, that once you have a sequence table with numbers from 1 to 100000 or so, you can calculate that Taxicab(2) = 1729 very easily (and all of the other numbers that are the sum of two cubes too), and the the sum of two cubes in three different ways also pretty easily (took 3 seconds on my laptop, and that value is 87539319). 

Here is the code:

declare @level int

set @level = 2 --sum of two cubes

;with cubes as
(select POWER(i,3) as i3
from   tools.sequence
where  i >= 1 and i < 500) --<<<Vary for performance, and for cheating reasons, max needed value

select c1.i3 + c2.i3 as [sum of 2 cubes in N Ways]
from   cubes as c1
         cross join cubes as c2
where c1.i3 <= c2.i3
group by (c1.i3 + c2.i3)
having count(*) = @level
order by 1

Ok, breaking this down the cubes CTE is pretty simple:

(select power(i,3) as i3
from   tools.sequence  --the table holds 100000 values
where  i >= 1 and i < 500)

This transforms our values to a table of cubes, so the values would be 1, 8, 27, 64, etc.  The query is a bit more interesting. We want the lowest value that meets the criteria that present in a second, so top is used.  I sum the two cube values, which I get from cross joining the CTE twice.

select c1.i3 + c2.i3 as [sum of 2 cubes in N Ways]
from   cubes as c1
                cross join cubes as c2
where c1.i3 <= c2.i3 --this gets rid of the "duplicate" value pairs

The where condition of c1.i3 <= c2.i3 gets rid of the "duplicate" value pairs since c1 and c2 have the same values, so without this, for 1729 you would get:

c1.i3                 c2.i3
-------------------- --------------------
1                    1728
729                  1000

1000                 729
1728                 1

These pairs are the same.  I don't eliminate equality to allow for the case where both number are equal, because they won't be doubled up.  With these values:

c1.i3                 c2.i3
-------------------- --------------------
1                    1728
729                  1000

You can see that 1729 is the sum of two cubes in two different ways.  So, lastly, the question of performance must come up.  Reading the articles, it is clear that this is not a terribly easy problem to solve.  Values for the sum of three cubes is fairly simple, leaving the sequence values bounded at 500, I get two values in around one second.

[sum of 2 cubes in N Ways]
---------------------------------
87539319
119824488

Four however, was a "bit" more challenging.  Knowing the answer from the article, I knew I could bound my numbers using 20000 and get the answer.  Using this "cheat" on my laptop, I was able to calculate the value of taxicab(4) was 6963472309248 (yea, it only found one) in just 1 hour and 33 minutes, this on a 2.2 Ghz Pentium M laptop with 2 GB of RAM. I tried calculating taxicab(5), but alas, I ran out of space for tempdb (and I had 50 GB available.)  For that you had to go up to i being greater than something like 350000....

I am thinking that if I turn the CTE into a physical, indexed table I would be able to do this.  And for 6, perhaps using the precision of the numeric datatype (38 places!), but not today, I don't want to melt my computer trying something this abstract.  Well at least not just yet, perhaps when the book is done...

Published Sunday, March 23, 2008 10:06 AM by drsql

Comment Notification

If you would like to receive an email when updates are made to this post, please register here

Subscribe to this post's comments using RSS

Comments

No Comments

Leave a Comment

(required) 
(required) 
Submit

This Blog

Syndication

Links to my other sites

Powered by Community Server (Commercial Edition), by Telligent Systems
  Privacy Statement