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

[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/

[Carlos Gortaris]

Pythonic mine's:

import sys
# isKaprekar(): {1, ..., sqrt(sys.maxint)} -> {1, ..., sys.maxint}
def isKaprekar(i):
    powered = i*i
    s   = str(powered)
    mid = len(s)/2
    if mid == 0:
        return i == powered
    elif mid > 0:
        lefti   = int(s[:mid])
        righti  = int(s[mid:])
        return i == lefti + righti

i = int(sys.argv[1])
if i > 0 and i<=int(pow(sys.maxint, 1.0/2.0)):
    kaprekar = []
    for n in xrange(1, i):
        if isKaprekar(n):
            kaprekar.append(n)
    print("{}".format(kaprekar))
else: # bad input
    print("Bad input: {}".format(i))
    sys.exit(-1)

Usage: python script.py max
max is the maximum integer to look up to (3037000499):

>>> pow(sys.maxint, 1.0/2.0)
3037000499.97605

[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());

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

[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)))

[Andrey Kostakov]

Something like this in python

from itertools import count

def kaprekar_generator(n):
    c=0
    for x in count(1):
        x2 = str(x**2)
        if int(x2[:int(len(x2)/2)] if len(x2) > 1 else 0) + int(x2[int(len(x2)/2):]) == x:
            yield x
            c+=1
            if c >= n: break

print([x for x in kaprekar_generator(8)])

[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);
    }
}

[Rocky de Vries]

Because I haven't done Groovy for a while. I miss it!

(0..999).each { 
    def square = String.valueOf(it*it)
    def len = square.length()
    square = len % 2 != 0 ? "0$square" : square
    square = square.replaceAll(/.*0+$/,'')
    len = square.length()
    def half = Integer.valueOf((len / 2).toString())
    def side1 = square.substring(0, half)
    def side2 = square.substring(half)
    if (side1 && side2 && Integer.valueOf(side1) + Integer.valueOf(side2) == it) {
        println it
    }
}

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

[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)))))