I think you could use Kolgomorov complexity to define simple, for these purposes. That way replacing your formula with "5##" wouldn't make it any simpler, because the machine would still have to execute all those multiplicative operations.

How can we be sure we have the simplest explanation? We can't be sure, because new data could come in to make us change our minds. But given a finite amount like {1, 2, ...} we can still weight possible formulae by Kogomorov complexity and prefer the simpler hypothesis.

I think natural numbers is simpler in this case, because n is simpler to calculate than 2^n. As for {1, ...} I don't think we have enough information to locate a hypothesis.

I'm uncertain about what I've said, so please correct me if I'm wrong about anything.