Post date: Oct 07, 2018 1:32:26 PM
"Find the last 10 digits of the prime number 28433 * (2 ** 7830457) +1, having 2357207 digits."
This problem was filled with some discussion about Mersenne primes, which is an interesting subject, but a bit of a red herring. It isn't required to solve the problem, which is a simple optimization problem. I didn't think I could calculate such a giant number, but SQL Server isn't as slow as that, even on an underpowered VM. It surprised me.
Remember that we don't need to keep the full number in memory. When we multiply, the digits to the left of a position don't affect the digits to the right. They just make more left.
Here's the slow answer...
DECLARE @big numeric(19,0), @two numeric(19,0), @p int = 1
--With a little extra padding to handle zeros at the cutoff.
WHILE @p <= 7830457
SELECT @p = @p + 1, @big = right(@big * @two, 12)
SELECT right(convert(numeric(19,0), 28433) * @big + convert(numeric(19,0), 1), 10)
For a faster result, we use recursion. Lucky it doesn't overflow...
CREATE FUNCTION dbo.DirtyPower(@big numeric(19,0), @p int)
RETURNS numeric(19,0)
AS
BEGIN
if @p = 0 return 1
if @big = 0 return 0
if @p % 2 = 0
RETURN dbo.DirtyPower(right(@big * @big,12), @p/2)
else
RETURN right(@big * dbo.DirtyPower(right(@big * @big,12), @p/2) , 12)
-- Never gets here
RETURN 0
END
GO
SELECT right(convert(numeric(19,0), 28433) * dbo.DirtyPower(2, 7830457) + convert(numeric(19,0), 1), 10)
GO
DROP FUNCTION dbo.DirtyPower
GO