Kaprekar numbers: Difference between revisions
m (changed example for xx credit) |
(→{{header|C}}: update) |
||
Line 25: | Line 25: | ||
=={{header|C}}== |
=={{header|C}}== |
||
Sample for extra extra credit: |
|||
<lang C>#include <stdio.h> |
<lang C>#include <stdio.h> |
||
typedef unsigned long long ulong; |
typedef unsigned long long ulong; |
||
int kaprekar(ulong n) |
int kaprekar(ulong n, int base) |
||
{ |
{ |
||
ulong nn = n * n, tens = 1; |
ulong nn = n * n, tens = 1; |
||
while (tens < nn) tens *= |
while (tens < nn) tens *= base; |
||
while ((tens /= |
while ((tens /= base) > n) { |
||
if (nn - n == (nn / tens) * (tens - 1)) |
if (nn - n == (nn / tens) * (tens - 1)) |
||
return |
return tens; |
||
} |
} |
||
return 1 == n; |
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() |
int main() |
||
{ |
{ |
||
ulong i; |
ulong i, tens; |
||
int cnt = 0; |
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); |
|||
}</lang> |
|||
for (i = 2, cnt = 1; i < 1000000; i++) |
|||
Output:<pre> 1: 1 |
|||
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:<lang>base 10: |
|||
1: 1 |
|||
2: 9 |
2: 9 |
||
3: 45 |
3: 45 |
||
4: 55 |
4: 55 |
||
5: 99 |
5: 99 |
||
... |
|||
⚫ | |||
. |
|||
. |
|||
52: 961038 |
52: 961038 |
||
53: 994708 |
53: 994708 |
||
54: 999999 |
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 |
|||
⚫ | |||
22: 76096 f854 e1f5166g e1f5 + 166g |
|||
23: 83520 gggg gggf0001 gggf + 1 |
|||
24: 266224 33334 a2c52a07g a2c5 + 2a07g</lang> |
|||
=={{header|C++}}== |
=={{header|C++}}== |
Revision as of 01:46, 17 June 2011
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
- The Kaprekar Numbers by Douglas E. Iannucci (2000). PDF version
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:<lang>base 10:
1: 1 2: 9 3: 45 4: 55 5: 99 ... 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 ... 22: 76096 f854 e1f5166g e1f5 + 166g 23: 83520 gggg gggf0001 gggf + 1 24: 266224 33334 a2c52a07g a2c5 + 2a07g</lang>
C++
<lang cpp>#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 ;
}</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
<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, 9, 45, 55, 99, 297, 703, 999, 2223, 2728, 4879, 4950, 5050, 5292, 7272,
- 7777, 9999 ]
Size(last);
- 17
Filtered([1 .. 1000000], IsKaprekar);
- [ 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 ]
Size(last);
- 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; int base = Integer.parseInt(args.length > 0 ? args[0] : "10"); for(long i = 1; i <= 1000000; i++){ String sqrStr = Long.toString(i * i, base); for(int j = 0; j < sqrStr.length(); 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
- 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