Kaprekar numbers

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

In this task, generate and show all Kaprekar numbers less than 10,000. For extra credit, count (and report the count of) how many Kaprekar numbers are less than 1,000,000.

A positive integer is a Kaprekar number if:

• It is 1
• The decimal representation of its square may be split once into two parts consisting of positive integers which sum to the original number. Note that a split resulting in a part consisting purely of 0s is not valid, as 0 is not considered positive.

Example Kaprekar numbers

• $2223$ is a Kaprekar number, as $2223*2223=4941729$, $4941729$ may be split to $494$ and $1729$, and $494+1729=2223$.
• The series of Kaprekar numbers begins is known as A006886, and begins as $1,9,45,55,...$.

Example process

10000 (100²) splitting from left to right:

• The first split is [1, 0000], and is invalid; the 0000 element consists entirely of 0s, and 0 is not considered positive.
• Slight optimization opportunity: When splitting from left to right, once the right part consists entirely of 0s, no further testing is needed; all further splits would also be invalid.

Reference

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

C

<lang C>#include <stdio.h>

typedef unsigned long long ulong;

int kaprekar(ulong n) {

   ulong nn = n * n, tens = 1; 

   while (tens < nn) tens *= 10;
   while ((tens /= 10) > n) {
       if (nn - n == (nn / tens) * (tens - 1))
           return 1;
   }

   return 1 == n;

}

int main() {

   ulong i;
   int cnt = 0;
   for (i = 1; i < 1000000; i++)
       if (kaprekar(i)) printf("%3d: %llu\n", ++cnt, i);

   return 0;

}</lang>

Output:

  1: 1
  2: 9
  3: 45
  4: 55
  5: 99
  6: 297
  .
  .
  .
 52: 961038
 53: 994708
 54: 999999

C++

<lang cpp>#include <vector>

1. include <string>
2. include <iostream>
3. include <sstream>
4. include <algorithm>
5. include <iterator>
6. include <utility>

long string2long( const std::string & s ) {

  long result ;
  std::istringstream( s ) >> result ;
  return result ;

}

bool isKaprekar( long number ) {

  long long squarenumber = ((long long)number) * number ;
  std::ostringstream numberbuf ;
  numberbuf << squarenumber ;
  std::string numberstring = numberbuf.str( ) ;
  for ( int i = 0 ; i < numberstring.length( ) ; i++ ) {
     std::string firstpart = numberstring.substr( 0 , i ) ,
                 secondpart = numberstring.substr( i ) ;
     //we do not accept figures ending in a sequence of zeroes
     if ( secondpart.find_first_not_of( "0" ) == std::string::npos ) {

return false ;

     }
     if ( string2long( firstpart ) + string2long( secondpart ) == number ) {

return true ;

     }
  }
  return false ;

}

int main( ) {

  std::vector<long> kaprekarnumbers ;
  kaprekarnumbers.push_back( 1 ) ;
  for ( int i = 2 ; i < 1000001 ; i++ ) {
     if ( isKaprekar( i ) ) 

kaprekarnumbers.push_back( i ) ;

  }
  std::vector<long>::const_iterator svi = kaprekarnumbers.begin( ) ;
  std::cout << "Kaprekar numbers up to 10000: \n" ;
  while ( *svi < 10000 ) {
     std::cout << *svi << " " ;
     svi++ ;
  }
  std::cout << '\n' ;
  std::cout << "All the Kaprekar numbers up to 1000000 :\n" ;
  std::copy( kaprekarnumbers.begin( ) , kaprekarnumbers.end( ) ,

std::ostream_iterator<long>( std::cout , "\n" ) ) ;

  std::cout << "There are " << kaprekarnumbers.size( )
     << " Kaprekar numbers less than one million!\n" ;
  return 0 ;

}</lang> Output:

Kaprekar numbers up to 10000: 
1 9 45 55 99 297 703 999 2223 2728 4879 4950 5050 5292 7272 7777 9999 
All the Kaprekar numbers up to 1000000 :
1
9
45
55
99
297
703
999
2223
2728
4879
4950
5050
5292
7272
7777
9999
17344
.....
818181
851851
857143
961038
994708
999999
There are 54 Kaprekar numbers less than one million!

