[Math] A sequence that avoids both arithmetic and geometric progressions

number theorysequences-and-series

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?

 
 
 
Avoiding3Terms

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.

Best Answer

$\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.