Post date: Feb 05, 2017 1:55:59 PM
"A product-sum number is a number where the same series of positive integers, whether added together or multiplied together, produces the same result. For each series length between 2 and 12000 (inclusive), find the smallest result, and then sum the distinct results."
Given any set of numbers (which are factors of an integer), it is possible to find a set of numbers where the sum is equal to the product, by simply adding 1s until they match. The number of 1s needed is the product minus the sum, which makes the total length product minus sum plus the count. We know that there can't me more than 12k 1s, so the product and base sum can't be more than about 12k off. This maximum difference occurs at 2 x 12000 minus 11998 1s. As the number of factors increases, they must become smaller to say within this range. Everything tops out at under 2 ** 15 (32k) so 14 factors is the greatest number of factors.
CREATE TABLE #Integers (i BIGINT PRIMARY KEY NOT NULL)
; WITH Integers (i) AS
(
SELECT 2
UNION ALL
SELECT i + 1
FROM Integers
WHERE i < 12000
)
INSERT INTO #Integers
SELECT i
FROM Integers
OPTION (MAXRECURSION 12000)
-- It is faster to build the factors from the bottom up than by recursively factorizing from the top down.
-- Normally I wouldn't store factors as a wide table like this, but this lets us easily whittle down the number of possibilities to a smaller set with each insertion.
-- Much faster than it takes to do it as a single step.
-- This set contains some dupes (permutations of the same numbers) so I am going to pull them out by making sure that the first numbers are bigger.
CREATE TABLE #Factors (Product INT NOT NULL, [Sum] INT NOT NULL, Factors INT NOT NULL,
i1 INT NOT NULL, i2 INT NOT NULL, i3 INT NOT NULL DEFAULT 0, i4 INT NOT NULL DEFAULT 0,
i5 INT NOT NULL DEFAULT 0, i6 INT NOT NULL DEFAULT 0, i7 INT NOT NULL DEFAULT 0, i8 INT NOT NULL DEFAULT 0,
i9 INT NOT NULL DEFAULT 0, i10 INT NOT NULL DEFAULT 0, i11 INT NOT NULL DEFAULT 0, i12 INT NOT NULL DEFAULT 0,
i13 INT NOT NULL DEFAULT 0, i14 INT NOT NULL DEFAULT 0)
INSERT INTO #Factors (Product, [Sum], Factors, i1, i2)
SELECT i1.i * i2.i, i1.i + i2.i
, 2, i1.i, i2.i
FROM #Integers i1
CROSS JOIN #Integers i2
WHERE i1.i * i2.i <= 24000
AND i1.i >= i2.i
INSERT INTO #Factors (Product, [Sum], Factors, i1, i2, i3)
SELECT i1 * i2 * i, i1 + i2 + i
, 3, i1, i2, i
FROM #Factors s
CROSS JOIN #Integers i
WHERE (i1 * i2 * i) <= 24000
AND i2 >= i
INSERT INTO #Factors (Product, [Sum], Factors, i1, i2, i3, i4)
SELECT i1 * i2 * i3 * i, i1 + i2 + i3 + i
, 4, i1, i2, i3, i
FROM #Factors s
CROSS JOIN #Integers i
WHERE (i1 * i2 * i3 * i) <= 24000
AND i3 >= i
INSERT INTO #Factors (Product, [Sum], Factors, i1, i2, i3, i4, i5)
SELECT i1 * i2 * i3 * i4 * i, i1 + i2 + i3 + i4 + i
, 5, i1, i2, i3, i4, i
FROM #Factors s
CROSS JOIN #Integers i
WHERE (i1 * i2 * i3 * i4 * i) <= 24000
AND i4 >= i
INSERT INTO #Factors (Product, [Sum], Factors, i1, i2, i3, i4, i5, i6)
SELECT i1 * i2 * i3 * i4 * i5 * i, i1 + i2 + i3 + i4 + i5 + i
, 6, i1, i2, i3, i4, i5, i
FROM #Factors s
CROSS JOIN #Integers i
WHERE (i1 * i2 * i3 * i4 * i5 * i) <= 24000
AND i5 >= i
INSERT INTO #Factors (Product, [Sum], Factors, i1, i2, i3, i4, i5, i6, i7)
SELECT i1 * i2 * i3 * i4 * i5 * i6 * i, i1 + i2 + i3 + i4 + i5 + i6 + i
, 7, i1, i2, i3, i4, i5, i6, i
FROM #Factors s
CROSS JOIN #Integers i
WHERE (i1 * i2 * i3 * i4 * i5 * i6 * i) <= 24000
AND i6 >= i
INSERT INTO #Factors (Product, [Sum], Factors, i1, i2, i3, i4, i5, i6, i7, i8)
SELECT i1 * i2 * i3 * i4 * i5 * i6 * i7 * i, i1 + i2 + i3 + i4 + i5 + i6 + i7 + i
, 8, i1, i2, i3, i4, i5, i6, i7, i
FROM #Factors s
CROSS JOIN #Integers i
WHERE (i1 * i2 * i3 * i4 * i5 * i6 * i7 * i) <= 24000
AND i7 >= i
INSERT INTO #Factors (Product, [Sum], Factors, i1, i2, i3, i4, i5, i6, i7, i8, i9)
SELECT i1 * i2 * i3 * i4 * i5 * i6 * i7 * i8 * i
, i1 + i2 + i3 + i4 + i5 + i6 + i7 + i8 + i
, 9, i1, i2, i3, i4, i5, i6, i7, i8, i
FROM #Factors s
CROSS JOIN #Integers i
WHERE (i1 * i2 * i3 * i4 * i5 * i6 * i7 * i8 * i) <= 24000
AND i8 >= i
INSERT INTO #Factors (Product, [Sum], Factors, i1, i2, i3, i4, i5, i6, i7, i8, i9, i10)
SELECT i1 * i2 * i3 * i4 * i5 * i6 * i7 * i8 * i9 * i
, i1 + i2 + i3 + i4 + i5 + i6 + i7 + i8 + i9 + i
, 10, i1, i2, i3, i4, i5, i6, i7, i8, i9, i
FROM #Factors s
CROSS JOIN #Integers i
WHERE (i1 * i2 * i3 * i4 * i5 * i6 * i7 * i8 * i9 * i) <= 24000
AND i9 >= i
INSERT INTO #Factors (Product, [Sum], Factors, i1, i2, i3, i4, i5, i6, i7, i8, i9, i10, i11)
SELECT i1 * i2 * i3 * i4 * i5 * i6 * i7 * i8 * i9 * i10 * i
, i1 + i2 + i3 + i4 + i5 + i6 + i7 + i8 + i9 + i10 + i
, 11, i1, i2, i3, i4, i5, i6, i7, i8, i9, i10, i
FROM #Factors s
CROSS JOIN #Integers i
WHERE (i1 * i2 * i3 * i4 * i5 * i6 * i7 * i8 * i9 * i10 * i) <= 24000
AND i10 >= i
INSERT INTO #Factors (Product, [Sum], Factors, i1, i2, i3, i4, i5, i6, i7, i8, i9, i10, i11, i12)
SELECT i1 * i2 * i3 * i4 * i5 * i6 * i7 * i8 * i9 * i10 * i11 * i
, i1 + i2 + i3 + i4 + i5 + i6 + i7 + i8 + i9 + i10 + i11 + i
, 12, i1, i2, i3, i4, i5, i6, i7, i8, i9, i10, i11, i
FROM #Factors s
CROSS JOIN #Integers i
WHERE (i1 * i2 * i3 * i4 * i5 * i6 * i7 * i8 * i9 * i10 * i11 * i) <= 24000
AND i11 >= i
INSERT INTO #Factors (Product, [Sum], Factors, i1, i2, i3, i4, i5, i6, i7, i8, i9, i10, i11, i12, i13)
SELECT i1 * i2 * i3 * i4 * i5 * i6 * i7 * i8 * i9 * i10 * i11 * i12 * i
, i1 + i2 + i3 + i4 + i5 + i6 + i7 + i8 + i9 + i10 + i11 + i12 + i
, 13, i1, i2, i3, i4, i5, i6, i7, i8, i9, i10, i11, i12, i
FROM #Factors s
CROSS JOIN #Integers i
WHERE (i1 * i2 * i3 * i4 * i5 * i6 * i7 * i8 * i9 * i10 * i11 * i12 * i) <= 24000
AND i12 >= i
INSERT INTO #Factors (Product, [Sum], Factors, i1, i2, i3, i4, i5, i6, i7, i8, i9, i10, i11, i12, i13, i14)
SELECT i1 * i2 * i3 * i4 * i5 * i6 * i7 * i8 * i9 * i10 * i11 * i12 * i13 * i
, i1 + i2 + i3 + i4 + i5 + i6 + i7 + i8 + i9 + i10 + i11 + i12 + i13 + i
, 14, i1, i2, i3, i4, i5, i6, i7, i8, i9, i10, i11, i12, i13, i
FROM #Factors s
CROSS JOIN #Integers i
WHERE (i1 * i2 * i3 * i4 * i5 * i6 * i7 * i8 * i9 * i10 * i11 * i12 * i13 * i) <= 24000
AND i13 >= i
DROP TABLE #Integers
SELECT Product, [Length] = Product - [Sum] + Factors
INTO #Results
FROM #Factors
; WITH MinimalProductSums (m) AS
(
SELECT MIN(Product)
FROM #Results
WHERE Length <= 12000
GROUP BY [Length]
)
SELECT SUM(DISTINCT m)
FROM MinimalProductSums
DROP TABLE #Factors
DROP TABLE #Results