Curious Numbers
June 28, 2016
If you calculated a sum other than 11111110947536882377, your solution is incorrect; press the back button on your browser and try again. Otherwise, you can look at the suggested solution on the next page.
A collection of etudes, updated weekly, for the education and enjoyment of the savvy programmer
If you calculated a sum other than 11111110947536882377, your solution is incorrect; press the back button on your browser and try again. Otherwise, you can look at the suggested solution on the next page.
Here’s a solution in Java. I noticed, as the solution mentions, that “trailing digits, once calculated, never disappear from the sequence”, and used that to generate subsequent numbers.
However, my solution, 103367370865749773002, includes a number that was seemingly omitted from the programmingpraxis solution sum (I haven’t tried figuring out why yet), 92256259918212890625.
Here’s the output:
Here’s the output showing running time (0.133s) using a 2013 laptop with a 2.8 GHz Intel Core i7:
@Daniel: I mistakenly wrote (curious 20) instead of (curious 21). Your total is correct.
I hope the formatting isn’t too bad…. in codepad
We can build up the set of n-digit curious numbers recursively: if c is a curious n-digit number, let
c = x*(10^(n-1)) + y
where
* 10^(n-k-1) < y < 10^(n-k), for some k > 0, and
* x is in [1..9]
Then since
c = y (mod 10^(n-k)), and
c = c*c (mod 10^n)
we have
c = c*c = y*y = y (mod 10^(n – k))
so y is also curious
So we can build up the list l(n) of curious numbers of at most n digits from the list l(n-1) of curious numbers of at most (n-1) digits fairly easily by filtering the curious numbers from the following list of candidates:
candidates(n) = [x*(10^(n-1)) + y | x <- [0..9], y <- l(n-1)]
i.e. l(n) = filter isCurious candidates(n)
(This may generate repeats so we will need to take unique elements of the list.)
Since curious numbers are rare, the list of curious numbers at the previous step is small, so filtering from this candidate set is not terribly expensive.
In Haskell, runs in less than 0.1s on a core i5-6200U processor.
module Main where
import Data.List
isCurious :: Integer -> Bool
isCurious n = n == (mod (n * n) p) where
powersOfTen = map (\x -> 10^x) [1..]
p = head $ dropWhile (< n) powersOfTen
curiousUpToNDigits :: Integer -> [Integer]
curiousUpToNDigits n
| n == 1 = [1,5,6]
| n > 1 = let l = (curiousUpToNDigits (n-1)) in
nub $ filter isCurious [x*(10^(n-1)) + y | x <- [0..9], y <- l]
| otherwise = []
— Compute the sum of curious numbers of at most n digits
—
— sumOfCurious 20 computes the answer to the question asked
sumOfCurious :: Integer -> Integer
sumOfCurious n = sum $ curiousUpToNDigits n
main :: IO ()
main = do
let sum = sumOfCurious 20
print “The sum is:”
print sum
Nice problem. I like the connection with p-adic numbers.
Here’s another way of directly calculating curious numbers: k-digit A is curious if A*A = A mod 10ᵏ, ie. A*A-A = A*(A-1) = X*10ᵏ = X*5ᵏ*2ᵏ for some X. A and A-1 must be co-prime so 5ᵏ must divide one and 2ᵏ must divide the other, which means that A satisfies:
A mod 5ᵏ = 0 and A mod 2ᵏ = 1
or:
A mod 5ᵏ = 1 and A mod 2ᵏ = 0
and we can solve such modular equations with the Chinese Remainder Theorem: a = x mod p, a = y mod q has solution a = y*p*r + x*q*s where r and s are modular inverses of p and q, ie: p*r = 1 mod q and q*s = 1 mod p.
Here’s a Python program using the extended Euclidean algorithm to calculate the modular inverses:
Interestingly, for larger k (> 100 or so) this approach is significantly faster than the suggested method – computation of the GCD is faster than exponentiation modulo 10ᵏ – we can compute eg. a 1 million digit curious numbers in a few minutes: