Challenge: find 'Kaprekar numbers'

I saw this tweet over the weekend—

Via Wikipedia—

In mathematics, a Kaprekar number for a given base is a non-negative integer, the representation of whose square in that base can be split into two parts—either or both of which may include leading zeroes—that add up to the original number. For instance, 45 is a Kaprekar number, because 452 = 2025 and 20 + 25 = 45.

Challenge

In the language of your choice, write a script to find the first 8 Kaprekar numbers. 1, 9, 45, 55, 99, 297, 703, 999

Two clarifications via @ripsup here:

First gotcha is the second part of the split numbers must be positive (no zeros). The second part was that you add a zero to the front if the length is odd.

Post your solution in the comments below!

Comments

[Heiko Dudzus]

I managed to reduce the number of divisions by throwing some mathematics on it. Put very short:

1. If n is a Kaprekar number (to a base b) there must be a divisor ( d=b^m ) with n^2 = xd+r with the constraint n=x+r. (x beeing the quotient and r the remainder)
2. Substituting r with n-x, we get: n^2 = xd +n -x = x(d-1) + n
3. So: n(n-1) = x (d-1) --> x = n(n-1)/(d-1) This division can have no remainder!
4. The quotient x has to be < n (because n=x+r (with r>0)). Conclusion: d>n. It tells me, I should start with exponents m so that b^m >n.

The improvements are:

• One modulo division is enough, where my original code had to compute quotient and remainder.
• The lower bound for the divisor is increased and, more important, preserved before divisions take place.

The computation time for the search up to 10^8 is reduced to 4 % compared to my original code.

isKaprekar base n =
  elem 0 $                                  -- any remainders 0? 
  takeWhile (<n) $ -- remainder has to be < n. Now the list is finite.
  map (\div -> (n*(n-1)) `mod` (div-1)) $ -- compute the critical remainders
  dropWhile (<=n) $ map (base^) [2..]       -- divisors must be > n

main = print $ filter (isKaprekar 10) [1..10^8]

[Peter Kim Frank]

I love seeing the iterations of your solutions. Not that this challenge was intended to have any "winners," but if we had to choose...

Do you have any ideas for new #challenge posts?

[Heiko Dudzus]

Thanks. I enjoyed learning about Kaprekar number as well as I enjoyed iterating my solutions as I digged deeper into it.

You encouraged me to pose a challenge, hoping it's not too easy and not too hard. dev.to/heikodudzus/challenge---pri...

BTW: I saw a possible error in my last iteration. takeWhile (<n) is not proven to be correct. It's better to do it that way:

isKaprekar base n = let sqr = n^2 in
  elem 0 $                              -- any remainder = 0? <=> is kaprekar!
  map (\div -> (sqr-n) `mod` (div-1)) $ -- compute the critical remainders
  takeWhile (<sqr) $ dropWhile (<=n) $  -- sensible bounds for divisors
  map (base^) [1..]                     -- infinite list of divisors

main = print $ 1:(filter (isKaprekar 10) [1..10^5])

Also, it's nicer to use upper and lower bounds for divisors before computing the devisions. This is proven to be correct now, but I lost speed. ;-) The speed improvement by melting construction and restriction together is only 86% instead of 96%.

[Heiko Dudzus]

Some last improvements:

1. Use fixed-width Ints instead of arbitrary sized Integers (by function signature) Large improvement!
2. It pays off to spend an additional modulo division if the number of possible divisors for the critical division can be heavily reduced.
3. 'any' slightly outperforms 'elem'. (in this case?)
4. A hand-rolled recursion sometimes performs better (without additional division) and sometimes worse (with additional division) than the folding recursions hidden in the 'elem' or 'any' functions. (But code with builtin folds is much nicer to read.)

The improvement steps were: 1000s - 500s - 90s - 60s - 19s - 13s - 9s. Quite funny to squeeze the algorithm like that. :-) This is what I came up with:

isKaprekar :: Int -> Int -> Bool
isKaprekar base n = let sqr = n^2 in
  any (\div -> (sqr-n) `mod` (div-1) == 0) $ -- any rem = 0? <=> kaprekar!
  takeWhile (\div -> (sqr `mod` div) < n) $  -- sensible bounds for divisors
  dropWhile (<=n) $                          
  map (base^) [1..]                          -- infinite list of divisors

main = print $ 1:(filter (isKaprekar 10) [1..10^8])

