El extraño orden de Sharkovskii

35

Introducción

En este desafío, trataremos con un cierto orden de los enteros positivos. El pedido es así:

   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

Primero enumeramos todos los enteros impares mayores que 1 en orden ascendente. Luego enumeramos dos veces enteros impares mayores que 1, luego 4 veces, luego 8 veces, y así sucesivamente: para todos los k , enumeramos 2 k veces los enteros impares mayores que 1 en orden ascendente. Finalmente, enumeramos las potencias de dos en orden descendente , terminando en 1. Cada entero positivo ocurre en esta "lista" exactamente una vez.

Más explícitamente, considere dos enteros positivos distintos A = n · 2 p y B = m · 2 q , donde n, m ≥ 1 son impares, y p, q ≥ 0 . Entonces A viene antes que B en el orden, si se cumple una de las siguientes condiciones:

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

Este orden aparece en el sorprendente resultado matemático conocido como el teorema de Sharkovskii , que se refiere a los puntos periódicos de los sistemas dinámicos. No entraré en detalles aquí.

La tarea

Su tarea en este desafío es calcular el orden anterior. Sus entradas son dos enteros positivos A y B , que pueden ser iguales. Su salida es un valor verdadero si A viene antes que B en el orden, y un valor falso de lo contrario. Si A = B , su salida debería ser veraz. Puede tomar A y B en cualquier orden, siempre que sea consistente.

No tiene que preocuparse por el desbordamiento de enteros, pero su algoritmo debería funcionar teóricamente para entradas arbitrariamente grandes.

Casos de prueba

Instancias de verdad

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

Instancias falsas

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

Respuestas:

6

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

Explicación:

  • Si b es 1, entonces a precede (o es igual) b
  • De lo contrario, si a es 1, entonces a no precede a b
  • De lo contrario, si tanto a como b son impares, use una verificación de desigualdad regular
  • De lo contrario, si a es impar, entonces precede a b
  • De lo contrario, si b es impar, entonces a no precede a b
  • De lo contrario, divida a y b entre 2 e intente nuevamente.

Editar: Guardado 2 bytes gracias a @Arnauld.

Neil
fuente
Agradable. No pensé en usar la recursividad aquí. Funcionaria a&1|~b&1&f(a/2,b/2)?
Arnauld
@Arnauld No estoy seguro, estaba preocupado de que se repita indefinidamente.
Neil
No puede porque b<2eventualmente será cierto. Ahora, otro problema es que procesará más iteraciones de las necesarias y obtendrá valores de coma flotante. Pero no puedo encontrar ningún contraejemplo que no funcione como se esperaba.
Arnauld
@Arnauld Ah, cierto, no estaba usando b<2originalmente, pero supongo que funcionará ahora.
Neil
@Arnauld Mejor aún, ya que f(a/2,b/2)sólo devuelve 0, 1, falseo true, no necesita ni siquiera el &1.
Neil
6

Python 2, 50 bytes

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

Cada número se asigna a un triple cuyo orden ordenado es el orden deseado.

  • El valor primario es [-n][n&n-1:], que maneja las potencias de 2 al final. El bit "y" n&n-1es cero exactamente cuando nes una potencia de 2. Si es así, obtenemos la lista [-n]y, de lo contrario, la lista vacía []. Esto pone todas las potencias de 2 al final del orden, en orden decreciente.
  • El valor secundario n&-nextrae el factor de potencia de 2 de n.
  • El valor final ndesempata iguala las potencias de 2 a favor del mayor número.

Las tuplas respectivas se pasan a cmppara ver si esa comparación es <=0. Python 3 ahorraría un byte con división flotante (n&n-1<1)/npara el primer valor en el triple, pero falta cmp.

xnor
fuente
¿No es cmp(...)<=0equivalente a cmp(...)<1?
Mathmandan
@mathmandan Sí :)
xnor
Creo que está permitido tomar los enteros en orden inverso y usarlos en ~lugar de<1
Mitch Schwartz
5

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)

Esto probablemente no gane premios de ningún tamaño, pero esta respuesta funciona construyendo una tupla de 3 usando 3 expresiones de un número entero que cuando se ordena lexicográficamente dará como resultado el orden correcto.

En términos legibles, la tupla es para A = n · 2 p :

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

JavaScript (ES6), 70 64 bytes

Probablemente podría jugar un poco más, pero como primer intento:

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

