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 (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.
- 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.
