“taxicab” numbers,<\/a> where the goal is to discover the smallest value that can be expressed as the sum of three cubes in N different ways.<\/p>\nHow 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).\u00a0<\/p>\n
Here is the code:<\/p>\n
declare @level int<\/p>\n
set @level = 2 –sum of two cubes<\/p>\n
;with cubes as
\n(select POWER(i,3) as i3
\nfrom\u00a0\u00a0 tools.sequence
\nwhere\u00a0 i >= 1 and i < 500) –<<<Vary for performance, and for cheating reasons, max needed value <\/p>\n
select c1.i3 + c2.i3 as [sum of 2 cubes in N Ways]
\nfrom\u00a0\u00a0 cubes as c1
\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 cross join cubes as c2
\nwhere c1.i3 <= c2.i3
\ngroup by (c1.i3 + c2.i3)
\nhaving count(*) = @level
\norder by 1<\/p>\n
Ok, breaking this down the cubes CTE is pretty simple:<\/p>\n
(select power(i,3) as i3
\nfrom\u00a0\u00a0 tools.sequence\u00a0 –the table holds 100000 values
\nwhere\u00a0 i >= 1 and i < 500)<\/p>\n
This transforms our values to a table of cubes, so the values would be 1, 8, 27, 64, etc.\u00a0 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.\u00a0 I sum the two cube values, which I get from cross joining the CTE twice.<\/p>\n
select c1.i3 + c2.i3 as [sum of 2 cubes in N Ways]
\nfrom\u00a0\u00a0 cubes as c1
\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 cross join cubes as c2
\nwhere c1.i3 <= c2.i3 –this gets rid of the “duplicate” value pairs<\/p>\n
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:<\/p>\n
c1.i3\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 c2.i3
\n——————– ——————–
\n1\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 1728
\n729\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 1000<\/p>\n
1000\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 729
\n1728\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 1<\/p>\n
These pairs are the same.\u00a0 I don’t eliminate equality to allow for the case where both number are equal, because they won’t be doubled up.\u00a0 With these values:<\/p>\n
c1.i3\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 c2.i3
\n——————– ——————–
\n1\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 1728
\n729\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 1000<\/p>\n
You can see that 1729 is the sum of two cubes in two different ways.\u00a0 So, lastly, the question of performance must come up.\u00a0 Reading the articles, it is clear that this is not a terribly easy problem to solve.\u00a0 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.<\/p>\n
[sum of 2 cubes in N Ways]
\n———————————
\n87539319
\n119824488<\/p>\n
Four however, was a “bit” more challenging.\u00a0 Knowing the answer from the article, I knew I could bound my numbers using 20000 and get the answer.\u00a0 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.)\u00a0 For that you had to go up to i being greater than something like 350000….<\/p>\n
I am thinking that if I turn the CTE into a physical, indexed table I would be able to do this.\u00a0 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.\u00a0 Well at least not just yet, perhaps when the book is done…<\/p>\n","protected":false},"excerpt":{"rendered":"
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.\u00a0 And frankly, sometimes the……<\/p>\n","protected":false},"author":56085,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[2],"tags":[],"coauthors":[19684],"class_list":["post-82030","post","type-post","status-publish","format-standard","hentry","category-blogs"],"acf":[],"_links":{"self":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts\/82030","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/users\/56085"}],"replies":[{"embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/comments?post=82030"}],"version-history":[{"count":2,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts\/82030\/revisions"}],"predecessor-version":[{"id":84364,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts\/82030\/revisions\/84364"}],"wp:attachment":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/media?parent=82030"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/categories?post=82030"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/tags?post=82030"},{"taxonomy":"author","embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/coauthors?post=82030"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}