Post date: Aug 10, 2015 1:2:13 AM
"What is the smallest number of objects that can be separated into 1 million, or a multiple of 1 million, distinct groupings/piles?"
This problem is stated as separating coins into piles, but really it's the same as 76. The recursive method of problem 76 will solve this, if you step up one by one so you avoid the 32 level limit of SQL Server. But it takes an hour.
If you're willing to step up one by one, we could probably get away with a table, using lookups, not calculations, saving time. But there is a problem. The numbers involved in this problem are so large that there are no words for them. But in this equation, we only care about the lesser digits, so we can lop off anything that is bigger than a certain point. This keeps us in SQL Server's maximum numeric range.
We have no clues about the order of magnitude of the answer, just that it is an even multiple of 1 million. I found out the answer by solving it the slow way, which is cheating, but oh well. This solution uses an overlarge estimate, as if I went at it by guessing. It would handle n up to 1000000000000, which is (way) more than we end up needing.
CREATE TABLE #KValues (k NUMERIC(38,0) PRIMARY KEY NOT NULL, m NUMERIC(38,0) NOT NULL, a1 NUMERIC(38,0) NOT NULL, a2 NUMERIC(38,0) NOT NULL)
CREATE TABLE #Ten (i BIGINT PRIMARY KEY NOT NULL)
INSERT INTO #Ten VALUES (0), (1), (2), (3), (4), (5), (6), (7), (8), (9)
; WITH Integers (i) AS
(
SELECT o.i +
10 * d.i +
100 * h.i +
1000 * k.i +
10000 * k10.i +
100000 * k100.i
FROM #Ten o
CROSS JOIN #Ten d
CROSS JOIN #Ten h
CROSS JOIN #Ten k
CROSS JOIN #Ten k10
CROSS JOIN #Ten k100
)
INSERT INTO #KValues
SELECT i,
CASE WHEN i % 2 = 1 THEN 1 ELSE -1 END,
i * (3 * i - 1) / 2,
i * (3 * i + 1) / 2
FROM Integers
DROP TABLE #Ten
CREATE TABLE #Cache (i numeric(38,0) PRIMARY KEY NOT NULL, a numeric(38,0) NOT NULL)
INSERT INTO #Cache VALUES (0, 1) -- P(0) = 1
GO
CREATE PROCEDURE dbo.MakeTruncatedPartition
@n numeric(38,0)
AS
BEGIN
IF @n < 0 RETURN
DECLARE @result numeric(38,0) = 0
SET @result = 0
SELECT @result = @result + ISNULL(SUM(k.m * c.a),0)
FROM #KValues k
INNER JOIN #Cache c
ON c.i = @n - k.a1
AND @n >= k.a1
WHERE k.k < SQRT(@n) + 1
SELECT @result = @result + ISNULL(SUM(k.m * c.a),0)
FROM #KValues k
INNER JOIN #Cache c
ON c.i = @n - k.a2
AND @n >= k.a2
WHERE k.k < SQRT(@n) + 1
-- We know that every result is more than 0. So if we see a negative, its because we've been truncating our results.
-- If we went negative then bump it up to a big number
WHILE @result < 0
SET @result = @result + 1000000000000000000
-- We'll trim the result to 15 digits. This is reasonably small, but gives us a little bit of leeway considering that the negative k values we may be subtracting are up to 13 digits
IF @result > 1000000000000000
SET @result = @result % 1000000000000000
IF @result <= 0 RETURN
INSERT INTO #Cache
VALUES (@n, @result)
END
GO
DECLARE @i bigint = 1
WHILE 1 = 1
BEGIN
EXEC MakeTruncatedPartition @i
IF EXISTS (SELECT 1
FROM #Cache
WHERE a % 1000000 = 0
AND i = @i)
BREAK
SET @i = @i + 1
END
SELECT @i
DROP TABLE #KValues
DROP TABLE #Cache
GO
DROP PROCEDURE dbo.MakeTruncatedPartition
GO