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 consisting of positive integers 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 (1002) 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.
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>
- include <string>
- include <iostream>
- include <sstream>
- include <cstdlib>
- include <algorithm>
- include <iterator>
void splitString( std::vector<std::string> & parts , std::string & s ,
int pos ) {
parts.push_back( s.substr( 0 , pos ) ) ;
parts.push_back( s.substr( pos++ ) ) ;
}
bool isKaprekar( long number ) {
long long squarenumber = number * number ;
std::ostringstream numberbuf ;
numberbuf << squarenumber ;
std::string numberstring( numberbuf.str( ) ) ;
std::vector<std::string> stringparts ;
int i = 0 ;
while ( i < numberstring.length( ) ) {
splitString( stringparts , numberstring , i ) ;
//we do not accept figures ending in a sequence of zeroes
if ( (stringparts.begin( ) + 1)->find_first_not_of( "0" ) == std::string::npos ) {
return false ;
}
if ( atol(( stringparts.begin( ))->c_str( ) )
+ atol(( stringparts.begin( ) + 1 )->c_str( )) != number ) { i++ ; stringparts.clear( ) ;
}
else {
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 t0 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(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
Alternative version, going from right to left, produces same output <lang d>bool isKaprekar(ulong n) {
if (n <= 1) return n == 1;
ulong nn = n * n;
ulong a = nn % 10, b, c, d = 1;
while (nn > 0) {
a += c * d;
b = nn / 10;
if (a && a + b == n)
return true;
c = b % 10;
d *= 10;
nn /= 10;
}
return false;
}</lang>
Fortran
<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
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
- 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;
}
}
- 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
<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
}
- Base goal
for {set i 1} {$i < 10000} {incr i} {
if {[kaprekar $i]} {lappend klist $i}
} puts [join $klist ", "]
- 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