Toma entrada con la sintaxis de curry (x)(y). Devoluciones 0/ 1.

Casos de prueba

Arnauld
fuente
Puede quitar los corchetes por dentro y por dentro b>a||(b==a&&y>=x), no hará una diferencia en la ejecución.
XavCo7
@ XavCo7 Está bien quitar los corchetes dentro pero no alrededor. Todos los casos de prueba existentes aún pasarían, pero una entrada como la [1, 5]que se identifica incorrectamente como verdadera.
Arnauld
1
@Arnauld Agregaré eso como un nuevo caso de prueba para el futuro.
Zgarb
3

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

( Pruébelo en línea )

No es exactamente breve, pero pensé que sería interesante escribir una solución que realmente genere la secuencia de pedido (hasta un límite superior seguro para cada subsecuencia), y luego verifica qué entrada aparece primero.

Por ejemplo:

  • Para la entrada 2, 3genera:

    3 5
    6 6
    12
    4 2 1
    ... y luego observa que 3aparece antes 2.

  • Para la entrada 9, 6genera:

    3 5 7 9 11
    6 10
    12
    24
    48
    16 8 4 2 1
    ... y luego observa que 9aparece antes 6.

Podría ser más inteligente y generar aún menos secuencia, pero eso requeriría más bytes de código.

smls
fuente
2

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]

Una solución recursiva similar a la de Neil.

orlp
fuente
Esto parece estropear algunos casos de prueba. Dice que f(158,158)es falso y f(2,8)es verdadero.
xnor
@xnor Vaya, debería arreglarse ahora.
orlp
Esto dice que f(1,5)es falso.
xnor
Lo malo, quise decir que f(1,5)debería ser Falso, pero el código da Verdadero.
xnor
@xnor Ah, vi el error, solucionado ahora (para bien, espero). Seguí la descripción de Neil con demasiada soltura.
orlp
1

Mathematica, 65 bytes

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

Función sin nombre que toma una lista de enteros positivos y regresa Truesi la lista forma una secuencia ascendente en el orden Sharkovskii, de lo Falsecontrario. (En particular, la lista de entrada no tiene que tener solo dos elementos: obtenemos la funcionalidad adicional de forma gratuita).

El corazón del algoritmo es la función {1,#}&/@#//.{a_,b_/;EvenQ@b}->{2a,b/2}, que mueve repetidamente factores de 2 para convertir un entero de la forma m*2^k, con mimpar, en el par ordenado {2^k,m}(y lo hace para cada elemento de la lista de entrada). OrderedQluego decide si la lista resultante de pares ordenados ya está ordenada; por defecto, eso significa en orden creciente por el primer elemento, luego en orden creciente por el segundo elemento.

Eso es exactamente lo que queremos, excepto que los números que son potencias de 2 siguen reglas diferentes. Entonces, antes de registrarnos OrderingQ, aplicamos una última regla /.{a_,1}->{∞,-a}, que convierte (por ejemplo) {64,1}a {∞,-64}; eso pone potencias de 2 en el lugar correcto en el orden.

Greg Martin
fuente
1

APL (Dyalog Extended) , 27 bytes

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

Pruébalo en línea!

Una función diádica tácita cuyo argumento izquierdo es ay el derecho es b.

El enfoque es casi idéntico a la solución Python 2 de xnor , ya que convertimos cada número en una matriz anidada y hacemos una comparación lexicográfica entre ellos.

Parte 1: Convertir número a matriz anidada

{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: compara dos matrices anidadas

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)

La sintaxis dfn admite declaraciones condicionales, por ejemplo , {a:x ⋄ b:y ⋄ z}significado if a then x else if b then y else z, pero es demasiado detallada para usar en este caso.

Bubbler
fuente
0

Haskell, 143 138 bytes

Básicamente, una implementación relativamente sencilla de los criterios:

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  

Pruébalo en línea!

falla
fuente
0

Python, 159 158 153 144 142 141 bytes

Guardado de un 2 bytes gracias a Kritixi Lithos!

¡Esto es principalmente para practicar golf en mi Python!
Usó la fórmula dada por el OP en lugar de las formas de todas las respuestas más 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))
Fideos9
fuente
Puede jugar golf eliminando los espacios innecesarios: por ejemplo, en (a, b)la segunda línea, donde puede eliminar el espacio entre la coma y b.
Kritixi Lithos