MacMahon–Andrews conjecture

The MacMahon sequence starts at a1=1a_1=1. At each subsequent step it appends the least positive integer absent from the consecutive sums of the existing sequence. In particular every positive integer eventually has a consecutive-sum representation. Andrews conjectured ak∼klogk/loglogka_k\sim k\log k/\log\log k. Erdős repeated the conjecture and asked whether the growth is superlinear and subpolynomial relative to linear growth. The problem archive credits Porubský with a pointwise lower bound for the counting function along a subsequence, namely limsupA(x)/π(x)≥1/log2\limsup A(x)/\pi(x)\ge1/\log 2. I found no resolution of Andrews's asymptotic. Andrews (1975) · Erdős (1977), p. 70 · Erdős Problems wiki, #359 · OEIS A002048 · Research issue

A lower bound for the reciprocal sum on every scale

Let AA be any increasing sequence of positive integers such that all sufficiently large integers are sums of consecutive terms of AA. Then

∑a∈A,a≤X1a≥loglogXlog2−O(1).\sum_{a\in A,\ a\le X}\frac1a \ \ge\ \frac{\log\log X}{\log 2}-O(1). \tag{1}

More locally, uniformly for X≥Y≥2X\ge Y\ge2,

∑a∈A,Y<a≤X1a≥loglogX−loglogYlog2−O(1logY).\sum_{a\in A,\ \sqrt Y<a\le X}\frac1a \ \ge\ \frac{\log\log X-\log\log Y}{\log 2} -O\left(\frac1{\log Y}\right). \tag{2}

The constants may depend on the finite number of exceptions to coverage. The proof uses only coverage and strictly increasing positive integer terms. Moser uses the related count of windows by length for the sequence of ordinary primes. The problem archive's summary of Porubský's paper records the pointwise limsup but gives no statement about (1) or (2). I could not obtain that paper's full text to check priority for these estimates. Moser (1963), p. 159 · Bibliographic record of Porubský's results

Proof

Write R(x)R(x) for the number of consecutive blocks of AA whose sum is at most xx, including blocks with one term. Coverage implies R(x)≥x−O(1)R(x)\ge x-O(1). A block of length hh starting at aa has sum at least both ahah and h2/2h^2/2. Define T(a,h)=max(ah,h2/2)T(a,h)=\max(ah,h^2/2) and

g(x)=1x(log(2x)+4),w(x)=−g′(x)(x≥1).g(x)=\frac{1}{x(\log(2x)+4)},\qquad w(x)=-g'(x)\quad(x\ge1).

The weight ww is positive. For a fixed starting term aa, integrating the upper bound given by T(a,h)T(a,h) against ww on [1,X][1,X] gives at most ∑h≥1g(T(a,h))\sum_{h\ge1}g(T(a,h)). To bound this, put L=log(2a)L=\log(2a) and split at h=2ah=2a. Then

a∑h≥1g(T(a,h))≤1L+4+log2L+4L+4+12L+4≤log2.a\sum_{h\ge1}g(T(a,h)) \le \frac1{L+4} +\log\frac{2L+4}{L+4} +\frac1{2L+4} \le \log 2.

For the first two terms, sum the decreasing function 1/(h(log(2ah)+4))1/(h(\log(2ah)+4)) for h≤2ah\le2a using the first term and its integral. For the last term, use log(h2)≥2L\log(h^2)\ge2L and ∑h>2ah−2≤1/(2a)\sum_{h>2a}h^{-2}\le 1/(2a). The final inequality follows from

log2−log2L+4L+4=−log(1−2L+4)≥2L+4.\log 2-\log\frac{2L+4}{L+4} =-\log\left(1-\frac2{L+4}\right) \ge\frac2{L+4}.

Only a≤Xa\le X matter on [1,X][1,X]. The lower bound from coverage and integration by parts gives

∫1XR(x)w(x)dx≥∫1Xg(x)dx−Xg(X)−O(1)=loglogX−O(1).\int_1^X R(x)w(x)\,dx \ge \int_1^X g(x)\,dx-Xg(X)-O(1) =\log\log X-O(1).

Combining the per-start upper bounds proves (1). For (2), integrate over [Y,X][Y,X]. The starting terms at most Y\sqrt Y are at most Y\sqrt Y in number and each permits at most 2x\sqrt{2x} lengths. Thus their aggregate contribution to the integral is at most

Y∫Y∞2xw(x)dx≪1logY.\sqrt Y\int_Y^\infty\sqrt{2x}\,w(x)\,dx \ll \frac1{\log Y}.

The lower bound from coverage is loglogX−loglogY−O(1/logY)\log\log X-\log\log Y-O(1/\log Y), with the boundary terms estimated by xg(x)≪1/logYxg(x)\ll1/\log Y at x≥Yx\ge Y. Apply the same per-start bound for the remaining terms to obtain (2).

The mean representation count under the conjectured asymptotic

Suppose more generally that ak∼cklogk/loglogka_k\sim c k\log k/\log\log k for some c>0c>0. Its counting function then satisfies A(t)∼c−1tloglogt/logtA(t)\sim c^{-1}t\log\log t/\log t. Put H=H(x)H=H(x) for the maximum length of a block of sum at most xx. The initial block has the smallest sum among blocks of each length, so HH is the largest index for which ∑k≤Hak≤x\sum_{k\le H} a_k\le x. Partial summation and asymptotic inversion give

H∼2xloglogxclogx.H\sim 2\sqrt{\frac{x\log\log x}{c\log x}}.

For a fixed length hh, at most A(x/h)A(x/h) blocks have sum at most xx, since each such block starts at a term at most x/hx/h. At least A(x/h)−h+1A(x/h)-h+1 do, since all blocks of length hh ending at a term at most x/hx/h qualify. Summing yields

R(x)=x∫x/HxA(t)t2dt+O(A(x)+H2)∼log2cxloglogx.R(x)=x\int_{x/H}^{x}\frac{A(t)}{t^2}\,dt + O\bigl(A(x)+H^2\bigr) \sim \frac{\log 2}{c}\,x\log\log x.

The integral comparison for the sum over lengths uses the monotonicity of A(x/h)A(x/h), with error at most A(x)A(x). In the integral, log(x/H)=(1/2+o(1))logx\log(x/H)=(1/2+o(1))\log x, so loglogt∼loglogx\log\log t\sim\log\log x uniformly in the range and ∫x/Hxdt/(tlogt)→log2\int_{x/H}^x dt/(t\log t)\to\log2. At Andrews's predicted c=1c=1, the mean number of representations is therefore asymptotic to (log2)loglogx(\log 2)\log\log x. Recovering the density of the integers with zero representations using blocks of length at least two requires more information about the multiplicities. The mean alone leaves that density undetermined.