Kaprekar numbers

From Rosetta Code
Revision as of 20:51, 3 July 2011 by rosettacode>Fwend (→‎{{header|D}}: better toBase version)
Task
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
  • is a Kaprekar number, as , may be split to and , and .
  • The series of Kaprekar numbers is known as A006886, and begins as .
Example process

10000 (1002) 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.
Extra extra credit

The concept of Kaprekar numbers is not limited to base 10 (i.e. decimal numbers); if you can, show that Kaprekar numbers exist in other bases too. For this purpose, do the following:

  • Find all Kaprekar numbers for base 17 between 1 and 1,000,000 (one million);
  • Display each of them in base 10 representation;
  • Optionally, using base 17 representation (use letters 'a' to 'g' for digits 10(10) to 16(10)), display each of the numbers, its square, and where to split the square. For example, 225(10) is "d4" in base 17, its square "a52g", and a5(17) + 2g(17) = d4(17), so the display would be something like:
    225   d4  a52g  a5 + 2g
Reference

C

Sample for extra extra credit: <lang C>#include <stdio.h> typedef unsigned long long ulong;

int kaprekar(ulong n, int base) { 

       ulong nn = n * n, tens = 1;

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

       return 1 == n;

}

void print_num(ulong n, int base) { 

       ulong q, div = base;

       while (div < n) div *= base;
       while (n && (div /= base)) {
               q = n / div;
               if (q < 10)     putchar(q + '0');
               else            putchar(q + 'a' - 10);
               n -= q * div;
       }

}

int main() { 

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

       base = 17;
       printf("\nbase %d:\n  1: 1\n", base);
       for (i = 2, cnt = 1; i < 1000000; i++)
               if ((tens = kaprekar(i, base))) {
                       printf("%3d: %llu", ++cnt, i);
                       printf(" \t"); print_num(i, base);
                       printf("\t");  print_num(i * i, base);
                       printf("\t");  print_num(i * i / tens, base);
                       printf(" + "); print_num(i * i % tens, base);
                       printf("\n");
               }

       return 0;

}</lang>Output: 

base 10:
  1: 1
  2: 9
  3: 45
  4: 55
  5: 99
  6: 297
  7: 703
  8: 999
  9: 2223
 10: 2728
 11: 4879
 12: 4950
 13: 5050
 14: 5292
 15: 7272
 16: 7777
 17: 9999
 ...
 47: 791505
 48: 812890
 49: 818181
 50: 851851
 51: 857143
 52: 961038
 53: 994708
 54: 999999

base 17:
  1: 1
  2: 16 	g	f1	f + 1
  3: 64 	3d	e2g	e + 2g
  4: 225 	d4	a52g	a5 + 2g
  5: 288 	gg	gf01	gf + 1
  6: 1536 	556	1b43b2	1b4 + 3b2
  7: 3377 	bbb	8093b2	809 + 3b2
  8: 4912 	ggg	ggf001	ggf + 1
  9: 7425 	18bd	24e166g	24e + 166g
 10: 9280 	1f1f	39b1b94	39b + 1b94
 ...
 21: 74241 	f1f2	d75f1b94	d75f + 1b94
 22: 76096 	f854	e1f5166g	e1f5 + 166g
 23: 83520 	gggg	gggf0001	gggf + 1
 24: 266224 	33334	a2c52a07g	a2c5 + 2a07g

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 <lang d>import std.stdio, std.string;

bool isKaprekar(long n, int base = 10, bool verbose = false) { 

   ulong a = n * n, b = a % base;

   for (ulong d = 1, t = 0; a > 0; d *= base) {
       b += t * d;
       if (b > n)
           break;
       a /= base;
       if (b && a + b == n) {
           if (verbose)
               writefln("%s\t%s\t%-10s\t%s + %s", n,
                        toBase(n, base), toBase(n * n, base),
                        toBase(a, base), toBase(b, base));
           return true;
       }
       t = a % base;
   }

   return false;

}

string toBase(long n, int b) in { 

   assert(2 <= b && b <= 35);

} body { 

   enum chars = digits ~ uppercase;
   long r = n % b;
   char c = chars[cast(size_t) abs(r)];
   if (n == r) {
       return (n < 0 ? "-" : "") ~ c;
   }
   return toBase((n - r) / b, b) ~ c;

}

void main() { 

   int count = 1;
   writeln("Base 10:");
   foreach (i; 1 .. 1_000_000)
       if (isKaprekar(i))
           writefln("%d: %d", count++, i);

   writeln("\nBase 17:");
   foreach (i; 1 .. 1_000_000)
       isKaprekar(i, 17, true);

}</lang> 

