55
$\begingroup$

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.

$\endgroup$
  • 6
    $\begingroup$ 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. $\endgroup$ – Michael Stocker Jul 7 '14 at 13:16
  • 3
    $\begingroup$ The answer to Q2 is definitely Yes, it converges, because even just avoiding arithmetic progressions leads to convergence. Converges to what constant is unclear. $\endgroup$ – Joseph O'Rourke Jul 9 '14 at 0:33
  • 2
    $\begingroup$ @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. $\endgroup$ – John Molokach Mar 25 '16 at 2:46
  • 1
    $\begingroup$ @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. $\endgroup$ – Turambar Apr 28 '16 at 17:52
  • 1
    $\begingroup$ 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$. $\endgroup$ – Turambar May 10 '16 at 16:14
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ @Joseph O'Rourke Approximation can be changed, but parametrization is actual. $\endgroup$ – Yuri Negometyanov Jan 7 at 6:55
2
+100
$\begingroup$

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."

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.