**R - 148 chars**

(so far away from the rest of the competition but still)


 f=function(n){
 q=rep(n,n)
 r=c()
 for(i in 4:n){
 while(q[i]){
 r[i]=paste(q[i]%%i,r[i])
 q[i]=q[i]%/%i
 }
 }
 which.max(sapply(lapply(strsplit(r," "),`==`,4),sum))
 }

Basically transform the input from base 10 to all bases from 4 to n (using modulo `%%` and integer division `%/%`) and pick the index of the one with the most 4s.

 f(624)
 [1] 5
 f(444)
 [1] 10