First of all, this pursuit reminds me of a quote from the Gnostic Gospels: Anyone who attempts to generate random numbers by deterministic means is, of course, living in a state of sin. --John von Neumann. As already pointed out, the notion of restricting oneself to a "simple" language is arbitrary and can't be made non-arbitrary non-arbitrarily. Patterns of certain sorts can be interesting-- for instance, long arithmetic or quadratic series of primes, or Simon Plouffe's f(n) = round(exp(f(n-1)) serieses. A program to produce all the primes, and only the primes, is easy to write in finite space, as long as one's language is Turing complete. That's the ultimate compression ratio, one for the Guinness Book of Records that will never be surpassed. But there's another way that seems to me not-as- ill-defined and not as pointless. Take a finite, plausible but imperfect model of the probability that a given number is prime, and then see what happens when you entropy-encode (e.g. arithmetic- code) the actual primes with it. (One cute thing about arithmetic coding is that it's already part of the idea to interpret the encoded form of an infinite sequence as a single real number.) For instance, there's this formula for prime density: P(is_prime(n)) = 1 / log(n). What's interesting with this (I think) is to ask how unexpected the primes are (i.e. how much info each number's prime-or-not-ness represents in light of the assumption) which amounts to a function (already mentioned in this thread) from how many primes to cumulative bits to encode them. One could complicate one's model by adding "not divisible by two", "not divisible by three", ad infinitum. What's to stop us from doing that isn't complexity exactly, it's that *that would be boring*, at least without some sort of interesting result coming out of it. I think it's right to say that what compels this sort of quest is interestingness as a whole, not simplicity per se. What is the curve of information-- the curve of mismatch between the 1/log(n) model and reality-- per n as n gets higher? One could guess at it and have a model of the inaccuracy of the 1/log(n) model. (For sure the information per n gets *spikier* as n goes up.) Does the naive model generally do what a reasonable mathematician would expect? Is the natural guess way off? Is the curve just generally higher, generally *lower*?? does it have unexpected long deep wobbles? Sharp cliffs? What's the frequency spectrum of the error? Is it brownian noise? 1/f noise? What is the expected and measured fractal dimension of the distribution of spikes in a given neighborhood? Also, we know the 1/log(n) model is wrong in specific ways! With this sort of meta-error perspective, eliminating even numbers, numbers divisible by three, etc. is more interesting: what happens to the curve of model inaccuracy as you improve the model by making it reject numbers with low prime divisors? A quality-improvement curve. Does *that* curve go the way one would expect? Also, there are probably (!) more refined, general- seeming ideas about prime density that I don't know about. How much improvement over -log2(1/log(n)) bits should we expect each of them to give? The thing is, maybe there are ideas that are both more complicated and less accurate than the definition of "prime," but more interesting or seemingly likely to be fruitful. The real meta question here is what makes a math investigation interesting. I believe there's such a thing as interesting, and math has it. --Steve