Curious Numbers

June 28, 2016

Today’s exercise is in the style of Project Euler, so the rules are that your solution must not use more than a minute of computer time and that you can’t peek at the solution until you have the answer yourself.

Some numbers have the curious property that when they are squared, the number appears in the least-significant digits of the product. For instance, 6252 = 390625, and 71063762 = 50543227109376.

What is the sum of all numbers less than 1020 that have this curious property?

Your task is to find the sum described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2 3

5 Responses to “Curious Numbers”

  1. Daniel said

    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.

    import java.math.BigInteger;
    
    public class PraxisCuriousNumbers {
        private static BigInteger getNextCurious(BigInteger integer) {
            for (BigInteger i = BigInteger.ONE; true; i = i.add(BigInteger.ONE)) {
                BigInteger next = new BigInteger(i.toString()+integer.toString());
                if (next.multiply(next).toString().endsWith(next.toString())) {
                    return next;
                }
            }
        }
        
        public static void main(String[] args) {
            BigInteger limit = new BigInteger("10").pow(20);
            BigInteger sum = new BigInteger("12"); // 0 + 1 + 5 + 6
            
            for (String start : new String[]{"5", "6"}) {
                BigInteger current = new BigInteger(start);
                while (true) {
                    current = getNextCurious(current);
                    if (current.compareTo(limit) < 0) {
                        sum = sum.add(current);
                    } else {
                        break;
                    }
                }   
            }
            
            System.out.println("sum: " + sum);
        }
    }
    

    Here’s the output:

    sum: 103367370865749773002
    
  2. Daniel said

    Here’s the output showing running time (0.133s) using a 2013 laptop with a 2.8 GHz Intel Core i7:

    $ time java PraxisCuriousNumbers 
    sum: 103367370865749773002
    
    real	0m0.133s
    user	0m0.125s
    sys	0m0.029s
    
  3. programmingpraxis said

    @Daniel: I mistakenly wrote (curious 20) instead of (curious 21). Your total is correct.

  4. al said

    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

  5. matthew said

    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:

    def egcd(a,b):
        x = 1; y = 0; z = 0; w = 1
        while b != 0:
            q,r = divmod(a,b)
            a,b =  b,r
            x,y,z,w = z,w,x-q*z,y-q*w
        return a,x,y
    
    def curious(k):
        p = 5**k; q = 2**k
        (d,r,s) = egcd(p,q)
        if r < 0: r += q
        if s < 0: s += p
        return (p*r,q*s)
    
    def curioussum(n):
        sum = 1
        for k in range(1,n+1):
            min = 10**(k-1)
            (a,b) = curious(k)
            if a >= min: sum += a
            if b >= min: sum += b
        return sum
    
    >>> print(curioussum(20))
    103367370865749773002
    

    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:

    >>> print("%d\n%d"%curious(1000000))
    4770144151139899673799525600941150267423...
    5229855848860100326200474399058849732576...
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: