DEV Community

Challenge: find 'Kaprekar numbers'

Peter Kim Frank on November 13, 2017

I saw this tweet over the weekend— // Detect dark theme var iframe = document.getElementById('tweet-929715470655254535-889'); if (documen...
Read full post
Collapse
 
heikodudzus profile image
Heiko Dudzus • • Edited

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]
Collapse
 
peter profile image
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?

Collapse
 
heikodudzus profile image
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%.

Thread Thread
 
heikodudzus profile image
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. :)

Collapse
 
joshavg profile image
Josha von Gizycki • • Edited

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.

Collapse
 
joshavg profile image
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)))
Collapse
 
asfo profile image
Asfo • • Edited

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/

Collapse
 
heikodudzus profile image
Heiko Dudzus • • Edited

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.

Collapse
 
heikodudzus profile image
Heiko Dudzus • • Edited

I tried to compute the Kaprekar numbers up to 108. 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]
Collapse
 
0nomat0 profile image
0nomat0 • • Edited

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.

Collapse
 
wammkd_64 profile image
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)))))
Collapse
 
heikodudzus profile image
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.

Collapse
 
peter profile image
Peter Kim Frank • • Edited

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.

Collapse
 
heikodudzus profile image
Heiko Dudzus • • Edited

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

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

What makes 5292 so special?

Thread Thread
 
thmuch profile image
Thomas Much •

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

Thread Thread
 
heikodudzus profile image
Heiko Dudzus •

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

Collapse
 
heikodudzus profile image
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 ;-)

Collapse
 
mervinsv profile image
Mervin • • Edited

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());
Collapse
 
danieljsummers profile image
Daniel J. Summers • • Edited

OK - this was way more of a rabbit hole than I thought... :) Here's two, new (F#) and old (COBOL). Both of these work within the constraints of the initial challenge, but will fail outside of that; had I not spent the amount of time I already spent on these, I might have at least made the F# version be able to handle others.

p.s. 0 also fits the description from the tweet! (02 = 0; 00 = 0 + 0 = 0; 0 = 0)

F#

[<EntryPoint>]
let main _ =
  Seq.initInfinite (fun nbr ->
    let square = nbr * nbr
    let split =
      match square with
      | _ when square >= 10000 -> 1000
      | _ when square >= 100 -> 100
      | _ -> 10
    let topHalf = square / split
    let bottomHalf = square % split
    topHalf + bottomHalf = nbr, nbr)
  |> Seq.filter fst
  |> Seq.skip 1
  |> Seq.take 8
  |> Seq.map (fun pair -> (snd >> string) pair)
  |> Seq.reduce (fun acc nbr -> sprintf "%s, %s" acc nbr)
  |> System.Console.WriteLine
  0

COBOL

(Free format, "*>" denotes a comment)

identification division.
  program-id. kaprekar.
data division.
  working-storage section.
    77 current-nbr   pic 9(4)  value zeroes.
    77 square        pic 9(6)  value zeroes.
    77 split         pic 9(6)  value zeroes.
    77 top-half      pic 9(3)  value zeroes.
    77 bottom-half   pic 9(3)  value zeroes.
    77 sum-of-halves pic 9(6)  value zeroes.
    01 kap-numbers             value all zeroes.
       03 result     pic 9(3)  occurs 100 times indexed by accrue-idx, display-idx.
    77 results       pic x(80) value spaces.
    77 results-ptr   pic 9(2)  value 1.
    77 formatted-nbr pic x(3)  value spaces.
procedure division
. calculate-kaprekars.
  set accrue-idx to 1
  perform varying current-nbr from 1 by 1 until current-nbr > 999
    multiply current-nbr by current-nbr giving square
    *> Determine the split for the square
    evaluate true
      when square >= 10000
        move 1000 to split
      when square >= 100
        move 100 to split
      when other
        move 10 to split
    end-evaluate
    *> Split, sum, and compare
    divide square by split giving top-half remainder bottom-half
    add top-half bottom-half giving sum-of-halves
    if sum-of-halves = current-nbr
      move current-nbr to result(accrue-idx)
      set accrue-idx up by 1
    end-if
  end-perform
  set accrue-idx down by 1
  perform varying display-idx from 1 by 1 until display-idx > accrue-idx
    *> Left-justified numbers
    evaluate true
      when result(display-idx) < 10
        move result(display-idx)(3:1) to formatted-nbr
      when result(display-idx) < 100
        move result(display-idx)(2:2) to formatted-nbr
      when other
        move result(display-idx) to formatted-nbr
    end-evaluate
    string formatted-nbr delimited by space into results with pointer results-ptr
    if display-idx not = accrue-idx
      string ', ' into results with pointer results-ptr
    end-if
  end-perform
  display results
  goback
