Кіріспе
Екі есе экспоненциалды бүтін сандар тізбегі
Сандар теориясында Сильвестр тізбегі – әрбір мүшесі алдыңғы мүшелердің көбейтіндісіне бірді қосқаннан туындайтын бүтін сандар тізбегі. Оның алғашқы бірнеше мүшелері:
2, 3, 7, 43, 1807, 3263443, 10650056950807, 113423713055421844361000443.
Сильвестр тізбегі алғаш рет 1880 жылы зерттеген Джеймс Джозеф Сильвестрдің есімімен аталады. Оның мәндері екі есе экспоненциалды түрде өседі, ал оның өзара шамаларының қосындысы – бірлік бөлшектердің кез келген басқа тізбегіне қарағанда 1-ге тезірек жақындайтын бірлік бөлшектер тізбегін құрайды. Бос жиынның көбейтіндісі 1-ге тең, сондықтан бұл формула s₀ = 2 нәтижесін береді, жеке базалық жағдай қажет емес. Басқаша айтқанда, тізбекті s₀ = 2 базалық жағдайымен рекурренттік формула арқылы анықтауға болады. Индукция арқылы осы екі анықтаманың эквивалентті екенін көрсету оңай.
2, 3, 7, 43, 1807, 3263443, 10650056950807, 113423713055421844361000443
Sylvester's sequence is named after James Joseph Sylvester, who first investigated it in 1880. Its values grow doubly exponentially, and the sum of its reciprocals forms a series of unit fractions that converges to 1 more rapidly than any other series of unit fractions. The product of the empty set is 1, so this formula gives s0 = 2, without need of a separate base case. Alternatively, one may define the sequence by the recurrence
with the base case s0 = 2. It is straightforward to show by induction that this is equivalent to the other definition.
Қолданбалар
Сильвестр тізбесінің қасиеттерін пайдаланып, жұп еселі өлшемді сфералардың немесе экзотикалық сфералардың дифференциалдық топологиясына ие Сасакиан Эйнштейн көптүрліліктерінің үлкен санын анықтаңыз. Олар 2n − 1 өлшемді топологиялық сферадағы Сасакиан Эйнштейн метрикаларының саны кем дегенде sn-ге пропорционалды екенін және сондықтан n-мен екі есе экспоненциалдық өсуге ие екенін көрсетеді. Сильвестр тізбегінен алынған мәндерді сипаттағандай және онлайн контейнерлерді қаптау алгоритмдері үшін төменгі шекті мысалдарды құру үшін қолданды. Сол сияқты, екі өлшемді кесу қорларының алгоритмінің өнімділігінің төменгі шегін анықтау үшін тізбекті пайдаланыңыз. Znám проблемасы сандар жиынтығына қатысты, мұнда жиынтықтағы әрбір сан жиынтықтағы қалған сандардың көбейтіндісін бөледі, бірақ оған тең емес, сондай-ақ бірге. Теңсіздік талабы болмаса, Сильвестр тізбегіндегі мәндер бұл мәселені шешер еді; аталған талап болған жағдайда, Сильвестр тізбегін анықтайтын рекурренцияларға ұқсас рекурренциялардан алынған басқа да шешімдер бар. Znám проблемасының шешімдері беттік сингулярлықтарды жіктеуге (Брентон мен Хилл 1988) және нондетерминистік шекті автоматтар теориясына қолданылады. Бірлік бөлшектерінің k-мүшелі қосындыларының бірлікке ең жақын жуықтамаларын пайдаланып, кез келген толық санның бөлгіштерінің санының төменгі шегін анықтайды, ал сол қасиетті белгілі бір топтардың мөлшерінің жоғарғы шегін анықтау үшін қолданады.
As describe, and used values derived from Sylvester's sequence to construct lower bound examples for online bin packing algorithms. similarly use the sequence to lower bound the performance of a two dimensional cutting stock algorithm. Znám's problem concerns sets of numbers such that each number in the set divides but is not equal to the product of all the other numbers, plus one. Without the inequality requirement, the values in Sylvester's sequence would solve the problem; with that requirement, it has other solutions derived from recurrences similar to the one defining Sylvester's sequence. Solutions to Znám's problem have applications to the classification of surface singularities (Brenton and Hill 1988) and to the theory of nondeterministic finite automata. describes an application of the closest approximations to one by k term sums of unit fractions, in lower bounding the number of divisors of any perfect number, and uses the same property to upper bound the size of certain groups.