Post date: Aug 26, 2014 12:51:18 AM
"What is the largest prime number that contains the digits between 1 and n each exactly once?"
The max n is obviously 9, because unless we go to hexadecimal or something, 9 is the largest single digit. We know that there are no 9 digit pandigital primes, because all 9 digit pandigitals are divisible by 3 (remember the old trick, adding up the digits, well if you add 1+2+3+...+9, you get 45). We know there are no 8 digit primes for the same reason. The biggest 7 possible digit prime is 7654321, which is too big to quickly sieve through. A couple minutes rather than a couple seconds. In this case, because we only have to check the numbers that have the digits 1 through 7 once, using a function is actually fairly efficient ... or at least not as inefficient as it usually is. Having to count through each number in a loop is slow, but not having to write 10 million integers to a table is fast.
The best solution, of course, is simply having a table with a lot of primes, say up to 100 million, sitting around for this kind of problem.
CREATE FUNCTION dbo.IsPrimeNumber (@number int)
RETURNS bit
AS
BEGIN
IF @number < 2
RETURN 0
DECLARE @counter int = 3
IF @number = 2
RETURN 1
IF @number % 2 = 0
RETURN 0
WHILE 1 = 1
BEGIN
IF @counter > SQRT(@number) BREAK
IF @number % @counter = 0
RETURN 0
SET @counter = @counter + 2
END -- While
RETURN 1
END
GO
CREATE TABLE #Integers (i tinyint not null primary key)
INSERT INTO #Integers (i) VALUES (0), (1), (2), (3), (4), (5), (6), (7) -- We skip 8-9 because the question requires an 7 digit number use only digits 1 to 7.
CREATE TABLE #Pandigital (p int NOT NULL primary key)
-- Return all possible numbers containing each digit uniquely, but allowing for duplicates in a single situation: left padding zeros.
-- So 0000123 is legal, even though it repeats 0. This is only being used to pad out the number to a static number of digits.
-- The last digit had better be non zero, however.
; WITH LeftPadded (p) As
(
SELECT RTRIM(d1.i) + RTRIM(d2.i) + RTRIM(d3.i) + RTRIM(d4.i) + RTRIM(d5.i) + RTRIM(d6.i) + RTRIM(d7.i)
FROM #Integers d1
INNER JOIN #Integers d2
ON (d2.i <> d1.i)
OR d2.i = 0
INNER JOIN #Integers d3
ON (d3.i <> d1.i
AND d3.i <> d2.i)
OR d3.i = 0
INNER JOIN #Integers d4
ON (d4.i <> d1.i
AND d4.i <> d2.i
AND d4.i <> d3.i)
OR d4.i = 0
INNER JOIN #Integers d5
ON (d5.i <> d1.i
AND d5.i <> d2.i
AND d5.i <> d3.i
AND d5.i <> d4.i)
OR d5.i = 0
INNER JOIN #Integers d6
ON (d6.i <> d1.i
AND d6.i <> d2.i
AND d6.i <> d3.i
AND d6.i <> d4.i
AND d6.i <> d5.i)
OR d6.i = 0
INNER JOIN #Integers d7
ON d7.i <> d1.i
AND d7.i <> d2.i
AND d7.i <> d3.i
AND d7.i <> d4.i
AND d7.i <> d5.i
AND d7.i <> d6.i
AND d7.i > 0
)
INSERT INTO #Pandigital
SELECT STUFF(p, 1, PATINDEX('%[^0]%',p) - 1, '') -- Strip out the left zeros
FROM LeftPadded
-- Though technically all you need to be pandigital is to use each digit at least once, the problem's requirement is that one digit numbers have 1, two digit numbers have 1 and 2, etc.
-- We need to prune numbers containing zeros and numbers with digits that are too large for their size (for example, a 3 digit number with a 6 in it).
DELETE FROM #Pandigital
WHERE p LIKE '%0%'
OR (p LIKE '%7%' AND LEN(p) < 7)
OR (p LIKE '%6%' AND LEN(p) < 6)
OR (p LIKE '%5%' AND LEN(p) < 5)
OR (p LIKE '%4%' AND LEN(p) < 4)
OR (p LIKE '%3%' AND LEN(p) < 3)
OR (p LIKE '%2%' AND LEN(p) < 2)
SELECT TOP 1 p
FROM #Pandigital
WHERE dbo.IsPrimeNumber(p) = 1
ORDER BY p DESC
DROP TABLE #Integers
DROP TABLE #Pandigital
GO
DROP FUNCTION dbo.IsPrimeNumber
GO