.
end program kaprekar.
Collapse
 
danieljsummers profile image
Daniel J. Summers •

OK - fixed format, just for grins...

(Fixed format: col 1-6 reserved, usually line numbers or blank; col 7 - "*" = comment, blank otherwise; col 8-11 - division/section identifiers, paragraph names, top-level data items; col 12-72 - executable code, data item sub-definitions; col 73+ - ignored)

       identification division.
         program-id. kaprekar.
       data division.
         working-storage section.
       77  current-nbr   pic 9(4)  value zeroes.
       77  square        pic 9(6)  value zeroes.
       77  split         pic 9(6)  value zeroes.
       77  top-half      pic 9(3)  value zeroes.
       77  bottom-half   pic 9(3)  value zeroes.
       77  sum-of-halves pic 9(6)  value zeroes.
       01  kap-numbers             value all zeroes.
           03  result    pic 9(3)  occurs 100 times
                                     indexed by accrue-idx,
                                                display-idx.
       77  results       pic x(80) value spaces.
       77  results-ptr   pic 9(2)  value 1.
       77  formatted-nbr pic x(3)  value spaces.
       procedure division
       . calculate-kaprekars.
           set accrue-idx to 1
           perform varying current-nbr from 1 by 1
             until current-nbr > 999
               multiply current-nbr by current-nbr giving square
      *>       Determine the split for the square
               evaluate true
                   when square >= 10000
                       move 1000 to split
                   when square >= 100
                       move 100 to split
                   when other
                       move 10 to split
               end-evaluate
      *>       Split, sum, and compare
               divide square by split giving top-half
                 remainder bottom-half
               add top-half bottom-half giving sum-of-halves
               if sum-of-halves = current-nbr
                   move current-nbr to result(accrue-idx)
                   set accrue-idx up by 1
               end-if
           end-perform
           set accrue-idx down by 1
           perform varying display-idx from 1 by 1
             until display-idx > accrue-idx
      *>       Left-justified numbers
               evaluate true
                   when result(display-idx) < 10
                       move result(display-idx)(3:1) to formatted-nbr
                   when result(display-idx) < 100
                       move result(display-idx)(2:2) to formatted-nbr
                   when other
                       move result(display-idx) to formatted-nbr
               end-evaluate
               string formatted-nbr delimited by space into results
                 with pointer results-ptr
               if display-idx not = accrue-idx
                   string ', ' into results with pointer results-ptr
               end-if
           end-perform
           display results
           goback
       .
       end program kaprekar.
Collapse
 
danieljsummers profile image
Daniel J. Summers •

Holy cow - the formatter knows COBOL! If I'd used fixed format, it wouldn't even look weird.

Collapse
 
ripsup profile image
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);


?>
Collapse
 
ripsup profile image
Richard Orelup • • Edited

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";

?>
Collapse
 
peter profile image
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.

Collapse
 
thmuch profile image
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);
  }
}
Collapse
 
thmuch profile image
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.

Collapse
 
heikodudzus profile image
Heiko Dudzus • • Edited

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.

Collapse
 
yondrin profile image
Alex Doroshenko •

Seems I'm pretty late for this, but anyway, here's some Rust solution:

fn main() {
    (1usize..)
        .into_iter()
        .filter(is_kaprekar)
        .take(8)
        .for_each(|num| println!("{}", num));
}

fn is_kaprekar(n: &usize) -> bool {
    split_num(n * n).iter().sum::<usize>() == *n
}

fn split_num(num: usize) -> [usize; 2] {
    let num_str = num.to_string();
    let len = num_str.len();

    let (left, right) = num_str.split_at(len / 2);

    [as_usize(left), as_usize(right)]
}

fn as_usize(n: &str) -> usize {
    n.parse().unwrap_or(0)
}
Collapse
 
yondrin profile image
Alex Doroshenko • • Edited

And if you consider that parts of a number should not necessarily be of equal size, the solution becomes a bit more wordy (suppose, a lot can be improved here):

fn main() {
    (1usize..)
        .into_iter()
        .filter(is_kaprekar)
        .take(8)
        .for_each(|num| println!("{}", num));
}

fn is_kaprekar(num: &usize) -> bool {
    NumberParts::of(num * num)
        .any(|(left, right)| {
            right > 0 && left + right == *num
        })
}

struct NumberParts {
    original_number: usize,
    split_position: usize,
}

impl NumberParts {
    fn of(original_number: usize) -> Self {
        NumberParts {
            original_number,
            split_position: 10usize.pow(
                (original_number as f64).log(10f64) as u32 + 1,
            ),
        }
    }
}

impl Iterator for NumberParts {
    type Item = (usize, usize);

    fn next(&mut self) -> Option<Self::Item> {
        let split = self.split_position;

        if split == 1 {
            None
        } else {
            self.split_position /= 10;
            Some((
                self.original_number / split,
                self.original_number % split,
            ))
        }
    }
}
Collapse
 
heikodudzus profile image
Heiko Dudzus • • Edited

I have much sympathy for LISP and Clojure but have not that much experience with it. So, to stay in touch with it, here is my Clojure program, mostly a one-to-one translation of my latest Haskell program:

(ns kaprekar.core
  (:gen-class))
(use '[clojure.math.numeric-tower :as math])

(defn isKaprekar?
  [base n]
  (let [sqr (* n n)]
    (->>
     (map #(math/expt base %1) (range))          ; list of divisors
     (drop-while #(<= %1 n))                     ; discard if too small
     (take-while #(< %1 sqr))                    ; discard if too big
     (some #(= 0 (mod (- sqr n) (- %1 1)))))))   ; remainder = 0? <=> kaprekar

(defn findKaprekar
  [base n]
  (->>
   (range n)
   (filter #(isKaprekar? base %1))
   (cons 1))) 

(defn -main
  "Finding the Kaprekar number base 10 up to 10000000"
  [& args]
  (time (print (findKaprekar 10 (math/expt 10 8)))))

I really like the threading macros. :-) Computing up to 10^8 , the execution time of the jar file is ten times the execution time of the compiled Haskell. Did I make a serious mistake, performance-wise? Of course, there is the JVM, but I didn't expect this program to be slower with factor 10.

Collapse
 
0nomat0 profile image
0nomat0 • • Edited

Here's my Ruby novice solution -- Works for the known oddballs (4879, 5292, 38962). Prepending '0' to odd-sized numbers inspired by others here.

def kaprekar?(k)
  s = k.to_s.size    # s = nr. of digits in k
  k_sq = (k**2).to_s    # k_sq = square of k (String)
  k_sq.prepend("0") if (k_sq.size.even? == false)    # prepend '0' to odd-sized numbers
  if k_sq[s-1] == "0"    # if digit 's-1' is 0, loop different combinations
    (0..s).each do |x|
      part1 = k_sq[0..x-1].to_i
      part2 = k_sq[x..-1].to_i
      return true if (k == part1 + part2)
    end
  else    # if not, split before digit 's' (Integers)
    part1 = k_sq[0..s-1].to_i
    part2 = k_sq[s..-1].to_i
    return true if k == (part1 + part2)
  end
  false    # else returns false
end
Collapse
 
0nomat0 profile image
0nomat0 • • Edited

I don't like the exceptions (4879, 5292, 38962...) -- it feels like they don't belong in the sequence. And look how pretty the code is without them!

  def kaprekar?(k)
    s = k.to_s.size
    k_sq = (k**2).to_s
    k_sq.prepend("0") if (k_sq.size.even? == false)
    part1 = k_sq[0..s-1].to_i
    part2 = k_sq[s..-1].to_i
    return true ? k == part1 + part2 : false
  end
Collapse
 
rockympls profile image
Rocky de Vries • • Edited

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
    }
}
Collapse
 
ayumukasuga profile image
Andrey Kostakov • • Edited

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)])
Collapse
 
cgortaris profile image
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
Collapse
 
peter profile image
Peter Kim Frank • • Edited

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