Бүтін сандар тізбектерінің онлайн энциклопедиясы

Кіріспе

Бүтін сандар тізбектерінің онлайн дерекқоры

Бүтін сандар тізбектерінің онлайн энциклопедиясы (OEIS) – бүтін сандар тізбектерінің онлайн дерекқоры. Оны Нил Слоан AT&T зертханасында жұмыс істеген кезінде жасады және күтіп келді. 2009 жылы ол OEIS-тің интеллектуалдық меншігі мен хостингін OEIS Foundation-ға берді. Слоан – OEIS Foundation-ның төрағасы. OEIS кәсіби және әуесқой математиктерге қызықты бүтін сандар тізбектері туралы ақпаратты сақтайды және оған жиі сілтеме жасалады. 2024 жылғы мәліметтер бойынша, онда 370 000-нан астам тізбек бар, бұл оны осы сияқты ең ірі дерекқор етеді. Әрбір жазбада тізбектің бастапқы мүшелері, кілт сөздер, математикалық түсіндірмелер, әдебиетке сілтемелер және график жасау немесе тізбектің музыкалық бейнесін ойнату опциясы сияқты қосымша ақпараттар бар. Дерекқорды кілт сөздер, ішкі тізбектер немесе 16 түрлі өріс бойынша іздеуге болады.

Тарих

Нил Слоан 1964 жылы комбинаторикадағы жұмысын қолдау үшін бүтін сандар тізбектерін аспирант ретінде жинауды бастады. База бастапқыда перфокарталарда сақталған. Ол деректер базасынан таңдап алынған деректерді екі рет кітап түрінде жариялады: *A Handbook of Integer Sequences* (1973, ), онда 2372 тізбек лексикографиялық тәртіппен және 1-ден 2372 дейін нөмірленген. Саймон Плауфпен бірге *The Encyclopedia of Integer Sequences* (1995, ), құрамында 5488 тізбек және тағайындалған M нөмірлері M0000-ден M5487-ге дейін. Энциклопедияда N0001-ден N2372 дейінгі (1-ден 2372-ге дейін емес) N сандар ретінде *A Handbook of Integer Sequences* кітабындағы сәйкес тізбектердің анықтамалары (олардың бастапқы терминдерімен айырмашылығы болуы мүмкін) кіреді. Энциклопедияда OEIS-те қолданылатын А сандары бар, ал *Handbook*-та жоқ. Бұл кітаптар жақсы қабылдады, әсіресе екінші басылымнан кейін математиктер Слоанға жаңа тізбектердің тұрақты ағынын ұсынды. Жинақ кітап түрінде басқарылмады, ал деректер қоры 16 000 жазбаға жеткенде, Слоан онлайн-форматқа шығуға шешім қабылдады - алдымен электрондық пошта қызметі ретінде (1994 жылдың тамызы), содан кейін веб-сайт ретінде (1996). Деректер базасының жұмысынан кейін Слоан 1998 жылы *Journal of Integer Sequences* журналын құрды. Деректер қоры жылына 10 000-ға жуық жаңа жазбамен өсіп келеді. Слоан 40 жыл бойы "өзінің" тізбектерін жеке басқарып келді, бірақ 2002 жылдан бастап редакторлар мен еріктілердің кеңесі деректер базасын сақтауға көмектесті. 2004 жылы Слоан дерекқорына 100 000-шы тізбектің қосылуын атап өтті, ол Ишанго сүйегіндегі таңбаларды санайды. 2006 жылы пайдаланушы интерфейсі жаңартылып, одан да жетілдірілген іздеу мүмкіндіктері қосылды. 2010 жылы OEIS редакторлары мен үлескерлерінің ынтымақтастығын жеңілдету үшін OEIS.org сайтында OEIS вики құрылды. 2011 жылдың қараша айында деректер базасына 200 000-шы тізбек, қосылды; ол бастапқыда A200715 ретінде енгізілген болатын, ал SeqFan пошталық тізімінде бір апта талқыланғаннан кейін A200000-ге көшірілді, бұл OEIS бас редакторы Чарльз Грейтхаустың A200000 үшін арнайы тізбекті таңдау туралы ұсынысынан кейін болды. A300000 2018 жылдың ақпанында анықталды, ал 2023 жылдың қаңтарының соңына дейін деректер базасында 360 000-нан астам тізбек болды.