Base 10: 
1: 1
2: 9
3: 45
4: 55
5: 99
6: 297
7: 703
8: 999
9: 2223
10: 2728
11: 4879
12: 4950
13: 5050
14: 5292
15: 7272
16: 7777
17: 9999
...
51: 857143
52: 961038
53: 994708
54: 999999

Base 17:
1       1       1               0 + 1
16      G       F1              F + 1
64      3D      E2G             E + 2G
225     D4      A52G            A5 + 2G
288     GG      GF01            GF + 1
1536    556     1B43B2          1B4 + 3B2
3377    BBB     8093B2          809 + 3B2
4912    GGG     GGF001          GGF + 1
7425    18BD    24E166G         24E + 166G
9280    1F1F    39B1B94         39B + 1B94
...
74241   F1F2    D75F1B94        D75F + 1B94
76096   F854    E1F5166G        E1F5 + 166G
83520   GGGG    GGGF0001        GGGF + 1
266224  33334   A2C52A07G       A2C5 + 2A07G


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


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

IntegerToBaseRep := function(n, base) local s, digit; if base > 36 then return fail; elif n = 0 then return "0"; else s := ""; digit := "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"; while n <> 0 do Add(s, digit[RemInt(n, base) + 1]); n := QuoInt(n, base); od; return Reversed(s); fi; end;

PrintIfKaprekar := function(n, base) local v; v := IsKaprekarAndHow(n, base); if IsList(v) then Print(n, "(10) or in base ", base, ", ", IntegerToBaseRep(n, base), "^2 = ", IntegerToBaseRep(n^2, base), " and ", IntegerToBaseRep(v[2], base), " + ", IntegerToBaseRep(v[1], base), " = ", IntegerToBaseRep(n, base), "\n"); fi; return fail; end;

  1. In base 17...

Perform([1 .. 1000000], n -> PrintIfKaprekar(n, 17));

  1. 16(10) or in base 17, G^2 = F1 and F + 1 = G
  2. 64(10) or in base 17, 3D^2 = E2G and E + 2G = 3D
  3. 225(10) or in base 17, D4^2 = A52G and A5 + 2G = D4
  4. 288(10) or in base 17, GG^2 = GF01 and GF + 1 = GG
  5. 1536(10) or in base 17, 556^2 = 1B43B2 and 1B4 + 3B2 = 556
  6. 3377(10) or in base 17, BBB^2 = 8093B2 and 809 + 3B2 = BBB
  7. 4912(10) or in base 17, GGG^2 = GGF001 and GGF + 1 = GGG
  8. 7425(10) or in base 17, 18BD^2 = 24E166G and 24E + 166G = 18BD
  9. 9280(10) or in base 17, 1F1F^2 = 39B1B94 and 39B + 1B94 = 1F1F
  10. 16705(10) or in base 17, 36DB^2 = B992C42 and B99 + 2C42 = 36DB
  11. 20736(10) or in base 17, 43CD^2 = 10DE32FG and 10DE + 32FG = 43CD
  12. 30016(10) or in base 17, 61EB^2 = 23593F92 and 2359 + 3F92 = 61EB
  13. 36801(10) or in base 17, 785D^2 = 351E433G and 351E + 433G = 785D
  14. 37440(10) or in base 17, 7A96^2 = 37144382 and 3714 + 4382 = 7A96
  15. 46081(10) or in base 17, 967B^2 = 52G94382 and 52G9 + 4382 = 967B
  16. 46720(10) or in base 17, 98B4^2 = 5575433G and 5575 + 433G = 98B4
  17. 53505(10) or in base 17, AF26^2 = 6GA43F92 and 6GA4 + 3F92 = AF26
  18. 62785(10) or in base 17, CD44^2 = 9A5532FG and 9A55 + 32FG = CD44
  19. 66816(10) or in base 17, DA36^2 = AEG42C42 and AEG4 + 2C42 = DA36
  20. 74241(10) or in base 17, F1F2^2 = D75F1B94 and D75F + 1B94 = F1F2
  21. 76096(10) or in base 17, F854^2 = E1F5166G and E1F5 + 166G = F854
  22. 83520(10) or in base 17, GGGG^2 = GGGF0001 and GGGF + 1 = GGGG
  23. 266224(10) or in base 17, 33334^2 = A2C52A07G and A2C5 + 2A07G = 33334</lang>

Go

This example is incomplete. Tasks ask to "generate and show all Kaprekar numbers less than 10,000". Please ensure that it meets all task requirements and remove this message.

<lang Go>package main

import ( "fmt" "strconv" )

