53
$\begingroup$

In this Numberphile video (from 3:36 to 7:41), Neil Sloane explains an amazing sequence:

It is the lexicographically first among the sequences of positive integers without triple in arithmetic progression (i.e., such that for any two distinct points in the graph, there is no point in their middle, as for $a_n=n^2$ or $b_n = 2^n$). It is due to Jack W. Grahl (2013): A229037. $$1, 1, 2, 1, 1, 2, 2, 4, 4, 1, 1, 2, 1, 1, 2, 2, 4, 4, 2, 4, 4, 5, 5, 8, 5, 5, 9, 1, 1, 2, 1, 1, 2, 2, 4, 4, \dots$$ Its graph is surprising:

enter image description here enter image description here
The following colored plot of 16 million terms is due to reddit user garnet420 (horizontal divisions are 1000000; vertical divisions are 25000).

enter image description here

This sequence reveals many possible questions (like the existence of a convergent pattern, a fractal structure)). The following one is due to Charles R. Greathouse (and deserves to be posted here):

Question: Does the term $1$ appear infinitely many times in this sequence?

Remark: the first numbers $n$ for which the $n^{th}$ term is $1$ are given by A236246.
$$1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 32, 37, 38, 40, 41, 82, 83, 85, 86, 92, 93, 96, 105, \dots$$ enter image description here

In addition, we observe that the succession $1, 1, 2, 1, 1, 2, 2, 4, 4$ appears several times, so we could also ask whether it appears infinitely many times.

Finally, we can create variations of the first sequence, replacing triple by $r$-tuple for a fixed $r \ge 3$, and ask the same questions.


Let us consider the variation suggested by Richard Stanley in comment where we only exclude weakly increasing arithmetic progressions. The first terms are the same up to the $54^{th}$ term.
For the former sequence, the $20$ next terms are $$ 9, 4, 4, 5, 5, 10, 5, 5, 10, 2, 10, 13, 11, 10, 8, 11, 13, 10, 12, 10, 10 $$ whereas for the variation they are $$ 2, 4, 4, 5, 5, 10, 5, 5, 10, 10, 11, 13, 10, 11, 10, 11, 13, 10, 10, 12, 13 $$ It is now available on OEIS at A309890. Listen it played with a marimba, it's incredibly pleasant!

Its graph is completely different, but also amazing:

enter image description here enter image description here

Finally the numbers $n$ for which the $n^{th}$ term is $1$ are given by A003278 (see Richard's comment). enter image description here


A SageMath code computing the variation:

# %attach SAGE/ThreeFree.spyx

from sage.all import *

cpdef ThreeFree(int n):
    cdef int i,j,k,s,Li,Lj
    cdef list L,Lb
    cdef set b
    L=[1,1]
    for k in range(2,n):
        b=set()
        for i in range(k):
            if 2*((i+k)/2)==i+k:
                j=(i+k)/2
                Li,Lj=L[i],L[j]
                s=2*Lj-Li
                if s>0 and Li<=Lj: # this second assumption provides the variation
                    b.add(s)
        if 1 not in b:
            L.append(1)
        else:
            Lb=list(b)
            Lb.sort()
            for t in Lb:
                if t+1 not in b:
                    L.append(t+1)
                    break 
    return L

For having the graph, do points([(i+1,L[i]) for i in range(n)],size=1,alpha=0.04,dpi=1000)

$\endgroup$
8
  • 4
    $\begingroup$ If we modify the definition so that we only exclude weakly increasing arithmetic progressions, i.e., $a(j),a(j+k),a(j+2k)$ are in arithmetic progression (with $k\geq 1$) and $a(j)\leq a(j+k)\leq a(j+2k)$, then it is easy to see that terms equal to 1 are indexed by oeis.org/A236246. This suggests looking some more at this modified sequence. Could it coincide with the original sequence? I haven't tried to check this experimentally. $\endgroup$ Aug 17, 2019 at 23:25
  • $\begingroup$ @RichardStanley Let $a$ be the former sequence, let $b$ be the modified one, and assume that the terms indexed by $1$ are unchanged. Observe that $a(27) = 9$ and $a(59) = 5$, but there is no $i \ge 0$ and $k>0$ such that $a(i)=a(i+k)=1$ and $i+2k = 59+59-27 = 91$, so $b(91) = 1$, but $a(91)=2$, contradiction. $\endgroup$ Aug 18, 2019 at 12:29
  • 2
    $\begingroup$ Oops, I foolishly assumed that A236246 was actually oeis.org/A003278 without checking. It is clear that the indices for which $b(n)=1$ coincide with A003278. Perhaps it would be interesting to consider $b(n)$ for its own sake. $\endgroup$ Aug 19, 2019 at 14:36
  • 1
    $\begingroup$ I wonder if for the question whether every natural occurs at all in this sequence, even though it seems intuitively clear, it is easier to prove that the answer is positive. $\endgroup$
    – Wolfgang
    Aug 20, 2019 at 20:13
  • 1
    $\begingroup$ A better visualization (see this question on ask.sagemath.org, especially the last comments) shows that the "empty" regions are not empty, but simply too sparse to get a visible representation on the rendered graph. $\endgroup$ Aug 25, 2019 at 15:59

1 Answer 1

-3
$\begingroup$

This is not my area of work but there is some recent progress in this field which was profiled in Quanta Magazine: Surprise Computer Science Proof Stuns Mathematicians (March 21, 2023).

In it the author details two works, a proof from computer science that there are strong bounds for sequences which contain arithmetic progression of the form {a, a + b, a + 2b} where b =/= 0, Strong Bounds for 3-Progressions (Kelly & Meka 2023) as well as a companion paper written by some mathematicians, translating the work in computer science to their audience, The Kelley--Meka bounds for sets free of three-term arithmetic progressions (Bloom & Sisack 2023).

I don't have the competence to determine whether their work can immediately answer your question, though I suspect it points the way. In that respect I feel it is more appropriate as an answer than a comment.

$\endgroup$
3
  • $\begingroup$ Well, thanks I guess. $\endgroup$ Mar 23, 2023 at 18:19
  • 4
    $\begingroup$ I'm not one of the downvoters, but this answer is getting downvotes because it is discussing a different problem. The Kelly&Meska article is about subsets $S$ of $\mathbb{Z}$ which contain no 3-term AP; the question is about a sequence $a_n$ such that the set $\{ (n, a_n) \}$ in $\mathbb{Z}^2$ contains no $3$-term AP. I could imagine a relation between these, but it certainly isn't clear. $\endgroup$ Mar 24, 2023 at 3:27
  • $\begingroup$ Also not a downvoter, but to agree with David, the Kelley-Meka methods are addressing quite a different problem (even if it is also about 3APs), and I don't see a way that those methods could help with this problem. $\endgroup$ Jun 19, 2023 at 9:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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