Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

A Kaprekar number is an n-digit number k that, when the first n or n-1 digits of k^2 are added to the second n the digits of N^2, the result is N.

Examples:

9^2 = 81.  8+1 = 9.
45^2 = 2025.  20+25 = 45.
297^2 = 88,209. 88+209 = 297

The Kaprekar sequence begins at 1.

Write a program that calculates and outputs the first n Kaprekar numbers, with n being in the range, but not limited to the range, of 1 to 100. Each Kaprekar number must be separated with whitespace and nothing else.

More Kaprekar numbers can be found here to check your program against, but this resource MAY NOT be used in any way to help with the calculation - in other words, no hard-coding, reading from this source, or using it in any other exploitive way - all the numbers must be generated by your program.

Shortest code wins.

share|improve this question
    
@devnull Is this better? It means that the program must support an n up to at least 100. –  hosch250 Feb 27 at 4:45
    
MathWorld's definition conflicts with A006886 (MathWorld specifies that m is the length of the original number, A006886 specifies that it is at least that large). Your definition in the first paragraph is slightly different than both. –  primo Feb 27 at 5:04
    
@primo OK, I get it now. Will revise. –  hosch250 Feb 27 at 5:18
    
Ahh, you're right. They are equivalent statements. A note should be made that the two definitions are not identical, though. 4879 is the first counter example (the square is split 3:5, rather than 4:4). –  primo Feb 27 at 5:22
    
@primo Is this better? So the length of the number squared must be equal to twice the length of the number or twice the length of the number plus 1? –  hosch250 Feb 27 at 5:24
show 6 more comments

11 Answers

up vote 4 down vote accepted

Perl - 63 bytes