func kaprekar(n uint64, base uint64) (bool, int) { order := 0 if n == 1 { return true, -1 }

nn, power := n * n, uint64(1) for power <= nn { power *= base order ++ }

power /= base order -- for ; power > 1; power /= base { q, r := nn / power, nn % power if q >= n { return false, -1 }

if q + r == n { return true, order }

order-- }

return false, -1 }

func main() { count, base := 0, uint64(10) fmt.Println("With base ", base, ":") for m := uint64(0); m < 1000000; m++ { is, _ := kaprekar(m, base) if is { count ++ fmt.Println(count, m) } }

count, base = 0, 17 fmt.Println("\nWith base ", base, ":") for m := uint64(0); m < 1000000; m++ { is, pos := kaprekar(m, base) if !is { continue } count ++ sq  := strconv.Uitob64(m * m, uint(base)) str := strconv.Uitob64(m, uint(base)) fmt.Print(count, m, "\t", str, "\t", sq, "\t")

if pos > 0 { fmt.Println(" ", sq[0:pos], "+", sq[pos:len(sq)]) } else { fmt.Println() } } }</lang> Output:<lang>With base 10 : 1 1 2 9 3 45 4 55 . . . 51 857143 52 961038 53 994708 54 999999

With base 17 : 1 1 1 1 2 16 g f1 f + 1 3 64 3d e2g e2 + g 4 225 d4 a52g a5 + 2g . . . 22 76096 f854 e1f5166g e1f5 + 166g 23 83520 gggg gggf0001 gggf + 0001 24 266224 33334 a2c52a07g a2c52 + a07g</lang>

Icon and Unicon

<lang Icon>procedure is_kaprekar(n) #: return n if n is a kaprekar number if ( n = 1 ) | 

  ( n^2 ? ( n = move(1 to *&subject-1) + (0 ~= tab(0)) | fail )) then
  return n

end

procedure main() every write(is_kaprekar(1 to 10000)) # primary goal every (count := 0, is_kaprekar(1 to 999999), count +:= 1) # stretch goal 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,. [ ^ 1 + [: i. 1 + [ <.@^. >.&1 isKap=: 1 e. ] ((0 < {:"1@]) *. [ = +/"1@]) kapbase #: *:@]</lang>

Example use:

<lang j> I. 10 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>

"Extra credit": (text representing numbers left in boxes for alignment purposes) <lang j> 

  ]K17=: I. 17 isKap"0 i.1e6

1 16 64 225 288 1536 3377 4912 7425 9280 16705 20736 30016 36801 37440 46081 46720 53505 62785 66816 74241 76096 83520 266224 

  base=: [: (] u:@+ 39 * 57 < ]) 48 + #.inv 
  17 ([ base&.> ],*:@],] (] {:@,@#~ (0 < {:"1@]) *. [ = +/"1@]) kapbase #: *:@])"0 x:K17

┌─────┬─────────┬─────┐ │1 │1 │1 │ ├─────┼─────────┼─────┤ │g │f1 │1 │ ├─────┼─────────┼─────┤ │3d │e2g │2g │ ├─────┼─────────┼─────┤ │d4 │a52g │2g │ ├─────┼─────────┼─────┤ │gg │gf01 │1 │ ├─────┼─────────┼─────┤ │556 │1b43b2 │3b2 │ ├─────┼─────────┼─────┤ │bbb │8093b2 │3b2 │ ├─────┼─────────┼─────┤ │ggg │ggf001 │1 │ ├─────┼─────────┼─────┤ │18bd │24e166g │166g │ ├─────┼─────────┼─────┤ │1f1f │39b1b94 │1b94 │ ├─────┼─────────┼─────┤ │36db │b992c42 │2c42 │ ├─────┼─────────┼─────┤ │43cd │10de32fg │32fg │ ├─────┼─────────┼─────┤ │61eb │23593f92 │3f92 │ ├─────┼─────────┼─────┤ │785d │351e433g │433g │ ├─────┼─────────┼─────┤ │7a96 │37144382 │4382 │ ├─────┼─────────┼─────┤ │967b │52g94382 │4382 │ ├─────┼─────────┼─────┤ │98b4 │5575433g │433g │ ├─────┼─────────┼─────┤ │af26 │6ga43f92 │3f92 │ ├─────┼─────────┼─────┤ │cd44 │9a5532fg │32fg │ ├─────┼─────────┼─────┤ │da36 │aeg42c42 │2c42 │ ├─────┼─────────┼─────┤ │f1f2 │d75f1b94 │1b94 │ ├─────┼─────────┼─────┤ │f854 │e1f5166g │166g │ ├─────┼─────────┼─────┤ │gggg │gggf0001 │1 │ ├─────┼─────────┼─────┤ │33334│a2c52a07g│2a07g│ └─────┴─────────┴─────┘</lang>

The fastest times can be obtained by two optimizations: first, partitions with over half of the digits on the left (i.e. more than 3 for a 5-digit number) will not be considered because the left half is mathematically guaranteed to be greater than the original number in this case. Second, the numbers are computed in groups corresponding to the number of digits in their squares to allow isKap to be computed at full rank. Note that this method excludes 1, so it must be added manually to the list of solutions. <lang j> kapbase=: 0,.10 ^ [: (<.+i.@>.)@(-:&.<:) 10 <.@^. >.&1 

  isKapGroup=: [: +./"1 (((0 < {:"1@]) *. [ = +/"1@]) (kapbase@{: #:"2 0 ])@:*:)
  6!:2 'a=.1, I. ([:; (<@isKapGroup/.~ 10<.@^.*:)) i.1e6'

