26
\$\begingroup\$

Why is the number 6174 so interesting? As defined by Wikipedia

  1. Take any four-digit number, using at least two different digits. (Leading zeros are allowed.)
  2. Arrange the digits in ascending and then in descending order to get two four-digit numbers, adding leading zeros if necessary.
  3. Subtract the smaller number from the bigger number.
  4. Go back to step 2.

The above process, known as Kaprekar's routine, will always reach 6174 in at most 7 iterations. Once 6174 is reached, the process will continue yielding it.

Write a program which runs the Kaprekar's routine against a given four-digit number (see definition above) printing out each step of the routine.

Rules:

  • Submissions must be complete programs.
  • Input must be read from standard input. Piping from echo is OK.
  • Input should be in numeric form.
  • Printing out leading zeros is required. (See examples below.)
  • Last line should say how many iterations were needed. Punctuation is required.

Examples:

> 2607
7620 - 0267 = 7353
7533 - 3357 = 4176
7641 - 1467 = 6174
Iterations: 3.

> 1211
2111 - 1112 = 0999
9990 - 0999 = 8991
9981 - 1899 = 8082
8820 - 0288 = 8532
8532 - 2358 = 6174
Iterations: 5.

> 6174
7641 - 1467 = 6174
Iterations: 1.

Any programming language is welcome. Extra points for esoteric ones + a small bounty.

Update 1: There is already a similar question.

Update 2: Added example for 6174 as input. Thanks to Peter Taylor for the notice.

\$\endgroup\$
12
  • \$\begingroup\$ This is news for me. Someone call a moderator... \$\endgroup\$
    – lunohodov
    Jun 6, 2011 at 21:44
  • \$\begingroup\$ Uh... isn't there a "migrate" button? \$\endgroup\$ Jun 6, 2011 at 22:20
  • \$\begingroup\$ I've flagged this for a moderator to migrate. May I suggest altering the rules on input output to agree with the earlier 3-digit version? And linking to the earlier version in the body of the question. \$\endgroup\$ Jun 7, 2011 at 1:12
  • \$\begingroup\$ @dmckee I didn't know about this site and could not know that there is already a similar question (on stackoverflow there was none). However I would hesitate altering the rules to agree with the 3-digit version and thus making the two questions even more similar. It is pointless to post a duplicate or a slight variation of an existing question. Even when done unintentional. \$\endgroup\$
    – lunohodov
    Jun 8, 2011 at 8:47
  • 3
    \$\begingroup\$ Please add 6174 as an example so we can see how the output should be formatted. \$\endgroup\$ Jun 10, 2011 at 6:26

22 Answers 22

10
\$\begingroup\$

Ruby 1.9, 122 characters

puts"Iterations: #{(1..7).find{s=$_.chars.sort*"";puts [r=s.reverse,?-,s,?=,$_="%04d"%(r.to_i-s.to_i)]*" ";~/6174/}}."

Example invocation:

$ echo 1211 | ruby -ln kaprekar.rb

I've counted the -ln flag as 4 characters (difference between the normal invocation ruby kaprekar.rb and ruby -ln kaprekar.rb).

\$\endgroup\$
4
  • \$\begingroup\$ I saved this script as kaprekar.rb then invoked it with ruby -lp kaprekar.rb. Entered a number and pressed <Enter> but the output is the entered number itself. Clearly I am missing something... Please advise how to use the script. \$\endgroup\$
    – lunohodov
    Jun 16, 2011 at 12:52
  • \$\begingroup\$ @lunohodov: I've added an example invocation. It now also generates the correct output for 6174 as input, which unfortunately brings this solution up to 128 characters. \$\endgroup\$
    – Ventero
    Jun 16, 2011 at 21:54
  • \$\begingroup\$ Using echo 1234 | ruby kaprekar.rb raises a warning and ends with an error undefined method 'chars' for nil:NilClass (NoMethodError). Executing echo 1234 | ruby -lp kaprekar.rb issues only a warning and behaves as expected. The output is not as expected, as it contains a warning message kaprekar.rb:3: warning: regex literal in condition \$\endgroup\$
    – lunohodov
    Jun 17, 2011 at 9:12
  • \$\begingroup\$ @lunohodov: Fixed the warning and the example invocation. \$\endgroup\$
    – Ventero
    Jun 17, 2011 at 9:30
