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 is known as A006886, and begins as 1,9,45,55,….

- Example process

10000 (100^{2}) 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.

- Task description

Generate and show all Kaprekar numbers less than 10,000.

### Using String Manipulation (very slow)

#include <vector> #include <string> #include <iostream> #include <sstream> #include <algorithm> #include <iterator> #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 ; }

- 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!

### Casting Out Nines (fast)

The code `"if ((k*(k-1))%(Base-1) == 0)"`

is explained here: Casting out nines.

// Generate Kaperkar Numbers // // Nigel Galloway. June 24th., 2012 // #include <iostream> int main() { const int Base = 10; const int N = 6; int Paddy_cnt = 0; for (int nz=1; nz<=N; nz++) for (unsigned long long int k=pow((double)Base,nz-1); k<pow((double)Base,nz); k++) if ((k*(k-1))%(Base-1) == 0) for (int n=nz; n<nz*2; n++){ const unsigned long long int B = pow((double)Base,n); const double nr = k*(B-k)/(B-1); const int q = k-nr; if ((k*k==q*B+nr && 0<nr)){ std::cout << std::dec << ++Paddy_cnt << ": " << k << " is " << q << " + " << (int)nr << " and squared is " << k*k << ". It is a member of Residual Set " << k%(Base-1) << "\n"; break; }} return 0; }

Produces:

1: 1 is 0 + 1 and squared is 1. It is a member of Residual Set 1 2: 9 is 8 + 1 and squared is 81. It is a member of Residual Set 0 3: 45 is 20 + 25 and squared is 2025. It is a member of Residual Set 0 4: 55 is 30 + 25 and squared is 3025. It is a member of Residual Set 1 5: 99 is 98 + 1 and squared is 9801. It is a member of Residual Set 0 6: 297 is 88 + 209 and squared is 88209. It is a member of Residual Set 0 7: 703 is 494 + 209 and squared is 494209. It is a member of Residual Set 1 8: 999 is 998 + 1 and squared is 998001. It is a member of Residual Set 0 9: 2223 is 494 + 1729 and squared is 4941729. It is a member of Residual Set 0 10: 2728 is 744 + 1984 and squared is 7441984. It is a member of Residual Set 1 11: 4879 is 238 + 4641 and squared is 23804641. It is a member of Residual Set 1 12: 4950 is 2450 + 2500 and squared is 24502500. It is a member of Residual Set 0 13: 5050 is 2550 + 2500 and squared is 25502500. It is a member of Residual Set 1 14: 5292 is 28 + 5264 and squared is 28005264. It is a member of Residual Set 0 15: 7272 is 5288 + 1984 and squared is 52881984. It is a member of Residual Set 0 16: 7777 is 6048 + 1729 and squared is 60481729. It is a member of Residual Set 1 17: 9999 is 9998 + 1 and squared is 99980001. It is a member of Residual Set 0 18: 17344 is 3008 + 14336 and squared is 300814336. It is a member of Residual Set 1 19: 22222 is 4938 + 17284 and squared is 493817284. It is a member of Residual Set 1 20: 38962 is 1518 + 37444 and squared is 1518037444. It is a member of Residual Set 1 21: 77778 is 60494 + 17284 and squared is 6049417284. It is a member of Residual Set 0 22: 82656 is 68320 + 14336 and squared is 6832014336. It is a member of Residual Set 0 23: 95121 is 90480 + 4641 and squared is 9048004641. It is a member of Residual Set 0 24: 99999 is 99998 + 1 and squared is 9999800001. It is a member of Residual Set 0 25: 142857 is 20408 + 122449 and squared is 20408122449. It is a member of Residual Set 0 26: 148149 is 21948 + 126201 and squared is 21948126201. It is a member of Residual Set 0 27: 181819 is 33058 + 148761 and squared is 33058148761. It is a member of Residual Set 1 28: 187110 is 35010 + 152100 and squared is 35010152100. It is a member of Residual Set 0 29: 208495 is 43470 + 165025 and squared is 43470165025. It is a member of Residual Set 1 30: 318682 is 101558 + 217124 and squared is 101558217124. It is a member of Residual Set 1 31: 329967 is 108878 + 221089 and squared is 108878221089. It is a member of Residual Set 0 32: 351352 is 123448 + 227904 and squared is 123448227904. It is a member of Residual Set 1 33: 356643 is 127194 + 229449 and squared is 127194229449. It is a member of Residual Set 0 34: 390313 is 152344 + 237969 and squared is 152344237969. It is a member of Residual Set 1 35: 461539 is 213018 + 248521 and squared is 213018248521. It is a member of Residual Set 1 36: 466830 is 217930 + 248900 and squared is 217930248900. It is a member of Residual Set 0 37: 499500 is 249500 + 250000 and squared is 249500250000. It is a member of Residual Set 0 38: 500500 is 250500 + 250000 and squared is 250500250000. It is a member of Residual Set 1 39: 533170 is 284270 + 248900 and squared is 284270248900. It is a member of Residual Set 1 40: 538461 is 289940 + 248521 and squared is 289940248521. It is a member of Residual Set 0 41: 609687 is 371718 + 237969 and squared is 371718237969. It is a member of Residual Set 0 42: 627615 is 39390 + 588225 and squared is 393900588225. It is a member of Residual Set 0 43: 643357 is 413908 + 229449 and squared is 413908229449. It is a member of Residual Set 1 44: 648648 is 420744 + 227904 and squared is 420744227904. It is a member of Residual Set 0 45: 670033 is 448944 + 221089 and squared is 448944221089. It is a member of Residual Set 1 46: 681318 is 464194 + 217124 and squared is 464194217124. It is a member of Residual Set 0 47: 791505 is 626480 + 165025 and squared is 626480165025. It is a member of Residual Set 0 48: 812890 is 660790 + 152100 and squared is 660790152100. It is a member of Residual Set 1 49: 818181 is 669420 + 148761 and squared is 669420148761. It is a member of Residual Set 0 50: 851851 is 725650 + 126201 and squared is 725650126201. It is a member of Residual Set 1 51: 857143 is 734694 + 122449 and squared is 734694122449. It is a member of Residual Set 1 52: 961038 is 923594 + 37444 and squared is 923594037444. It is a member of Residual Set 0 53: 994708 is 989444 + 5264 and squared is 989444005264. It is a member of Residual Set 1 54: 999999 is 999998 + 1 and squared is 999998000001. It is a member of Residual Set 0

