Knuth's up-arrow notation and the Ackermann function are both designed to make very large numbers easy to notate, but unfortunately I don't know how difficult it would be to write a program to find an expression for any number in one or the other (I'm sure there are plenty of others on HN who can). Might still be worth looking into however.
In principle, not every number can be directly expressed as the result of a nontrivial Ackermann function or Knuth operator (just as not every number is a square or a cube) - although there is a section in the Knuth page you linked on how to represent any nonnegative integer as a series of Knuth-type operations.
I would imagine, though, that to represent an arbitrary integer between 0 and n still needs ceil(log_2(n+1)) bits - since you have to distinguish between n+1 choices, whichever notation you use.
I would imagine, though, that to represent an arbitrary integer between 0 and n still needs ceil(log_2(n+1)) bits - since you have to distinguish between n+1 choices, whichever notation you use.