Znajdowanie małych zbiorów liczb całkowitych, w których każdy element jest sumą dwóch innych

Jest to kontynuacja tego pytania na math.stackexchange.

Powiedzmy, że niepusty zbiór S ⊆ ℤ jest samonośny, jeśli dla każdego a  ∈ S istnieją odrębne elementy b, c  ∈ S takie, że a  =  b  + c. Dla dodatnich liczb całkowitych n , proste przykłady obejmują idealną S =  n ℤ lub (dla n > 3) przedział liczb całkowitych [- n ,  n ].

Powiemy, że S jest silnie samonośna jeśli S jest rozłączne z -S: to znaczy, jeśli  ∈ S, a następnie -  ∉ S. Żadne z powyższych przykładów są silnie samonośna, ponieważ są one w rzeczywistości zamknięte pod negacją. Istnieją zestawy skończone, które są silnie samonośne: na przykład zestawy {−22, −20, −18, −16, −14, −12, −10, −2, 1, 3, 7, 8, 15 , 23} i {−10, −8, −6, −2, 1, 3, 4, 5}.

Pytanie 1. Dla dodatniej liczby całkowitej N > 0, czy istnieje algorytm poli ( N ) -time [lub polylog ( N ) -time], który albo (i)  wytworzy silnie samonośny zestaw, którego maksymalna wartość bezwzględna wynosi N , lub (ii )  ustalić, czy taki zestaw nie istnieje? [ Edycja : jak wskazano w najstarszej odpowiedzi + mój komentarz na ten temat, zawsze istnieje taki zestaw dla N  ≥ 10.]

Pytanie 2. Czy dla N > 0 można zbudować silnie samonośny zestaw z maksymalną wartością bezwzględną N i który ma najmniej możliwych elementów?

Przypuszczam, że dla pytania nr 1 powinien być możliwy liniowy algorytm czasu (a jeśli chcesz poradzić sobie z inną reprezentacją, algorytm czasu O (1))

Biorąc pod uwagę dowolne N> = 23, tworzymy silnie samonośny zestaw, który zawiera 1 i N.

Możemy to zrobić łatwo, jeśli zbudujemy to samo dla N-1, a następnie dodamy N do wynikowego zestawu.

W przypadku przypadku podstawowego 23 możemy zacząć od zestawu przykładów.

Aby zmniejszyć rozmiar, powinniśmy być w stanie zastosować podobne podejście:

Twórz zestawy zawierające 1, N and N-1.

Używamy tych zestawów ograniczonych i wykonujemy tę konstrukcję rekurencyjnie, aby sprowadzić rozmiar do O (logN) w następujący sposób:

• Jeśli N jest parzyste, aby zbudować zestaw zawierający 1, N i N-1, rekurencyjnie skonstruuj zestaw zawierający 1, N / 2 i N / 2-1 (tj. Zestaw odpowiadający N / 2) i dodaj N i N-1 do wynikowego zestawu. Ponieważ N-1 = N / 2 + N / 2-1 i N = 1 + N-1, jest to prawidłowy zestaw.

• Jeśli N jest nieparzyste, konstruuj zestaw dla N-1 i N do zbioru wynikowego.

W przypadkach podstawowych możemy zacząć od {−22, −20, −18, −16, −14, −12, −10, −2, 1, 3, 7, 8, 15, 23,24} dla N = 24 Dla 24 <N <= 47 możemy użyć powyższego liniowego algorytmu czasowego i oprzeć się na zbiorze dla N = 24. Dla N> = 48 przełączamy na redukcję o połowę.

W rzeczywistości dla złożonego N możemy sprowadzić rozmiar do rozmiaru wymaganego dla jednej z małych liczb pierwszych, która dzieli N: Znajdź zestaw dla małej liczby pierwszej i po prostu pomnóż wszystkie liczby przez odpowiedni współczynnik.

Interesujące może być udowodnienie niektórych dolnych granic w przypadku, gdy N jest liczbą pierwszą.

Dla N ≥ 10 można zbudować silnie samonośny zestaw wielkości co najwyżej jedenastu, w następujący sposób:

{−N, NN + 2, NN + 4, 22, 1, 3, 4, 5, N − 7, N − 6, N − 5}.

Krótszy przykład przedstawiony w pierwotnym pytaniu odpowiada przypadkowi N = 10. Jest to prawie optymalne, ponieważ każdy silnie samonośny zestaw musi mieć liczność co najmniej osiem .

Tak więc problem można rozwiązać w czasie O (log (N)) [podejmowanym w zwykłych operacjach arytmetycznych na N], uzyskując zbiór liczności między ósmą a jedenastą.

Konstrukcja tej odpowiedzi została po raz pierwszy zaprezentowana dla pytania mat.stackoverflow , które daje również intuicję do konstrukcji. Czy nadal możemy uzyskać mniejsze konstrukcje, np. Pasujące do dolnej granicy ośmiu dla każdego N> 9? Co z przypadkami N ∈ {8,9}?