The code may be modified to use a base other than 10:

const int Base = 16; const int N = 4; std::cout << std::dec << ++Paddy_cnt << ": " << std::hex << k << " is " << q << " + " << (int)nr << " and squared is " << k*k << ". It is a member of Residual Set " << k%(Base-1) << "\n";

Which produces:

1: 1 is 0 + 1 and squared is 1. It is a member of Residual Set 1 2: 6 is 2 + 4 and squared is 24. It is a member of Residual Set 6 3: a is 6 + 4 and squared is 64. It is a member of Residual Set a 4: f is e + 1 and squared is e1. It is a member of Residual Set 0 5: 33 is a + 29 and squared is a29. It is a member of Residual Set 6 6: 55 is 1c + 39 and squared is 1c39. It is a member of Residual Set a 7: 5b is 2 + 59 and squared is 2059. It is a member of Residual Set 1 8: 78 is 38 + 40 and squared is 3840. It is a member of Residual Set 0 9: 88 is 48 + 40 and squared is 4840. It is a member of Residual Set 1 10: ab is 72 + 39 and squared is 7239. It is a member of Residual Set 6 11: cd is a4 + 29 and squared is a429. It is a member of Residual Set a 12: ff is fe + 1 and squared is fe01. It is a member of Residual Set 0 13: 15f is 1e + 141 and squared is 1e141. It is a member of Residual Set 6 14: 334 is a4 + 290 and squared is a4290. It is a member of Residual Set a 15: 38e is ca + 2c4 and squared is ca2c4. It is a member of Residual Set a 16: 492 is 14e + 344 and squared is 14e344. It is a member of Residual Set 0 17: 4ed is 184 + 369 and squared is 184369. It is a member of Residual Set 1 18: 7e0 is 3e0 + 400 and squared is 3e0400. It is a member of Residual Set 6 19: 820 is 420 + 400 and squared is 420400. It is a member of Residual Set a 20: b13 is 7aa + 369 and squared is 7aa369. It is a member of Residual Set 0 21: b6e is 82a + 344 and squared is 82a344. It is a member of Residual Set 1 22: c72 is 9ae + 2c4 and squared is 9ae2c4. It is a member of Residual Set 6 23: ccc is a3c + 290 and squared is a3c290. It is a member of Residual Set 6 24: ea1 is d60 + 141 and squared is d60141. It is a member of Residual Set a 25: fa5 is f4c + 59 and squared is f4c059. It is a member of Residual Set 0 26: fff is ffe + 1 and squared is ffe001. It is a member of Residual Set 0 27: 191a is 276 + 16a4 and squared is 27616a4. It is a member of Residual Set 6 28: 2a2b is 6f2 + 2339 and squared is 6f22339. It is a member of Residual Set a 29: 3c3c is e2c + 2e10 and squared is e2c2e10. It is a member of Residual Set 0 30: 4444 is 1234 + 3210 and squared is 12343210. It is a member of Residual Set 1 31: 5556 is 1c72 + 38e4 and squared is 1c7238e4. It is a member of Residual Set 6 32: 6667 is 28f6 + 3d71 and squared is 28f63d71. It is a member of Residual Set a 33: 7f80 is 3f80 + 4000 and squared is 3f804000. It is a member of Residual Set 0 34: 8080 is 4080 + 4000 and squared is 40804000. It is a member of Residual Set 1 35: 9999 is 5c28 + 3d71 and squared is 5c283d71. It is a member of Residual Set 6 36: aaaa is 71c6 + 38e4 and squared is 71c638e4. It is a member of Residual Set a 37: bbbc is 89ac + 3210 and squared is 89ac3210. It is a member of Residual Set 0 38: c3c4 is 95b4 + 2e10 and squared is 95b42e10. It is a member of Residual Set 1 39: d5d5 is b29c + 2339 and squared is b29c2339. It is a member of Residual Set 6 40: e6e6 is d042 + 16a4 and squared is d04216a4. It is a member of Residual Set a 41: ffff is fffe + 1 and squared is fffe0001. It is a member of Residual Set 0