I wanted to have it in C for reference. Even expressed imperatively, it is now a very simple and nice algorithm. (2-3s)

#include <stdio.h>

int isKaprekar (int b, long long n) {
  long long sqr = n*n;
  long long div = 1;
  while (div <= n) div *= b;
  while (sqr % div < n) {
    if ((sqr - n) % (div - 1) == 0) return 1;
    div *= b;
  }
  return 0;
}

int main() {
  int base = 10;
  printf("%i ", 1);
  for (long long n=2; n<=100000000; n++) {
    if (isKaprekar(base,n)) printf("%i ", n);
  }
  return 0;
}

C profited more by the additional division, it reduced the execution time by 75%, Haskell profited only by 50 %.

I hope, I'm really done, now. :)

[Josha von Gizycki]

Time to get my repl up and running. Not very clean, but gets the job done. Here's some Clojure:

(ns kaprekar)

(defn is-kap? [n]
  (let [square (* n n)
        ss (str square)
        length (count ss)
        ss (if (odd? length) (str "0" ss) ss)
        length (count ss)
        half-length (/ length 2)
        first-half (bigint (subs ss 0 half-length))
        second-half (bigint (subs ss half-length))]
    (= n (+ first-half second-half))))

(defn find-kaps []
  (loop [i 1 found 0]
    (if (is-kap? i)
      (do
        (println i)
        (when (< found 7)
          (recur (inc i) (inc found))))
      (recur (inc i) found))))

Thanks to Richard Orelup' tip to zero-pad the number if its length is odd.

[Josha von Gizycki]

Taking inspiration from Thomas Much's answer, I refactored my code to be more functional-esque and idiomatic:

(ns kaprekar)

(defn is-kap? [n]
  (let [square (* n n)
        ss (str square)
        length (count ss)
        ss (if (odd? length) (str "0" ss) ss)
        length (count ss)
        half-length (/ length 2)
        first-half (bigint (subs ss 0 half-length))
        second-half (bigint (subs ss half-length))]
    (= n (+ first-half second-half))))

(defn find-kaps []
  (->>
    (iterate inc 1)
    (filter is-kap?)
    (take 8)
    (run! println)))

[WammKD]

For those a fan of Guile:

(use-modules (srfi srfi-1))

