24
\$\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\$

migrated from stackoverflow.com Jun 7 '11 at 3:10

This question came from our site for professional and enthusiast programmers.

  • \$\begingroup\$ This is news for me. Someone call a moderator... \$\endgroup\$ – lunohodov Jun 6 '11 at 21:44
  • \$\begingroup\$ Uh... isn't there a "migrate" button? \$\endgroup\$ – Dr. Rebmu Jun 6 '11 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\$ – dmckee Jun 7 '11 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 '11 at 8:47
  • 3
    \$\begingroup\$ Please add 6174 as an example so we can see how the output should be formatted. \$\endgroup\$ – Peter Taylor Jun 10 '11 at 6:26

22 Answers 22

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\$
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\$
  • \$\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 '11 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 '11 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 '11 at 9:12
  • \$\begingroup\$ @lunohodov: Fixed the warning and the example invocation. \$\endgroup\$ – Ventero Jun 17 '11 at 9:30
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\$
  • \$\begingroup\$ +1 for slick padding with %04d. I learned something today! \$\endgroup\$ – arrdem Jun 7 '11 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\$ – Keith Randall Jun 8 '11 at 3:31
  • \$\begingroup\$ @keith-randall: thanks, got it down to 141 now. \$\endgroup\$ – Martin Ueding Jun 8 '11 at 11:55
6
+25
\$\begingroup\$

Golfscript, 74 characters

);:|;{0):0;|$:§-1%" - "§" = ""0"4$~§~-+-4>:|n|6174`=!}do"Iterations: "0"."
\$\endgroup\$
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\$
  • \$\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 '11 at 4:04
  • \$\begingroup\$ Replacing show x++s with shows x s gains 2 more bytes. 186 now. \$\endgroup\$ – Rotsor Jun 20 '11 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 '11 at 5:18
4
\$\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\$
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\$
  • 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\$ – Martin Ueding Jun 10 '11 at 12:56
  • \$\begingroup\$ The credit should go to keith-randall who suggested it for my Python solution. \$\endgroup\$ – Martin Ueding Jun 10 '11 at 16:57
  • \$\begingroup\$ You can save 5 more characters by replacing while(n.length<4) with while(!n[3]). \$\endgroup\$ – DocMax Jun 16 '11 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 '11 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 '11 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\$
  • \$\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 '11 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 '11 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\$ – TwoScoopsofPig Oct 17 '12 at 19:02
  • \$\begingroup\$ Also, I hate mini-markdown. \$\endgroup\$ – TwoScoopsofPig Oct 17 '12 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\$
  • \$\begingroup\$ My browser freezes - had to cancel the execution of the script. \$\endgroup\$ – lunohodov Jun 16 '11 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\$ – Jonas Elfström Jun 16 '11 at 20:19
  • \$\begingroup\$ Using 0 (as suggested by the prompt) or clicking the cancel button causes Safari to freeze. \$\endgroup\$ – lunohodov Jun 17 '11 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\$ – Jonas Elfström Jun 17 '11 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 '11 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\$
  • \$\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 '11 at 11:40
  • \$\begingroup\$ lunohodov@: Added missing point. Also, I have used gnu awk (gawk), and that may explain the missing function. \$\endgroup\$ – Dan Andreatta Jun 26 '11 at 7:53
  • \$\begingroup\$ The subtraction numbers are the wrong way round: e.g. should be 9992 - 2999 = 6993 \$\endgroup\$ – Chris Degnen Jan 12 '14 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\$
  • \$\begingroup\$ ruby is pretty cool \$\endgroup\$ – don bright Mar 22 at 2:27
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\$
  • \$\begingroup\$ Thats ~310 chars... \$\endgroup\$ – Aman ZeeK Verma Jun 14 '11 at 17:40
1
\$\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\$

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.