The strange ordering of Sharkovskii

Question

Introduction

In this challenge, we will be dealing with a certain ordering of the positive integers. The ordering goes like this:

   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

We first list all odd integers greater than 1 in ascending order. Then we list two times odd integers greater than 1, then 4 times, then 8 times, and so on: for all k, we list 2^k times the odd integers greater than 1 in ascending order. Finally, we list the powers of two in descending order, ending at 1. Every positive integer occurs in this "list" exactly once.

More explicitly, consider two distinct positive integers A = n·2^p and B = m·2^q, where n, m ≥ 1 are odd, and p, q ≥ 0. Then A comes before B in the ordering, if one of the following conditions holds:

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

This ordering appears in the surprising mathematical result known as Sharkovskii's theorem, which concerns the periodic points of dynamical systems. I will not go into the details here.

The task

Your task in this challenge is to compute the above ordering. Your inputs are two positive integers A and B, which may be equal. Your output is a truthy value if A comes before B in the ordering, and a falsy value otherwise. If A = B, your output should be truthy. You can take A and B in either order, as long as you're consistent.

You don't have to worry about integer overflow, but your algorithm should theoretically work for arbitrarily large inputs.

Test cases

Truthy instances

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

Falsy instances

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

Answer 1

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

Explanation:

• If b is 1, then a precedes (or equals) b
• Otherwise, if a is 1, then a does not precede b
• Otherwise, if both a and b are odd, then use regular inequality check
• Otherwise, if a is odd, then it precedes b
• Otherwise, if b is odd, then a does not precede b
• Otherwise, divide both a and b by 2 and try again.

Edit: Saved 2 bytes thanks to @Arnauld.

Answer 2

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)

This probably won't win any size awards, but this answer works by constructing a 3-tuple using 3 expressions from an integer that when lexicographically ordered will result in the correct ordering.

In readable terms, the tuple is for A = n·2^p:

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

Answer 3

Python 2, 50 bytes

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

Each number is mapped to a triple whose sorted order is the desired order.

• The primary value is [-n][n&n-1:], which handles the powers of 2 at the end. The bitwise "and" n&n-1 is zero exactly when n is a power of 2. If so, we get the list [-n], and otherwise the empty list []. This puts all powers of 2 at the end of the order, in decreasing order.
• The secondary value n&-n extracts the power-of-2 factor of n.
• The final value n tiebreaks equal powers of 2 in favor of the greater number.

The respective tuples are passed to cmp to see if that comparison is <=0. Python 3 would save a byte with float division (n&n-1<1)/n for the first value in the triple, but lacks cmp.

Answer 4

JavaScript (ES6), 70 64 bytes

Could probably be golfed some more, but as a first attempt:

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

Takes input with currying syntax (x)(y). Returns 0 / 1.

Test cases

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

Answer 5

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

(Try it online.)

Not exactly short, but I thought it would be interesting to write a solution that actually generates the ordering sequence (up to a safe upper bound for each sub-sequence), and then checks which input appears in it first.

For example:

• For input 2, 3 it generates:

  3 5
  6
  12
  4 2 1

  ...and then observes that 3 appears before 2.

• For input 9, 6 it generates:

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

  ...and then observes that 9 appears before 6.

It could be smarter and generate even less of the sequence, but that would take more bytes of code.

Answer 6

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]

A recursive solution similar to Neil's.

Answer 7

APL (Dyalog Extended), 27 bytes

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

Try it online!

A tacit dyadic function whose left argument is a and the right is b.

The approach is almost identical to xnor's Python 2 solution, in that we convert each number to a nested array and do lexicographical comparison between them.

Part 1: Convert number to nested array

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

Part 2: Compare two nested arrays

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)

The dfn syntax does support conditional statements e.g. {a:x ⋄ b:y ⋄ z} meaning if a then x else if b then y else z, but it's way too verbose to use in this case.

Answer 8

Mathematica, 65 bytes

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

Unnamed function taking a list of positive integers and returning True if the list forms an ascending sequence in the Sharkovskii order, False otherwise. (In particular, the input list doesn't have to have only two elements—we get the added functionality for free.)

The heart of the algorithm is the function {1,#}&/@#//.{a_,b_/;EvenQ@b}->{2a,b/2}, which repeatedly moves factors of 2 around to convert an integer of the form m*2^k, with m odd, to the ordered pair {2^k,m} (and does so to every element of the input list). OrderedQ then decides whether the resulting list of ordered pairs is already sorted; by default, that means in increasing order by the first element, then increasing order by the second element.

That's exactly what we want, except numbers that are powers of 2 follow different rules. So before checking in with OrderingQ, we apply one last rule /.{a_,1}->{∞,-a}, which converts (for example) {64,1} to {∞,-64}; that puts powers of 2 in the correct spot in the ordering.

Answer 9

Haskell, 143 138 bytes

Basically a relatively straightforward implementation of the criteria:

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  

Try it online!

Answer 10

Python, 159 158 153 144 142 141 bytes

Saved a 2 bytes thanks to Kritixi Lithos!

This is mainly just to practice golfing my Python!
Used the formula given by the OP rather than the ways of all the cleverer answers

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

Answer 11

05AB1E, 14 bytes

ΣxÓs1ǝzDg≠i(]Q

Try it online! or validate all test cases.