(let find-kaprekars ([kaprekars '()] [currNum 1])
  (if (= (length kaprekars) 8)
      (reverse kaprekars)
    (if (let ([cnStr (string-append "0" (number->string (expt currNum 2)))])
          (any
            (lambda (index)
              (let ([scndPart (string->number (substring cnStr index))])
                (if (zero? scndPart)
                    #f
                  (=
                    (+ (string->number (substring cnStr 0 index)) scndPart)
                    currNum))))
            (iota (1- (string-length cnStr)) 1)))
        (find-kaprekars (cons currNum kaprekars) (1+ currNum))
      (find-kaprekars kaprekars (1+ currNum)))))

[Asfo]

I'm not pretty good at coding but I tried in my own way :) just for fun and I hope is ok.

Here is my JS version:

var numbers = [1, 9, 45, 55, 99, 297, 703, 999];
console.log("Kaprekar");
for (var i = 0; i < numbers.length; i++) {
  var sq = numbers[i] * numbers[i];
  if (sq.toString().length % 2 === 0) {
    var kap = sq.toString().split("");
    var left = "";
    var right = "";
    for (var j = 0; j < kap.length; j++) {
      if (j < kap.length / 2) {
        left += kap[j].toString();
      } else {
        right += kap[j].toString();
      }
    }
    if ((parseInt(left) + parseInt(right)) === numbers[i]) {
      console.log(numbers[i] + "^2 = " + sq + " -> " + left + " + " + right + " = " + (parseInt(left) + parseInt(right)));
    }
  } else {
    console.log(numbers[i] + " Is not Kaprekar");
  }
}

Here is the JSFiddle link:
jsfiddle.net/kw95nv45/2/

[Heiko Dudzus]

Solution in Haskell:

I didn't want to take the route to String representation and back, I considered it as a computational problem and I wanted to find a purely computational solution. So I used digit values. Drawbacks: It appends number 1 as being kaprekar by convention. Benefit: It works for all bases (although output is decimal).

f base n =
  map ((+) <$> fst <*> snd) $
  filter ((/= 0).snd) $ takeWhile ((/=0).fst) $
  map ((quotRem (n^2)).(base^)) [1..]

kaprekar base = (1:) $ filter (elem <*> f base) [1..999]

f is like:

1. Divide the square by all powers of the base. -> infinite list of possibilities to split the number.
2. quotRem builds a tuple of integer quotient and remainder.
3. Keep the list entries until the quotient gets 0 to make the list finite. (Nothing interesting is happening beyond that point).
4. Remove the entries having a remainder of 0.
5. Build the sum of quotient and remainder.

f returns a list of sums of quotient and remainder. Now filter in the solution function, if n is an element of f n.

[Heiko Dudzus]

I tried to compute the Kaprekar numbers up to 10^8. A simple improvement in taking the interesting part and dropping the rest: If quotient or remainder are > n the sum of both must be > n. This reduced execution time by 50 %.

f base n =
  map ((+) <$> fst <*> snd) $
  takeWhile ((<n).snd) $ dropWhile ((>=n).fst) $
  map ((quotRem (n^2)).(base^)) [1..]

kaprekar n base = (1:) $ filter (elem <*> f base) [1..n]

[0nomat0]

Could I trouble someone to comment this code? Oops, I guess that's in the parent comment, thanks! I don't know Haskell but I'm interested in it. Does this solution work for the 'strange' ones like 4789, 5292?

Trying to wrap my head around how to interpret the definition of a Kaprekar number, in a way that includes these oddball numbers.

I'm currently studying Ruby -- I'll necro-post my Ruby solution if I manage to get it working with the oddballs.

[Mervin]

Here is my Javascript version of Kaprekar numbers

function getSubInt(str, start, end){
    if(end == undefined)
        return parseInt(str.substring(start)) || 0;
    return parseInt(str.substring(0, end)) || 0;
}

function getKaprekar(max){
    var kaprekar = [], count = 0;

    for(var i = 1; count < max; i++){
        var sqr = (i * i).toString();
        var middle = (sqr.length / 2);

        if((getSubInt(sqr, 0, middle) + getSubInt(sqr, middle)) === i){
            kaprekar.push(i);
            count++;
        }
    }

    return kaprekar;
}

console.log(getKaprekar(8).toString());

[Heiko Dudzus]

As far as I can see, most (if not all) programs use the strategy to convert the square to a string, pad it with 0 if the length is not even, and split it in the middle.

This seems to work for the range of Kaprekar numbers in the given range [1..999]. However, when I tried to speed up my program by splitting in the middle, I found out a problem with 5292. It is a Kaprekar number:

Prelude> 5292^2
28005264
Prelude> 28 + 005264
5292
Prelude>

But to recognize it, you have to split 2 and 6 of 8 digits.

The implicit assumption about the Kaprekar property to show up when the number is split in the middle seems to be wrong. I tested some Javascript programs of this challenge with 5292 and it is not recognized as Kaprekar number.

[Peter Kim Frank]

Dang, that's a great point. I should have made the OP more detailed to clarify that the "split" isn't always right down the middle — even if it happens to work in the [1...999] range.

I definitely didn't think of that possibly while creating the post, or while working on my personal solution.

What does your approach to this look like? Now you've got me curious about how you're going about solving it. NVM, now I see your other comment.

[Heiko Dudzus]

Is anyone interested in finding another 'strange' Kaprekar number like 5292?

I searched among the first 91 Kaprekar numbers in the range [ 1..10⁸ ]. So far, 5252 is the only one you have to split asymmetrically.

What makes 5292 so special?

[Thomas Much]

4879 is 'strange', too:
4879 = 238 + 04641

[Heiko Dudzus]

Ok, I see. I've missed it because of the leading zero in the second part.

[Heiko Dudzus]

I think your OP is really ok. I also didn't expect something like this. I think I will inspect some higher Kaprekar number.

But I am looking forward to see how the JS/Java/Clojure/LISP-like solutions get fixed (and I apologize for beeing such a killjoy ;-)

[Richard Orelup]

This was a lot harder than I thought mainly because I had to look up why some numbers were and weren't Kaprekar numbers because the above description doesn't include all the details. First gotcha is the second part of the split numbers must be positive (no zeros). The second part was that you add a zero to the front if the length is odd.

<?php

$kaprekarNumbers = array();
$i = 1;

while (count ($kaprekarNumbers) < 8) {

  $square = $i * $i;
  if (strlen((string)$square) % 2  === 0) {
    $splitLength = strlen((string)$square) / 2;
  } else {
    $splitLength = round(strlen((string)$square) / 2);
    $square = "0".(string)$square;
  }

  $splitSquare = str_split((string)$square, $splitLength);

  if ((int)$splitSquare[1] != 0 && (int)$splitSquare[0]+(int)$splitSquare[1] == $i) {
    $kaprekarNumbers[] = $i;
  }

  $i++;
}


print_r($kaprekarNumbers);


?>

[Richard Orelup]

And I already refactored my answer. I'm happier with this one.

<?php

$kaprekarNumbers = array();
$i = 1;

while (count ($kaprekarNumbers) < 8) {

  $square = $i * $i;

  $splitLength = round(strlen((string)$square) / 2, 0, PHP_ROUND_HALF_DOWN);

  $splitFront = substr((string)$square, 0, $splitLength);
  $splitBack = substr((string)$square, $splitLength - strlen((string)$square));

  if ((int)$splitFront+(int)$splitBack == $i) {
    $kaprekarNumbers[] = $i;
  }

  $i++;
}

echo "\n\n".implode(",",$kaprekarNumbers)."\n\n";

?>

[Peter Kim Frank]

Awesome job refactoring, and apologies for not including the pertinent info re: zeros in the OP!! I'll add that info to the main post.

[Peter Kim Frank]

Figure it's only fair to throw my answer into the ring. Clearly very novice and verbose 😇. Added a number of comments for the other #beginners out there.

var kap = function(number){ 

    var whole = number.toString(); // convert number to string

    if(whole.length % 2 !== 0){ // if the length is odd, add a zero to the front
        whole = "0" + whole; // IE 123 becomes 0123
    }

    var middle = whole.length/2; // find the index of the middle and end of the string
    var end = whole.length;

    var piece1 = whole.slice(0,middle); // break it into two pieces
    var piece2 = whole.slice(middle,end);

    piece1 = parseInt(piece1); // convert back to numbers
    piece2 = parseInt(piece2);

    var final = piece1 + piece2; // add them together

    return final; // return result
}

for(i = 1; i < 1000; i++){ // simple for loop from 1 to 1,000

    var squared = i*i;
    var kapval = kap(squared);

    if(i == kapval){ // sees if they match
        console.log(i);
    }
}

[Thomas Much]

Ok, here's a Java 8 version:

import java.util.function.IntPredicate;
import java.util.stream.IntStream;

public class FirstEightKaprekarNumbers {

  public static void main(String... args) {

    IntPredicate isKaprekar = i -> {
      String square = String.valueOf(i*i);
      String padded = (square.length() % 2 == 0) ? square : "0" + square;
      int halfLen = padded.length() / 2;
      int left = Integer.parseInt(padded.substring(0, halfLen));
      int right = Integer.parseInt(padded.substring(halfLen));
      return i == left + right;
    };

    IntStream.iterate(1, i -> i + 1).filter(isKaprekar).limit(8).forEach(System.out::println);
  }
}

[Thomas Much]

As Heiko points out, the solution was incorrect, because the split was always done in the middle of the string...

So, here's a (hopefully correct) Java 9 solution (Java 9 because I use takeWhile):

import java.util.function.IntPredicate;
import java.util.stream.IntStream;

public class FirstSixteenKaprekarNumbers {

  public static void main(String... args) {

    IntPredicate isKaprekar = i -> {
      long square = i * i;
      // first, generate a stream of possible 10-base divisors (if the left side is zero, we're done):
      return IntStream.iterate(10, div -> div * 10).takeWhile(div -> square / div > 0)
          // then, filter out zero right sides:
          .filter(div -> square % div > 0)
          // finally, see if the sum of the parts match the original number:
          .anyMatch(div -> i == square / div + square % div);
    };

    IntStream.concat(IntStream.of(1), IntStream.iterate(2, i -> i + 1).filter(isKaprekar))
      .limit(16)
      .forEach(System.out::println);

    // 1, 9, 45, 55, 99, 297, 703, 999, 2223, 2728, 4879, 4950, 5050, 5292, 7272, 7777
  }
}

I chose to output the first 16 numbers so we can see the output includes numbers 4879 and 5292.

[Heiko Dudzus]

I really like to see your use of Streams and lambdas solving this problem. Nice occasion for me to learn a little bit more about them.