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.
#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 …
A haskell solution
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:
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]
;; 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.
A soultion in Haskell using Data.Digits
Anyone have an idea, how to implement it without reversing the list twice?
Hackish code will come back to it when I have time.
Mine in F #
C Implementation
This is in python:
[…] 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:
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 :/ )