Sequence of integers without 3-terms AP in it.

Question

In a school there are $2023$ students, numbered $1$ to $2023$. The teacher met the students one by one in the order of their numbers, and gave a candy to each student except if that would mean three students whose numbers form an arithmetic sequence all got candies. In this way, the teacher would give a candy to students 1 and 2, but not student 3 (as 1, 2, 3 form an arithmetic sequence), then to students 4 and 5, but not to students 6 and 7 (as both 4, 5, 6 and 1, 4, 7 are arithmetic sequences), and so on. How many students got candies in the end?

I tried to list the number and found the number 1,2,4,5,10,11,13,14,28,29,31,32,37,38,40,41 is available In the first 50 numbers. The thing I could only found is that everytime it start getting a candy, it would be in the form of ✅✅❌✅✅ (for example: In number 10,11,12,13,14, 12 is not available)

Answer 1

I programmed the thing supposing you don't want $3$ consecutive elements of your list to be in an arithmetic sequence, i.e. for $p<q<r$ in your list, $q-p \neq r-q$, here is the list I obtained: $$[1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 32, 37, 38, 40, 41, 82, 83, 85, 86, 91, 92, 94, 95, 109, 110, 112, 113, 118, 119, 121, 122, 244, 245, 247, 248, 253, 254, 256, 257, 271, 272, 274, 275, 280, 281, 283, 284, 325, 326, 328, 329, 334, 335, 337, 338, 352, 353, 355, 356, 361, 362, 364, 365, 730, 731, 733, 734, 739, 740, 742, 743, 757, 758, 760, 761, 766, 767, 769, 770, 811, 812, 814, 815, 820, 821, 823, 824, 838, 839, 841, 842, 847, 848, 850, 851, 973, 974, 976, 977, 982, 983, 985, 986, 1000, 1001, 1003, 1004, 1009, 1010, 1012, 1013, 1054, 1055, 1057, 1058, 1063, 1064, 1066, 1067, 1081, 1082, 1084, 1085, 1090, 1091, 1093, 1094]$$

I double checked it with a verification function. Its length is $128$

Here is my codeine python:

def next_arithmetics (lis):
    n = len(lis)
    nex = []
    maxi = lis[n-1]
    for i in range(n):
        for j in range(i):
            p = 2*lis[i] - lis [j]
            if p > maxi and not(p in nex):
                nex.append(p)
    nex.sort()
    return nex

def non_arithmetics (n):
    lis = [1,2]
    mini = 3
    while mini <= n:
        nex = next_arithmetics(lis)
        if nex[0] > mini:
            lis.append(mini)
            mini = mini+1
        else:
            i = 0
            l = len(nex)
            while (i <l-1) and (nex[i+1] == nex[i] + 1):
                i += 1
            if nex[i]+1 <= n:
                lis.append(nex[i]+1)
            mini = nex[i]+2
    return lis

def is_not_arithmetic (lis):
    n = len(lis)
    cond = True
    l = -1
    for i in range(n):
        for j in range(i):
            for k in range(j):
                if lis[i]-lis[j] == lis[j]- lis[k]:
                    return False, (k,j,i)
    return True

The first describes the candidate you should avoid for the next members of your list, the second just gives the answer and the last checks if you don't have 3 consecutive numbers of an arithmetic sequence in you list.

Mathematically, I had some insights like trying to compute the next arithmetic number, or working with projections of affine lines in $\mathbb{N}^2$ but I did not succeed

Here is the graph of len(Szekeres(n)): And a second one with bigger $n$

It seems we gat by dezooming a sort of Cantor's staircase or devil's staircase I don't know how you call it

Edit: with the property of the basis $3$ is it clearer why it forms a sort of cantor's staircase...

Answer 2

The answer I calculate using mod 3 is 128. And here is the ways. I calculate the number available in 100 and the numbers are 1,2,4,5,10,11,13,14,28,29,31,32,37,38,40,41,82,83,85,86,91,92,94,95,109,110,112,113,118,119,121,122(I don't think it is possible to get further without the help of a computer)

we can observe that the number is in 4 a group

then change the number to base 3

1. 1,2,11,12
2. 101,102,111,112
3. 1001,1002,1011,1012
4. 1101,1102,1111,1112
5. 10001,10002,10011,10012
6. 10101,10102,10111,10112
7. 11001, 11002,11011,11012
8. 11101, 11102,11111,11112

then u just need to observe the pattern and find the answer easily

The largest number will be 1111112 which is 1094

and u can list a total of 128 number

Answer 3

$n+1$ is in your sequence iff $n$ base $3$ only has $0$ and $1$’s. The math works out nicer if you include $0$ in your sequence initially and then later shift everything over by $1$.

If a number has any $2$’s in it, you can see it forms a linear sequence by replacing the $2$’s with $0$’s and $1$’s. For example, $1202_3$ is in a linear progression with $1101_3$ and $1000_3$. Similarly, if $x$ and $y$ first differ in base 3 at the $k$th digit, then $2x-y$ has the same last $k-1$ digits and the $k$th digit would be 2 (either $2\cdot 1-0=2$ or $2\cdot0-1=-1$ triggers a carry leading to $3-1=2$), so any term with only $0$ and $1$’s in base 3 can’t be in a linear progression.

$2022_{10}=2202220_3$, so that gives $0_3,1_3,10_3,…,1111111_3$. That’s $0$ or $1$ in 7 positions, so there are $2^7=128$ numbers in your list up to that point.

Answer 4

Here is a short way to program the sequence (Matlab) :

L=[1;2;4];
for k=5:1094
   b=0; % (1)
   p=1; % (2)
   while (p<length(L)) && (b==0)
      b=ismember((L(p)+k)/2,L);
      p=p+1;
   end;
   if b==0;L=[L;k];end; % (3)
end
plot(L)

Explanations :

(1) b : boolean variable remaining false while no A.P. found.

(2) p : browsing index in (the current state of) L.

(3) conditional adding of element k to list L.

The result is a kind of reciprocal of the curve given in the answer by @Jules Besson :

Answer 5

Here is my Python program:

N = 2023

candied = []
noncandied = []
for i in range(1, N+1):
    if i in noncandied:
        continue

    candied.append(i)
    noncandied.extend(i + (i-c) for c in candied)

print(candied)
```