Neil Sloane started collecting integer sequences as a graduate student in 1964 to support his work in combinatorics. The database was at first stored on punched cards. He published selections from the database in book form twice:
A Handbook of Integer Sequences (1973, ), containing 2,372 sequences in lexicographic order and assigned numbers from 1 to 2372. The Encyclopedia of Integer Sequences with Simon Plouffe (1995, ), containing 5,488 sequences and assigned M numbers from M0000 to M5487. The Encyclopedia includes the references to the corresponding sequences (which may differ in their few initial terms) in A Handbook of Integer Sequences as N numbers from N0001 to N2372 (instead of 1 to 2372.) The Encyclopedia includes the A numbers that are used in the OEIS, whereas the Handbook did not. These books were well received and, especially after the second publication, mathematicians supplied Sloane with a steady flow of new sequences. The collection became unmanageable in book form, and when the database had reached 16,000 entries Sloane decided to go online—first as an email service (August 1994), and soon after as a website (1996). As a spin off from the database work, Sloane founded the Journal of Integer Sequences in 1998. The database continues to grow at a rate of some 10,000 entries a year. Sloane has personally managed 'his' sequences for almost 40 years, but starting in 2002, a board of associate editors and volunteers has helped maintain the database. In 2004, Sloane celebrated the addition of the 100,000th sequence to the database, , which counts the marks on the Ishango bone. In 2006, the user interface was overhauled and more advanced search capabilities were added. In 2010 an OEIS wiki at OEIS. org was created to simplify the collaboration of the OEIS editors and contributors. The 200,000th sequence, , was added to the database in November 2011; it was initially entered as A200715, and moved to A200000 after a week of discussion on the SeqFan mailing list, following a proposal by OEIS Editor in Chief Charles Greathouse to choose a special sequence for A200000. A300000 was defined in February 2018, and by end of January 2023 the database contained more than 360,000 sequences.

Бүкіл емес сандар

Түпнұсқалық сандар тізбектерінен басқа, OEIS бөлшектердің тізбектерін, трансценденттік сандардың цифрларын, кешенді сандарды және т.б. бүтін сандар тізбектеріне түрлендіру арқылы каталогтайды. Бөлшектер тізбектері екі тізбекпен көрсетіледі (негізгі сөз "frac" арқылы аталады): санаушылар тізбегі және бөлімдер тізбегі. Мысалы, бесінші реттік Фарей тізбегі 1, 1, 1, 2, 1, 3, 2, 3, 4 санаушылар тізбегі және 5, 4, 3, 5, 2, 5, 3, 4, 5 бөлімдер тізбегі ретінде тізілген. Маңызды иррационал сандар, мысалы, π = 3.1415926535897, ондық кеңейтімдер (мұнда 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3, 2, 3, 8, 4, 6, 2, 6, 4, 3, 3, 8, 3, 2, 7, 9, 5, 0, 2, 8, 8, ...), екілік кеңейтімдер (мұнда 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, ...) немесе жалғастырылған бөлшек кеңейтімдері (мұнда 3, 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 2, 1, 1, 2, 2, 2, 2, 1, 84, 2, 1, 1, ...) сияқты өкілдік бүтін сандар тізбектерімен каталогталады.

Конвенциялар

OEIS 2011 жылға дейін қарапайым ASCII мәтінімен шектелген, және ол әлі де дәстүрлі математикалық нотацияның сызықтық түрін қолданады (мысалы, функциялар үшін f(n), өзгеретін айнымалылар үшін n және т.б.). Грек әріптері көбінесе олардың толық аттарымен жазылады, мысалы, мю үшін μ, фи үшін φ. Әрбір тізбек А әрпімен басталып, одан кейін алты цифрмен белгіленеді, көбінесе алдынан нөлдер қойылады, мысалы, A315 емес, A000315. Тізбектердің жекелеген мүшелері үтірмен бөлінеді. Сандар тобы үтірлермен, нүктелермен немесе бос орындармен бөлінбейді. Түсініктемелерде, формулаларда және т.б. a(n) тізбектің n-ші мүшесін көрсетеді.

