Математика — Бесконечные Ординалы Из Упорядоченного

Ваша задача — написать короткую программу, представляющую большой (бесконечный) порядковый номер, используя упорядоченный набор положительных целых чисел. Ваша программа возьмет два разных положительных целых числа и укажет, какое из них больше в выбранном вами порядке. Тип заказа колодца представляет собой представленный порядковый номер. Задача состоит в том, чтобы минимизировать размер вашего кода и представленный порядковый номер соответственно.

Объяснение

Обычно положительные целые числа располагаются следующим образом:

 
 
 
 
 1, 2, 4, 8, 16, ..., 3, 6, 12, 24, 48, ..., 9, 18, 36, 72, ..., ..., 5, 10, 20, 40, 80, ..., 15, 30, ..., 45, ..., ..., ..., etc. 
 
 
 
 

В таком порядке выражения: 2, 4, 8, 16, 32, ..., 3, 9, 27, 81, ..., 5, 25, 125, ..., ..., 1, 6, 10, 12, 14, ... , 1, 2, 4, 8, 16, ..., 3, 5, 6, 9, 10, 12, 17, 18, ..., 7, 11, 13, 14, 19, 21, 22, ..., 15, 23, 27, ..., ... , 1, 3, 2, 4, 5, 7, 6, 8, ... , are true, as usual. The expressions 1, 2, 3, 4, 5, ... 2, 4, 6, 8, 10, ..., 1, 3, 5, 7, ... 2, 4, 6, 8, 10, ..., 3, 9, 15, 21, ..., 5, 25, ..., ..., 1 , 1, 3, 5, 7, 9, ..., ..., 10, 8, 6, 4, 2 , and so on, are false. However, we can order the positive integers also in the following way:

Здесь за всеми четными числами следуют все нечетные числа. Теперь выражения 120 < 110 , 5 < 3 , 101 < 2 , 100 < 51 верны, а выражения 1 < 5 6 < 8 и 2 < 1 are false.

Это еще один хороший порядок:

Сначала у нас есть все четные числа, затем все оставшиеся числа, которые делятся на 3, затем те, которые делятся на 5 и так далее. Наконец, в самом конце стоит 1. Обратите внимание, что у нас есть вложенный «...». Это разрешено. Что недопустимо, так это «...», начинающееся слева.

Это не порядок (просто полный порядок). Более строгий способ формулировки этого правила состоит в том, что каждое непустое подмножество должно иметь наименьший элемент. Здесь подмножество четных чисел не имеет ни одного наименьшего элемента.

Другой способ взглянуть на это — представить, что вы начинаете справа и идете налево. Вы можете перепрыгивать произвольное (возможно, бесконечное) количество чисел, но вам всегда придется идти налево. Если числа упорядочены, ваша прогулка всегда будет занимать конечное количество шагов. Однако в этом примере вы можете просто оставаться на четной стороне, никогда не перепрыгивая через три точки и, таким образом, никогда не достигая начала.

Обратите внимание: если вы положите три порядка колодцев друг на друга следующим образом:

Они имеют разную «длину». Нижний – самый длинный, верхний – самый короткий. «Длина» называется «типом ордера» и может измеряться порядковым числом. Наш первый порядок колодца имеет тип порядка \$\omega\$, второй \$\omega\cdot2\$ и третий \$\omega^2+1\$

Ваша программа сравнит два положительных целых числа в соответствии с выбранным вами упорядочением. Таким образом, ваша программа будет представлять тип ордера вашего заказа.

Для получения дополнительной информации об ординалах посетите страницу Википедии: ординалы и порядковая арифметика. Дополнительные порядковые номера см. на странице Гугология вики. Также ознакомьтесь с предыдущий бесконечный порядковый вопрос по Code Golf.

Более порядковые примеры

\$\омега\$ 3 < 19

\$\омега^2\$ 1 < 2 (popcount then value)

\$\omega^2+\omega\$ 2 < 5

\$\омега^\омега\$ 1, 2, 3, 4, 5, ... (reverse lexiographic ordering of the стандартная форма)

