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,cy,c2y 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,

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

Q1. What is its growth rate?

 
 
 
Avoiding3Terms

Q2. Does i=11/si converge? (Where si 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.

Answer

HINT

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

Suppose
F3(1)=1,F3(2)=2,P(1)=P(2)=P(5)=P(6)=1,P(3)=P(4)=P(7)=P(8)=0,
V(N)=Ni=1P(i),F3(N)=[V1(N)].

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

Suppose
P(N)=Pa(N)Pg(N)).

Arithmetic Probability estimation.

Suppose
Pa(N)=[N/2]k=1Pa(N,k),
where Pa(N,k) is the probability that arithmetic progression {N2k,Nk,N} does not exist for any j.
Suppose
Pa(N,k)=(1P(N2k))((1P(Nk)).

Geometric Probability estimation.

Suppose
Pg(N)=[Nn]k=1Pg(N,k),
where Pg(N,k) is the probability that geometric progression (Nk2,Nk,N} with the denominator k does not exist for all i,j.

Taking in account that the geometric progression can exist only if k2| N, suppose
Pg(N,k)=(11k2P(Nk2))(1P(Nk)).

Common model.

Common model can be simplified to next one,
{P(N)=1[N/21]k=1(1(1P(N2k))(1P(Nk)))×[N]k=1(1(11k2P(Nk2))(1P(Nk)))P(1)=P(2)=P(5)=P(6)=1,P(3)=P(4)=P(7)=P(8)=0V(N)=Ni=1P(i),F3(n)=[V1(n)].

Looking the solution in the form of
{P(N)=Pv(N),wherev=[N1mod42],P0(N)={1,ifN<9cNs,otherwiseP1(N)={0,ifN<9dNt,otherwise

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.

Attribution
Source : Link , Question Author : Joseph O'Rourke , Answer Author : Yuri Negometyanov

Leave a Comment