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