https://quomodocumque.wordpress.com/2026/02/03/whats-the-entropy-of-a-random-integer/ Quomodocumque Math, Madison, food, the Orioles, books, my kids. * Home * About * Booklist 2011- * How Not To Be Wrong Feb 03 2026 2 Comments By JSE math, offhand What's the entropy of a random integer? Surely people have thought about this but I couldn't find anything on a short search. The question: let n be a random integer, say in [N,2N]. It factors as the product of p_i^a_i. So you can think of the proportion of n that is "made of" the prime p_i to be (a_i log p_i / log n). OK, now this gives you a probability distribution. What's its entropy? You can make this a little simpler by restricting to squarefree integers. (Not sure whether this should change the answer.) The sizes of the prime factors of a random squarefree integer are supposed to match the cycle lengths of a random large permutation (say on N letters), so now we can ask that question: break a random permutation up into cycles, which gives another probability distribution; namely, that which assigns each cycle the probability cycle length / N. (This is called the Poisson-Dirichlet process with parameters (0,1). Here's a Terry T. post about it, and why it governs prime factorizations of random integers.) What's the entropy of this one? Well, we can at least guess the average. Let X_i be the number of i-cycles in a random permutation on N letters. Then the X_i are roughly independent Poisson variables of mean 1/i. So there are X_i i-cycles, each appearing with probability i/n, and thus each contributing (-i/N) log (i/N) or (i/N)(log N - log i) to the entropy of the distribution. Now all we have to do is sum over i! You are summing (i/N) X_i log N - (i/N) X_i log i over all i. The first sum is easy; the sum of iX_i has to be N, so this is just log N. What about the subtrahend? This is \frac{1}{N} \sum (i \log i) X_i. Since X_i has expected value 1/i, the expected value of this part should be \frac{1}{N} \sum \log i. I didn't tell you how long the sum was! But i certainly can't be greater than N so let's stop the sum there. Then the sum of log_i, by Stirling's formula, is very close to N log N - N. So the second part of the sum is about log N - 1. Almost exact cancellation! Our estimate for the mean entropy is log N - (log N - 1) = 1. Is that true? Is it also true for integers? (I did actually run some computations on this and the mean looked less than one, but numbers with only five or six digits are just lousy with primes and near-primes, which could well mess this up.) Does the entropy actually converge to a distribution or does it just have a mean? What about the exponential of the entropy, the so-called perplexity? Does it have a mean? I ask because I tend to think of the perplexity of a probability distribution as roughly "the actual number of possible outcomes if you count them with information in mind." So you could think of the distribution of perplexity, if there is one, as the information theorist's version of the Erdos-Kac theorem. "You thought the number of prime factors grew like log log n, Pal and Mark, but come on, some of those primes are so small they barely matter -- actually the expected number of prime factors is constant!" I'm sure this is all well-understood by someone, but as I've mentioned before I think a blog is a good place to model the casual way mathematicians think about things in real life, but not always in public. Share this: * Email a link to a friend (Opens in new window) Email * Share on Facebook (Opens in new window) Facebook * Share on Reddit (Opens in new window) Reddit * Share on X (Opens in new window) X * Like Loading... Related Tagged entropy, primes, probability, random permutations 2 thoughts on "What's the entropy of a random integer?" 1. Terence Tao says: February 4, 2026 at 2:30 am You might find this paper of Kontoyiannis to be of interest. I also have a more recent blog post exploring these themes here. 2. Jon Awbrey says: February 4, 2026 at 8:48 am on a couple of related notes https://oeis.org/wiki/Riffs_and_Rotes Leave a comment [ ] [ ] [ ] [ ] [ ] [ ] [ ] D[ ] - Previous post Next post - Recent Posts * Now pitching, Cadeler Wellvich * George Birkhoff, faces made of lines * What's the entropy of a random integer? * It's a good old-fashioned Wisconsin booger-freezer out there! * Dick Gross * If one is not to make a mess of life * The encylopedia of triangle centers * Bruhat intervals that are large hypercubes * I'm holding out for the trigonometry of happiness * Dyadiku Recent Comments * George J.R. on George Birkhoff, faces made of lines * Jon Awbrey on What's the entropy of a random integer? * Terence Tao on What's the entropy of a random integer? * Jason Starr on Dick Gross * Jon Awbrey on I'm holding out for the trigonometry of happiness * Jon Awbrey on I'm holding out for the trigonometry of happiness * Allen K. on It's a good old-fashioned Wisconsin booger-freezer out there! * AG on I'm holding out for the trigonometry of happiness * JSE on If one is not to make a mess of life * networkscience2018 on If one is not to make a mess of life Top Posts & Pages * What's the entropy of a random integer? * About * Booklist 2011- * How Not To Be Wrong * George Birkhoff, faces made of lines * Now pitching, Cadeler Wellvich * The moduli space of chords: Dmitri Tymoczko on "Geometry and Music", Friday 7 Mar, 2:30pm * Dick Gross * The capacity to be alone * Sphere packing, cap set, and the Turan problem are all the same thing Blogroll * @JSEllenberg at Twitter * Cathy O'Neil * Crooked Timber * Emmanuel Kowalski's Blog * Gelman blog * God Plays Dice * Gowers's weblog * Lacunae * Letters from a broad... * Light Reading * Malvasia Blanca * Persiflage * Tea, Lemon, Old Books * The Value of the Variable * What's New ab academia bad statistics baseball blog books cars children cj college comedy commerce computers economics education ethics family food friends harvard history how not to be wrong language lists madison magazines math movies music news nostalgia offhand orioles papers philosophy poetry politics psychology recipes shows slate teaching travel Uncategorized writing Search for: [ ] [Search] RSS Feed * RSS - Posts * RSS - Comments Blog at WordPress.com. * Comment * Reblog * Subscribe Subscribed + [wpcom-] Quomodocumque Join 1,032 other subscribers [ ] Sign me up + Already have a WordPress.com account? Log in now. * + [wpcom-] Quomodocumque + Subscribe Subscribed + Sign up + Log in + Copy shortlink + Report this content + View post in Reader + Manage subscriptions + Collapse this bar %d [b]