### Casting Out Nines C++11 For Each Generator (v.fast)

For details of ran and co9 see: http://rosettacode.org/wiki/Casting_out_nines#C.2B.2B11_For_Each_Generator

// Generate Kaprekar Numbers using Casting Out Nines Generator // // Nigel Galloway. July 13th., 2012 // #include <cmath> int main() { const ran r(10); int Paddy_cnt = 0; for (int nz=1; nz<=6; nz++) for (unsigned long long int k : co9(std::pow(r.base,nz-1),std::pow(r.base,nz)-1,&r)) for (int n=nz; n<nz*2; n++) { const unsigned long long int B = pow(r.base,n); const double nr = k*(B-k)/(B-1); const int q = k-nr; if ((k*k==q*B+nr && 0<nr)) { std::cout << ++Paddy_cnt << ": " << k << " is " << q << " + " << (int)nr << " and squared is " << k*k << ". It is a member of Residual Set " << k%(r.base-1) << "\n"; }} return 0; }

Produces:

1: 1 is 0 + 1 and squared is 1. It is a member of Residual Set 1 2: 9 is 8 + 1 and squared is 81. It is a member of Residual Set 0 3: 45 is 20 + 25 and squared is 2025. It is a member of Residual Set 0 4: 55 is 30 + 25 and squared is 3025. It is a member of Residual Set 1 5: 99 is 98 + 1 and squared is 9801. It is a member of Residual Set 0 6: 297 is 88 + 209 and squared is 88209. It is a member of Residual Set 0 7: 703 is 494 + 209 and squared is 494209. It is a member of Residual Set 1 8: 999 is 998 + 1 and squared is 998001. It is a member of Residual Set 0 9: 2223 is 494 + 1729 and squared is 4941729. It is a member of Residual Set 0 10: 2728 is 744 + 1984 and squared is 7441984. It is a member of Residual Set 1 11: 4879 is 238 + 4641 and squared is 23804641. It is a member of Residual Set 1 12: 4950 is 2450 + 2500 and squared is 24502500. It is a member of Residual Set 0 13: 5050 is 2550 + 2500 and squared is 25502500. It is a member of Residual Set 1 14: 5292 is 28 + 5264 and squared is 28005264. It is a member of Residual Set 0 15: 7272 is 5288 + 1984 and squared is 52881984. It is a member of Residual Set 0 16: 7777 is 6048 + 1729 and squared is 60481729. It is a member of Residual Set 1 17: 9999 is 9998 + 1 and squared is 99980001. It is a member of Residual Set 0 18: 17344 is 3008 + 14336 and squared is 300814336. It is a member of Residual Set 1 19: 22222 is 4938 + 17284 and squared is 493817284. It is a member of Residual Set 1 20: 38962 is 1518 + 37444 and squared is 1518037444. It is a member of Residual Set 1 21: 77778 is 60494 + 17284 and squared is 6049417284. It is a member of Residual Set 0 22: 82656 is 68320 + 14336 and squared is 6832014336. It is a member of Residual Set 0 23: 95121 is 90480 + 4641 and squared is 9048004641. It is a member of Residual Set 0 24: 99999 is 99998 + 1 and squared is 9999800001. It is a member of Residual Set 0 25: 142857 is 20408 + 122449 and squared is 20408122449. It is a member of Residual Set 0 26: 148149 is 21948 + 126201 and squared is 21948126201. It is a member of Residual Set 0 27: 181819 is 33058 + 148761 and squared is 33058148761. It is a member of Residual Set 1 28: 187110 is 35010 + 152100 and squared is 35010152100. It is a member of Residual Set 0 29: 208495 is 43470 + 165025 and squared is 43470165025. It is a member of Residual Set 1 30: 318682 is 101558 + 217124 and squared is 101558217124. It is a member of Residual Set 1 31: 329967 is 108878 + 221089 and squared is 108878221089. It is a member of Residual Set 0 32: 351352 is 123448 + 227904 and squared is 123448227904. It is a member of Residual Set 1 33: 356643 is 127194 + 229449 and squared is 127194229449. It is a member of Residual Set 0 34: 390313 is 152344 + 237969 and squared is 152344237969. It is a member of Residual Set 1 35: 461539 is 213018 + 248521 and squared is 213018248521. It is a member of Residual Set 1 36: 466830 is 217930 + 248900 and squared is 217930248900. It is a member of Residual Set 0 37: 499500 is 249500 + 250000 and squared is 249500250000. It is a member of Residual Set 0 38: 500500 is 250500 + 250000 and squared is 250500250000. It is a member of Residual Set 1 39: 533170 is 284270 + 248900 and squared is 284270248900. It is a member of Residual Set 1 40: 538461 is 289940 + 248521 and squared is 289940248521. It is a member of Residual Set 0 41: 609687 is 371718 + 237969 and squared is 371718237969. It is a member of Residual Set 0 42: 627615 is 39390 + 588225 and squared is 393900588225. It is a member of Residual Set 0 43: 643357 is 413908 + 229449 and squared is 413908229449. It is a member of Residual Set 1 44: 648648 is 420744 + 227904 and squared is 420744227904. It is a member of Residual Set 0 45: 670033 is 448944 + 221089 and squared is 448944221089. It is a member of Residual Set 1 46: 681318 is 464194 + 217124 and squared is 464194217124. It is a member of Residual Set 0 47: 791505 is 626480 + 165025 and squared is 626480165025. It is a member of Residual Set 0 48: 812890 is 660790 + 152100 and squared is 660790152100. It is a member of Residual Set 1 49: 818181 is 669420 + 148761 and squared is 669420148761. It is a member of Residual Set 0 50: 851851 is 725650 + 126201 and squared is 725650126201. It is a member of Residual Set 1 51: 857143 is 734694 + 122449 and squared is 734694122449. It is a member of Residual Set 1 52: 961038 is 923594 + 37444 and squared is 923594037444. It is a member of Residual Set 0 53: 994708 is 989444 + 5264 and squared is 989444005264. It is a member of Residual Set 1 54: 999999 is 999998 + 1 and squared is 999998000001. It is a member of Residual Set 0

