Введение

В этой задаче мы будем иметь дело с определенным порядком положительных целых чисел. Порядок выглядит так:

   3,    5,    7,    9,    11, ...
 2*3,  2*5,  2*7,  2*9,  2*11, ...
 4*3,  4*5,  4*7,  4*9,  4*11, ...
 8*3,  8*5,  8*7,  8*9,  8*11, ...
16*3, 16*5, 16*7, 16*9, 16*11, ...
 ...
... 64, 32, 16, 8, 4, 2, 1

Сначала мы перечислим все нечетные целые числа больше 1 в порядке возрастания. Затем мы перечислим два нечетных целых числа, больше 1, затем 4 раза, затем 8 раз и т. Д.: Для всех k мы перечислим 2 ^k нечетных чисел больше 1 в порядке возрастания. Наконец, мы перечисляем степени двойки в порядке убывания, заканчивающемся на 1. Каждое положительное целое число встречается в этом «списке» ровно один раз.

Более подробно рассмотрим два различных положительных целых числа A = n · 2 ^p и B = m · 2 ^q , где n, m ≥ 1 нечетные, а p, q ≥ 0 . Тогда A предшествует B в порядке, если выполняется одно из следующих условий:

• n> 1 , m> 1 и p <q
• 1 <n <m и p = q
• n> m = 1
• n = m = 1 и p> q

Это упорядочение появляется в удивительном математическом результате, известном как теорема Шарковского , которая касается периодических точек динамических систем. Я не буду вдаваться в подробности здесь.

Задание

Ваша задача в этой задаче - вычислить вышеуказанный порядок. Ваши входные данные - это два натуральных числа A и B , которые могут быть равны. Ваш вывод является истинным значением, если A предшествует B в порядке, и ложным значением в противном случае. Если A = B , ваш вывод должен быть правдивым. Вы можете взять A и B в любом порядке, если вы последовательны.

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

Контрольные примеры

Правдивые случаи

3 11
9 6
48 112
49 112
158 158
36 24
14 28
144 32
32 32
32 8
3 1
1 1

Ложные случаи

1 2
1 5
11 5
20 25
2 8
256 255
256 257
72 52
2176 1216
2176 2496

JavaScript (ES6), 53 49 байт

f=(a,b)=>b<2||a>1&&(a&b&1?a<=b:a&1|~b&f(a/2,b/2))

Объяснение:

• Если b равно 1, то a предшествует (или равно) b
• В противном случае, если a равно 1, то a не предшествует b
• В противном случае, если a и b нечетны, используйте регулярную проверку неравенства
• В противном случае, если a нечетно, то оно предшествует b
• В противном случае, если b нечетно, то a не предшествует b
• В противном случае разделите a и b на 2 и попробуйте снова.

Редактировать: 2 байта сохранены благодаря @Arnauld.

Python 2, 50 байт

lambda*l:cmp(*[([-n][n&n-1:],n&-n,n)for n in l])<1

Каждое число сопоставляется с тройкой, сортированный порядок которой является желаемым порядком.

• Основное значение [-n][n&n-1:], которое обрабатывает степени 2 в конце. Побитовое «и» n&n-1равно нулю именно тогда, когда nэто степень 2. Если это так, мы получаем список [-n], а в противном случае пустой список []. Это помещает все степени 2 в конце порядка, в порядке убывания.
• Вторичное значение n&-nизвлекает коэффициент степени 2 n.
• Окончательное значение nсвязывает равные степени 2 в пользу большего числа.

Соответствующие кортежи передаются, cmpчтобы увидеть, если это сравнение <=0. Python 3 сохранит байт с плавающим делением (n&n-1<1)/nдля первого значения в тройке, но ему не хватает cmp.

Python 2, 87 71 байт

k=lambda n:[n&~-n<1,(n&-n)*cmp(n&~-n,1),n/(n&-n)]
lambda a,b:k(a)<=k(b)

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

В понятных терминах кортеж для A = n · 2 ^p :

[n == 0, p * (1 - 2*(n == 0)), n]

JavaScript (ES6), 70 64 байта

Вероятно, можно играть в гольф еще, но в качестве первой попытки:

x=>y=>(a=x&-x,x/=a,b=y&-y,y/=b,y<2?x>1|b<=a:x>1&(b>a|b==a&y>=x))

Принимает ввод с синтаксисом карри (x)(y). Возвращает 0/ 1.

Контрольные примеры

let f =

x=>y=>(a=x&-x,x/=a,b=y&-y,y/=b,y<2?x>1|b<=a:x>1&(b>a|b==a&y>=x))

console.log('Testing truthy instances ...');
console.log(f(3)(11));
console.log(f(9)(6));
console.log(f(48)(112));
console.log(f(49)(112));
console.log(f(158)(158));
console.log(f(36)(24));
console.log(f(14)(28));
console.log(f(144)(32));
console.log(f(32)(32));
console.log(f(32)(8));
console.log(f(3)(1));
console.log(f(1)(1));

console.log('Testing falsy instances ...');
console.log(f(1)(2));
console.log(f(1)(5));
console.log(f(11)(5));
console.log(f(20)(25));
console.log(f(2)(8));
console.log(f(256)(255));
console.log(f(256)(257));
console.log(f(72)(52));
console.log(f(2176)(1216));
console.log(f(2176)(2496));

