Kaprekar Numbers

September 21, 2010

Wolfram’s MathWorld describes Kaprekar numbers like this:

Consider an n-digit number k. Square it and add the right n digits to the left n or n-1 digits. If the resultant sum is k, then k is called a Kaprekar number. For example, 9 is a Kaprekar number since 92 = 81 and 8 + 1 = 9 and 297 is a Kaprekar number since 2972 = 88209 and 88 + 209 = 297.

Your task is to write a function that identifies Kaprekar numbers and to determine the Kaprekar numbers less than a thousand. 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.

Advertisements

Pages: 1 2

24 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. Lautaro Pecile said
    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. […]

  20. […] A few days ago I attempted to put my Ruby skills to use, given a programming puzzle centred on Kaprekar numbers. […]

  21. Finally, I have understood kaprekar number. Thanks guys

  22. Daniel said

    C++:

    using namespace std;

    bool isKep(int num)
    {
    int n = num;
    int digit = 1;
    int right = 0;
    int squere = n*n;
    while (n)
    {
    right += digit*(squere%10);
    n /= 10;
    squere /= 10;
    digit *= 10;
    }
    if (squere+right == num) {return true;}
    else {return false;}
    }

    int main()
    {
    for (int i=1;i<1000;i++){
    if (isKep(i)) {cout << i << " ";}
    }
    return 0;
    }

  23. sealfin said

    September 21st, 2010.c:

    #include "seal_bool.h" /* <http://GitHub.com/sealfin/C-and-C-Plus-Plus/blob/master/seal_bool.h> */
    #include "printDateAndTime.h" /* <http://Gist.GitHub.com/sealfin/6d35f3a3958bd6797a0f> */
    #include <stdlib.h>
    #include <stdio.h>
    #include <string.h>
    
    const unsigned int k_Limit = 999;
    
    size_t f_NumberOfDigits( const unsigned long p )
    {
      size_t number_of_digits = 1;
      unsigned long divisor = 10;
    
      while( p / divisor != 0 )
      {
        number_of_digits ++;
        divisor *= 10;
      }
      return number_of_digits;
    }
    
    unsigned int f_PartialStringToNumber( const char * const p_string, const size_t p_indexOfFirstCharacter, const size_t p_numberOfCharacters )
    {
      size_t i = p_indexOfFirstCharacter + p_numberOfCharacters;
      unsigned int multiplier = 1, number = 0;
    
      for( ; i > p_indexOfFirstCharacter; i --, multiplier *= 10 )
        number += (( p_string[ i - 1 ] - '0' ) * multiplier );
      return number;
    }
    
    char *g_k_squared_string = NULL;
    
    bool f_IsAKaprekarNumber( const unsigned int k )
    {
      size_t number_of_left_digits, number_of_right_digits;
      unsigned int left, right;
    
      if( g_k_squared_string == NULL )
        g_k_squared_string = ( char* )malloc( sizeof( char ) * ( f_NumberOfDigits(( unsigned long )k_Limit * k_Limit ) + 1 ));
      sprintf( g_k_squared_string, "%lu", ( unsigned long )k * k );
      number_of_left_digits = number_of_right_digits = f_NumberOfDigits( k );
      if( number_of_left_digits + number_of_right_digits > strlen( g_k_squared_string ))
        number_of_left_digits --;
      left = f_PartialStringToNumber( g_k_squared_string, 0, number_of_left_digits );
      right = f_PartialStringToNumber( g_k_squared_string, number_of_left_digits, number_of_right_digits );
      return left + right == k;
    }
    
    void main( void )
    {
      p_PrintDateAndTime();
      printf( "\n" );
    
      {
        unsigned int k = 1;
        size_t number_of_Kaprekar_numbers = 0;
        unsigned int *Kaprekar_numbers;
    
        for( ; k <= k_Limit; k ++ )
          if( f_IsAKaprekarNumber( k ))
          {
            number_of_Kaprekar_numbers ++;
            if( number_of_Kaprekar_numbers == 1 )
              Kaprekar_numbers = ( unsigned int* )malloc( sizeof( unsigned int ));
            else
              Kaprekar_numbers = ( unsigned int* )realloc( Kaprekar_numbers, sizeof( unsigned int ) * number_of_Kaprekar_numbers );
            Kaprekar_numbers[ number_of_Kaprekar_numbers - 1 ] = k;
          }
        printf( "The" );
        if( number_of_Kaprekar_numbers == 0 )
          printf( "re are no" );
        printf( " Kaprekar number%s in the range [ 1, %u ]", ( number_of_Kaprekar_numbers != 1 )?"s":"", k_Limit );
        if( number_of_Kaprekar_numbers > 0 )
        {
          size_t i = 0;
    
          printf( " " );
          if( number_of_Kaprekar_numbers == 1 )
            printf( "is" );
          else
            printf( "are" );
          printf( ": " );
          for( ; i < number_of_Kaprekar_numbers; i ++ )
          {
            if(( i == 1 ) && ( number_of_Kaprekar_numbers == 2 ))
              printf( " and " );
            else
              if( i > 0 )
              {
                printf( ", " );
                if( i + 1 == number_of_Kaprekar_numbers )
                  printf( "and " );
              }
            printf( "%u", Kaprekar_numbers[ i ] );
          }
          free( Kaprekar_numbers );
        }
        printf( ".\n" );
      }
    
      if( g_k_squared_string != NULL )
        free( g_k_squared_string );
      printf( "\n" );
      p_PrintDateAndTime();
    }

    Output:

    The Kaprekar numbers in the range [ 1, 999 ] are: 1, 9, 45, 55, 99, 297, 703, and 999.

    On an Apple Power Mac G4 (AGP Graphics) (450MHz processor, 1GB memory) to run the solution took approximately one second on both Mac OS 9.2.2 (International English) (the solution interpreted using Leonardo 3.4.1) and Mac OS X 10.4.11 (the solution compiled using Xcode 2.2.1).

    (I’m just trying to solve the problems posed by this ‘site whilst I try to get a job; I’m well aware that my solutions are far from the best – but, in my defence, I don’t have any traditional qualifications in computer science :/ )

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: