Kaprekar numbers

Kaprekar numbers
You are encouraged to solve this task according to the task description, using any language you may know.

A positive integer is a Kaprekar number if it is 1, or if the string representation of its square can be split once into parts that when summed add up to the original number.

For example 2223 is a Kaprekar number as 2223*2223 == 4941729 and 494 + 1729 == 2223

The series of Kaprekar numbers begins: 1, 9, 45, 55, ....

The task is to generate and show all the Kaprekar numbers less than 10,000

As a stretch goal count and show how many Kaprekar numbers there are that are less than one million.

Reference

• The Kaprekar Numbers by Douglas E. Iannucci (2000). PDF version

Note

In comparing splits of the square, a split of all zeroes is not counted - as zero is not considered positive.

Example: 10000 (100²) splitting from left to right: The first split is [1, 0000], which is not OK because "a split of all zeroes is not counted - as zero is not considered positive". Slight optimization opportunity: When splitting from left to right, once the right part becomes all zeroes, you don't need to test this number anymore because its splits will always be invalid.

D

<lang d>import std.stdio, std.conv, std.algorithm, std.range;

bool isKaprekar(long n) in {

   assert(n > 0);

} body {

   if (n == 1) return true;
   auto sn = text(n ^^ 2);
   foreach (i; 1 .. sn.length) {
       long a = to!long(sn[0 .. i]);
       long b = to!long(sn[i .. $]);
       if (b && a + b == n) return true;
   }
   return false;

}

void main() {

   writeln(filter!isKaprekar(iota(1, 10_000)));
   writeln(count!isKaprekar(iota(1, 1_000_000)));

}</lang> Output:

[1, 9, 45, 55, 99, 297, 703, 999, 2223, 2728, 4879, 4950, 5050, 5292, 7272, 7777, 9999]
54

Fortran

Works with: Fortran version 95 and later

<lang fortran>program Karpekar_Numbers

 implicit none
  
 integer, parameter :: i64 = selected_int_kind(18)
 integer :: count 

 call karpekar(10000_i64, .true.)
 write(*,*)
 call karpekar(1000000_i64, .false.)
 

contains

subroutine karpekar(n, printnums)

 integer(i64), intent(in) :: n
 logical, intent(in) :: printnums
 integer(i64) :: c, i, j, n1, n2
 character(19) :: str, s1, s2
 
 c = 0
 do i = 1, n
   write(str, "(i0)") i*i
   do j = 0, len_trim(str)-1
     s1 = str(1:j)
     s2 = str(j+1:len_trim(str)) 
     read(s1, "(i19)") n1
     read(s2, "(i19)") n2
     if(n2 == 0) cycle
     if(n1 + n2 == i) then
       c = c + 1
       if (printnums .eqv. .true.) write(*, "(i0)") i
       exit
     end if
   end do    
 end do
 if (printnums .eqv. .false.) write(*, "(i0)") c

end subroutine end program</lang> Output

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

54

J