Perl 6 , 89 84 байта

->\a,\b{my \u=*>max a,b;a==first a|b,flat [1,2,4...u].&{(3*$_,5*$_...u for $_),.reverse}}

{my \u=*>@_.max;@_[0]==first @_.any,flat [1,2,4...u].&{.map(*X*(3,5...u)),.reverse}}

( Попробуйте онлайн. )

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

Например:

• Для ввода 2, 3он генерирует:

  3 5
  6
  12
  4 2 1

  ... а затем наблюдает, что 3появляется раньше 2.

• Для ввода 9, 6он генерирует:

  3 5 7 9 11
  6 10
  12
  24
  48
  16 8 4 2 1

  ... а затем наблюдает, что 9появляется раньше 6.

Это может быть умнее и генерировать еще меньше последовательности, но это займет больше байтов кода.

Python 2, 54 байта

f=lambda a,b:b<2or[f(a/2,b/2),a>1,0,1<a<=b][a%2+b%2*2]

Рекурсивное решение, похожее на решение Нейла.

Mathematica, 65 байт

OrderedQ[{1,#}&/@#//.{a_,b_/;EvenQ@b}->{2a,b/2}/.{a_,1}->{∞,-a}]&

Безымянная функция, принимающая список натуральных чисел и возвращающая, Trueесли список формирует восходящую последовательность в порядке Шарковского, в Falseпротивном случае. (В частности, список ввода не должен содержать только два элемента - мы получаем дополнительную функциональность бесплатно.)

Сердцем алгоритма является функция {1,#}&/@#//.{a_,b_/;EvenQ@b}->{2a,b/2}, которая многократно перемещает множители 2 для преобразования целого числа формы m*2^kс mнечетным в упорядоченную пару {2^k,m}(и делает это для каждого элемента входного списка). OrderedQзатем решает, отсортирован ли результирующий список упорядоченных пар; по умолчанию это означает возрастание порядка по первому элементу, а затем увеличение порядка по второму элементу.

Это именно то, что мы хотим, за исключением того, что числа со степенью 2 следуют другим правилам. Поэтому перед проверкой с помощью OrderingQмы применяем одно последнее правило /.{a_,1}->{∞,-a}, которое преобразует (например) {64,1}в {∞,-64}; это помещает полномочия 2 в правильное место в заказе.

APL (Dyalog Extended) , 27 байт

1⊃∘⍋⍮⍥{p⍵⍮⍨-⍵⍴⍨⍵=2*p←⊥⍨~⊤⍵}

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

Молчаливая двоичная функция, левый аргумент которой a а правый есть b.

Подход почти идентичен решению xnor Python 2 в том, что мы конвертируем каждое число во вложенный массив и проводим лексикографическое сравнение между ними.

Часть 1. Преобразование числа во вложенный массив

{p⍵⍮⍨-⍵⍴⍨⍵=2*p←⊥⍨~⊤⍵}  ⍝ Input: positive integer N
                  ⊤⍵   ⍝ Convert N to binary digits
                 ~     ⍝ Flip all the bits (1 to 0, 0 to 1)
             p←⊥⍨      ⍝ Count trailing ones and assign it to p
                       ⍝ (maximum power of 2 that divides N)
         ⍵=2*          ⍝ Test if N itself is equal to 2^p
     -⍵⍴⍨              ⍝ If true, create 1-element array containing -N;
                       ⍝ otherwise, an empty array
 p⍵⍮⍨                  ⍝ Form a 2-element nested array;
                       ⍝ 1st element is the above, 2nd is [p, N]

Часть 2: Сравните два вложенных массива

1⊃∘⍋⍮⍥f  ⍝ Input: A (left) and B (right)
     ⍥f  ⍝ Evaluate f A and f B
    ⍮    ⍝ Create a 2-element nested array [f A, f B]
   ⍋     ⍝ Grade up; indexes of array elements to make it sorted
         ⍝ Here, the result is [0 1] if A ≤ B, [1 0] otherwise
1⊃∘      ⍝ Take the element at index 1 (0-based)

Синтаксис dfn поддерживает условные операторы, например, {a:x ⋄ b:y ⋄ z}значение if a then x else if b then y else z, но в этом случае он слишком многословен, чтобы использовать его.

Haskell, 143 138 байт

В основном относительно простая реализация критериев:

e n=head[k-1|k<-[0..],n`mod`(2^k)>0]   -- exponent of 2
f n=n`div`2^e n                        -- odd part
a#b|n<-f a,p<-e a,m<-f b,q<-e b=n>1&&(m>1&&p<q||n<m&&p==q||m<2)||n<2&&m<2&&p>q||a==b  

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

Python, 159 158 153 144 142 141 байт

Сохраненный 2 байта благодаря Kritixi Lithos!

В основном это просто практика игры в гольф на моем Питоне!
Использовал формулу, заданную ОП, а не способы всех более умных ответов

f=lambda a,p=0:(a&1)*(a,p)or f(a>>1,p+1)
t=lambda(n,p),(m,q):(n==1)*(m==1)&(p>=q)or (m>1)&(p<=q)|(n<=m)&(p==q)or m==1
lambda a,b:t(f(a),f(b))

05AB1E , 14 байтов

ΣxÓs1ǝzDg≠i(]Q

Попробуйте онлайн! или подтвердите все контрольные примеры .