I managed to reduce the number of divisions by throwing some mathematics on it. Put very short:
If n is a Kaprekar number (to a base b) there must be a divisor ( d=b^m ) with n^2 = xd+r with the constraint n=x+r. (x beeing the quotient and r the remainder)
Substituting r with n-x, we get: n^2 = xd +n -x = x(d-1) + n
So: n(n-1) = x (d-1) --> x = n(n-1)/(d-1) This division can have no remainder!
The quotient x has to be < n (because n=x+r (with r>0)). Conclusion: d>n. It tells me, I should start with exponents m so that b^m >n.
The improvements are:
One modulo division is enough, where my original code had to compute quotient and remainder.
The lower bound for the divisor is increased and, more important, preserved before divisions take place.
The computation time for the search up to 10^8 is reduced to 4 % compared to my original code.
isKaprekarbasen=elem0$-- any remainders 0? takeWhile(<n)$-- remainder has to be < n. Now the list is finite.map(\div->(n*(n-1))`mod`(div-1))$-- compute the critical remaindersdropWhile(<=n)$map(base^)[2..]-- divisors must be > nmain=print$filter(isKaprekar10)[1..10^8]
BTW: I saw a possible error in my last iteration. takeWhile (<n) is not proven to be correct. It's better to do it that way:
isKaprekarbasen=letsqr=n^2inelem0$-- any remainder = 0? <=> is kaprekar!map(\div->(sqr-n)`mod`(div-1))$-- compute the critical remainderstakeWhile(<sqr)$dropWhile(<=n)$-- sensible bounds for divisorsmap(base^)[1..]-- infinite list of divisorsmain=print$1:(filter(isKaprekar10)[1..10^5])
Also, it's nicer to use upper and lower bounds for divisors before computing the devisions. This is proven to be correct now, but I lost speed. ;-) The speed improvement by melting construction and restriction together is only 86% instead of 96%.
Use fixed-width Ints instead of arbitrary sized Integers (by function signature) Large improvement!
It pays off to spend an additional modulo division if the number of possible divisors for the critical division can be heavily reduced.
'any' slightly outperforms 'elem'. (in this case?)
A hand-rolled recursion sometimes performs better (without additional division) and sometimes worse (with additional division) than the folding recursions hidden in the 'elem' or 'any' functions. (But code with builtin folds is much nicer to read.)
The improvement steps were: 1000s - 500s - 90s - 60s - 19s - 13s - 9s. Quite funny to squeeze the algorithm like that. :-) This is what I came up with:
isKaprekar::Int->Int->BoolisKaprekarbasen=letsqr=n^2inany(\div->(sqr-n)`mod`(div-1)==0)$-- any rem = 0? <=> kaprekar!takeWhile(\div->(sqr`mod`div)<n)$-- sensible bounds for divisorsdropWhile(<=n)$map(base^)[1..]-- infinite list of divisorsmain=print$1:(filter(isKaprekar10)[1..10^8])
I wanted to have it in C for reference. Even expressed imperatively, it is now a very simple and nice algorithm. (2-3s)
I didn't want to take the route to String representation and back, I considered it as a computational problem and I wanted to find a purely computational solution. So I used digit values. Drawbacks: It appends number 1 as being kaprekar by convention. Benefit: It works for all bases (although output is decimal).
I tried to compute the Kaprekar numbers up to 108. A simple improvement in taking the interesting part and dropping the rest: If quotient or remainder are > n the sum of both must be > n. This reduced execution time by 50 %.
Could I trouble someone to comment this code? Oops, I guess that's in the parent comment, thanks! I don't know Haskell but I'm interested in it. Does this solution work for the 'strange' ones like 4789, 5292?
Trying to wrap my head around how to interpret the definition of a Kaprekar number, in a way that includes these oddball numbers.
I'm currently studying Ruby -- I'll necro-post my Ruby solution if I manage to get it working with the oddballs.
As far as I can see, most (if not all) programs use the strategy to convert the square to a string, pad it with 0 if the length is not even, and split it in the middle.
This seems to work for the range of Kaprekar numbers in the given range [1..999]. However, when I tried to speed up my program by splitting in the middle, I found out a problem with 5292. It is a Kaprekar number:
But to recognize it, you have to split 2 and 6 of 8 digits.
The implicit assumption about the Kaprekar property to show up when the number is split in the middle seems to be wrong. I tested some Javascript programs of this challenge with 5292 and it is not recognized as Kaprekar number.
Dang, that's a great point. I should have made the OP more detailed to clarify that the "split" isn't always right down the middle — even if it happens to work in the [1...999] range.
I definitely didn't think of that possibly while creating the post, or while working on my personal solution.
What does your approach to this look like? Now you've got me curious about how you're going about solving it. NVM, now I see your other comment.
This was a lot harder than I thought mainly because I had to look up why some numbers were and weren't Kaprekar numbers because the above description doesn't include all the details. First gotcha is the second part of the split numbers must be positive (no zeros). The second part was that you add a zero to the front if the length is odd.
Figure it's only fair to throw my answer into the ring. Clearly very novice and verbose 😇. Added a number of comments for the other #beginners out there.
varkap=function(number){varwhole=number.toString();// convert number to stringif(whole.length%2!==0){// if the length is odd, add a zero to the frontwhole="0"+whole;// IE 123 becomes 0123}varmiddle=whole.length/2;// find the index of the middle and end of the stringvarend=whole.length;varpiece1=whole.slice(0,middle);// break it into two piecesvarpiece2=whole.slice(middle,end);piece1=parseInt(piece1);// convert back to numberspiece2=parseInt(piece2);varfinal=piece1+piece2;// add them togetherreturnfinal;// return result}for(i=1;i<1000;i++){// simple for loop from 1 to 1,000varsquared=i*i;varkapval=kap(squared);if(i==kapval){// sees if they matchconsole.log(i);}}
As Heiko points out, the solution was incorrect, because the split was always done in the middle of the string...
So, here's a (hopefully correct) Java 9 solution (Java 9 because I use takeWhile):
importjava.util.function.IntPredicate;importjava.util.stream.IntStream;publicclassFirstSixteenKaprekarNumbers{publicstaticvoidmain(String...args){IntPredicateisKaprekar=i->{longsquare=i*i;// first, generate a stream of possible 10-base divisors (if the left side is zero, we're done):returnIntStream.iterate(10,div->div*10).takeWhile(div->square/div>0)// then, filter out zero right sides:.filter(div->square%div>0)// finally, see if the sum of the parts match the original number:.anyMatch(div->i==square/div+square%div);};IntStream.concat(IntStream.of(1),IntStream.iterate(2,i->i+1).filter(isKaprekar)).limit(16).forEach(System.out::println);// 1, 9, 45, 55, 99, 297, 703, 999, 2223, 2728, 4879, 4950, 5050, 5292, 7272, 7777}}
I chose to output the first 16 numbers so we can see the output includes numbers 4879 and 5292.
OK - this was way more of a rabbit hole than I thought... :) Here's two, new (F#) and old (COBOL). Both of these work within the constraints of the initial challenge, but will fail outside of that; had I not spent the amount of time I already spent on these, I might have at least made the F# version be able to handle others.
p.s. 0 also fits the description from the tweet! (02 = 0; 00 = 0 + 0 = 0; 0 = 0)
identification division.
program-id. kaprekar.
data division.
working-storage section.
77 current-nbr pic 9(4) value zeroes.
77 square pic 9(6) value zeroes.
77 split pic 9(6) value zeroes.
77 top-half pic 9(3) value zeroes.
77 bottom-half pic 9(3) value zeroes.
77 sum-of-halves pic 9(6) value zeroes.
01 kap-numbers value all zeroes.
03 result pic 9(3) occurs 100 times indexed by accrue-idx, display-idx.
77 results pic x(80) value spaces.
77 results-ptr pic 9(2) value 1.
77 formatted-nbr pic x(3) value spaces.
procedure division
. calculate-kaprekars.
set accrue-idx to 1
perform varying current-nbr from 1 by 1 until current-nbr > 999
multiply current-nbr by current-nbr giving square
*> Determine the split for the square
evaluate true
when square >= 10000
move 1000 to split
when square >= 100
move 100 to split
when other
move 10 to split
end-evaluate
*> Split, sum, and compare
divide square by split giving top-half remainder bottom-half
add top-half bottom-half giving sum-of-halves
if sum-of-halves = current-nbr
move current-nbr to result(accrue-idx)
set accrue-idx up by 1
end-if
end-perform
set accrue-idx down by 1
perform varying display-idx from 1 by 1 until display-idx > accrue-idx
*> Left-justified numbers
evaluate true
when result(display-idx) < 10
move result(display-idx)(3:1) to formatted-nbr
when result(display-idx) < 100
move result(display-idx)(2:2) to formatted-nbr
when other
move result(display-idx) to formatted-nbr
end-evaluate
string formatted-nbr delimited by space into results with pointer results-ptr
if display-idx not = accrue-idx
string ', ' into results with pointer results-ptr
end-if
end-perform
display results
goback
.
end program kaprekar.
(Fixed format: col 1-6 reserved, usually line numbers or blank; col 7 - "*" = comment, blank otherwise; col 8-11 - division/section identifiers, paragraph names, top-level data items; col 12-72 - executable code, data item sub-definitions; col 73+ - ignored)
identification division.
program-id. kaprekar.
data division.
working-storage section.
77 current-nbr pic 9(4) value zeroes.
77 square pic 9(6) value zeroes.
77 split pic 9(6) value zeroes.
77 top-half pic 9(3) value zeroes.
77 bottom-half pic 9(3) value zeroes.
77 sum-of-halves pic 9(6) value zeroes.
01 kap-numbers value all zeroes.
03 result pic 9(3) occurs 100 times
indexed by accrue-idx,
display-idx.
77 results pic x(80) value spaces.
77 results-ptr pic 9(2) value 1.
77 formatted-nbr pic x(3) value spaces.
procedure division
. calculate-kaprekars.
set accrue-idx to 1
perform varying current-nbr from 1 by 1
until current-nbr > 999
multiply current-nbr by current-nbr giving square
*> Determine the split for the square
evaluate true
when square >= 10000
move 1000 to split
when square >= 100
move 100 to split
when other
move 10 to split
end-evaluate
*> Split, sum, and compare
divide square by split giving top-half
remainder bottom-half
add top-half bottom-half giving sum-of-halves
if sum-of-halves = current-nbr
move current-nbr to result(accrue-idx)
set accrue-idx up by 1
end-if
end-perform
set accrue-idx down by 1
perform varying display-idx from 1 by 1
until display-idx > accrue-idx
*> Left-justified numbers
evaluate true
when result(display-idx) < 10
move result(display-idx)(3:1) to formatted-nbr
when result(display-idx) < 100
move result(display-idx)(2:2) to formatted-nbr
when other
move result(display-idx) to formatted-nbr
end-evaluate
string formatted-nbr delimited by space into results
with pointer results-ptr
if display-idx not = accrue-idx
string ', ' into results with pointer results-ptr
end-if
end-perform
display results
goback
.
end program kaprekar.
Here's my Ruby novice solution -- Works for the known oddballs (4879, 5292, 38962). Prepending '0' to odd-sized numbers inspired by others here.
defkaprekar?(k)s=k.to_s.size# s = nr. of digits in kk_sq=(k**2).to_s# k_sq = square of k (String)k_sq.prepend("0")if(k_sq.size.even?==false)# prepend '0' to odd-sized numbersifk_sq[s-1]=="0"# if digit 's-1' is 0, loop different combinations(0..s).eachdo|x|part1=k_sq[0..x-1].to_ipart2=k_sq[x..-1].to_ireturntrueif(k==part1+part2)endelse# if not, split before digit 's' (Integers)part1=k_sq[0..s-1].to_ipart2=k_sq[s..-1].to_ireturntrueifk==(part1+part2)endfalse# else returns falseend
I have much sympathy for LISP and Clojure but have not that much experience with it. So, to stay in touch with it, here is my Clojure program, mostly a one-to-one translation of my latest Haskell program:
(nskaprekar.core(:gen-class))(use'[clojure.math.numeric-tower:asmath])(defnisKaprekar?[basen](let[sqr(*nn)](->>(map#(math/exptbase%1)(range)); list of divisors(drop-while#(<=%1n)); discard if too small(take-while#(<%1sqr)); discard if too big(some#(=0(mod(-sqrn)(-%11))))))); remainder = 0? <=> kaprekar(defnfindKaprekar[basen](->>(rangen)(filter#(isKaprekar?base%1))(cons1)))(defn-main"Finding the Kaprekar number base 10 up to 10000000"[&args](time(print(findKaprekar10(math/expt108)))))
I really like the threading macros. :-) Computing up to 10^8 , the execution time of the jar file is ten times the execution time of the compiled Haskell. Did I make a serious mistake, performance-wise? Of course, there is the JVM, but I didn't expect this program to be slower with factor 10.
And if you consider that parts of a number should not necessarily be of equal size, the solution becomes a bit more wordy (suppose, a lot can be improved here):
I managed to reduce the number of divisions by throwing some mathematics on it. Put very short:
The improvements are:
The computation time for the search up to 10^8 is reduced to 4 % compared to my original code.
I love seeing the iterations of your solutions. Not that this challenge was intended to have any "winners," but if we had to choose...
Do you have any ideas for new #challenge posts?
Thanks. I enjoyed learning about Kaprekar number as well as I enjoyed iterating my solutions as I digged deeper into it.
You encouraged me to pose a challenge, hoping it's not too easy and not too hard. dev.to/heikodudzus/challenge---pri...
BTW: I saw a possible error in my last iteration. takeWhile (<n) is not proven to be correct. It's better to do it that way:
Also, it's nicer to use upper and lower bounds for divisors before computing the devisions. This is proven to be correct now, but I lost speed. ;-) The speed improvement by melting construction and restriction together is only 86% instead of 96%.
Some last improvements:
The improvement steps were: 1000s - 500s - 90s - 60s - 19s - 13s - 9s. Quite funny to squeeze the algorithm like that. :-) This is what I came up with:
I wanted to have it in C for reference. Even expressed imperatively, it is now a very simple and nice algorithm. (2-3s)
C profited more by the additional division, it reduced the execution time by 75%, Haskell profited only by 50 %.
I hope, I'm really done, now. :)
Time to get my repl up and running. Not very clean, but gets the job done. Here's some Clojure:
Thanks to Richard Orelup' tip to zero-pad the number if its length is odd.
Taking inspiration from Thomas Much's answer, I refactored my code to be more functional-esque and idiomatic:
For those a fan of Guile:
I'm not pretty good at coding but I tried in my own way :) just for fun and I hope is ok.
Here is my JS version:
Here is the JSFiddle link:
jsfiddle.net/kw95nv45/2/
Solution in Haskell:
I didn't want to take the route to String representation and back, I considered it as a computational problem and I wanted to find a purely computational solution. So I used digit values. Drawbacks: It appends number 1 as being kaprekar by convention. Benefit: It works for all bases (although output is decimal).
f is like:
f returns a list of sums of quotient and remainder. Now filter in the solution function, if n is an element of f n.
I tried to compute the Kaprekar numbers up to 108. A simple improvement in taking the interesting part and dropping the rest: If quotient or remainder are > n the sum of both must be > n. This reduced execution time by 50 %.
Could I trouble someone to comment this code? Oops, I guess that's in the parent comment, thanks!I don't know Haskell but I'm interested in it. Does this solution work for the 'strange' ones like 4789, 5292?Trying to wrap my head around how to interpret the definition of a Kaprekar number, in a way that includes these oddball numbers.
I'm currently studying Ruby -- I'll necro-post my Ruby solution if I manage to get it working with the oddballs.
Here is my Javascript version of Kaprekar numbers
As far as I can see, most (if not all) programs use the strategy to convert the square to a string, pad it with 0 if the length is not even, and split it in the middle.
This seems to work for the range of Kaprekar numbers in the given range [1..999]. However, when I tried to speed up my program by splitting in the middle, I found out a problem with 5292. It is a Kaprekar number:
But to recognize it, you have to split 2 and 6 of 8 digits.
The implicit assumption about the Kaprekar property to show up when the number is split in the middle seems to be wrong. I tested some Javascript programs of this challenge with 5292 and it is not recognized as Kaprekar number.
Dang, that's a great point. I should have made the OP more detailed to clarify that the "split" isn't always right down the middle — even if it happens to work in the [1...999] range.
I definitely didn't think of that possibly while creating the post, or while working on my personal solution.
What does your approach to this look like? Now you've got me curious about how you're going about solving it.NVM, now I see your other comment.Is anyone interested in finding another 'strange' Kaprekar number like 5292?
I searched among the first 91 Kaprekar numbers in the range [ 1..108 ]. So far, 5252 is the only one you have to split asymmetrically.
What makes 5292 so special?
4879 is 'strange', too:
4879 = 238 + 04641
Ok, I see. I've missed it because of the leading zero in the second part.
I think your OP is really ok. I also didn't expect something like this. I think I will inspect some higher Kaprekar number.
But I am looking forward to see how the JS/Java/Clojure/LISP-like solutions get fixed (and I apologize for beeing such a killjoy ;-)
This was a lot harder than I thought mainly because I had to look up why some numbers were and weren't Kaprekar numbers because the above description doesn't include all the details. First gotcha is the second part of the split numbers must be positive (no zeros). The second part was that you add a zero to the front if the length is odd.
And I already refactored my answer. I'm happier with this one.
Awesome job refactoring, and apologies for not including the pertinent info re: zeros in the OP!! I'll add that info to the main post.
Figure it's only fair to throw my answer into the ring. Clearly very novice and verbose 😇. Added a number of comments for the other #beginners out there.
Ok, here's a Java 8 version:
As Heiko points out, the solution was incorrect, because the split was always done in the middle of the string...
So, here's a (hopefully correct) Java 9 solution (Java 9 because I use takeWhile):
I chose to output the first 16 numbers so we can see the output includes numbers 4879 and 5292.
I really like to see your use of Streams and lambdas solving this problem. Nice occasion for me to learn a little bit more about them.
OK - this was way more of a rabbit hole than I thought... :) Here's two, new (F#) and old (COBOL). Both of these work within the constraints of the initial challenge, but will fail outside of that; had I not spent the amount of time I already spent on these, I might have at least made the F# version be able to handle others.
p.s. 0 also fits the description from the tweet! (02 = 0; 00 = 0 + 0 = 0; 0 = 0)
F#
COBOL
(Free format, "*>" denotes a comment)
OK - fixed format, just for grins...
(Fixed format: col 1-6 reserved, usually line numbers or blank; col 7 - "*" = comment, blank otherwise; col 8-11 - division/section identifiers, paragraph names, top-level data items; col 12-72 - executable code, data item sub-definitions; col 73+ - ignored)
Holy cow - the formatter knows COBOL! If I'd used fixed format, it wouldn't even look weird.
Here's my Ruby novice solution -- Works for the known oddballs (4879, 5292, 38962). Prepending '0' to odd-sized numbers inspired by others here.
I don't like the exceptions (4879, 5292, 38962...) -- it feels like they don't belong in the sequence. And look how pretty the code is without them!
Because I haven't done Groovy for a while. I miss it!
I have much sympathy for LISP and Clojure but have not that much experience with it. So, to stay in touch with it, here is my Clojure program, mostly a one-to-one translation of my latest Haskell program:
I really like the threading macros. :-) Computing up to 10^8 , the execution time of the jar file is ten times the execution time of the compiled Haskell. Did I make a serious mistake, performance-wise? Of course, there is the JVM, but I didn't expect this program to be slower with factor 10.
Pythonic mine's:
Usage:
python script.py maxmaxis the maximum integer to look up to (3037000499):Something like this in python
Seems I'm pretty late for this, but anyway, here's some Rust solution:
And if you consider that parts of a number should not necessarily be of equal size, the solution becomes a bit more wordy (suppose, a lot can be improved here):