Кіріспе

Математикада, оң бүтін сан n-ді есептеу үшін қосу тізбегі 1-ден басталып, n-мен аяқталатын табиғи сандар тізбегі арқылы беріледі, мұнда тізбектегі әрбір сан екі алдыңғы санның қосындысы болып табылады. Қосу тізбегінің ұзындығы – тізбектегі барлық сандарды алу үшін қажетті қосылымдардың саны, яғни сандар тізбегінің санынан бір кем.

Қосу тізбектерін есептеу әдістері

Ең аз ұзындықтағы қосу тізбегін есептеу оңай емес; мәселенің жалпыланған түрі, онда бірқатар мәндердің әрқайсысын бірдей құрайтын тізбекті табу қажет, NP-толық. Белгілі бір сан үшін ең аз қосу тізбегін есептеуге кепілді түрде ақылға қонымды уақыт немесе аз жадты пайдаланумен келетін алгоритм жоқ. Дегенмен, салыстырмалы түрде қысқа тізбектерді есептеуге арналған бірнеше әдістер белгілі, бірақ олар әрқашан ең жақсы нәтиже бермейді. Салыстырмалы түрде қысқа қосу тізбегін есептеудің кең таралған әдісі – бинарлық әдіс, ол квадрат арқылы дәрежелеуге ұқсас. Бұл әдісте санның қосу тізбегі рекурсивті түрде алынады. Егер сан жұп болса, ол бір қосымша қосым арқылы алынады, ал егер тақ болса, бұл әдіс оны есептеу және содан кейін бірді қосу арқылы алу үшін екі қосымды пайдаланады. қосу тізбегінен бір қосымша қосымды қосу арқылы алынуы мүмкін, содан кейін тізбектер ұзындығы бойынша теңсіздік туындайды. Дегенмен, бұл әрқашан теңдік емес, себебі кейбір жағдайларда осылайша алынған тізбектен қысқа тізбек болуы мүмкін. Мысалы, Кнуттың байқауынша, 1=l(n)=l*(n). Бірақ Хансен n-нің кейбір мәндері үшін l(n)≠l*(n) болатынын көрсетті, мысалы, 1=n=2^(6106)+2^(3048)+2^(2032)+2^(2016)+1, онда 1=l*(n)=6110, l(n)≤6109. Мұндай ең кіші n – 12509.

Шолц болжамы

Шолц болжамы (кейде Шолц–Брауер немесе Брауер–Шолц болжамы деп аталады), Арнольд Шолц және Альфред Т. Брауердің есімдерімен аталған, 1937 жылғы болжам. Бұл теңсіздік барлық Хансен сандары үшін орындалатыны белгілі, бұл Брауер сандарының жалпылама түрі; Нилл Клифт компьютер арқылы барлығының Хансен сандары екенін тексерді (ал 5784689 – емес). Клифт одан әрі бұл фактіні барлық жағдайларда растады.