Kaprekar Numbers

September 21, 2010

We could work with individual digits, but it is easier to consider the number k modulo n; p is the left n or n-1 digits, and q is the right n digits:

(define (kaprekar? k)
  (let* ((k2 (* k k))
         (n (+ (quotient (ilog 10 k2) 2) 1))
         (p (quotient k2 (expt 10 n)))
         (q (modulo k2 (expt 10 n))))
    (= (+ p q) k)))

Then a list comprehension gives the solution:

> (list-of k (k range 1 1000) (kaprekar? k))
(1 9 45 55 99 297 703 999)

Kaprekar numbers appear as Sloane’s A053816. We used ilog and list-of from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/6qJEU7Wi.

About these ads

Pages: 1 2

20 Responses to “Kaprekar Numbers”

  1. Eric H said

    #lang racket
    (require (planet soegaard/math/math))

    (for/fold ([result '()])
    ([x (in-range 1000)])
    (let ([d (digits (* x x))])
    (let-values ([(left right) (split-at d (quotient (length d) 2))])
    (if (equal? x (+ (digits->number left)
    (digits->number right)))
    (cons x result)
    result))))

  2. Justin said

    This is a good problem for python.

    def kaprekar(n):
    l = str(n * n)
    length = len(l)
    return n == int(l[0:length/2]) + int(l[length/2:])

    for i in range(4,10000000):
    if kaprekar(i):
    print i

  3. slabounty said

    A simple ruby version …

    def keprekar?(k)
        n = k.to_s.length
        k_sqr_str = (k**2).to_s
        right = k_sqr_str[-n, n]
        left = k_sqr_str[0, k_sqr_str.length-right.length]
        sum = left.to_i + right.to_i
        sum == k ? true : false
    end
    
    1.upto(1000) do |k|
        puts "#{k} is a keprekar number" if keprekar?(k)
    end
    
  4. Mithrandir said

    A haskell solution

    isKaprekar :: Int -> Bool
    isKaprekar n
      | n < 2 = True
      | n < 4 = False
      | otherwise = (read.reverse $ l1) + (read.reverse $ l2) == n
      where
        (l2, l1) = splitAt (length.show $ n) (reverse.show $ n * n)
    
    kaprekarLessThan n = filter isKaprekar [1..n]
    

    which gives


    *Main> kaprekarLessThan 1000
    [1,9,45,55,99,297,703,999]

  5. slabounty said

    And yes, yes I did misspell Kaprekar.

  6. Graham said

    Answered in Python, with some pre-computating values and working only with digits (as opposed to strings) for speed:

  7. Graham said

    Oops! Here we go:

    def num_digits(k):
        c = 0
        while k > 0:
            c += 1
            k /= 10
        return c
    
    def is_kaprekar(k):
        k2 = pow(k, 2)
        p10ndk = pow(10, num_digits(k))
        if k == (k2 // p10ndk) + (k2 % p10ndk):
            return True
        else:
            return False
    
    if __name__ == '__main__':
        for k in range(1, 1001):
            if is_kaprekar(k): print(k)
    
  8. def kaprekar?(k)
      # Consider an n-digit number k.
      n = k.to_s.length
      # Square it
      square = k*k
      # And add the right n digits
      right_digits = square.to_s.slice((-1*n)..-1)
      # To the left n or n-1 digits.
      left_digits  = square.to_s.slice(0...(-1*n))
      sum = right_digits.to_i + left_digits.to_i
      # If the resultant sum is k, then k is called a Kaprekar number.
      sum == k ? true : false
    end
    
    def kaprekar_to(upper)
      (0..upper).select do |k|
        kaprekar? k
      end
    end
    


    ruby-1.9.2-p0 > require "kaprekar"
    => true
    ruby-1.9.2-p0 > kaprekar? 9
    => true
    ruby-1.9.2-p0 > kaprekar? 297
    => true
    ruby-1.9.2-p0 > kaprekar? 50
    => false
    ruby-1.9.2-p0 > kaprekar_to 1000
    => [1, 9, 45, 55, 99, 297, 703, 999]

  9. Axio said

    ;; First time I ever use the prelude…

    (define (kaprekar? n)
      (let* ((n2 (ipow n 2))
             (size (+ 1 (ilog 10 n2)))
             (size-l (if (even? size) (/ size 2) (/ (- size 1) 2)))
             (size-r (if (even? size) size-l (+ 1 size-l))))
        (let* ((right (modulo n2 (ipow 10 size-r)))
               (left (/ (- n2 right) (ipow 10 size-r))))
          (= n (+ left right)))))

    (define (kaprekar n)
      (filter kaprekar? (range 0 n)))

  10. Axio said

    ;; err, that was the wrong version.
    (define (kaprekar? n)
      (let* ((n2 (ipow n 2))
             (size (+ 1 (ilog 10 n2)))
             (size-r (/ (if (even? size) size (+ 1 size)) 2)))
        (let* ((mask (ipow 10 size-r))
               (right (modulo n2 mask))
               (left (/ (- n2 right) mask)))
          (= n (+ left right)))))

  11. Jan Van lent said

    Common Lisp solution. No strings manipulation, but arithmetic (log, expt, ceiling, floor).
    Same as model solution in scheme.

    (use-package :iterate)
    
    (defun number-of-digits (k b)
      (ceiling (log (+ k 1) b)))
    
    (defun kaprekar (k)
      (let ((n (number-of-digits k 10)))
        (multiple-value-bind (left right) (floor (expt k 2) (expt 10 n))
          (+ left right))))
    
    (defun kaprekarp (k)
      (= k (kaprekar k)))
    
    (defun find-kaprekar (kmax)
      (iter (for k from 1 to kmax)
            (when (kaprekarp k) (collect k))))
    
    ;; (find-kaprekar 1000)
    
  12. def is_kaprekar(n):
        s_sq = str(n ** 2)
        idx = len(s_sq) - len(str(n))
        a = int(s_sq[idx:])
        try:
            b = int(s_sq[:idx])
        except ValueError:
            b = 0
        return a + b == n
        
    print filter(is_kaprekar, xrange(1000))
    
  13. Sebastian said

    A soultion in Haskell using Data.Digits

    Anyone have an idea, how to implement it without reversing the list twice?

    import Data.Digits
    import Data.List.Split
    
    main :: IO ()
    main = putStrLn $ show $ kap 1000
    
    kap :: Int -> [Int]
    kap n = filter (\x -> kap_trans x == x) [1..n]
    
    kap_trans :: Int -> Int
    kap_trans n = 
        sum (map (unDigits 10) 
                     (map reverse (splitEvery (length (digits 10 n)) $ 
                                              reverse $ 
                                                   digits 10 (n*n))))
    
  14. Rodrigo Menezes said

    Hackish code will come back to it when I have time.

    for( int i = 1; i < 1000; i++)
    {
       int j;
    
       string num = (Math.Pow(i, 2)).ToString();
       if (num.Length > 1)
       {
          string left = num.Substring(0, num.Length / 2);
          string right = num.Substring(num.Length / 2);
          j = Int32.Parse(left) + Int32.Parse(right);
       }
       // C# does not like converting empti strings to numbers.
       // will look to see if there is a way to get rid of this when I have time.
       else
       {
          j = Int32.Parse(num);
       }
    
       //Is Kaprekar?
       if (j == i)
       {
          Console.WriteLine(j);
       }
    }
    
  15. Khanh Nguyen said

    Mine in F #

    
    let isKaprekar (input:int) =     
        match input with
        | 1 -> true
        | _ when input < 4 -> false
        | _ ->     
            let n = string(input).Length
            let squared = string(input * input)   
            let rightNDigits = int(squared.[(squared.Length-n) .. (squared.Length-1)])
            input = int(squared.[0 .. (squared.Length - n - 1)]) + rightNDigits           
    
    List.filter isKaprekar [1 .. 999]
    
  16. Jebb said
      1 #!/usr/bin/python2.7
      2 
      3 def testKap(num):
      4     if num < 4: return False
      5     num2 = num**2
      6     snum = str(num)  
      7     snum2 = str(num2)  
      8     testsum = int(snum2[:-len(snum)]) + int(snum2[-len(snum):])
      9     if testsum == num: return True
     10     else: return False
     11 
     12 def KapInRange(ubound):
     13     results = [i for i in xrange(ubound) if testKap(i)]
     14     return results
    
  17. Vikas Tandi said
    void find_kaprekar_numbers(int limit)
    {
    	int i;
    
    	for(i = 1; i <= limit; i++)
    	{
    		int m, n;
    		int r, power;
    
    		for(m = i, n = i*i, r = 0, power = 1;
    			m > 0;
    			m = m/10)
    		{	
    			r = r + power * (n % 10);
    			n = n/10;
    			power = power * 10;
    		}
    
    		if(n > 0 &&
    			r > 0 &&
    			(n + r) == i)
    			printf("	%d", i);
    	}
    }
    
  18. This is in python:

    def kaprekar(n):
        lengthofn = len(str(n))
        squared = n * n
        
        extractor = lengthofn - 1
        if lengthofn == 1:
            extractor = 1
        
        firstset = int(str(squared)[:extractor])
        secondset = int(str(squared)[extractor:])
        return n == firstset + secondset
        
    print [n for n in range(4, 10000) if kaprekar(n)]
    #[9, 297, 2223, 2728, 4879]
    
  19. […] Below is my solution to the Programming Praxis problem from Sept. 21, 2010. The problem was to find all Kaprekar numbers less than 1000. I wrote my solution in C++ to refresh my skills a little. For more info, see┬áthis link. […]

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

Follow

Get every new post delivered to your Inbox.

Join 617 other followers

%d bloggers like this: