J, 107 112 characters

'4 is magic.',~}:('.',~":@{.,' is ',":@{:)"1]2&{.\.
(]{&(#.100 4$,#:3 u:ucp'䌵䐵吶梇禈榛ꪛ멩鮪鮺墊馊꥘誙誩墊馊ꥺ겻곋榛ꪛ멩鮪鮺'))^:a:

(Newline for readability only)

Usage and output:

    '4 is magic.',~}:('.',~":@{.,' is ',":@{:)"1]2&{.\.(]{&(#.100 4$,#:3 u:ucp'䌵䐵吶梇禈榛ꪛ멩鮪鮺墊馊꥘誙誩墊馊ꥺ겻곋榛ꪛ멩鮪鮺'))^:a:12
12 is 6.
6 is 3.
3 is 5.
5 is 4.
4 is magic.

Python:

#!/usr/bin/env python


# Number of letters in each part, we don't count spaces
Decades = ( 0, 3, 6, 6, 6, 5, 5, 7, 6, 6, 0 )
Smalls  = ( 0, 3, 3, 5, 4, 4, 3, 5, 5, 4 )
Teens  =  ( 6, 6, 8, 8, 7, 7, 9, 8, 8 )


def Count(n):
if n > 10 and n < 20: return Teens[n-11]
return   Smalls[n % 10 ] + Decades [ n / 10 ]


N = input()


while N-4:
Cnt = Count(N)
print "%d is %d" % ( N, Cnt)
N = Cnt


print "4 is magic"

Python 2.x, 144 150 154 166 chars

This separates the number into tens and ones and sum them up. The undesirable property of the pseudo-ternary operator a and b or c that c is returned if b is 0 is being abused here.

n=input()
x=0x4d2d0f47815890bd2
while n-4:p=n<20and x/10**n%10or 44378/4**(n/10-2)%4+x/10**(n%10)%10+4;print n,"is %d."%p;n=p
print"4 is magic."

The previous naive version (150 chars). Just encode all lengths as an integer.

n=input()
while n-4:p=3+int('1yrof7i9b1lsi207bozyzg2m7sclycst0zsczde5oks6zt8pedmnup5omwfx56b29',36)/10**n%10;print n,"is %d."%p;n=p
print"4 is magic."

Java (with boilerplate), 308 290 286 282 280 characters

class A{public static void main(String[]a){int i=4,j=0;for(;;)System.out.printf("%d is %s.%n",i=i==4?new java.util.Scanner(System.in).nextInt():j,i!=4?j="43354435543668877988699;::9;;:699;::9;;:588:998::9588:998::9588:998::97::<;;:<<;699;::9;;:699;::9;;:".charAt(i)-48:"magic");}}

I'm sure Groovy would get rid of much of that.

Explanation and formatting (all comments, newlines and leading/trailing whitespace removed in count):

Reasonably straight forward, but

//boilerplate
class A{
public static void main(String[]a){
//i is current/left number, j right/next number.  i=4 signals to start
//by reading input
int i=4,j=0;
for(;;)
//print in the form "<left> is <right>."
System.out.printf(
"%d is %s.%n",
i=i==4?
//<left>: if i is 4 <left> will be a new starting number
new java.util.Scanner(System.in).nextInt():
//otherwise it's the next val
j,
i!=4?
//use string to map number to its length (:;< come after 9 in ASCII)
//48 is value of '0'.  store in j for next iteration
j="43354435543668877988699;::9;;:699;::9;;:588:998::9588:998::9588:998::97::<;;:<<;699;::9;;:699;::9;;:".charAt(i)-48:
//i==4 is special case for right; print "magic"
"magic");
}
}

Edit: No longer use hex, this is less keystrokes

Perl: 148 characters

(Perl: 233 181 212 206 200 199 198 185 179 149 148 characters)

• Moved exceptions hash into unit array. This resulted in my being able to cut a lot of characters :-)
• mobrule pointed out a nasty bug. Quick fix adds 31 characters, ouch!
• Refactored for zero special case, mild golfing done as well.
• Direct list access for single use rather than storing to array? Hell yes!
• SO MUCH REFACTORING for just ONE bloody character. This, truly, is the life of a golfer. :-(
• Oops, easy whitespace fix. 198 now.
• Refactored some redundant code.
• Last return keyword in r is unnecessary, shaved some more off.
• Massive refactoring per comments; unfortunately I could only get it to 149 because I had to fix a bug that was present in both my earlier code and the commenters' versions.
• Trying bareword "magic".

Let's get this ball rolling with a modest attempt in Perl.

@u=split'','4335443554366887798866555766';$_=<>;chop;print"$_ is ".($_=$_==4?0:$_<20?$u[$_]:($u[$_/10+18]+($_%10&&$u[$_%10]))or magic).".
"while$_

Tricks:

Too many!

C++ Stdio version, minified: 196 characters

#include <cstdio>
#define P;printf(
char*o="43354435543668877988";main(int p){scanf("%d",&p)P"%d",p);while(p!=4){p=p<20?o[p]-48:"0366555966"[p/10]-96+o[p%10]P" is %d.\n%d",p,p);}P" is magic.\n");}

C++ Iostreams version, minified: 195 characters

#include <iostream>
#define O;std::cout<<
char*o="43354435543668877988";main(int p){std::cin>>p;O p;while(p!=4){p=p<20?o[p]-48:"0366555966"[p/10]-96+o[p%10]O" is "<<p<<".\n"<<p;}O" is magic.\n";}

Original, un-minified: 344 characters

#include <cstdio>


int ones[] = { 4, 3, 3, 5, 4, 4, 3, 5, 5, 4, 3, 6, 6, 8, 8, 7, 7, 9, 8, 8 };
int tens[] = { 0, 3, 6, 6, 5, 5, 5, 9, 6, 6 };


int n(int n) {
return n<20 ? ones[n] : tens[n/10] + ones[n%10];
}


int main(int p) {
scanf("%d", &p);
while(p!=4) {
int q = n(p);
printf("%i is %i\n", p, q);
p = q;
}
printf("%i is magic\n", p);
}

Ruby, 164 characters

n=gets.to_i;s="03354435543668877987";if n==0;puts"0 is 4.";else;puts"#{n} is #{n=(n<20)?s[n]-48:"0066555766"[n/10]-48+s[n%10]-48}." until n==4;end;puts"4 is magic."

decoded:

n = gets.to_i
s = "03354435543668877987"
if n == 0
puts "0 is 4."
else
puts "#{n} is #{n = (n < 20) ? s[n] - 48 : "0066555766"[n / 10] - 48 + s[n % 10] - 48}." until n == 4
end


puts "4 is magic."

C, 158 characters

main(n,c){char*d="03354435543668877988";for(scanf("%d",&n);n-4;n=c)printf("%d is %d.\n",n,c=n?n<19?d[n]-48:d[n%10]-"_,**+++)**"[n/10]:4);puts("4 is magic.");}

(originally based on Vlad's Python code, borrowed a trick from Tom Sirgedas' C++ solution to squeeze out a few more characters)

expanded version:

main(n, c) {
char *d = "03354435543668877988";
for (scanf("%d",&n); n-4; n = c)
printf("%d is %d.\n", n, c = n ? n<19 ? d[n]-48 : d[n%10] - "_,**+++)**"[n/10]  : 4);
puts("4 is magic.");
}

PhP Code

function get_num_name($num){
switch($num){
case 1:return 'one';
case 2:return 'two';
case 3:return 'three';
case 4:return 'four';
case 5:return 'five';
case 6:return 'six';
case 7:return 'seven';
case 8:return 'eight';
case 9:return 'nine';
}
}


function num_to_words($number, $real_name, $decimal_digit, $decimal_name){
$res = '';
$real = 0;
$decimal = 0;


if($number == 0)
return 'Zero'.(($real_name == '')?'':' '.$real_name);
if($number >= 0){
$real = floor($number);
$decimal = number_format($number - $real, $decimal_digit, '.', ',');
}else{
$real = ceil($number) * (-1);
$number = abs($number);
$decimal = number_format($number - $real, $decimal_digit, '.', ',');
}
$decimal = substr($decimal, strpos($decimal, '.') +1);


$unit_name[1] = 'thousand';
$unit_name[2] = 'million';
$unit_name[3] = 'billion';
$unit_name[4] = 'trillion';


$packet = array();


$number = strrev($real);
$packet = str_split($number,3);


for($i=0;$i<count($packet);$i++){
$tmp = strrev($packet[$i]);
$unit = $unit_name[$i];
if((int)$tmp == 0)
continue;
$tmp_res = '';
if(strlen($tmp) >= 2){
$tmp_proc = substr($tmp,-2);
switch($tmp_proc){
case '10':
$tmp_res = 'ten';
break;
case '11':
$tmp_res = 'eleven';
break;
case '12':
$tmp_res = 'twelve';
break;
case '13':
$tmp_res = 'thirteen';
break;
case '15':
$tmp_res = 'fifteen';
break;
case '20':
$tmp_res = 'twenty';
break;
case '30':
$tmp_res = 'thirty';
break;
case '40':
$tmp_res = 'forty';
break;
case '50':
$tmp_res = 'fifty';
break;
case '70':
$tmp_res = 'seventy';
break;
case '80':
$tmp_res = 'eighty';
break;
default:
$tmp_begin = substr($tmp_proc,0,1);
$tmp_end = substr($tmp_proc,1,1);


if($tmp_begin == '1')
$tmp_res = get_num_name($tmp_end).'teen';
elseif($tmp_begin == '0')
$tmp_res = get_num_name($tmp_end);
elseif($tmp_end == '0')
$tmp_res = get_num_name($tmp_begin).'ty';
else{
if($tmp_begin == '2')
$tmp_res = 'twenty';
elseif($tmp_begin == '3')
$tmp_res = 'thirty';
elseif($tmp_begin == '4')
$tmp_res = 'forty';
elseif($tmp_begin == '5')
$tmp_res = 'fifty';
elseif($tmp_begin == '6')
$tmp_res = 'sixty';
elseif($tmp_begin == '7')
$tmp_res = 'seventy';
elseif($tmp_begin == '8')
$tmp_res = 'eighty';
elseif($tmp_begin == '9')
$tmp_res = 'ninety';


$tmp_res = $tmp_res.' '.get_num_name($tmp_end);
}
break;
}


if(strlen($tmp) == 3){
$tmp_begin = substr($tmp,0,1);


$space = '';
if(substr($tmp_res,0,1) != ' ' && $tmp_res != '')
$space = ' ';


if($tmp_begin != 0){
if($tmp_begin != '0'){
if($tmp_res != '')
$tmp_res = 'and'.$space.$tmp_res;
}
$tmp_res = get_num_name($tmp_begin).' hundred'.$space.$tmp_res;
}
}
}else
$tmp_res = get_num_name($tmp);
$space = '';
if(substr($res,0,1) != ' ' && $res != '')
$space = ' ';
$res = $tmp_res.' '.$unit.$space.$res;
}


$space = '';
if(substr($res,-1) != ' ' && $res != '')
$space = ' ';


if($res)
$res .= $space.$real_name.(($real > 1 && $real_name != '')?'s':'');


if($decimal > 0)
$res .= ' '.num_to_words($decimal, '', 0, '').' '.$decimal_name.(($decimal > 1 && $decimal_name != '')?'s':'');
return ucfirst($res);
}

//////////// testing ////////////////

 $str2num = 12;
while($str2num!=4){
$str = num_to_words($str2num, '', 0, '');
$str2num = strlen($str)-1;
echo $str . '=' . $str2num .'<br/>';
if ($str2num == 4)
echo 'four is magic';
}

////// Results /////////

Twelve =6
Six =3
Three =5
Five =4
four is magic

C++, 171 characters (#include omitted)

void main(){char x,y,*a="03354435543668877988";scanf("%d",&x);for(;x-4;x=y)y=x?x<19?a[x]-48:"_466555766"[x/10]+a[x%10]-96:4,printf("%d is %d.\n",x,y);puts("4 is magic.");}

C# 314 286 283 274 289 273 252 chars.

Squished:

252

Normal:

using C = System.Console;
class P
{
static void Main()
{
var x = "4335443554366877798866555766";
int m, o, v = int.Parse(C.ReadLine());
do {
C.Write("{0} is {1}.\n", o = v, v == 4 ? (object)"magic" : v = v < 20 ? x[v] - 48 : x[17 + v / 10] - 96 + ((m = v % 10) > 0 ? x[m] : 48));
} while (o != 4);
C.ReadLine();
}
}

Edit Dykam: Did quite some carefull insertions and changes:

• Changed the l.ToString() into a cast to object of the string "magic".
• Created a temporary variable o, so I could move the break outside the for loop, that is, resulting in a do-while.
• Inlined the o assignment, aswell the v assignment, continueing in inserting the calculation of l in the function arguments altogether, removing the need for l. Also inlined the assignment of m.
• Removed a space in int[] x, int[]x is legit too.
• Tried to transform the array into a string transformation, but the using System.Linq was too much to make this an improvement.

Edit 2 Dykam Changed the int array to a char array/string, added proper arithmics to correct this.

C#: 210 Characters.

Squished:

using C=System.Console;class B{static void Main(){int
x=0,y=int.Parse(C.ReadLine());while(x!=4)C.Write((x=y)+" is {0}.\n",x==4?"magic":""+(y=x==0?4:"03354435543668877988"[x<20?x:x%10]+"0066555766"[x/10]-96));}}

Expanded:

using C=System.Console;
class B
{
static void Main()
{
int x=0,y=int.Parse(C.ReadLine());
while(x!=4)
C.Write((x=y)+" is {0}.\n",
x==4?
"magic":
""+(y= x==0?
4:
"03354435543668877988"[x<20?x:x%10]+
"0066555766"[x/10]-96)
);
}
}

Tricks this approach uses:

• Create a lookup table for number name lengths based on digits that appear in the number.
• Use character array lookup on a string, and char arithmetic instead of a numeric array.
• Use class name aliasing to short Console. to C.
• Use the conditional (ternary) operator (?:) instead of if/else.
• Use the \n with Write escape code instead of WriteLine
• Use the fact that C# has a defined order of evaluation to allow assignments inside the Write function call
• Use the assignment expressions to eliminate extra statements, and thus extra braces

Common Lisp 157 Chars

New more conforming version, now reading form standard input and ignoring spaces and hyphens:

(labels((g (x)(if(= x 4)(princ"4 is magic.")(let((n(length(remove-if(lambda(x)(find x" -"))(format nil"~r"x)))))(format t"~a is ~a.~%"x n)(g n)))))(g(read)))

In human-readable form:

 (labels ((g (x)
(if (= x 4)
(princ "4 is magic.")
(let ((n (length (remove-if (lambda(x) (find x " -"))
(format nil "~r" x)))))
(format t"~a is ~a.~%" x n)
(g n)))))
(g (read)))

And some test runs:

>24
24 is 10.
10 is 3.
3 is 5.
5 is 4.
4 is magic.


>23152436
23152436 is 64.
64 is 9.
9 is 4.
4 is magic.

And the bonus version, at 165 chars:

 (labels((g(x)(if(= x 4)(princ"four is magic.")(let*((f(format nil"~r"x))(n(length(remove-if(lambda(x)(find x" -"))f))))(format t"~a is ~r.~%"f n)(g n)))))(g(read)))

Giving

>24
twenty-four is ten.
ten is three.
three is five.
five is four.
four is magic.


>234235
two hundred thirty-four thousand two hundred thirty-five is forty-eight.
forty-eight is ten.
ten is three.
three is five.
five is four.
four is magic.

Windows PowerShell: 152 153 184 bytes

based on the previous solution, with more influence from other solutions

$o="03354435543668877988"
for($input|sv b;($a=$b)-4){if(!($b=$o[$a])){$b=$o[$a%10]-48+"66555766"[($a-$a%10)/10-2]}$b-=48-4*!$a
"$a is $b."}'4 is magic.'

Lua 185 190 199

added periods, added io.read, removed ()'s on last print

 n=io.read();while(n~=4)do m=('43354435543668877988699;::9;;:699;::9;;:588:998::9588:998::9588:998::97::<;;:<<;699;::9;;:699;::9;;:'):sub(n+1):byte()-48;print(n,' is ',m,'.')n=m;end print'4 is magic.'

with line breaks

 n=io.read()
while (n~=4) do
m=('43354435543668877988699;::9;;:699;::9;;:588:998::9588:998::9588:998::97::<;;:<<;699;::9;;:699;::9;;:'):sub(n+1):byte()-48;
print(n,' is ',m,'.')
n=m;
end
print'4 is magic.'

Haskell, 224 270 characters

o="43354435543668877988"
x!i=read[x!!i]
n x|x<20=o!x|0<1="0066555766"!div x 10+o!mod x 10
f x=zipWith(\a b->a++" is "++b++".")l(tail l)where l=map show(takeWhile(/=4)$iterate n x)++["4","magic"]
main=readLn>>=mapM putStrLn.f

And little more readable -

ones = [4,3,3,5,4,4,3,5,5,4,3,6,6,8,8,7,7,9,8,8]
tens = [0,0,6,6,5,5,5,7,6,6]


n x = if x < 20 then ones !! x else (tens !! div x 10) + (ones !! mod x 10)


f x = zipWith (\a b -> a ++ " is " ++ b ++ ".") l (tail l)
where l = map show (takeWhile (/=4) (iterate n x)) ++ ["4", "magic"]
    

main = readLn >>= mapM putStrLn . f

C - with number words

445 431 427 421 399 386 371 359^* 356 354^† 348 347 characters

That's it. I don't think I can make this any shorter.

All newlines are for readability and can be removed:

i;P(x){char*p=",one,two,three,four,five,six,sM,eight,nine,tL,elM,twelve,NP,4P,
fifP,6P,7P,8O,9P,twLQ,NQ,forQ,fifQ,6Q,7Q,8y,9Q,en,evL,thir,eL,tO,ty, is ,.\n,
4RmagicS,zero,";while(x--)if(*++p-44&&!x++)*p>95|*p<48?putchar(*p),++i:P(*p-48);
}main(c){for(scanf("%d",&c);c+(i=-4);P(34),P(c=i),P(35))P(c?c>19?P(c/10+18),
(c%=10)&&putchar(45):0,c:37);P(36);}

Below, it is somewhat unminified, but still pretty hard to read. See below for a more readable version.

i;
P(x){
char*p=",one,two,three,four,five,six,sM,eight,nine,tL,elM,twelve,NP,4P,fifP,6P,7P,8O,9P,twLQ,NQ,forQ,fifQ,6Q,7Q,8y,9Q,en,evL,thir,eL,tO,ty, is ,.\n,4RmagicS,zero,";
while(x--)
if(*++p-44&&!x++)
*p>95|*p<48?putchar(*p),++i:P(*p-48);
}
main(c){
for(scanf("%d",&c);c+(i=-4);P(34),P(c=i),P(35))
P(c?
c>19?
P(c/10+18),
(c%=10)&&
putchar(45)
:0,
c
:37);
P(36);
}

Expanded and commented:

int count; /* type int is assumed in the minified version */


void print(int index){ /* the minified version assumes a return type of int, but it's ignored */
/* see explanation of this string after code */
char *word =
/* 1 - 9 */
",one,two,three,four,five,six,sM,eight,nine,"
/* 10 - 19 */
"tL,elM,twelve,NP,4P,fifP,6P,7P,8O,9P,"
/* 20 - 90, by tens */
"twLQ,NQ,forQ,fifQ,6Q,7Q,8y,9Q,"
/* lookup table */
"en,evL,thir,eL,tO,ty, is ,.\n,4RmagicS,zero,";


while(index >= 0){
if(*word == ',')
index--;
else if(index == 0) /* we found the right word */
if(*word >= '0' && *word < 'a') /* a compression marker */
print(*word - '0'/*convert to a number*/);
else{
putchar(*word); /* write the letter to the output */
++count;
}
++word;
}
}
int main(int argc, char **argv){ /* see note about this after code */
scanf("%d", &argc); /* parse user input to an integer */


while(argc != 4){
count = 0;
if(argc == 0)
print(37/*index of "zero"*/);
else{
if(argc > 19){
print(argc / 10/*high digit*/ + 20/*offset of "twenty"*/ - 2/*20 / 10*/);
argc %= 10; /* get low digit */


if(argc != 0) /* we need a hyphen before the low digit */
putchar('-');
}
print(argc/* if 0, then nothing is printed or counted */);
}
argc = count;
print(34/*" is "*/);
print(argc); /* print count as word */
print(35/*".\n"*/);
}
print(36/*"four is magic.\n"*/);
}

About the encoded string near the beginning

The names of the numbers are compressed using a very simple scheme. Frequently used substrings are replaced with one-character indices into the name array. A "lookup table" of extra name entries is added to the end for substrings not used in their entirety in the first set. Lookups are recursive: entries can refer to other entries.

For instance, the compressed name for 11 is elM. The print() function outputs the characters e and l (lower-case 'L', not number '1') verbatim, but then it finds the M, so it calls itself with the index of the 29th entry (ASCII 'M' - ASCII '0') into the lookup table. This string is evL, so it outputs e and v, then calls itself again with the index of the 28th entry in the lookup table, which is en, and is output verbatim. This is useful because en is also used in print()0 for print()1 (used after print()2 in print()3), which is used in print()4 for print()5 (used for every other print()6 name).

This scheme results in a fairly significant compression of the number names, while requiring only a small amount of code to decompress.

The commas at the beginning and end of the string account for the simplistic way that substrings are found within this string. Adding two characters here saves more characters later.

About the abuse of main()

argv is ignored (and therefore not declared in the compressed version), argc's value is ignored, but the storage is reused to hold the current number. This just saves me from having to declare an extra variable.

About the lack of #include

Some will complain that omitting #include <stdio.h> is cheating. It is not at all. The given is a completely legal C program that will compile correctly on any C compiler I know of (albeit with warnings). Lacking protoypes for the stdio functions, the compiler will assume that they are cdecl functions returning int, and will trust that you know what arguments to pass. The return values are ignored in this program, anyway, and they are all cdecl ("C" calling convention) functions, and we do indeed know what arguments to pass.

Output

Output is as expected:

0
zero is four.
four is magic.

1
one is three.
three is five.
five is four.
four is magic.

4
four is magic.

20
twenty is six.
six is three.
three is five.
five is four.
four is magic.

21
twenty-one is nine.
nine is four.
four is magic.

_{^* The previous version missed the mark on two parts of the spec: it didn't handle zero, and it took input on the command line instead of stdin. Handling zeros added characters, but using stdin instead of command line args, as well as a couple of other optimzations saved the same number of characters, resulting in a wash.}

_{^† The requirements have been changed to make clear that the number word should be printed on both sides of " is ". This new version meets that requirement, and implements a couple more optimizations to (more than) account for the extra size necessary.}

GolfScript - 101 96 93 92 91 90 94 86 bytes

90 → 94: Fixed output for multiples of 10.
94 → 86: Restructured code. Using base 100 to remove non-printable characters.
86 → 85: Shorter cast to string.

{n+~."+#,#6$DWOXB79Bd")base`1/10/~{~2${~1$+}%(;+~}%++=" is "\".
"1$4$4-}do;;;"magic."

Delphi: 329 characters

Single Line Version:

program P;{$APPTYPE CONSOLE}uses SysUtils;const S=65;A='EDDFEEDFFEDGGIIHHJII';B='DGGFFFJGG';function Z(X:Byte):Byte;begin if X<20 then Z:=Ord(A[X+1])-S else Z:=(Ord(B[X DIV 10])-S)+Z(X MOD 10)end;var X,Y:Byte;begin Write('> ');ReadLn(X);repeat Y:=Z(X);WriteLn(Format('%d is %d.',[X,Y]));X:=Y;until X=4;WriteLn('4 is magic.');end.

Formated:

program P;


{$APPTYPE CONSOLE}


uses
SysUtils;


const
S = 65;
A = 'EDDFEEDFFEDGGIIHHJII';
B = 'DGGFFFJGG';


function Z(X:Byte):Byte;
begin
if X<20
then Z := Ord(A[X+1])-S
else Z := (Ord(B[X DIV 10])-S) + Z(X MOD 10);
end;


var
X,Y: Byte;


begin
Write('> ');
ReadLn(X);


repeat
Y:=Z(X);
WriteLn(Format('%d is %d.' , [X,Y]));
X:=Y;
until X=4;


WriteLn('4 is magic.');
end.

Probably room for some more squeezing... :-P

JavaScript 1.8 (SpiderMonkey) - 153 Chars

l='4335443554366887798866555766'.split('')
for(b=readline();(a=+b)-4;print(a,'is '+b+'.'))b=a<20?l[a]:+l[18+a/10|0]+(a%10&&+l[a%10])
print('4 is magic.')

Usage: echo 42 | js golf.js

Output:

42 is 8.
8 is 5.
5 is 4.
4 is magic.

With bonus - 364 chars

l='zero one two three four five six seven eight nine ten eleven twelve thirteen fourteen fifteen sixteen seventeen eighteen nineteen twenty thirty fourty fifty sixty seventy eighty ninety'.split(' ')
z=function(a)a<20?l[a]:l[18+a/10|0]+(a%10?' '+l[a%10]:'')
for(b=+readline();(a=b)-4;print(z(a),'is '+z(b)+'.'))b=z(a).replace(' ','').length
print('four is magic.')

Output:

ninety nine is ten.
ten is three.
three is five.
five is four.
four is magic.

T-SQL, 413 451 499 chars

CREATE FUNCTION d(@N int) RETURNS int AS BEGIN
Declare @l char(50), @s char(50)
Select @l='0066555766',@s='03354435543668877987'
if @N<20 return 0+substring(@s,@N+1,1) return 0+substring(@l,(@N/10)+1,1) + 0+(substring(@s,@N%10+1,1))END
GO
CREATE proc M(@x int) as BEGIN
WITH r(p,n)AS(SELECT p=@x,n=dbo.d(@x) UNION ALL SELECT p=n,n=dbo.d(n) FROM r where n<>4)Select p,'is',n,'.' from r print '4 is magic.'END

(Not that I'm seriously suggesting you'd do this... really I just wanted to write a CTE)

To use:

M 95

Returns

p                n
----------- ---- -----------
95          is   10.
10          is   3.
3           is   5.
5           is   4.
4 is magic.

C - without number words

180 175^* 172 167 characters

All newlines are for readability and can be removed:

i;V(x){return"\3#,#6$:WOXB79B"[x/2]/(x%2?1:10)%10;}main(c){for(scanf("%d",&c);
c-4;)i=c,printf("%d is %d.\n",i,c=c?c>19?V(c/10+19)+V(c%10):V(c):4);puts(
"4 is magic.");}

Slightly unminified:

i;
V(x){return"\3#,#6$:WOXB79B"[x/2]/(x%2?1:10)%10;}
main(c){
for(scanf("%d",&c);c-4;)
i=c,
printf("%d is %d.\n",i,c=c?c>19?V(c/10+19)+V(c%10):V(c):4);
puts("4 is magic.");
}

_{^* The previous version missed the mark on two parts of the spec: it didn't handle zero, and it took input on the command line instead of stdin. Handling zero added characters, but using stdin instead of command line args saved even more, resulting in a net savings.}

Perl, about 147 char

Loosely based on Platinum Azure's solution:

               chop
($_.=
<>);@
u="433
5443554
366  887
798   866
555    766
"=~     /\d
/gx      ;#4
sub       r{4
-$_        ?$_
<20         ?$u
[$_          ]:(
$'?           $u[
$']            :0)
+$u[18+$&]:magic}print"
$_ is ",$_=r(),'.'while
/\d
/x;
444

Perl - 130 chars

5.12.1   (130 chars) ^{121 123 132 136 140}

#        1         2         3         4         5         6         7         8         9        100        11        12        13       14
#23456789 123456789 123456789 123456789 123456789 123456789 123456789 123456789 123456789 123456789 123456789 123456789 123456789 123456789 123


@u='4335443554366887798866555766'=~/./g;$_=pop;say"$_ is ",$_=$_-4?$_<20?$u[$_]:$u[$_/10+18]+(($_%=10)&&$u[$_]):magic,"."until/\D/

5.10.1   (134 chars) ^{125 127 136 140 144}

#        1         2         3         4         5         6         7         8         9        100        11        12        13       14
#23456789 123456789 123456789 123456789 123456789 123456789 123456789 123456789 123456789 123456789 123456789 123456789 123456789 123456789 1234


@u='4335443554366887798866555766'=~/./g;$_=pop;print"$_ is ",$_=$_-4?$_<20?$u[$_]:$u[$_/10+18]+(($_%=10)&&$u[$_]):magic,".\n"until/\D/

Change History:

20100714:2223 - reverted change at the attention of mobrule, but ($_%10&&$u[$_%10]) → (($_%=10)&&$u[$_]), which is the same # of chars, but I did it in case someone might see a way to improve it

20100714:0041 - split//,'...' → '...'=~/./g
20100714:0025 - ($_%10&&$u[$_%10]) → $u[$_%10]
20100713:2340 - while$_ → until/\D/ + removed unnecessary parentheses
20100713:xxxx - $=<>;chop; → $_=pop; - courtesy to mobrule

Note: I was tired of improving others' answers in comments, so now I'm being greedy and can just add my changes here :) This is a split off from Platinum Azure's answer - credit in part to Hobbs, mobrule, and Platinum Azure.

Python, 129 133 137 148 chars

As a warm-up, here is my first version (improves couple of chars over previous best Python).

PS. After a few redactions now it is about twenty char's shorter:

n=input()
while n-4:p=(922148248>>n/10*3&7)+(632179416>>n%10*3&7)+(737280>>n&1)+4*(n<1);print n,'is %d.'%p;n=p
print'4 is magic.'

while(true)
{
string a;
ReadLine(a)
WriteLine(4);


}

Shameless Perl with Number Words (329 characters)

Adapted fairly directly from P Daddy's C code, with some tweaks to p() to make it do the same thing using Perl primitives instead of C ones, and a mostly-rewritten mainloop. See his for an explanation. Newlines are all optional.

@t=(qw(zero one two three four five six sM eight nine
tL elM twelve NP 4P fifP 6P 7P 8O 9P twLQ NQ forQ fifQ
6Q 7Q 8y 9Q en evL thir eL tO ty 4SmagicT)," is ",".\n");
sub p{local$_=$t[pop];1while s/[0-Z]/$t[-48+ord$&]/e;
print;length}$_=<>;chop;while($_-4){
$_=($_>19?(p($_/10+18),$_&&print("-"),$_%=10)[0]:0)+p$_;
p 35;p$_;p 36}p 34

Side note: it's too bad that perl print just returns true/false; if it returned a count it would save me 7 strokes.

Lua, 176 Characters

o={[0]=4,3,3,5,4,4,3,5,5,4,3,6,6,8,8,7,7,9,8,8}t={3,6,6,5,5,5,7,6,6}n=0+io.read()while n~=4 do a=o[n]or o[n%10]+t[(n-n%10)/10]print(n.." is "..a..".")n=a end print"4 is magic."

or

  o={[0]=4,3,3,5,4,4
,3,5,5,4,3,6,6,8,8
,7,7,9,8,8}t={3,6,
6,5,5,5,7,6,6}n=
0+io.read()while
n ~= 4 do a= o[n
]or o[n%10]+t[(n
-n%10)/10]print(
n.." is "..a.."." )n=a
end print"4 is magic."

perl, 123 122 characters

Just realized that there is no requirement to output to STDOUT, so output to STDERR instead and knock off another character.

@u='0335443554366887798866555766'=~/./g;$_+=<>;warn"$_ is ",$_=$_-4?$_<20?$u[$_]||4:$u[chop]+$u[$_+18]:magic,".\n"until/g/

And, a version that returns spelled out numbers:

279 278 276 280 characters

@p=(Thir,Four,Fif,Six,Seven,Eigh,Nine);@n=("",One,Two,Three,Four,Five,@p[3..6],Ten,Eleven,Twelve,map$_.teen,@p);s/u//for@m=map$_.ty,Twen,@p;$n[8].=t;sub n{$n=shift;$n?$n<20?$n[$n]:"$m[$n/10-2] $n[$n%10]":Zero}$p+=<>;warnt$m=n($p)," is ",$_=$p-4?n$p=()=$m=~/\w/g:magic,".\n"until/c/

While that meets the spec, it is not 100% well formatted. It returns an extra space after numbers ending in zero. The spec does say:

"I don't care how you separate the word tokens, though they should be separated"

That's kind of weaselly though. A more correct version at

282 281 279 283 characters

@p=(Thir,Four,Fif,Six,Seven,Eigh,Nine);@n=("\x8",One,Two,Three,Four,Five,@p[3..6],Ten,Eleven,Twelve,map$_.teen,@p);s/u//for@m=map$_.ty,Twen,@p;$n[8].=t;sub n{$n=shift;$n?$n<20?$n[$n]:"$m[$n/10-2]-$n[$n%10]":Zero}$p+=<>;warn$m=n($p)," is ",$_=$p-4?n$p=()=$m=~/\w/g:magic,".\n"until/c/

Ruby, 141 chars:

n=gets.to_i;m="4335443554366887798866555766";loop{s=n;n=n>20?m[18+n/10]+m[n%10]-96: m[n]-48;puts"#{s} is #{n==s ? 'magic': n}.";n==s &&break}