Let $A_N$ be the subset of $\{1,\ldots,\ N\}$ that has no $3$-term A.P's and maximises $\sum_{n\in A_N}\frac{1}{n}.$ Does $A_N\to A003278?$

58 Views Asked by At

This question is about A003278, which we define as: $\ a(1) = 1,\ a(2) = 2,\ $ and thereafter $\ a(n)\ $ is smallest number $\ k\ $ which avoids any $\ 3-$term arithmetic progression in $\ a(1),\ a(2),\ \ldots,\ a(n-1),\ k.$ The first few terms are:

$$1,\ 2,\ 4,\ 5,\ 10,\ 11,\ 13,\ 14,\ 28,\ 29,\ 31,\ 32,\ 37,\ 38,\ldots$$

$$$$

For each $\ N\geq 2,\ $ let $\ A_N\ $ be the subset of $\ \{1,\ldots,\ N\}\ $ that has no three-term A.P.'s, and maximises $\ \displaystyle\sum_{n\in A_N} \frac{1}{n}.\ $

My question is, if $\ A_N \overset{n\to\infty}{\to}\ A003278\ $ in some (strong?) sense. What's the strongest true claim that is known about this?

I ran a Python program, and here are my results in a table:


\begin{array}{|c|c|c|} \hline \text{N} & A_N \\ \hline \mathbb{4} & \{1,2,4\} \\ \hline \mathbb{5} & \{1,2,4,5\} \\ \hline \mathbb{6} & \{1,2,4,5\} \\ \hline \mathbb{7} & \{1,2,4,5\} \\ \hline \mathbb{8} & \{1,2,4,5\} \\ \hline \mathbb{9} & \{1,2,4,8,9\} \\ \hline \mathbb{10} & \{1,2,4,5,10\} \\ \hline \mathbb{11} & \{1,2,4,5,10,11\} \\ \hline \mathbb{12} & \{1,2,4,5,10,11\} \\ \hline \mathbb{13} & \{1,2,4,5,10,11,13\} \\ \hline \mathbb{14} & \{1,2,4,5,10,11,13,14\} \\ \hline \mathbb{15} & \{1,2,4,5,10,11,13,14\} \\ \hline \mathbb{16} & \{1,2,4,5,10,11,13,14\} \\ \hline \mathbb{17} & \{1,2,4,5,10,11,13,14\} \\ \hline \mathbb{18} & \{1,2,4,5,10,11,13,14\} \\ \hline \mathbb{19} & \{1,2,4,5,10,11,13,14\} \\ \hline \end{array}

After this, the computation time becomes too large.

So I wonder if only $\ \{1,2,4,8,9\}\ $ "behaves badly", i.e. doesn't match the first few terms from $\ A003278.\ $

It's clear that each $\ A_N\ $ must contain the number $\ 1,\ $ for if it didn't, then reducing each member of $\ A_N\ $ by $\ \min(A_N) - 1\ $ would give a greater value of $\ \displaystyle\sum_{n\in A_N} \frac{1}{n}.\ $

But I can't even think of any argument/reason as to why $\ 2\in A_N\ $ for all sufficiently large $N.$

Edit: Here is my Python code, which I suspect is very inefficient:

# -*- coding: utf-8 -*-
"""
Created on Tue Nov 29 08:34:17 2022

@author: adamr
"""
import itertools
for n in range(4,22):
    startinglist=[]
    for i in range(n):
        startinglist.append(i+1)
    
    '''print(list5)
    print(list(itertools.combinations(list5, 3)))'''
    
    bigSubsetlist=[]
    
    #for L in range(3,len(startinglist) + 1):
        #for subset in itertools.combinations(startinglist, L):
            #print(subset)
            
    for L in range(3,len(startinglist) + 1):
        for subset in itertools.combinations(startinglist, L):
            subset = list(subset)
            failedSubset=False
            for i in range(len(subset)-2):
                #if failedSubset==True:
                    #break
                for j in range(i+1,len(subset)-1):
                    #if failedSubset==True:
                        #break
                    for k in range(j+1,len(subset)):
                        if failedSubset==True:
                            break
                        #print("index: ", i,j,k), "list: ", []
                        if subset[j] - subset[i] == subset[k] - subset[j]:
                            failedSubset=True
                            break
            if failedSubset==False:
                subset.append( sum( 1/n for n in  subset) )
                bigSubsetlist.append(subset)
                
    #print(bigSubsetlist)
                
    biggest_Search=[bigSubsetlist[0]]
for subList in bigSubsetlist[1:]:
    if subList[-1] > biggest_Search[0][-1]:
        biggest_Search = [subList]
            
print("biggest_Search= ", biggest_Search, '\n')