Правила

Вы должны выбрать хороший порядок на \$\mathbb{Z}^+\$. Хороший порядок — это бинарное отношение \$<\$ такое, что для всех различных элементов \$a\$, \$b\$, \$c\$, \$a

Ваша программа получит два различных положительных целых числа \$a\$ и \$b\$ в некотором разумном формате. Программа выведет TRUE, если \$a

Вместо чтения из stdin/cmdline и записи в sdtout вы можете создать функцию, принимающую два целых числа. Функция по-прежнему должна иметь только два возможных (различных) возвращаемых значения, хотя они не обязательно должны быть строками.

Если ваш язык программирования не имеет встроенной поддержки bignum, вы можете предположить, что собственный целочисленный тип данных имеет бесконечный диапазон (не переполняется).

Подсчет очков

Ваша оценка — это кортеж \$(Value, Bytes)\$, где \$Value\$ — представленный порядковый номер, а \$Bytes\$ — количество байтов в вашей программе. Например, если вы реализуете порядковый номер \$\omega^3+\omega\$ в 6 байтах, ваша оценка составит \$(\omega^3+\omega, 6)\$.

Для сравнения результатов мы определяем частичный порядок \$\ge\$ так, что \$(v_0, b_0)\ge (v_1, b_1)\$ тогда и только тогда, когда \$v_0\ge v_1\$ и \$b_0\le b_1\$ . Оценка \$(v_0, b_0)\$ лучше, чем оценка \$(v_1, b_1)\$ тогда и только тогда, когда \$(v_0, b_0)\ge (v_1, b_1)\$ и оценки не равны.

Другими словами, ваша работа лучше, чем другая, если вы добьетесь большей отдачи от затраченных средств. То есть вы достигаете большего порядкового номера с тем же количеством байт или достигаете того же порядкового номера с меньшим количеством байтов. И очевидно, что если вы достигнете большего порядкового номера с меньшим количеством байтов, ваше представление будет лучше.

Это означает, что некоторые результаты нельзя сравнивать. Например, \$(\omega\cdot 2, 2)\$ и \$(\omega^2, 4)\$ несравнимы.

Вы победитель, если ни одна работа не окажется лучше вашей.

Если есть две или более заявки с одинаковым количеством баллов, победителем считается та, которая была отправлена ​​первой. Поскольку некоторые результаты невозможно сравнить с другими, победителей может быть несколько. Вы можете подать несколько заявок и, возможно, иметь несколько победителей.

#математика #вызов кода #задача принятия решения #открытая функция #занятый бобер

Пиф, \$(ω^ω, 6)\$

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 [4, 1, 10, 100_000_000_001] 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Попробуйте онлайн!

Сравнивает перевернутые простые факторизации двух входных данных.

Пиф, \$(ε_0, 17)\$

Попробуйте онлайн!

Порядковый номер, соответствующий каждому положительному целому числу, определяется выражением

$$α(p_{i_0}p_{i_1} \dotsc p_{i_{c-1}}) = \sum_k ω^{α(i_k)}$$

где \$p_i\$ — \$i\$-е простое число, а сумма справа берется в порядке невозрастания \$α(i_k)\$ (поскольку порядковое сложение не коммутативно). Это позволяет построить любой ординал конечной длины. Канторова нормальная форма. Например:

Пиф, \$(ε_0, 19)\$

Объяснение за этот старый ответ, который уже устарел, но может представлять интерес для переноса на языки, в которых отсутствуют встроенные функции, связанные с простыми числами.

Хаскелл, \$(\омега, 3)\$

Это решение очень простое, его действительно невозможно превзойти в Haskell.

Попробуйте онлайн!

Хаскелл, \$(\omega+n,19+2\left\lfloor\log_{10}(n+1)\right\rfloor)\$

Вот схема получения \$\omega + n\$ для любого \$n\in\mathbb{N}\$. Просто замените +1 s below with one more than \$n\$. This will make the first \$n\$ numbers bigger than all other numbers but otherwise compare normally.

