On 30/03/2013 04:54, Dan Asimov wrote:
It's curious that there are no 3-term representations, at least up to Gareth's 11 million. Is there some simple reason for this?
(The first 3-termer actually comes at 18567920; my program found it while I was asleep, and Charles Greathouse's email reports the same number without explicitly saying it's where you first need three terms.) I think it depends on what you mean by a simple reason. Numbers of the form k.p^r with 1 <= k < p are quite common, so the gaps between them are quite short, so for smallish N two terms generally suffice. You need three terms once the gap reaches a length that takes two terms, which is to say 12. How common *are* numbers of the form k.p^r with 1 <= k < p? Asymptotically, presumably only r=1 matters. For fixed k, the count is then pi(n/k) - pi(k). So: sum {k<sqrt(n)} pi(n/k) - pi(k) which, simple-mindedly, is approximately sum {k<sqrt(n)} (n/k)/log(n/k) - k/log(k) = {splitting out the two terms} sum {k<sqrt(n)} (n/k)/log(n/k) - sum {k<sqrt(n)} k/log(k) ~= {asymptotics for second term} (sum {k<sqrt(n)} (n/k)/log(n/k)) - n / log n = {rearrange first term a little} ((n / log n) sum {k<sqrt(n)} (1/k)/(1 - log(k)/log(n))) - n / log n ~= {that denominator is always between 1/2 and 1} (A (n / log n) sum {k<sqrt(n)} (1/k)) - n / log n ~= {asymptotics} ((n / log n) A/2 log n) - n / log n ~= {triv} A/2 n where I've probably done all sorts of illegitimate things, but the point is that it seems like at least a constant proportion of numbers have that form, which suggests that large gaps should be rare. Exactly how rare is probably a hard problem. -- g