37
\$\begingroup\$

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 2k 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·2p and B = m·2q, 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
\$\endgroup\$

11 Answers 11

7
\$\begingroup\$

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.

\$\endgroup\$
5
  • \$\begingroup\$ Nice. I didn't think about using recursion here. Would a&1|~b&1&f(a/2,b/2) work? \$\endgroup\$
    – Arnauld
    Commented Dec 20, 2016 at 17:02
  • \$\begingroup\$ @Arnauld I'm not sure, I was worried that it would loop indefinitely. \$\endgroup\$
    – Neil
    Commented Dec 20, 2016 at 17:07
  • \$\begingroup\$ It can't because b<2 will eventually be true. Now, another problem is that you'll process more iterations than needed and get floating point values. But I can't find any counterexample that would not work as expected. \$\endgroup\$
    – Arnauld
    Commented Dec 20, 2016 at 17:24
  • \$\begingroup\$ @Arnauld Ah, right, I wasn't using b<2 originally, but I guess it will work now. \$\endgroup\$
    – Neil
    Commented Dec 20, 2016 at 19:35
  • \$\begingroup\$ @Arnauld Better still, since f(a/2,b/2) only returns 0, 1, false or true, I don't even need the &1. \$\endgroup\$
    – Neil
    Commented Dec 20, 2016 at 21:49
6
\$\begingroup\$

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·2p:

[n == 0, p * (1 - 2*(n == 0)), n]
\$\endgroup\$
6
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ Isn't cmp(...)<=0 equivalent to cmp(...)<1? \$\endgroup\$
    – mathmandan
    Commented Dec 21, 2016 at 16:13
  • \$\begingroup\$ @mathmandan Yes :) \$\endgroup\$
    – xnor
    Commented Dec 22, 2016 at 4:39
  • \$\begingroup\$ I think it's permissible to take the integers in reverse order and use ~ instead of <1 \$\endgroup\$ Commented Dec 22, 2016 at 7:03
4
\$\begingroup\$

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

\$\endgroup\$
3
  • \$\begingroup\$ You can take out the brackets around and inside b>a||(b==a&&y>=x), won't make a difference to execution. \$\endgroup\$
    – user62802
    Commented Dec 20, 2016 at 14:41
  • \$\begingroup\$ @XavCo7 It's OK to remove the brackets inside but not around. All existing test cases would still pass, but an input such as [1, 5] would be incorrectly identified as truthy. \$\endgroup\$
    – Arnauld
    Commented Dec 20, 2016 at 14:57
  • 1
    \$\begingroup\$ @Arnauld I'll add that as a new test case for the future. \$\endgroup\$
    – Zgarb
    Commented Dec 20, 2016 at 15:08
3
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
5
  • \$\begingroup\$ This seems to mess up some test cases. It says f(158,158) is False and f(2,8) is True. \$\endgroup\$
    – xnor
    Commented Dec 20, 2016 at 23:08
  • \$\begingroup\$ @xnor Oops, should be fixed now. \$\endgroup\$
    – orlp
    Commented Dec 20, 2016 at 23:32
  • \$\begingroup\$ This says f(1,5) is False. \$\endgroup\$
    – xnor
    Commented Dec 20, 2016 at 23:53
  • \$\begingroup\$ My bad, I meant that f(1,5) should be False, but the code gives True. \$\endgroup\$
    – xnor
    Commented Dec 21, 2016 at 0:03
  • \$\begingroup\$ @xnor Ah, I spotted the bug, fixed now (for good I hope). I went about following Neil's description a bit too loosely. \$\endgroup\$
    – orlp
    Commented Dec 21, 2016 at 0:08
2
+200
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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))
\$\endgroup\$
1
  • \$\begingroup\$ You can golf it by removing the unnecessary spaces: for example in (a, b) on the second line where you can remove the space between the comma and b. \$\endgroup\$
    – user41805
    Commented Dec 23, 2016 at 13:06
0
\$\begingroup\$

05AB1E, 14 bytes

ΣxÓs1ǝzDg≠i(]Q

Try it online! or validate all test cases.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.