I’ve never been much at math
But I’ve always liked reading about it. It’s super interesting, and it always blows my mind. Like, guaranteed. Once in a while I’ll even try my hand at solving problems I read about in SQL. Not because SQL is a particularly good language for it; but just because sometimes I get sick of trying to find new ways to look at DMV data! I stumbled across this Popular Mechanics article recently about five simple math problems that no one can solve. The title is a little misleading, but whatever.
The Collatz Conjecture
The only problem in there that could really be written in SQL was the Collatz Conjecture. It states that when you take any number, and if it’s even you divide it by 2, and if it’s odd you multiply it by 3 and add 1, you’ll always eventually end up with 1. Fair enough. There’s probably a use for that out somewhere out there.
Writing it in SQL was super easy, of course. Just throw a CASE expression at it.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
DECLARE @i BIGINT = (SELECT ABS(CHECKSUM(NEWID()) % 9223372036854775807 + 1 /*2305843009213693951*/)) DECLARE @cntr BIGINT = 1 PRINT 'Starting with ' + CONVERT(VARCHAR(100), @i) WHILE @i <> 1 BEGIN SELECT @i = CASE WHEN (@i % 2) = 0 THEN (@i / 2) ELSE (@i * 3) + 1 END PRINT 'Iteration ' + CONVERT(VARCHAR(100), @cntr) + ' resulted in ' + CONVERT(VARCHAR(100), @i) SET @cntr +=1 END |
Stumbling blocks
I tried throwing some larger numbers at it, but once you get up around the BIGINT max any time you try to multiply by 3 you end up with errors. Even dividing 9223372036854775807 by 3 got me more arithmetic overflow errors than successful tries.
I know, I know. It’s not set-based. Shame on me. But it still runs pretty darn fast, even when you get up to higher numbers. The most steps it took me to get to 1 was 723, and even that ran in milliseconds.
Maybe SQL is alright for math after all!
Thanks for reading!
5 Comments. Leave new
B-b-but… it’s a perfect excuse to use the old MAXRECURSION query hint!
WITH CTE (
n, iteration
)
AS (
/* anchor part */
SELECT CONVERT(bigint,ABS(CHECKSUM(NEWID()) % 9223372036854775807 + 1 /*2305843009213693951*/)) as n
,1 as iteration
UNION ALL
/* recursive part */
SELECT
CASE
WHEN (n % 2) = 0
THEN (n / 2)
ELSE (n * 3) + 1
END AS n
,iteration + 1 AS iteration
FROM CTE
WHERE n 1
)
/* actual SELECT-y bit */
SELECT n, iteration
FROM CTE
OPTION (MAXRECURSION 32767)
Aw, but I *liked* my PRINT-y messages!
All T-SQL children are pretty.
(except for set-based ones, they’re prettier ;-P )
Thanks for the Friday maths fun, Eric!
I think a ‘greater than’ sign has gone missing during rendering. Should be between ‘n’ and ‘1’.
IIRC almost every problem I’ve managed to solve on Project Euler (only about 100-150 of them; I’m also a fan of maths but sadly unable to wrap my head around most of it) had at least one SQL-based solution amongst the previous answers. I’ve considered going through them again with SQL instead of Python, but I suspect I wouldn’t learn much about SQL or set logic that I don’t already know 🙁
Check the site out if you’re not aware of it already though, it’s good fun — especially if you’re trying to get to grips with a new language.