12.3963 

  #a

54</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;
       int base = (args.length > 0) ? Integer.parseInt(args[0]) : 10;
       for(long i = 1; i <= 1000000; i++){
           String sqrStr = Long.toString(i * i, base);
           for(int j = 0; j < sqrStr.length() / 2 + 1; j++){
               String[] parts = splitAt(sqrStr, j);
               long firstNum = Long.parseLong(parts[0], base);
               long secNum = Long.parseLong(parts[1], base);
               //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 + "\t" + Long.toString(i, base) +
                           "\t" + sqrStr + "\t" + parts[0] + " + " + parts[1]);
                   count++;
                   break;
               }
           }
       }
       System.out.println(count + " Kaprekar numbers < 1000000 (base 10) in base "+base);
   }

}</lang> Output (base 10, shortened): 

1	1	1	0 + 1
9	9	81	8 + 1
45	45	2025	20 + 25
55	55	3025	30 + 25
99	99	9801	98 + 01
297	297	88209	88 + 209
703	703	494209	494 + 209
999	999	998001	998 + 001
2223	2223	4941729	494 + 1729
2728	2728	7441984	744 + 1984
4879	4879	23804641	238 + 04641
4950	4950	24502500	2450 + 2500
5050	5050	25502500	2550 + 2500
5292	5292	28005264	28 + 005264
7272	7272	52881984	5288 + 1984
7777	7777	60481729	6048 + 1729
9999	9999	99980001	9998 + 0001
...
818181	818181	669420148761	669420 + 148761
851851	851851	725650126201	725650 + 126201
857143	857143	734694122449	734694 + 122449
961038	961038	923594037444	923594 + 037444
994708	994708	989444005264	989444 + 005264
999999	999999	999998000001	999998 + 000001
54 Kaprekar numbers < 1000000 (base 10) in base 10

Output (base 17, shortened): 

1	1	1	0 + 1
16	g	f1	f + 1
64	3d	e2g	e + 2g
225	d4	a52g	a5 + 2g
288	gg	gf01	gf + 01
1536	556	1b43b2	1b4 + 3b2
3377	bbb	8093b2	809 + 3b2
4912	ggg	ggf001	ggf + 001
7425	18bd	24e166g	24e + 166g
9280	1f1f	39b1b94	39b + 1b94
...
76096	f854	e1f5166g	e1f5 + 166g
83520	gggg	gggf0001	gggf + 0001
266224	33334	a2c52a07g	a2c5 + 2a07g
24 Kaprekar numbers < 1000000 (base 10) in base 17

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.

PHP

<lang php>set_time_limit(300);

print_r(array_filter(range(1, 10000), 'isKaprekar')); echo count(array_filter(range(1, 1000000), 'isKaprekar'));

function isKaprekar($n) { 

   $a = $n * $n; 
   $b = bcmod("$a", "10");
   for ($d = 1, $t = 0; $a > 0; $d *= 10) {
       $b += $t * $d;
       if ($b > $n) break;
       $a = floor($a / 10);
       if ($b && $a + $b == $n) 
           return true;
       $t = bcmod("$a", "10");
   }
   return false;

}</lang> 

Array
(
    [0] => 1
    [8] => 9
    [44] => 45
    [54] => 55
    [98] => 99
    [296] => 297
    [702] => 703
    [998] => 999
    [2222] => 2223
    [2727] => 2728
    [4878] => 4879
    [4949] => 4950
    [5049] => 5050
    [5291] => 5292
    [7271] => 7272
    [7776] => 7777
    [9998] => 9999
)
54

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
Retrieved from "https://rosettacode.org/wiki/Kaprekar_numbers?oldid=187365"