## 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.

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

```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 :/ )