# A sequence that avoids both arithmetic and geometric progressions

Sequences that avoid arithmetic progressions have been studied, e.g., "Sequences Containing No 3-Term Arithmetic Progressions," Janusz Dybizbański, 2012, journal link.

I started to explore sequences that avoid both arithmetic and geometric progressions, i.e., avoid $$x, x+c, x+2c$$ and avoid $$y, c y, c^2 y$$ anywhere in the sequence (not necessarily consecutively). Starting with $$(1,2)$$, one cannot extend with $$3$$ because $$(1,2,3)$$ forms an arithemtical progression, and one cannot extend with $$4$$ because $$(1,2,4)$$ is a geometric progression. But $$(1,2,5)$$ is fine.

Continuing in the same manner leads to the following "greedy" sequence: $$1, 2, 5, 6, 12, 13, 15, 16, 32, 33, 35, 39, 40, 42, 56, 81, 84, 85, 88,$$ $$90, 93, 94, 108, 109, 113, 115, 116, 159, 189, 207, 208, 222, \ldots$$

This sequence is not in the OEIS. Here are a few questions:

Q1. What is its growth rate?

Q2. Does $$\sum_{i=1}^\infty 1/s_i$$ converge? (Where $$s_i$$ is the $$i$$-th term of the above sequence.)

Q3. If it does, does it converge to e? Update: No. The sum appears to be approximately $$2.73 > e$$, as per @MichaelStocker and @Turambar.

That is wild numerical speculation. The first 457 terms (the extent of the graph above) sum to 2.70261.

Addendum. 11Jul2014. Starting with $$(0,1)$$ rather than $$(1,2)$$ renders a direct hit on OEIS A225571.

• Expanding on your numerical data I conclude that Q3 can be answered in the negative. 457th term is 17933 with sum of reciprocals : 2.702607644337383 1000th term is 66102 : 2.718058753659135 but alas, somewhere shortly after that the sum excedes e. 2000 253701 2.7259164358931023. 3000 442429 2.7287027640882804. – Michael Stocker Jul 7 '14 at 13:16
• The answer to Q2 is definitely Yes, it converges, because even just avoiding arithmetic progressions leads to convergence. Converges to what constant is unclear. – Joseph O'Rourke Jul 9 '14 at 0:33
• @JosephO'Rourke Really? I may be ignorant here so going out on a limb, but I don't think $a_n=n\ln n$ is in an arithmetic progression, but the sum of its reciprocals diverges. – John Molokach Mar 25 '16 at 2:46
• @JohnMolokach In fact, when you look at the difference in terms in the OEIS sequence, it looks a lot like OEIS A006519, which is $O(n\ln(n))$. The sequence talked about in the question is a bit different, but I think asymptotically they'd be the same, meaning the sum of reciprocals diverges. And of course, this is just a heuristic, not a proof. – Turambar Apr 28 '16 at 17:52
• On the other hand, after looking at it out to $i = 10,000$, the chart of the differences doesn't seem to be as similar to A006519 as I thought. Its peaks grow faster and have a more bell curve distribution around them instead of the recursive characteristics of A006519. At $i = 10,000$, $\ln(s_i)/\ln(i) = 1.679258559$ and generally growing, with the sum of reciprocals around $2.734896156$. So if the "power" keeps generally growing (and doesn't start dropping to 1 after some point), then the sum is below $2.736095249$. – Turambar May 10 '16 at 16:14

$$\color{brown}{\textbf{HINT}}$$

Denote the target sequence $$\{F_3(n)\}$$ and let us try to estimate the probability $$P(N)\}$$ that natural number belongs to $$\{F_3\}.$$

Suppose $$F_3(1)=1,\quad F_3(2)=2,\quad P(1)=P(2)=P(5) = P(6) = 1,\\ P(3)=P(4)=P(7)=P(8)=0,\tag1$$ $$V(N)=\sum\limits_{i=1}^{N}P(i),\quad F_3(N) = \left[V^{-1}(N)\right].\tag2$$