Solution: <lang j>kapbase=: 0,.10 ^ 1 + [: i. 1 + 10 <.@^. >.&1 isKap=: 1 e. (((0 < {:"1@]) *. [ = +/"1@]) (kapbase #: ])@*:)</lang>

Example use:

<lang j> I. isKap"0 i.1e6 1 9 45 55 99 297 703 999 2223 2728 4879 4950 5050 5292 7272 7777 9999 17344 22222 38962 77778 82656 95121 99999 142857 148149 181819 187110 208495 318682 329967 351352 356643 390313 461539 466830 499500 500500 533170 538461 609687 627615 643357 648648 670033 681318 791505 812890 818181 851851 857143 961038 994708 999999</lang>

Alternative solution: The following is a more naive, mechanical solution <lang j>splitNum=: {. ,&(_&".) }. allSplits=: (i.&.<:@# splitNum"0 1 ])@": sumValidSplits=: +/"1@:(#~ 0 -.@e."1 ]) filterKaprekar=: #~ ] e."0 1 [: sumValidSplits@allSplits"0 *:</lang>

Example use: <lang j> filterKaprekar i. 10000 0 9 45 55 99 297 703 999 2223 2728 4879 4950 5050 5292 7272 7777 9999

  #filterKaprekar i. 1e6

54</lang>

Java

<lang java>public class Kaprekar {

   private static String[] splitAt(String str, int idx){
       String[] ans = new String[2];
       ans[0] = str.substring(0, idx);
       if(ans[0].equals("")) ans[0] = "0"; //parsing "" throws an exception
       ans[1] = str.substring(idx);
       return ans;
   }
       
   public static void main(String[] args){
       int count = 0;
       for(long i = 1; i <= 1000000; i++){
           String sqrStr = Long.toString(i * i);
           for(int j = 0; j < sqrStr.length(); j++){
               String[] parts = splitAt(sqrStr, j);
               long firstNum = Long.parseLong(parts[0]);
               long secNum = Long.parseLong(parts[1]);
               //if the right part is all zeroes, then it will be forever, so break
               if(secNum == 0) break;
               if(firstNum + secNum == i){
                   System.out.println(i);
                   count++;
                   break;
               }
           }
       }
       System.out.println(count + " Kaprekar numbers < 1000000");
   }

}</lang> Output (shortened):

1
9
45
55
99
297
703
999
2223
2728
4879
4950
5050
5292
7272
7777
9999
...
818181
851851
857143
961038
994708
999999
54 Kaprekar numbers < 1000000

PARI/GP

<lang parigp>K(d)={

 my(D=10^d,DD,t,v=List());
 for(n=D/10+1,D-1,
   t=divrem(n^2,D);
   if(t[2]&t[1]+t[2]==n,listput(v,n);next);
   DD=D;
   while(t[2]<n,
     t=divrem(n^2,DD*=10);
     if(t[2]&t[1]+t[2]==n,listput(v,n);next(2))
   );
   DD=D;
   while(t[1]<n,
     t=divrem(n^2,DD/=10);
     if(t[2]&t[1]+t[2]==n,listput(v,n);next(2))
   )
 );
 Vec(v)

}; upTo(d)=my(v=[1]);for(n=1,d,v=concat(v,K(n)));v; upTo(4) v=upTo(6);v

1. v</lang>

Output:

%1 = [1, 9, 45, 55, 99, 297, 703, 999, 2223, 2728, 4879, 4950, 5050, 5292, 7272, 7777, 9999]

%2 = [1, 9, 45, 55, 99, 297, 703, 999, 2223, 2728, 4879, 4950, 5050, 5292, 7272, 7777, 9999, 17344, 22222, 38962, 77778, 82656, 95121, 99999, 142857, 148149, 181819, 187110, 208495, 318682, 329967, 351352, 356643, 390313, 461539, 466830, 499500, 500500, 533170, 538461, 609687, 627615, 643357, 648648, 670033, 681318, 791505, 812890, 818181, 851851, 857143, 961038, 994708, 999999]

%3 = 54

Perl 6

<lang perl6>sub kaprekar( Int $n ) {

   my $sq = $n ** 2;
   for 0 ^..^ $sq.chars -> $i {
       my $x = +$sq.substr(0, $i);
       my $y = +$sq.substr($i) || return;
       return True if $x + $y == $n;
   }
   False;

}

print 1; print " $_" if .&kaprekar for ^10000; print "\n";</lang>

Output:

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

Note that we check only the second part for 0 since the first must start with a non-zero digit.

PicoLisp

<lang PicoLisp>(de kaprekar (N)

  (let L (cons 0 (chop (* N N)))
     (for ((I . R) (cdr L) R (cdr R))
        (NIL (gt0 (format R)))
        (T (= N (+ @ (format (head I L)))) N) ) ) )</lang>

Output:

: (filter kaprekar (range 1 10000))
-> (1 9 45 55 99 297 703 999 2223 2728 4879 4950 5050 5292 7272 7777 9999)

: (cnt kaprekar (range 1 1000000))
-> 54

Python

(Swap the commented return statement to return the split information). <lang python>>>> def k(n): n2 = str(n**2) for i in range(len(n2)): a, b = int(n2[:i] or 0), int(n2[i:]) if b and a + b == n: return n #return (n, (n2[:i], n2[i:]))

>>> [x for x in range(1,10000) if k(x)] [1, 9, 45, 55, 99, 297, 703, 999, 2223, 2728, 4879, 4950, 5050, 5292, 7272, 7777, 9999] >>> len([x for x in range(1,1000000) if k(x)]) 54 >>> </lang>

Tcl

<lang tcl>package require Tcl 8.5; # Arbitrary precision arithmetic, for stretch goal only proc kaprekar n {

   if {$n == 1} {return 1}
   set s [expr {$n * $n}]
   for {set i 1} {$i < [string length $s]} {incr i} {

scan $s "%${i}d%d" a b if {$b && $n == $a + $b} { return 1 #return [list 1 $a $b] }

   }
   return 0

}

1. Base goal

for {set i 1} {$i < 10000} {incr i} {

   if {[kaprekar $i]} {lappend klist $i}

} puts [join $klist ", "]

1. Stretch goal

for {set i 1} {$i < 1000000} {incr i} {

   incr kcount [kaprekar $i]

} puts "$kcount Kaprekar numbers less than 1000000"</lang> Output:

1, 9, 45, 55, 99, 297, 703, 999, 2223, 2728, 4879, 4950, 5050, 5292, 7272, 7777, 9999
54 Kaprekar numbers less than 1000000