Нөлдің ерекше мәні

0 жиі болмайтын реттік элементтерді көрсету үшін қолданылады. Мысалы, "n × n сиқырлы квадратын құру үшін n2 тізбектелген алғашқы сандардың ең кіші алғашқысын, немесе егер мұндай сиқырлы квадрат болмаса 0-ді есептейді". a(1) (1 × 1 сиқырлы квадрат) мәні 2; a(3) – 1480028129. Бірақ 2 × 2 сиқырлы квадрат жоқ, сондықтан a(2) – 0. Бұл ерекше қолданыс белгілі бір сану функцияларында математикалық негізделген; мысалы, тотиенттік валенттілік функциясы Nφ(m) φ(x) = m теңдеуінің шешімдерін санайды. 4 саны үшін 4 шешім бар, бірақ 14 саны үшін шешім жоқ, сондықтан A014197 тізіміндегі a(14) – 0, яғни шешімдер жоқ. Басқа да мәндер қолданылады, көбінесе -1 (қараңыз немесе ).

Лексикографиялық рет

OEIS реттіліктердің лексикографиялық тәртібін сақтайды, сондықтан әр реттіліктің алдыңғысы мен кейінгісі бар («контексті»). OEIS лексикографиялық ретке келтіру үшін тізбектерді қалыпқа келтіреді, (әдетте) барлық бастапқы нөлдер мен бірліктерді, сондай-ақ әрбір элементтің таңбасын ескермейді. Салмақты бөлу кодтарының тізбектерінде жиі периодты қайталап тұратын нөлдер кездеспейді. Мысалы, қарастырайық: жай сандар, палиндромдық жай сандар, Фибоначчи тізбегі, жалқау шебердің тізбегі және OEIS лексикографиялық тәртібімен берілген қатардағы кеңейтімнің коэффициенттері: Тізбек #1: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,
Тізбек #2: 2, 3, 5, 7, 11, 101, 131, 151, 181, 191, 313, 353, 373, 383, 727, 757, 787, 797, 919, 929,
Тізбек #3: 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597,
Тізбек #4: 2, 4, 7, 11, 16, 22, 29, 37, 46, 56, 67, 79, 92, 106, 121, 137, 154,
Тізбек #5: 3, 8, 3, 24, 24, 48, 3, 8, 72, 120, 24, 168, 144,
ал қалыпқа келтірілмеген лексикографиялық тәртіпте бұл тізбектер былай реттеледі: #3, #5, #4, #1, #2.

Өзін-өзі сілтемелеу реттіліктері

OEIS тарихының басында OEIS-тің өзіндегі тізбектердің нөмірленуіне байланысты анықталған тізбектер ұсынылды. "Мен осы тізбектерді ұзақ уақыт қосуға қарсы тұрдым, бір жағынан дерекқорының беделін сақтау ниетімен, екінші жағынан A22 тек 11 мүшесі ғана белгілі болғандықтан!", - деп еске алады Слоан. Слоан OEIS-ке қабылдаған ең алғашқы өзіне сілтеме жасайтын тізбектердің бірі (кейін) "a(n) = An тізбегінің n-ші мүшесі немесе An тізбегінде n-ден кем мүше болса –1" болды. Бұл тізбек An тізбегіндегі берілген алғашқы мүшені тізімдейтін терминдерді табуға көмектесті, бірақ ол офсеттерге қатысты пікірлер өзгеруіне байланысты уақыт-уақыт жаңартылып отыруы керек. Кейбір тізбектерде 2 және одан жоғары офсеттер болғандықтан, An тізбегінің a(1) мүшесін тізімдеу жақсы балама болып көрінеді. Бұл ой "An тізбегінде n саны бар ма?" деген сұраққа алып келеді, сондай-ақ "OEIS An тізбегінде n саны бар n сандары" және "n осы тізбекте тек және ғана An тізбегінде болмаса ғана болады" тізбектері пайда болды. Осылайша, 2808 құрама саны A053873 тізбегінде, себебі ол құрама сандар тізбегі, ал 40 жай емес саны A053169 тізбегінде, себебі ол жай сандар тізбегінде жоқ. Әрбір n осы екі тізбектің біріне ғана жатады, және принципте әрбір n қай тізбекке жататынын анықтауға болады, екі ерекшелік болмаса (олардың өзіне байланысты): 53873 саны A053873 тізбегіне жата ма, жоқ па, анықтау мүмкін емес. Егер ол тізбекте болса, онда олай болуы керек; егер ол тізбекте болмаса, онда (қайтадан, анықтама бойынша) олай болмауы керек. Дегенмен, екі шешім де дұрыс болар еді және 53873 саны A053169 тізбегіне жата ма, жоқ па деген сұраққа да жауап берер еді. 53169 саны A053169 тізбегіне жата да, жатпай да, деп дәлелдеуге болады. Егер ол тізбекте болса, онда анықтама бойынша олай болмауы керек; егер ол тізбекте болмаса, онда (қайтадан, анықтама бойынша) олай болуы керек. Бұл Расселдің парадоксының бір түрі. Сондықтан 53169 саны A053873 тізбегіне жата ма, жоқ па, деген сұраққа да жауап беру мүмкін емес.