Let $$P_a(N)$$ is the probability that N does not belong to arithmetic progression and $$P_g(N)$$ is the similar probability for geometric progressions.

Suppose $$P(N) = P_a(N)P_g(N)).\tag3$$

$$\color{brown}{\textbf{Arithmetic Probability estimation.}}$$

Suppose $$P_a(N)=\prod\limits_{k=1}^{[N/2]}P_a(N,k),\tag4$$ where $$P_a(N,k)$$ is the probability that arithmetic progression $$\{N-2k,N-k, N\}$$ does not exist for any $$j.$$ Suppose $$P_a(N,k) = \big(1-P(N-2k)\big)\big((1-P(N-k)\big).\tag5$$

$$\color{brown}{\textbf{Geometric Probability estimation.}}$$

Suppose $$P_g(N)=\prod\limits_{k=1}^{\left[\,\sqrt Nn\,\right]}P_g(N,k),\tag6$$ where $$P_g(N,k)$$ is the probability that geometric progression $$\left(\dfrac{N}{k^2}, \dfrac Nk, N\right\}$$ with the denominator $$k$$ does not exist for all $$i,j.$$

Taking in account that the geometric progression can exist only if $$k^2\,| \ N,$$ suppose $$P_g(N,k) = \left(1-\dfrac1{k^2}P\left(\dfrac{N}{k^2}\right)\right)\left(1-P\left(\dfrac{N}{k}\right)\right).\tag7$$

$$\color{brown}{\textbf{Common model.}}$$

Common model can be simplified to next one, $$\begin{cases} P(N) = 1-\prod\limits_{k=1}^{[N/2-1]}\Big(1-\big(1-P(N-2k)\big)\big(1-P(N-k)\big)\Big)\\ \times\prod\limits_{k=1}^{\left[\sqrt N\right]}\left(1-\left(1-\dfrac1{k^2}P\left(\dfrac{N}{k^2}\right)\right)\left(1-P\left(\dfrac{N}{k}\right)\right)\right)\\[4pt] P(1)=P(2)=P(5) = P(6) = 1,\quad P(3)=P(4)=P(7)=P(8)=0\\ V(N)=\sum\limits_{i=1}^{N}P(i),\quad F_3(n) = \left[V^{-1}(n)\right].\tag8 \end{cases}$$

Looking the solution in the form of \left\{\begin{align} &P(N)=P_v(N),\quad\text{where}\quad v=\left[\dfrac{N-1 \mod 4}2\right],\\[4pt] &P_0(N)= \begin{cases} 1,\quad\text{if}\quad N<9\\ cN^{-s},\quad\text{otherwise} \end{cases}\\[4pt] &P_1(N)= \begin{cases} 0,\quad\text{if}\quad N<9\\ dN^{-t},\quad\text{otherwise} \end{cases} \end{align}\right.\tag9

then $$\begin{cases} &P_0(N) =1-&\prod\limits_{k=1}^{[N/4-1]}\Big(1-\big(1-P_0(N-4k)\big)\big(1-P_1(N-2k)\big)\Big)\\ &&\times\Big(1-\big(1-P_1(N-4k-2)\big)\big(1-P_0(N-2k-1)\big)\Big)\\ &&\times\prod\limits_{k=1}^{\left[\sqrt N/2\right]-1} \left(1-\left(1-\dfrac1{(2k-1)^2}P_0\left(\dfrac{N}{(2k-1)^2}\right)\right) \left(1-P_1\left(\dfrac{N}{2k-1}\right)\right)\right)\\[4pt] &&\times\left(1-\left(1-\dfrac1{4k^2}P_1\left(\dfrac{N}{4k^2}\right)\right) \left(1-P_0\left(\dfrac{N}{2k}\right)\right)\right)\\[4pt] &P_1(N) = 1- &\prod\limits_{k=1}^{[N/4-1]}\Big(1-\big(1-P_1(N-4k)\big)\big(1-P_0(N-2k)\big)\Big)\\ &&\Big(1-\big(1-P_0(N-4k-2)\big)\big(1-P_1(N-2k-1)\big)\Big)\\ &&\times\prod\limits_{k=1}^{\left[\sqrt N/2\right]-1} \left(1-\left(1-\dfrac1{(2k-1)^2}P_1\left(\dfrac{N}{(2k-1)^2}\right)\right) \left(1-P_0\left(\dfrac{N}{2k-1}\right)\right)\right)\\[4pt] &&\times\left(1-\left(1-\dfrac1{4k^2}P_0\left(\dfrac{N}{4k^2}\right)\right) \left(1-P_1\left(\dfrac{N}{2k}\right)\right)\right). \end{cases}\tag{10}$$

Taking in account $$(9),$$ can be written $$\begin{cases} &P_0(N) =1-&\prod\limits_{k=[N/4-2]}^{[N/4-1]}\,c(N-2k-1)^{-s}\prod\limits_{k=1}^{[N/4-3]}\Big(1-\big(1-c(N-4k)^{-s}\big)\big(1-d(N-2k)^{-t}\big)\Big)\\ &&\times\Big(1-\big(1-d(N-4k-2)^{-t}\big)\big(1-c(N-2k-1)^{-s}\big)\Big)\\ &&\times\prod\limits_{k=1}^{\left[\sqrt N/2\right]-1} \left(1-\left(1-\dfrac1{(2k-1)^2}c\left(\dfrac{N}{(2k-1)^2}\right)^{-s}\right) \left(1-d\left(\dfrac{N}{2k-1}\right)^{-t}\right)\right)\\[4pt] &&\times\left(1-\left(1-\dfrac1{4k^2}d\left(\dfrac{N}{4k^2}\right)^{-t}\right) \left(1-c\left(\dfrac{N}{2k}\right)^{-s}\right)\right)\\[4pt] &P_1(N) = 1- &\prod\limits_{k=[N/4-2]}^{[N/4-1]}\,c(N-2k)^{-s}\prod\limits_{k=1}^{[N/4-3]}\Big(1-\big(1-d(N-4k)^{-t}\big)\big(1-(N-2k)^{-s}\big)\Big)\\ &&\Big(1-\big(1-(N-4k-2)^{-s}\big)\big(1-d(N-2k-1)^{-t}\big)\Big)\\ &&\times\prod\limits_{k=1}^{\left[\sqrt N/2\right]-1} \left(1-\left(1-\dfrac1{(2k-1)^2}d\left(\dfrac{N}{(2k-1)^2}\right)^{-t}\right) \left(1-c\left(\dfrac{N}{2k-1}\right)^{-s}\right)\right)\\[4pt] &&\times\left(1-\left(1-\dfrac1{4k^2}c\left(\dfrac{N}{4k^2}\right)^{-s}\right) \left(1-d\left(\dfrac{N}{2k}\right)^{-t}\right)\right). \end{cases}\tag{11}$$

Model $$(11)$$ should be checked theoretically and practically, but it gives the approach to the required estimations.

The next steps are estimation of parameters $$c,d,s,t$$ and using of obtained model.

• @Joseph O'Rourke Approximation can be changed, but parametrization is actual. – Yuri Negometyanov Jan 7 at 6:55

Since both @awwalker and @mathworker21 mentioned Erdős' conjecture, and because a paper discussing this conjecture was just published, I thought I would mention it:

Erdős Conjecture (1940s or 1950s). If $$A \subset \mathbb{N}$$ satisfies $$\sum_{n \in A} \frac{1}{n}= \infty$$, then $$A$$ contains arbitrarily long arithmetic progressions.

In

• Grochow, Joshua. "New applications of the polynomial method: The cap set conjecture and beyond." Bulletin of the American Mathematical Society, Vol.56, No.1, Jan. 2019,

he says:

"It remains open even to prove that a set $$A$$ satisfying the hypothesis contains $$3$$-term arithmetic progressions."