#!perl -l
map{1while$l=length++$_,$_**2=~/.{$l}$/,$`+$&^$_;print}($_)x<>

Counting the shebang as one byte. Input is taken from stdin.

This has an acceptable runtime for n ≤ 50, after that it gets a bit slow.

Sample usage:

$ echo 20 | perl kaprekar.pl
1
9
45
55
99
297
703
999
2223
2728
4950
5050
7272
7777
9999
17344
22222
77778
82656
95121
share|improve this answer
    
No problem about the runtime. This is just code golf. –  hosch250 Feb 27 at 6:05
1  
+1 for readability (very pretty, indeed) –  devnull Feb 27 at 11:35
add comment

C, 109 106

long long i=1;x=10,n;main(){scanf("%d",&n);for(;n;x*=x<=++i?10:1)(i-i*i/x-i*i%x)||printf("%lld ",i,n--);}
  • with n up to 17 it would be ok to remove the long long,
  • The exceeding printf parameter is abused:)
  • Why it is not possible to use empty statement in the ternary operator? the two 1 are silly...
  • Thank to Josh for aditional 3 characters...
share|improve this answer
1  
If you only care about the false value, you can use boolean logic instead of a ternary statement. Example, (i-i*i/x-i*i%x)||printf(...). –  Josh Feb 27 at 14:53
1  
You can also initialize x and i at the global scope instead of in the for loop to save a couple chars. –  Josh Feb 27 at 14:54
add comment

Mathematica 144 154

k@m_:=((x=m^2)-(w=FromDigits[Take[IntegerDigits@x,y=-IntegerLength@m]]))*10^y+w==m;
g@n_:=(s={};i=0;While[Length@s<n,If[k@i,s=Append[s,i]];i++];s)   

Test

g[14]

0
1
9
45
55
99
297
703
999
2223
2728
4950
5050
7272

share|improve this answer
    
Your output does not meet the criteria Each Kaprekar number must be separated with whitespace and nothing else. –  RononDex Feb 27 at 9:53
    
RononDex. I adjusted the output. –  David Carraher Feb 27 at 12:49
add comment

Javascript 96

for(i=0,n=prompt(s='');n;i++){t=''+i*i;if(t.substr(0,l=t.length/2)==i-t.substr(‌​l))n--,s+=i+' '}s

Output :

0 1 9 45 55 99 297 703 999 2223 2728 4950 5050 7272 7777 9999 17344 22222 77778 82656 95121 99999 142857 148149 181819 187110 208495 318682 329967 351352 356643 390313 461539 466830 499500 500500 533170 538461 609687 643357 648648 670033 681318 791505 812890 818181 851851 857143 961038 994708 999999 
share|improve this answer
    
The input specifies the number of values to output, and not the maximum value. –  primo Feb 27 at 14:31
    
missed that, fixed ! –  Michael Feb 27 at 14:47
1  
96: for(i=0,n=prompt(s='');n;i++){t=''+i*i;if(t.substr(0,l=t.length/2)==i-t.substr(‌​l))n--,s+=i+' '}s –  Florent Feb 27 at 15:08
    
Bien joué Florent :) –  Michael Feb 27 at 16:36
    
Why don't you store the values in an array and simply join them? –  Ismael Miguel Feb 28 at 3:52
show 1 more comment

C# - 255 Characters.

int x=100;decimal k=0;while(x>0){k++;decimal d=k*k;string s=d.ToString("n").Replace(",","").Split('.')[0];int g=k.ToString().Length;int h=s.Length;if(k==d||(h!=g&&long.Parse(s.Substring(h-g))+long.Parse(s.Substring(0,h-g))==k)){Console.Write(k+" ");x--;}}

x is the number of Kaprekar numbers you wish the code to find. This has been tested in the range of 1 to 100 but should support a lot more than this. 100 numbers took two and a quarter hours to return although the first 50 only took about 1 second - things slowed down gradually after that.

Output:

1 9 45 55 99 297 703 999 2223 2728 4950 5050 7272 7777 9999 17344 22222 77778 
82656 95121 99999 142857 148149 181819 187110 208495 318682 329967 351352 356643 
390313 461539 466830 499500 500500 533170 538461 609687 643357 648648 670033 
681318 791505 812890 818181 851851 857143 961038 994708 999999 4444444 4927941 
5072059 5555556 9372385 9999999 11111112 13641364 16590564 19273023 19773073 
24752475 25252525 30884184 36363636 38883889 44363341 44525548 49995000 50005000 
55474452 55636659 61116111 63636364 69115816 74747475 75247525 80226927 80726977 
83409436 86358636 88888888 91838088 94520547 99999999 234567901 332999667 
432432432 567567568 667000333 765432099 999999999 1111111111 1776299581 2020202020 
3846956652 3888938889 4090859091 4132841328 4756047561

Laid out this code is as follows;

        int x = 100;
        decimal k = 0; 
        while (x > 0) 
        {
            k++;
            decimal d = k * k;
            string s = d.ToString("n").Replace(",", "").Split('.')[0];
            int g = k.ToString().Length; 
            int h = s.Length; 

            if (k == d || (h != g && long.Parse(s.Substring(h - g)) + long.Parse(s.Substring(0, h - g)) == k) )
            { 
                Console.Write(k + " "); x--; 
            } 
        }

I'd love to know if this can be shortened further.

share|improve this answer
add comment

Python 2.7, 144 (including newlines)

def c(c):
 l="1";i=2;u=1
 while u<c:
  r=str(i**2);w=len(r)
  if w>1:
   if i==int(r[:w/2])+int(r[w/2:]):
    l+=" "+str(i);u+=1
  i+=1
 print l

Output for c = 10:

1 9 45 55 99 297 703 999 2223 2728

Output for u = 20:

1 9 45 55 99 297 703 999 2223 2728 4950 5050 7272 7777 9999 17344 22222 77778 82656 95121
share|improve this answer
    
Whoops! Fixed that now. Slightly longer, but correct. I discovered semicolons in Python! Hurrah! –  KBKarma Feb 27 at 15:17
2  
Then this will blow your mind: line 7 can go at the end of the previous line. –  primo Feb 27 at 15:19
    
... Oh. Ah damn. Oh well. Still pretty good for something I knocked together during my lunch break, considering that my knowledge of Python is meagre at best. –  KBKarma Feb 27 at 18:37
add comment

python - 98

I used some nice python slicing to shave a few characters off.

i=n=0
while n<20:
 i+=1;s=str(i**2);l=-len(str(i))
 if int("0"+s[:l])+int(s[l:])==i:print(i);n+=1
share|improve this answer
    
Nice job. I ran out of votes for today, but I will upvote it in a hour. –  hosch250 Feb 27 at 22:14
add comment

R, 99 characters

k=n=0;N=scan();while(n<N){k=k+1;j=k^2;i=10^ceiling(nchar(j)/2);if(k==j%/%i+j%%i){cat(k," ");n=n+1}}

With i being half the number of digits of k^2 rounded up, the evaluation of wether k is a Kaprekar number is performed here by adding the quotient and the remainder of the integer division of k^2 by 10^i (the quotient being the left half of the digits rounded down and the remainder the right half rounded up).

share|improve this answer
add comment

bash+sed, 75 characters

Bash does integer-only arithmetic and represents numbers as decimal strings; these attributes are helpful for golfing this challenge. Also undeclared/unassigned variables are assumed to have a value of 0 when doing arithmetic.

for((;s=++i*i,l=${#s}/2,1;));{
((${s:0:l}+10#${s:l}-i))||echo $i
}|sed $1q

It irked me to put the 10# in there, but something like this is necessary if the second half of the split starts with a 0. When doing arithmetic, treats such numbers as octal, unless the base is explicitly stated.

$ ./kaprekar.sh 10
1
9
45
55
99
297
703
999
2223
2728
$ 
share|improve this answer
add comment

Python 3.3 - 117 characters

n=int(input())
p=1
while n>0:
    v=str(p**2)
    l=len(v)
    if p==int(v[l//2:])+int('0'+v[:l//2]):
        print(p)
        n-=1
    p+=1

Each level of indentation, and each newline except the final one, all count for 1 character. I think that is fair for Python code. The script expects the user to input the number of Kaprekar numbers to compute.

share|improve this answer
add comment

J - 64

Kinda ugly, but still. It checks all numbers up to one million then takes n of them, so it works only for n<=50.

n{.}.I.(]=+/&;&:(10&#.&.>)&(<.@-:@#({.;}.)])&(10&#.inv@*:))i.1e6

n is where to put the input

share|improve this answer
    
In the spec, it said to calculate up to 100 of them. It probably wouldn't add that many characters to add another variable solely for counting the number of Kaprekar numbers found. –  hosch250 Feb 28 at 16:13
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.