Very early in the history of the OEIS, sequences defined in terms of the numbering of sequences in the OEIS itself were proposed. "I resisted adding these sequences for a long time, partly out of a desire to maintain the dignity of the database, and partly because A22 was only known to 11 terms! ", Sloane reminisced. One of the earliest self referential sequences Sloane accepted into the OEIS was (later ) "a(n) = n th term of sequence An or –1 if An has fewer than n terms". This sequence spurred progress on finding more terms of lists the first term given in sequence An, but it needs to be updated from time to time because of changing opinions on offsets. Listing instead term a(1) of sequence An might seem a good alternative if it were not for the fact that some sequences have offsets of 2 and greater. This line of thought leads to the question "Does sequence An contain the number n?" and the sequences , "Numbers n such that OEIS sequence An contains n", and , "n is in this sequence if and only if n is not in sequence An". Thus, the composite number 2808 is in A053873 because is the sequence of composite numbers, while the non prime 40 is in A053169 because it is not in , the prime numbers. Each n is a member of exactly one of these two sequences, and in principle it can be determined which sequence each n belongs to, with two exceptions (related to the two sequences themselves):
It cannot be determined whether 53873 is a member of A053873 or not. If it is in the sequence then by definition it should be; if it is not in the sequence then (again, by definition) it should not be. Nevertheless, either decision would be consistent, and would also resolve the question of whether 53873 is in A053169. It can be proved that 53169 both is and is not a member of A053169. If it is in the sequence then by definition it should not be; if it is not in the sequence then (again, by definition) it should be. This is a form of Russell's paradox. Hence it is also not possible to answer if 53169 is in A053873.

Слоанның саңылауы

2009 жылы Филипп Гульельметти әрбір бүтін санның «маңыздылығын» өлшеу үшін OEIS дерекқорын пайдаланды. Оң жақтағы графикте көрсетілген нәтиже екі бөлек нүктелік топтар арасындағы айқын «алшақтықты» көрсетеді: «қызығушылық тудырмайтын сандар» (көк нүктелер) және OEIS тізбектерінде салыстырмалы түрде жиі кездесетін «қызықты» сандар. Ол негізінен жай сандарды (қызыл), aⁿ түріндегі сандарды (жасыл) және жоғары құрамды сандарды (сары) қамтиды. Бұл құбылысты Николас Гаврит, Жан Пол Делахае және Гектор Зениль зерттеді, олар екі топтың жылдамдығын алгоритмдік күрделілік тұрғысынан, ал алшақтықты – жай сандар, жұп сандар, геометриялық және Фибоначчи типтес тізбектерге деген жасанды әлеуметтік қалауға негізделген факторлармен түсіндірді. Слоунның алшақтығы 2013 жылы Numberphile бейнесінде көрсетілді.