Einführung

In dieser Herausforderung werden wir uns mit einer bestimmten Reihenfolge der positiven ganzen Zahlen befassen. Die Bestellung geht so:

   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

Wir listen zuerst alle ungeraden ganzen Zahlen größer als 1 in aufsteigender Reihenfolge auf. Dann führen wir zwei mal ungerade ganze Zahlen größer als 1, dann 4 - mal, dann 8 mal, und so weiter: für alle k , wir listen 2 ^k mal die ungeraden Zahlen größer als 1 , um aufzusteigen. Schließlich listen wir die Potenzen von zwei in absteigender Reihenfolge auf und enden bei 1. Jede positive ganze Zahl kommt in dieser "Liste" genau einmal vor.

Man betrachte genauer gesagt zwei verschiedene positive ganze Zahlen A = n · 2 ^p und B = m · 2 ^q , wobei n, m ≥ 1 ungerade sind und p, q ≥ 0 . In der Bestellung steht dann A vor B , wenn eine der folgenden Bedingungen zutrifft:

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

Diese Ordnung kommt in dem überraschenden mathematischen Ergebnis vor, das als Sharkovski-Theorem bekannt ist und die periodischen Punkte dynamischer Systeme betrifft. Ich werde hier nicht auf die Details eingehen.

Die Aufgabe

Ihre Aufgabe bei dieser Herausforderung ist es, die obige Bestellung zu berechnen. Ihre Eingaben sind zwei positive ganze Zahlen A und B , die gleich sein können. Ihre Ausgabe ist ein wahrer Wert, wenn A in der Bestellung vor B steht , und ein falscher Wert, wenn nicht. Wenn A = B , sollte Ihre Ausgabe wahr sein. Sie können A und B in beliebiger Reihenfolge nehmen, solange Sie konsistent sind.

Sie müssen sich keine Gedanken über einen Ganzzahlüberlauf machen, aber Ihr Algorithmus sollte theoretisch für beliebig große Eingaben funktionieren.

Testfälle

Wahrheitsinstanzen

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

Falsche Instanzen

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

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)

Dies wird wahrscheinlich keine Größenauszeichnung gewinnen, aber diese Antwort funktioniert durch die Konstruktion eines 3-Tupels unter Verwendung von 3 Ausdrücken aus einer Ganzzahl, die bei lexikographischer Reihenfolge zur korrekten Reihenfolge führt.

In lesbaren Worten ist das Tupel für A = n · 2 ^p :

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

JavaScript (ES6), 53,49 Byte

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

Erläuterung:

• Wenn b 1 ist, dann steht a vor (oder gleich) b
• Wenn andernfalls a 1 ist, dann steht a nicht vor b
• Wenn andernfalls sowohl a als auch b ungerade sind, verwenden Sie die regelmäßige Ungleichheitsprüfung
• Wenn andernfalls a ungerade ist, steht es vor b
• Wenn andernfalls b ungerade ist, steht a nicht vor b
• Teilen Sie andernfalls a und b durch 2 und versuchen Sie es erneut.

Bearbeiten: 2 Bytes dank @Arnauld gespeichert.

Python 2, 50 Bytes

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

Jede Nummer wird einem Tripel zugeordnet, dessen sortierte Reihenfolge die gewünschte Reihenfolge ist.

• Der primäre Wert ist [-n][n&n-1:], der die Potenzen von 2 am Ende behandelt. Das bitweise "und" n&n-1ist genau dann Null, wenn neine Potenz von ist 2. In diesem Fall erhalten wir die Liste [-n]und ansonsten die leere Liste []. Dies setzt alle Potenzen von 2 am Ende der Reihenfolge in absteigender Reihenfolge.
• Der Sekundärwert n&-nextrahiert den Faktor der Zweierpotenz von n.
• Der Endwert ntiebreaks gleich Potenzen von 2 zugunsten der größeren Anzahl.

Die jeweiligen Tupel werden übergeben, cmpum festzustellen, ob dieser Vergleich vorliegt <=0. Python 3 würde ein Byte mit Gleitkommadivision (n&n-1<1)/nfür den ersten Wert im Tripel speichern , aber es fehlt cmp.

JavaScript (ES6), 70 64 Bytes

Könnte wohl noch etwas mehr golfen werden, aber als ersten Versuch:

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

Übernimmt Eingaben mit Curry-Syntax (x)(y). Rückgabe 0/ 1.

Testfälle

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

( Probieren Sie es online. )

Nicht gerade kurz, aber ich dachte, es wäre interessant, eine Lösung zu schreiben, die tatsächlich die Reihenfolge generiert (bis zu einer sicheren Obergrenze für jede Teilsequenz) und dann prüft, welche Eingabe zuerst darin erscheint.

Beispielsweise:

• Für die Eingabe 2, 3generiert es:

  3 5
  6
  12
  4 2 1

  ... und stellt dann fest, dass 3das vorher erscheint 2.

• Für die Eingabe 9, 6generiert es:

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

  ... und stellt dann fest, dass 9das vorher erscheint 6.

Es könnte intelligenter sein und noch weniger von der Sequenz erzeugen, aber das würde mehr Byte Code erfordern.

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]

Eine rekursive Lösung ähnlich der von Neil.

Mathematica, 65 Bytes

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

Unbenannte Funktion, die eine Liste positiver Ganzzahlen aufnimmt und zurückgibt, Truewenn die Liste eine aufsteigende Reihenfolge in der Sharkovskii-Reihenfolge bildet, Falseandernfalls. (Insbesondere muss die Eingabeliste nicht nur zwei Elemente enthalten - wir erhalten die hinzugefügte Funktionalität kostenlos.)

Das Herzstück des Algorithmus ist die Funktion {1,#}&/@#//.{a_,b_/;EvenQ@b}->{2a,b/2}, mit der wiederholt Faktoren von 2 verschoben werden, um eine ganze Zahl der Form m*2^kmit mungeraden Werten in das geordnete Paar {2^k,m}(und damit in jedes Element der Eingabeliste) umzuwandeln . OrderedQentscheidet dann, ob die resultierende Liste geordneter Paare bereits sortiert ist; Standardmäßig bedeutet dies, dass die Reihenfolge um das erste Element und die Reihenfolge um das zweite Element erhöht wird.

Das ist genau das, was wir wollen, außer dass Zahlen, die Potenzen von 2 sind, unterschiedlichen Regeln folgen. Bevor OrderingQwir mit einchecken , wenden wir eine letzte Regel an /.{a_,1}->{∞,-a}, die (zum Beispiel) {64,1}in konvertiert {∞,-64}; das setzt Potenzen von 2 an der richtigen Stelle in der Reihenfolge.

Haskell, 143 138 Bytes

Grundsätzlich eine relativ einfache Umsetzung der Kriterien:

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  

Probieren Sie es online!

Python, 159 158 153 144 142 141 Bytes

Gespeichert eine 2 - Byte dank Kritixi Lithos!

Dies dient hauptsächlich zum Üben des Golfspiels mit meiner Python!
Verwendete die vom OP gegebene Formel und nicht die Art und Weise aller klügeren Antworten

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