9
\$\begingroup\$

Perl - 147 143 134 130 129 126 129 128 126

for($_=<>;$_-6174+!$c;$c++){$_=reverse$d=join'',sort split//,"$_"
|$|x4;printf"$_ - $d = %04d\n",$_-=$d}die"Iterations: $c.\n"

EDIT: Now complies with 6174 case, at the cost of a few chars... run with echo -n <number> | perl kaprekar.pl

EDIT: Finally back to where I was before :D

\$\endgroup\$
7
\$\begingroup\$

Python, 141 chars

n=input()
i=0
while n-6174:a=''.join(sorted("%04d"%n));b=a[::-1];n=int(b)-int(a);print"%s - %s = %04d"%(b,a,n);i+=1
print"Iterations: %d."%i
\$\endgroup\$
3
  • \$\begingroup\$ +1 for slick padding with %04d. I learned something today! \$\endgroup\$
    – arrdem
    Jun 7, 2011 at 20:49
  • 3
    \$\begingroup\$ A few suggestions: put the whole loop on one line using ;s. while n-6174. No space between print and the quote. \$\endgroup\$ Jun 8, 2011 at 3:31
  • \$\begingroup\$ @keith-randall: thanks, got it down to 141 now. \$\endgroup\$ Jun 8, 2011 at 11:55
6
+25
\$\begingroup\$