Changing main:

const ran r = ran(16); std::cout << std::dec << ++Paddy_cnt << ": " << std::hex << k << " is " << q << " + " << (int)nr << " and squared is " << k*k << ". It is a member of Residual Set " << k%(r.base-1) << "\n";

Produces:

1: 1 is 0 + 1 and squared is 1. It is a member of Residual Set 1 2: 6 is 2 + 4 and squared is 24. It is a member of Residual Set 6 3: a is 6 + 4 and squared is 64. It is a member of Residual Set a 4: f is e + 1 and squared is e1. It is a member of Residual Set 0 5: 33 is a + 29 and squared is a29. It is a member of Residual Set 6 6: 55 is 1c + 39 and squared is 1c39. It is a member of Residual Set a 7: 5b is 2 + 59 and squared is 2059. It is a member of Residual Set 1 8: 78 is 38 + 40 and squared is 3840. It is a member of Residual Set 0 9: 88 is 48 + 40 and squared is 4840. It is a member of Residual Set 1 10: ab is 72 + 39 and squared is 7239. It is a member of Residual Set 6 11: cd is a4 + 29 and squared is a429. It is a member of Residual Set a 12: ff is fe + 1 and squared is fe01. It is a member of Residual Set 0 13: 15f is 1e + 141 and squared is 1e141. It is a member of Residual Set 6 14: 334 is a4 + 290 and squared is a4290. It is a member of Residual Set a 15: 38e is ca + 2c4 and squared is ca2c4. It is a member of Residual Set a 16: 492 is 14e + 344 and squared is 14e344. It is a member of Residual Set 0 17: 4ed is 184 + 369 and squared is 184369. It is a member of Residual Set 1 18: 7e0 is 3e0 + 400 and squared is 3e0400. It is a member of Residual Set 6 19: 820 is 420 + 400 and squared is 420400. It is a member of Residual Set a 20: b13 is 7aa + 369 and squared is 7aa369. It is a member of Residual Set 0 21: b6e is 82a + 344 and squared is 82a344. It is a member of Residual Set 1 22: c72 is 9ae + 2c4 and squared is 9ae2c4. It is a member of Residual Set 6 23: ccc is a3c + 290 and squared is a3c290. It is a member of Residual Set 6 24: ea1 is d60 + 141 and squared is d60141. It is a member of Residual Set a 25: fa5 is f4c + 59 and squared is f4c059. It is a member of Residual Set 0 26: fff is ffe + 1 and squared is ffe001. It is a member of Residual Set 0 27: 191a is 276 + 16a4 and squared is 27616a4. It is a member of Residual Set 6 28: 2a2b is 6f2 + 2339 and squared is 6f22339. It is a member of Residual Set a 29: 3c3c is e2c + 2e10 and squared is e2c2e10. It is a member of Residual Set 0 30: 4444 is 1234 + 3210 and squared is 12343210. It is a member of Residual Set 1 31: 5556 is 1c72 + 38e4 and squared is 1c7238e4. It is a member of Residual Set 6 32: 6667 is 28f6 + 3d71 and squared is 28f63d71. It is a member of Residual Set a 33: 7f80 is 3f80 + 4000 and squared is 3f804000. It is a member of Residual Set 0 34: 8080 is 4080 + 4000 and squared is 40804000. It is a member of Residual Set 1 35: 9999 is 5c28 + 3d71 and squared is 5c283d71. It is a member of Residual Set 6 36: aaaa is 71c6 + 38e4 and squared is 71c638e4. It is a member of Residual Set a 37: bbbc is 89ac + 3210 and squared is 89ac3210. It is a member of Residual Set 0 38: c3c4 is 95b4 + 2e10 and squared is 95b42e10. It is a member of Residual Set 1 39: d5d5 is b29c + 2339 and squared is b29c2339. It is a member of Residual Set 6 40: e6e6 is d042 + 16a4 and squared is d04216a4. It is a member of Residual Set a 41: ffff is fffe + 1 and squared is fffe0001. It is a member of Residual Set 0

Content is available under GNU Free Documentation License 1.2.