Kaprekar numbers
A positive integer is a Kaprekar number if the string representation of its square can be split once into parts 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.
Note: In comparing splits of the square, a split of all zeroes is not counted - as zero is not considered positive. However a conceptual single split at the very end or before the first digit that produces one empty string does have the empty string counted.
Example: 10000 (1002): The first split is [ ,10000], which is OK because "a conceptual single split...before the first digit that produces one empty string does have the empty string counted" (that is how 1 is a Kaprekar number). The second 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.
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
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