D

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

bool isKaprekar(in long n) in {

   assert(n > 0, "isKaprekar(n) is defined for n > 0.");

} body {

   if (n == 1)
       return true;
   const auto sn = text(n ^^ 2);

   foreach (i; 1 .. sn.length) {
       const long a = to!long(sn[0 .. i]);
       const 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

Alternative version, right to left, produces same output

<lang d>bool isKaprekar(in long n) {

   ulong a = n * n, b = a % 10;
   for (ulong d = 1, t = 0; a > 0; d *= 10) {
       b += t * d;
       if (b > n) break;
       a /= 10;
       if (b && a + b == n) 
           return 1;
       t = a % 10;
   }
   return 0;

}</lang> This third version, from the C version, is more than ten times faster than the first version (same output):

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

pure nothrow bool isKaprekar(in long n) in {

   assert(n > 0, "isKaprekar(n) is defined for n > 0.");
   assert(n <= 3_162_277_660UL, "isKaprekar(n) overflow.");

} body {

   immutable ulong nn = n * n;
   ulong tens = 1;
   while (tens < nn)
       tens *= 10;

   while ((tens /= 10) > n)
       if (nn - n == (nn / tens) * (tens - 1))
           return true;

   return n == 1;

}

void main() {

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

}</lang>

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

GAP

<lang gap>IsKaprekar := function(n) local a, b, p, q; if n = 1 then return true; fi; q := n*n; p := 10; while p < q do a := RemInt(q, p); b := QuoInt(q, p); if a > 0 and a + b = n then return true; fi; p := p*10; od; return false; end;

Filtered([1 .. 10000], IsKaprekar);

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

Size(last);

1. 17

Filtered([1 .. 1000000], IsKaprekar);

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

Size(last);

1. 54</lang>

Icon and Unicon

<lang Icon>procedure is_kaprekar (n)

 if n = 1 then {suspend n; return}

 ns := string (n*n) # square and convert into a string
 every i := 2 to *ns do {
   l := integer (ns[1:i])
   r := integer (ns[i:0])
   if l > 0 & r > 0 & l + r = n then suspend n
 }

end

procedure main ()

 # main goal
 every i := 1 to 10000 do
   if is_kaprekar (i) then write (i)
 # stretch goal
 count := 0
 every i := 1 to 999999 do 
   if is_kaprekar (i) then count +:= 1
 write ("Number of Kaprekar numbers less than 1000000 is ", count)

end</lang>

Output:

1
9
45
55
99
297
703
999
2223
2728
4879
4950
5050
5292
7272
7777
9999
Number of Kaprekar numbers less than 1000000 is 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

<lang Perl>sub is_kaprekar {

       my $n = shift;
       return 1 if $n == 1;
       my $s = $n * $n;
       for (1 .. length($s)) {
               return 1 if substr($s, 0, $_) + (0 + substr($s, $_) || return) == $n;
       }

}

1. one million is a small number, let's brute force it

is_kaprekar($_) and print "$_\n" for 1 .. 1_000_000;</lang>

Output:

1
9
10
45
55
99
297
703
999
2223
2728
4879
.
.
.
851851
857143
961038
994708
999999

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

PureBasic

Translation of: C

<lang PureBasic>Procedure Kaprekar(n.i)

 nn.q  = n*n
 tens.q= 1
 While tens<nn: tens*10: Wend  
 Repeat
   tens/10
   If tens<=n: Break: EndIf
   If nn-n = (nn/tens) * (tens-1)
     ProcedureReturn #True
   EndIf
 ForEver
 If n=1
   ProcedureReturn #True
 EndIf

EndProcedure

If OpenConsole()

 For i=1 To 1000000
   If Kaprekar(i)  
     cnt+1
     PrintN(RSet(Str(cnt),3)+":"+RSet(Str(i),8))
   EndIf
 Next
 ;
 Print("Press ENTER to exit")
 Input()

EndIf</lang>

  1:       1
  2:       9
  3:      45
  4:      55
  5:      99
  6:     297
  7:     703
  8:     999
 ...........
 51:  857143
 52:  961038
 53:  994708
 54:  999999
Press ENTER to exit

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