Golfscript, 74 characters

);:|;{0):0;|$:§-1%" - "§" = ""0"4$~§~-+-4>:|n|6174`=!}do"Iterations: "0"."
\$\endgroup\$
5
\$\begingroup\$

><> - 268 308

</&4pff1
v>i86*-:n&1-:&?!
>ao&        v
<v&0pff+1gff
 >&1+:4=   ?v&:a%:}-a,
 v&8[4r::0}~<
 >&1-:?!v&:@@:@(?$}&:&3%1=?}
 v      >~:}}:}@:}$:}
 \:n}:n}:n}:n}' - 'ooo:n}:n}:n}:n}' = 'ooo
 \a*+a*+a*+}a*+a*+a*+-:0&\
 v?       =4&:+1&,a-}:%a:<
/\&~~rnnnnao:29777****=   ?v
voooooooooooo"Iterations: "/
\ffgna'.'oo;

Not much of a contender for golf, but it was fun to write. :)

Run with ./fish.py kaprekar.fish -v <number>
EDIT: Now takes input from STDIN.

\$\endgroup\$
0
5
\$\begingroup\$

Haskell, 197 192 182 181 characters

import List
p=putStrLn.unwords
"6174"%k|k>0=p["Iterations:",shows k"."]
n%k=p[b,"-",a,"=",c]>>c%(k+1)where a=sort n;b=reverse a;c=take 4$shows(read b-read a)"0"
main=getLine>>=(%0)
\$\endgroup\$
3
  • \$\begingroup\$ Inlining r and s saves 2 characters. Also, "000" is redundant. "0" is enough. This brings us to 188 characters. I'm surprised interact does not help here. It usually does. \$\endgroup\$
    – Rotsor
    Jun 20, 2011 at 4:04
  • \$\begingroup\$ Replacing show x++s with shows x s gains 2 more bytes. 186 now. \$\endgroup\$
    – Rotsor
    Jun 20, 2011 at 4:28
  • \$\begingroup\$ By using pattern guards (|k>0) one can get rid of f. Further renaming g to % gets us to 182 chars. \$\endgroup\$
    – Rotsor
    Jun 20, 2011 at 5:18
4
\$\begingroup\$

JavaScript, 189 182 165 chars

Credit to DocMax:

for(n=prompt(i=o=e='');!i--|n-6174;o+=n+' - '+a+' = '+(n=(p=n-a+e)[3]?p:0+p)+'\n')
  b=n.split(e).sort(),n=b.reverse(a=b.join(e)).join(e);
alert(o+"Iterations: "+~i+'.')

Original:

for(n=prompt(i=o=e='');n-6174;o+=(i++?n+"\n":e)+(n=(a=n.split(e).sort().join(e)).split(e).reverse().join(e))+' - '+a+' = ',n=n-a+e)while(!n[3])n=0+n
alert(o+n+"\nIterations: "+i+'.')

Ungolfed:

var i = 0;
var n = prompt();
var out = '';
while (n != 6174) {
    while ((n=''+n).length<4) n='0'+n // pad number
    if(i)out+=n+"\n"

    a = n.split('').sort().join('');
    n = a.split('').reverse().join('');

    out += n + ' - ' + a + ' = '
    n-=a
    i++;
}
console.log(out + "6174\nIterations: " + i + '.');
\$\endgroup\$
8
  • 1
    \$\begingroup\$ I think that you can change n != 6174 to n-6174 since it will return zero, which is false (at least in C and Python). \$\endgroup\$ Jun 10, 2011 at 12:56
  • \$\begingroup\$ The credit should go to keith-randall who suggested it for my Python solution. \$\endgroup\$ Jun 10, 2011 at 16:57
  • \$\begingroup\$ You can save 5 more characters by replacing while(n.length<4) with while(!n[3]). \$\endgroup\$
    – DocMax
    Jun 16, 2011 at 3:27
  • 1
    \$\begingroup\$ I can't stop staring at this one! The following a) fixes the output when n=6174, b) rearranges when n+'\n' is added to avoid the conditional and an extra \n, c) uses a temp to avoid a join-split-join sequence, d) takes advantage of the fact that we only ever have to add a single '0' for padding: for(n=prompt(i=0,o=e='');n-6174;i++,o+=(n=(b=n.split(e).sort(),a=b.join(e),b).reverse().join(e))+' - '+a+' = '+(n=('0'+(n-a)).slice(-4))+'\n');alert(o+"Iterations: "+i+'.') which should be 172 chars. \$\endgroup\$
    – DocMax
    Jun 17, 2011 at 6:31
  • 1
    \$\begingroup\$ Impressive! According to the spec above though, when n=6174, it has to go through at least one iteration, so I added a check if i is 0 (+4) but combined that with the i++. Unfortunately, that gives an off by one error, so I switched the increment to a decrement and then used a little bitwise trickery at the end (-1). Then I changed i=0,o=e='' to i=o=e='' (-2), reformatted the for loop to avoid extra parentheses (-1), expanded (b=...,a=...,b) bit (-2), and sneaked a=b.join inside the reverse() call (-1). So 169, not bad! \$\endgroup\$
    – Casey Chu
    Jun 17, 2011 at 8:00
3
\$\begingroup\$

PowerShell, 125 128 130 131

for($a,$OFS=$input+'';$b-6174;++$i){$a=$b=+($c=''+($x="$a 000"[0..4]|sort)[4..0])-"$x"
"$c-$x = {0:d4}"-f$a}"Iterations: $i."

Passes all test cases from the question.

\$\endgroup\$
2
\$\begingroup\$

JavaScript, 260 bytes

function z(c){for(u=c+y;u.length<4;)u=0+u;return u}for(p=prompt(i=0,r=y="");;)
if(s=(p+y).split(y).sort(),t=s.concat().reverse(),a=s.join(y),b=t.join(y),q=a<b?b:a,
w=a<b?a:b,p=z(q-w),i++,r+=z(q)+" - "+z(w)+" = "+p+"\n",p==6174)break;alert(r+
"Iterations: "+i+".")
\$\endgroup\$
2
\$\begingroup\$

Clojure, 256 characters

(let[i #(Integer/parseInt%)f #(format"%04d"%)a #(->>% f sort(apply str)i)d #(->>% f sort reverse(apply str)i)k #(let[u(d %)l(a %)n(- u l)](println(f u)"-"(f l)"="(f n))n)](while true(println"Iterations:"(count(take-while #(not=% 6174)(iterate k(read)))))))
\$\endgroup\$
2
\$\begingroup\$

Scala 2.9, 194 characters

object K extends App{var(c,s)=(0,args(0));do{var d=s.sorted;var e=d.reverse.toInt-d.toInt;s="%04d".format(e);println(d.reverse+" - "+d+" = "+s);c+=1}while(s!="6174");print("Iterations: "+c+".")}

Makes use of the App trait from Scala 2.9.

Edit: gives correct output for initial input of 6174.

\$\endgroup\$
2
\$\begingroup\$

PHP, 215 259 276 characters

<?php echo">";$n=str_split(str_pad(trim(fgets(STDIN)),4,0,0));for($k=0,$z=0;$k-6174;$z++){sort($n);$a=implode($n);$b=strrev($a);$k=str_pad($b-$a,4,0,0);echo"$b - $a = $k\n";$n=str_split($k);}echo"Iterations: $z\n";

Ungolfed:

<?php
echo ">";
$n = str_split(str_pad(trim(fgets(STDIN)),4,0,0));
for($k=0, $z=0; $k-6174; $z++) {
    sort($n);
    $a = implode($n);
    $b = strrev($a);
    $k = str_pad($b-$a,4,0,0);
    echo "$b - $a = $k\n";
    $n = str_split($k);
}
echo "Iterations: $z\n";
\$\endgroup\$
4
  • \$\begingroup\$ I don't think you need the abs, max and min functions, since the sort will always mean that $b is greater than $a. That could save you 20ish characters. Also, I think that putting the sort inside the loop at the top will mean you only need to have it in your code once which will save you another 9. \$\endgroup\$
    – Gareth
    Jun 15, 2011 at 8:05
  • \$\begingroup\$ Wow, I guess I got distracted by the "subtract the smaller number from the bigger number" instruction. Thanks. \$\endgroup\$
    – rintaun
    Jun 15, 2011 at 8:25
  • \$\begingroup\$ <?function k($c){echo"> $c\n";$n=str_split(str_pad($c,4,0,0));for(;$k-6174;$z++){sort($n);$a=join($n);$b=strrev($a);$k=str_pad($b-$a,4,0,0);echo"$b - $a = $k\n";$n=str_split($k);}echo"Iterations: $z\n";} You can save 12 characters by changing your for statement, calling this as a function and using join instead of implode. \$\endgroup\$ Oct 17, 2012 at 19:02
  • \$\begingroup\$ Also, I hate mini-markdown. \$\endgroup\$ Oct 17, 2012 at 19:03
2
\$\begingroup\$

CoffeeScript, 233 225 characters

o=e='';i=0;n=prompt()
while n!=6174
  n=e+n;q=(n='0'+n if !n[3]) for x in [0..2];n?=q;o+=n+"\n" if i;a=n.split(e).sort().join(e);n=a.split(e).reverse().join(e);o+=n+' - '+a+' = ';n-=a;i++
alert(o+"6174\nIterations: "+i+'.')

Try it here or with instructions here.

\$\endgroup\$
6
  • \$\begingroup\$ My browser freezes - had to cancel the execution of the script. \$\endgroup\$
    – lunohodov
    Jun 16, 2011 at 17:31
  • \$\begingroup\$ What number did you enter? I tried it in Firefox and Chrome for 4711 and 1 and a couple of others. \$\endgroup\$ Jun 16, 2011 at 20:19
  • \$\begingroup\$ Using 0 (as suggested by the prompt) or clicking the cancel button causes Safari to freeze. \$\endgroup\$
    – lunohodov
    Jun 17, 2011 at 9:17
  • \$\begingroup\$ I don't know why it suggested that. You have to enter a number between 1 and 9998 whose digits are not all identical. 0 is the same as 0000 and will cause an infinite loop. It seems most of the solutions here skipped validating input to keep the number of characters down. \$\endgroup\$ Jun 17, 2011 at 11:43
  • \$\begingroup\$ See i56.tinypic.com/bhhoqe.png Your output also ends with "It took 5 iterations to reach Kaprekar's constant." which does not conform to the requirements. \$\endgroup\$
    – lunohodov
    Jun 17, 2011 at 12:12
2
\$\begingroup\$

Scala 276

object o{var i=0;def a(v:String){val c=v.toList.sortWith(_>_).mkString;val b=c.reverse;val d=c.toInt-b.toInt;val e="0"*(4-(d+"").length)+d;val p=c+" - "+b+" = "+e;if(d!=6174){println(p);i=i+1;a(e)}else{println(p+"\nIterations: "+(i+1)+".")}};def main(s:Array[String])=a(s(0))}

Scala 283

object o{var i=0;def a(v:String){val c=v.toList.sortWith(_>_).mkString;val b=c.reverse;val d=c.toInt-b.toInt;val e="0"*(4-(d+"").length)+d;val p=c+" - "+b+" = "+e;if(d!=6174){println(p);i=i+1;a(e)}else{println(p);println("Iterations: "+(i+1)+".")}};def main(s:Array[String])=a(s(0))}

diff:

else{println(p);println("Iterations: "+(i+1)+".")}};
// to
else{println(p+"\nIterations: "+(i+1)+".")}};
\$\endgroup\$
2
\$\begingroup\$

GAWK - 152 chars

This is a GNU awk version. It may not work with other non-gnu versions.

{for(z=$1;z-6174+!c;++k){split(z,a,"");asort(a);for(b=c=i=0;i<4;z=c-b){c+=a[i+1]*10^i;b=b*10+a[++i]}printf c" - %.4d = "z"\n",b}print"Iterations: "k"."}

$ awk -f k.awk <<< 9992
2999 - 9992 = 6993
3699 - 9963 = 6264
2466 - 6642 = 4176
1467 - 7641 = 6174
Iterations: 4
\$\endgroup\$
3
  • \$\begingroup\$ I receive awk: calling undefined function asort. Awk version is 20070501 running on OSX 10.6.7. Don't forget the . after the number of iterations. \$\endgroup\$
    – lunohodov
    Jun 25, 2011 at 11:40
  • \$\begingroup\$ lunohodov@: Added missing point. Also, I have used gnu awk (gawk), and that may explain the missing function. \$\endgroup\$ Jun 26, 2011 at 7:53
  • \$\begingroup\$ The subtraction numbers are the wrong way round: e.g. should be 9992 - 2999 = 6993 \$\endgroup\$ Jan 12, 2014 at 21:10
2
\$\begingroup\$

Ruby, 179 chars but posting anyway

s=gets.chomp
n=0
begin
  s=s.to_s.chars.sort.reduce{|s,c|s+c}.rjust(4,'0')
  a=s.reverse
  puts"#{a} - #{s} = #{'%04d'%(s=a.to_i-s.to_i)}"
  n+=1
end while s!=6174
puts"Iterations: #{n}."
\$\endgroup\$
0
2
\$\begingroup\$

K, 104

{b::();{b,:,k," = ",r:"0"^(-:4)$$. k:(x@>x)," - ",x@<x;r}\[$x];-1'c,,"Iterations: ",$#c:$[1=#b;b;-1_b];}

Test cases

k){b::();{b,:,k," = ",r:"0"^(-:4)$$. k:(x@>x)," - ",x@<x;r}\[$x];-1'c,,"Iterations: ",$#c:$[1=#b;b;-1_b];}'2607 1211 6174;
7620 - 0267 = 7353
7533 - 3357 = 4176
7641 - 1467 = 6174
Iterations: 3
2111 - 1112 = 0999
9990 - 0999 = 8991
9981 - 1899 = 8082
8820 - 0288 = 8532
8532 - 2358 = 6174
Iterations: 5
7641 - 1467 = 6174
Iterations: 1
\$\endgroup\$
1
\$\begingroup\$

PERL

chomp($n=<STDIN>);
    do{
       $t++;
       $desc=join('',reverse sort split(//,$n));
       $asc=join('', sort split(//,$n));
       $n=($desc - $asc);
       for($i=4;$i>length $n;$i--){
          $n="0".$n;
       }
       print $desc." - ".$asc." = ".$n."\n";
       $n="6174" if $n eq "0000";
    }while($n ne "6174");
    print "Iterations: $t.\n";
\$\endgroup\$
1
  • \$\begingroup\$ Thats ~310 chars... \$\endgroup\$ Jun 14, 2011 at 17:40
1
\$\begingroup\$

Mathematica, 314 291 characters

This is the program, kaprekar.m :-

SetOptions[$Output,FormatType->OutputForm];
x=$ScriptCommandLine[[2]];
f[x_]:=(a=Characters@x;
b=Sort@ToExpression@a;
c=Sort[FromDigits/@{#,Reverse@#}&@b];
{c,{b,a}}=IntegerString[{#2-#&@@c,c},10,4];
Print[a," - ",b," = ",c];c)
x=f@x;
e=NestWhileList[f,x,#!="6174"&];
Print["Iterations: ",N@Length@e]

Setting the path prior to running :-

$ PATH=${PATH}:/Applications/Mathematica.app/Contents/MacOS ; export PATH

Running the program :-

$ MathematicaScript -script kaprekar.m 2607
7620 - 0267 = 7353
7533 - 3357 = 4176
7641 - 1467 = 6174
Iterations: 3.
$ MathematicaScript -script kaprekar.m 1211
2111 - 1112 = 0999
9990 - 0999 = 8991
9981 - 1899 = 8082
8820 - 0288 = 8532
8532 - 2358 = 6174
Iterations: 5.
$ MathematicaScript -script kaprekar.m 6174
7641 - 1467 = 6174
Iterations: 1.
\$\endgroup\$
0
\$\begingroup\$

PHP, 160 bytes

function k($n,$d=1){$o=str_split($n);sort($o);echo$q=strrev($r=join($o))," - $r = ",$n=str_pad($q-$r,4,0,0),"
",$n==6174?"Iterations: $d.":k($n,++$d);}k($argn);

Try it online!

Complete program, input is STDIN, run with php -nF.

Output

> echo 2607|php -nF kap.php
7620 - 0267 = 7353
7533 - 3357 = 4176
7641 - 1467 = 6174
Iterations: 3.

> echo 1211|php -nF kap.php
2111 - 1112 = 0999
9990 - 0999 = 8991
9981 - 1899 = 8082
8820 - 0288 = 8532
8532 - 2358 = 6174
Iterations: 5.

> echo 6174|php -nF kap.php
7641 - 1467 = 6174
Iterations: 1.
\$\endgroup\$
0
\$\begingroup\$

Rust - 375 bytes

use std::io::{self,BufRead};fn main() {let mut x=io::stdin().lock().lines().next().unwrap().unwrap().parse::<i16>().unwrap();let mut n=0;println!("Iterations: {}.",loop {let mut v=[x/1000%10,x/100%10,x/10%10,x%10];v.sort();let j=v.iter().fold(0,|a,i|a*10+i);let k=v.iter().rev().fold(0,|a,i|a*10+i);x=k-j;n+=1;println!("{:04} - {:04} = {:04}",k,j,x);if x==6174{break n};});}

I present this as a possible "upper bound", I challenge anyone to find a language where a reasonable implementation of this is longer - as in there is nothing superfluous, but also nothing even remotely obvious that would shrink it significantly. The thing about Rust is that it takes about 120 characters just to read from stdin and parse into an integer. "Oh but then just use the string representation"... but im 99% confident that would be even longer

\$\endgroup\$
0
\$\begingroup\$

Perl 6 -n flag, 105 bytes

say "Iterations: "~+.&{{{say $!=.flip~" - $_"," = ",($/=$!.EVAL.fmt("%04d"));$/}([~] .comb.sort)}...6174}

Try it online!

I finally got to use my {}...* trick, since we need to have at least one iteration for 6174. I'm not sure why I need the extra wrapping .&{ } around the sequence though, which kinda sucks.

Explanation:

    .&{                         } # Call a function on the input
       {                }...6174  # Create a sequence that goes until 6174
        {           }([~] .comb.sort) # Get the sorted digits of the number
         say $!=.flip~" - $_"," = "~($/=$!.EVAL.fmt("%04d"))  # Print the iteration
                        ;$/  # Return the result
say "Iterations: "~+.&{      }     # Print the number of iterations
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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