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.
Programming Praxis 
#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))))
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
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) endA 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]
And yes, yes I did misspell Kaprekar.
Answered in Python, with some pre-computating values and working only with digits (as opposed to strings) for speed:
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)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 endruby-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]
;; 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)))
;; 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)))))
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)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))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))))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); } }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]C Implementation
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); } }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][…] 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. […]
[…] A few days ago I attempted to put my Ruby skills to use, given a programming puzzle centred on Kaprekar numbers. […]
Finally, I have understood kaprekar number. Thanks guys
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;
}
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:
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 :/ )