Introdução

Neste desafio, estaremos lidando com uma certa ordenação dos números inteiros positivos. A ordem é assim:

   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

Primeiro, listamos todos os números inteiros ímpares maiores que 1 em ordem crescente. Em seguida, listamos duas vezes números inteiros ímpares maiores que 1, depois 4 vezes, depois 8 vezes e assim por diante: para todo k , listamos 2 ^k vezes os números inteiros ímpares maiores que 1 em ordem crescente. Finalmente, listamos os poderes de dois em ordem decrescente , terminando em 1. Todo número inteiro positivo ocorre nesta "lista" exatamente uma vez.

Mais explicitamente, considere dois inteiros positivos distintos A = n · 2 ^p e B = m · 2 ^q , em que n, m ≥ 1 são ímpares ep, q ≥ 0 . Em seguida, A vem antes de B na ordem, se uma das seguintes condições ocorrer:

• n> 1 , m> 1 e p <q
• 1 <n <m e p = q
• n> m = 1
• n = m = 1 e p> Q

Essa ordem aparece no surpreendente resultado matemático conhecido como teorema de Sharkovskii , que diz respeito aos pontos periódicos dos sistemas dinâmicos. Não vou entrar em detalhes aqui.

A tarefa

Sua tarefa neste desafio é calcular a ordem acima. Suas entradas são dois números inteiros positivos A e B , que podem ser iguais. Sua saída é um valor verdadeiro se A for anterior a B na ordem e um valor falso caso contrário. Se A = B , sua saída deve ser verdadeira. Você pode pegar A e B em qualquer ordem, desde que seja consistente.

Você não precisa se preocupar com excesso de números inteiros, mas seu algoritmo deve teoricamente funcionar para entradas arbitrariamente grandes.

Casos de teste

Instâncias verdadeiras

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

Instâncias de falsidade

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

JavaScript (ES6), 53 49 bytes

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

Explicação:

• Se b é 1, a precede (ou é igual a) b
• Caso contrário, se a for 1, a não precederá b
• Caso contrário, se a e b forem ímpares, use a verificação regular de desigualdade
• Caso contrário, se a é ímpar, precede b
• Caso contrário, se b for ímpar, a não precederá b
• Caso contrário, divida aeb por 2 e tente novamente.

Editar: salvou 2 bytes graças a @Arnauld.

Python 2, 87 71 bytes

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

Isso provavelmente não ganhará nenhum prêmio de tamanho, mas essa resposta funciona construindo uma tupla com três expressões usando um número inteiro que, quando ordenado lexicograficamente, resultará na ordenação correta.

Em termos legíveis, a tupla é para A = n · 2 ^p :

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

Python 2, 50 bytes

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

Cada número é mapeado para um triplo cuja ordem classificada é a ordem desejada.

• O valor primário é [-n][n&n-1:], que lida com os poderes de 2 no final. O bit a bit "e" n&n-1é zero exatamente quando né uma potência de 2. Nesse caso, obtemos a lista [-n]e, caso contrário, a lista vazia []. Isso coloca todos os poderes de 2 no final do pedido, em ordem decrescente.
• O valor secundário n&-nextrai o fator de potência 2 de n.
• Os ntiebreaks de valor final são iguais a 2 em favor do número maior.

As respectivas tuplas são passadas cmppara ver se essa comparação é <=0. O Python 3 salvaria um byte com divisão float (n&n-1<1)/npelo primeiro valor no triplo, mas falta cmp.

JavaScript (ES6), 70 64 bytes

Provavelmente poderia ser jogado um pouco mais, mas como uma primeira tentativa:

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))

Recebe entrada com sintaxe de currying (x)(y). Retorna 0/ 1.

Casos de teste

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 bytes

->\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}}

( Experimente online. )

Não é exatamente curto, mas pensei que seria interessante escrever uma solução que realmente gerasse a sequência de pedidos (até um limite superior seguro para cada subseqüência) e depois verifique qual entrada aparece primeiro.

Por exemplo:

• Para entrada 2, 3, gera:

  3 5
  6
  12
  4 2 1

  ... e depois observa o que 3aparece antes 2.

• Para entrada 9, 6, gera:

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

  ... e depois observa o que 9aparece antes 6.

Poderia ser mais inteligente e gerar ainda menos da sequência, mas isso exigiria mais bytes de código.

Python 2, 54 bytes

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

Uma solução recursiva semelhante à de Neil.

Mathematica, 65 bytes

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

Função sem nome, obtendo uma lista de números inteiros positivos e retornando Truese a lista formar uma sequência crescente na ordem Sharkovskii, Falsecaso contrário. (Em particular, a lista de entrada não precisa ter apenas dois elementos - obtemos a funcionalidade adicionada gratuitamente.)

O coração do algoritmo é a função {1,#}&/@#//.{a_,b_/;EvenQ@b}->{2a,b/2}, que move repetidamente os fatores 2 para converter um número inteiro da forma m*2^k, com mímpar, para o par ordenado {2^k,m}(e o faz para todos os elementos da lista de entrada). OrderedQdepois decide se a lista resultante de pares ordenados já está classificada; por padrão, isso significa em ordem crescente pelo primeiro elemento e, em seguida, ordem crescente pelo segundo elemento.

É exatamente isso que queremos, exceto números com potências de 2 que seguem regras diferentes. Portanto, antes de fazer check-in OrderingQ, aplicamos uma última regra /.{a_,1}->{∞,-a}, que converte (por exemplo) {64,1}em {∞,-64}; que coloca potências de 2 no local correto na ordem.

Haskell, 143 138 bytes

Basicamente, uma implementação relativamente direta dos critérios:

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  

Experimente online!

Python, 159 158 153 153 142 142 141 bytes

Salvo um 2 bytes graças a Kritixi Lithos!

Isto é principalmente apenas para praticar golfe no meu Python!
Usou a fórmula dada pelo OP e não as formas de todas as respostas mais inteligentes

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))

APL (Dyalog Extended) , 27 bytes

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

Experimente online!

Uma função diádica tácita cujo argumento esquerdo é ae o direito é b.

A abordagem é quase idêntica à solução Python 2 do xnor , pois convertemos cada número em um array aninhado e fazemos uma comparação lexicográfica entre eles.

Parte 1: Converter número em matriz aninhada

{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]

Parte 2: compare duas matrizes aninhadas

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)

A sintaxe dfn suporta declarações condicionais, por exemplo , {a:x ⋄ b:y ⋄ z}significado if a then x else if b then y else z, mas é muito detalhada para usar neste caso.

05AB1E , 14 bytes

ΣxÓs1ǝzDg≠i(]Q

Experimente online! ou validar todos os casos de teste .