Попробуйте онлайн!

Похоже, что в таблице лидеров теперь должно быть бесконечное количество победителей. Однако мы можем довольно легко победить бесконечное их количество. Большую часть этого можно сделать, просто немного повозившись, пока мы не достигнем 26 байт. Поэтому свои оценки за 21, 23 и 25 я приведу без отдельных комментариев. Они должны быть довольно четкой модификацией 19-байтового случая.

21 байт, \$\omega+98\$

23 байта, \$\omega+387420488\$

25 байт, \$\omega+9^{99}-1\$

К счастью, если завершить это число до 26, мы можем получить гораздо больший порядковый номер:

Хаскелл, \$(\omega\cdot n,26+\left\lfloor\log_{10}(n)\right\rfloor)\$

Спасибо ОП за указание на то, что для этого мне не нужно деление.

Еще одна схема, очень похожая на предыдущую, замените +`\b(11+)(\1)+\b $1 1$#2$* with the desired number.

Попробуйте онлайн!

Мы снова можем использовать сложность Колмогорова, чтобы улучшить некоторые из них. Вот некоторые из них, которые на данный момент являются рекордами для соответствующих размеров программ.

28 байт, \$\omega\cdot 9^9\$

29 байт, \$\omega\cdot 9^{99}\$

30 байт, \$\omega\cdot 9^{9^9}\$

31 байт, \$\omega\cdot 9^{9^{99}}\$

32 байта, \$\omega\cdot 9^{9^{9^9}}\$

33 байта, \$\omega\cdot 9^{9^{9^{99}}}\$

Хаскелл, \$(\omega^\omega, 63)\$

Реализует порядок \$\omega^\omega\$ в вопросе.

Попробуйте онлайн!

Хаскелл, \$(\phi_{\Omega^\omega}(0)\cdot\omega,208)\$

Это реализует тот же порядковый номер, что и в ответ картонной коробки. Он немного больше маленького ординала Веблена \$\phi_{\Omega^\omega}(0)\$.

Конечно, здесь можно было бы больше играть в гольф. Я не уверен, что тип или экземпляр действительно необходимы, но на данный момент это возвращает Haskell в таблицу лидеров.

Попробуйте онлайн!

Хаскелл, \$(\phi_{\Omega^\omega}(0)^n\cdot\omega,218+2n)\$

В этом примере кода размером 222 байта предыдущий алгоритм повторяется дважды. Даём \$\phi_{\Omega^\omega}(0)^2\cdot\omega\$.

Попробуйте онлайн!

Каждый раз, когда мы добавляем > to the front of the definition of p мы прибавляем 1 к степени за счет двух байтов.

Таблица лидеров Haskell

Поскольку Haskell был полностью удален из основной таблицы лидеров, на данный момент я веду здесь краткий список победителей Haskell.

Питон 2, \$\psi_0(\Omega^{\Omega^\omega})\cdot\omega\$ относительно пси Бухгольца, 266 байт

Попробуйте онлайн!

По крайней мере, я думаю, что именно так пишется этот порядковый номер. Это немного больше, чем Малый порядковый номер Веблена.

ȯ;\← is a bijective function that maps natural numbers ¤ в кортежи ← of ordered trees and natural numbers. It does so by treating the reversed binary representation of the input as a sequence of 1 песок ¬¤>?o↔pȯ;\←← s, prepended by an extra ¬ . Как только начальный < is given a matching ¤ , неиспользованные биты образуют остаток. Например, p is ↔ в двоичном формате, который преобразуется в ¬¤<(↔p which becomes ¬F<m?o_\I%2 , давая 7 as the tree and ¬F<σ7\0 как остаток.

¬< is a well ordering of ordered trees, the ordinal of which is the small Veblen ordinal. It is taken from Jervell, Herman Ruge (2005), "Finite Trees as Ordinals" (which I found via the Wikipedia article linked above). I horizontally mirrored it because it made the code shorter.

scanl min accepts 2 natural numbers, converts them to 44521 кортежи и сравнивает их сначала по остатку, затем по дереву.

Числа, которые сопоставляются с кортежами в форме 45271 form the small Veblen ordinal.

Кортежи в форме scanl1 min.show come next, then (.q).(<).q q=scanl1 min.show>>=(,) , (.q).(<).q q=gcd 60>>=(,) etc. for a total of \$\omega\$ copies of the small Veblen ordinal, which I think is written \$\phi_{\Omega^\omega}(0)\cdot\omega\$.

Примечание: хотя я определил [1,2,3,6] in terms of non-negative integers, the ordinal doesn't change if you only use strictly positive integers.

Полиглот, \$(\omega, 1)\$

Не стесняйтесь добавлять языки в список.

Попробуйте это в:

• На самом деле. Выходы q x=(odd x,x) / q .
• Семейные языки APL: АПЛ, Дж, К, БКН. Выходы (.q).(<).q q=odd>>=(,) / lambda a,b:(a&-a,a)<(b&-b,b) .
• Желе. Выходы 1 / 0 .
• бочонок. Выходы < / ‹ .
• МатематикаГольф. Выходы 1 / 0 .
• МАТЛ. Выходы 0 / 1 .
• Пыт. Выходы True / False .
• Стакс. Выходы 0 / 1 .
• Виксал. Выходы 1 / 0 .

Также один байт в 05AB1E, но 1 instead of 0 . Выходы 0 / 1 .

Питон 3, \$(\omega^2,28)\$

Попробуйте онлайн!

Старая версия

Это упорядочивает сначала по количеству конечных нулей (двоичных представителей), а затем по самому числу.

Хаскелл, \$\omega\cdot 2\$, 22 байта

Попробуйте онлайн!

Основано на Ответы на Haskell от Grain Ghost. Функция 1 is pointfree for 0 . То есть мы сортируем числа по тому, являются ли они нечетными, а затем по самому числу, которое дает четные числа, за которыми следуют шансы. Мы можем обобщить эту идею так:

Хаскелл, \$\omega\cdot 4\$, 24 байта

Попробуйте онлайн!

Номера разбиений по наибольшим общим делителям с 6, что является одним из f . In general, we can replace 6 with any number \$c\$, and get order type \$ \omega \cdot \sigma(c)\$, where \$ \sigma(c)\$ counts the divisors of \$c\$. For instance:

Хаскелл, \$ \omega \cdot 12\$, 25 байт

Попробуйте онлайн!

Для трех цифр 840 дает \$ \omega \cdot 32\$ для 26 байт. Оптимальные значения \$c\$ для использования: Высокосложные числа.

Хаскелл, \$\omega^{10}\$, 34 байта

Попробуйте онлайн!

Помощник (tree, 1) takes the decimal representation of a number and computes the running minimum, resulting in a non-increasing sequence. For example, (tree, 0) становится (tree,remainder) . We then compare these representations lexicographically, tiebroken by the number itself.

Покажем, что неубывающие конечные списки цифр \$0,\dots,9\$ хорошо упорядочены с типом порядка \$\omega^{10}\$. При лексикографическом сравнении сначала проверяется, какая последовательность имеет больше девяток в префиксе, разбивается на ту, за которой следует больше восьмерок, и так далее до того, какая последовательность заканчивается большим количеством нулей. Итак, если мы представим список в виде \$a_9\$9, за которым следуют \$a_8\$8 и так далее до \$a_0\$0, сравнение эквивалентно сравнению \$a_9, a_8, \dots, a_0. \$ лексикографически. Каждый \$a_i\$ — произвольное натуральное число, поэтому это в точности тип порядка \$\omega^{10}\$.

f operation suffices to obtain almost every non-increasing sequence of digits 0 through 9, as is seen by it leaving the numbers represented by these digits unchanged -- the only exception is sequences made of only 0's, but their omission doesn't affect the order type. Moreover, each such sequence is produced by a finite number of values, a subset of the numbers with that many digits, and it doesn't matter what the tiebreak is among these values as long as there are no ties. So, the order type produced by the main function is also \$\omega^{10}\$.

Сортировка цифр по убыванию также сработала бы, но в Haskell нет встроенной сортировки. На других языках, скорее всего, подойдет сортировка.

Если бы мы могли убрать ограничение на 9 из значений цифр, мы бы получили тип ордера \$\omega^{\omega}\$

Шелуха, \$\omega\$, 2 байта

Попробуйте онлайн!

Скучное решение с одной омегой: хороший порядок — это обычный целочисленный порядок (рассматриваемый пример 1).

Шелуха, \$\omega\$+1, 7 байт

Попробуйте онлайн!

Омега+1: правильный порядок — это целые числа, начинающиеся с 1 в обычном порядке, но пропускающие 7 и, наконец, с 7 последней, поэтому: 1,2,3,4,5,6,8,9,10,..., 7.
Измените (()()) in the code to select any other digit at the end.

Шелуха, \$\omega\$.2, 11 байт

Попробуйте онлайн!

Сначала нечетные числа, затем четные, то есть: 1,3,5,7,...,2,4,6,8,... .

Шелуха, \$ω^ω\$, 6 байт

Попробуйте онлайн!

Порт Омега-омега-подход Нила: получает обратное ( 100101 ) 37 временные факторы каждого ) argument, and compares them lexicographically ( ( ), наконец, приняв логическое НЕ ( ( ) to ensure only two output values.

Шелуха, \$ω^ω\$+1, 12 байт

Попробуйте онлайн!

Лексикографический порядок обратных простых множителей входных данных минус 1, но, наконец, с ( last: subtract 1 ( (tree,remainder) ) от каждого ( n ) input, then if the result is falsey (zero), convert it to a list containing infinity ( T ), в противном случае составьте список его перевернутых ( l=len T=lambda i,s='(',d=1:T(i/2,s+['),','('][i%2],d+i*2%4-1)if d else(eval(s)[0],i) L=lambda A,B:any(A==b or L(A,b)for b in B)or all(L(a,B)for a in A)and(l(A)-l(B),0)<(0,next((L(a,b)for a,b in zip(A,B)if a!=b),0)) def f(a,b):A,a=T(a);B,b=T(b);return(a,0)<(b,L(A,B)) ) r коэффициенты времени, прежде чем сравнивать их ( g$ ) and taking the logical NOT ( data T=T[T]deriving Eq instance Ord T where a<=b=a==b||a<b;T a<T b=any(T a<=)b||(all(<T b)a&&(l a,a)<(l b,b)) l=length c x|odd x,(y,t)<-c$div x 2=(T t:)<$>c y|1>0=(div x 2,[]) g f x|(y,t)<-c x=(T t,f y) r=g$g id f=(.r).(<).r ).

Древесный уголь, \$ω^2\$, 10 байт

Попробуйте онлайн! Ссылка на подробную версию кода. Упорядочивается по сумме цифр, затем в обычном порядке по возрастанию, в результате чего получается следующий порядок:

n#1=[] n#a|mod a n<1=n#div a n++[n]|m<-n+1=m#a y=(.(2#)) f=y.y(<)

Древесный уголь, \$ω^2\cdot 9\$, 14 байт

Попробуйте онлайн! Ссылка на подробную версию кода. Упорядочивается по наибольшей цифре, затем по сумме цифр, затем по обычному возрастанию, в результате чего получается следующий порядок:

(.q).(<).q q x=(x`mod`9^9^9^9,x)

Древесный уголь, \$ω^3\$, 16 байт

Попробуйте онлайн! Ссылка на подробную версию кода. Упорядочивается по сумме цифр суммы цифр, затем по сумме цифр, затем в обычном порядке по возрастанию, в результате чего получается следующий порядок:

(.q).(<).q q x=(x`mod`9^9^9,x)

Древесный уголь, \$ω^ω\cdot 9\$, 29 байт

Попробуйте онлайн! Ссылка на подробную версию кода. Повторно суммирует цифры входных данных, пока они оба не достигнут своего цифрового корня, затем сравнивает результаты в обратном порядке от цифрового корня до исходного входного сигнала. Поскольку существует 9 цифровых корней и потенциально произвольное количество шагов суммирования, я думаю, что у меня есть правильное значение для этого. Для небольших входных данных порядок такой же, как и в предыдущей версии; сначала он расходится для 199, что, например, здесь сравнивается с меньшим, чем 99, но не в предыдущем порядке.

Ретина 0.8.2, \$ω^ω\$, 54 байта

Попробуйте онлайн! Ссылка включает тестовые примеры. Объяснение:

Преобразовать в унарный.

Факторизация с наименьшими простыми множителями выполняется в последнюю очередь.

Сравните лексикографически.

Питон 2, \$\omega^{10}\$, 48 байт

Попробуйте онлайн!

Выходы x#y=(x<99,x)<(y<99,y) for x#y=(x<9,x)<(y<9,y) и 9 for (<)

Берет каждое число и сортирует его цифры в порядке убывания, затем сравнивает лексикографически. Это эффективно сравнивает количество цифр 9, разбиваемое по количеству цифр 8 и так далее до 0. Все это зависит от значения самого числа.

Этот тип ордера \$\omega^{10}\$ следует тому же аргументу, что и мой Haskell \$\omega^{10}\$ ответ, с заменой сортировки с взятием промежуточного минимума.

Хаскелл, \$\omega^\omega\$,62 53 байта

Попробуйте онлайн!

-9 байт благодаря xnor

Концептуально это преобразует целое число в бесконечный список, который создается путем итерации α(1) = 0, y(1) = [] α(2) = 1, y(2) = [[]] α(4) = 2, y(4) = [[], []] α(8) = 3, y(8) = [[], [], []] α(16) = 4, y(16) = [[], [], [], []] α(3) = ω, y(3) = [[[]]] α(6) = ω + 1, y(6) = [[[]], []] α(12) = ω + 2, y(12) = [[[]], [], []] α(9) = ω·2, y(9) = [[[]], [[]]] α(18) = ω·2 + 1, y(18) = [[[]], [[]], []] α(27) = ω·3, y(27) = [[[]], [[]], [[]]] α(7) = ω^2, y(7) = [[[], []]] α(14) = ω^2 + 1, y(14) = [[[], []], []] α(21) = ω^2 + ω, y(21) = [[[], []], [[]]] α(49) = ω^2·2, y(49) = [[[], []], [[], []]] α(19) = ω^3, y(19) = [[[], [], []]] α(5) = ω^ω, y(5) = [[[[]]]] α(10) = ω^ω + 1, y(10) = [[[[]]], []] α(15) = ω^ω + ω, y(15) = [[[[]]], [[]]] α(35) = ω^ω + ω^2, y(35) = [[[[]]], [[], []]] α(25) = ω^ω·2, y(25) = [[[[]]], [[[]]]] α(13) = ω^(ω + 1), y(13) = [[[[]], []]] α(23) = ω^(ω·2), y(23) = [[[[]], [[]]]] α(17) = ω^ω^2, y(17) = [[[[], []]]] α(11) = ω^ω^ω, y(11) = [[[[[]]]]] α(31) = ω^ω^ω^ω, y(31) = [[[[[[]]]]]] , which just counts the zeroes, until zero is reached. Then it's just zeroes after that. Then those lists are then compared in reverse lexicographic order.

Чтобы сделать это на практике, списки строятся в обратном порядке, а заголовок списка имеет собственную длину. «Идеальные» бесконечные списки имеют бесконечный след из нулей, которые в «практичных» списках удаляются. Эти нули учитываются с длиной.

Например, число L def y(b): Pb prime factors of b m map over d: _d -d U range [-d, …, -1] P# filter for (negated) primes l count y recursively call y S sort _ reverse >yEyQ y(second input) > y(first input) has the "ideal" representation L_SmylP#U_dPb>yEy и «практическое» представление >_PE_P