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\$
  • \$\begingroup\$ Nice. I didn't think about using recursion here. Would a&1|~b&1&f(a/2,b/2) work? \$\endgroup\$ – Arnauld Dec 20 '16 at 17:02
  • \$\begingroup\$ @Arnauld I'm not sure, I was worried that it would loop indefinitely. \$\endgroup\$ – Neil Dec 20 '16 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 Dec 20 '16 at 17:24
  • \$\begingroup\$ @Arnauld Ah, right, I wasn't using b<2 originally, but I guess it will work now. \$\endgroup\$ – Neil Dec 20 '16 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 Dec 20 '16 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\$
  • \$\begingroup\$ Isn't cmp(...)<=0 equivalent to cmp(...)<1? \$\endgroup\$ – mathmandan Dec 21 '16 at 16:13
  • \$\begingroup\$ @mathmandan Yes :) \$\endgroup\$ – xnor Dec 22 '16 at 4:39
  • \$\begingroup\$ I think it's permissible to take the integers in reverse order and use ~ instead of <1 \$\endgroup\$ – Mitch Schwartz Dec 22 '16 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\$
  • \$\begingroup\$ You can take out the brackets around and inside b>a||(b==a&&y>=x), won't make a difference to execution. \$\endgroup\$ – XavCo7 Dec 20 '16 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 Dec 20 '16 at 14:57
  • 1
    \$\begingroup\$ @Arnauld I'll add that as a new test case for the future. \$\endgroup\$ – Zgarb Dec 20 '16 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\$
  • \$\begingroup\$ This seems to mess up some test cases. It says f(158,158) is False and f(2,8) is True. \$\endgroup\$ – xnor Dec 20 '16 at 23:08
  • \$\begingroup\$ @xnor Oops, should be fixed now. \$\endgroup\$ – orlp Dec 20 '16 at 23:32
  • \$\begingroup\$ This says f(1,5) is False. \$\endgroup\$ – xnor Dec 20 '16 at 23:53
  • \$\begingroup\$ My bad, I meant that f(1,5) should be False, but the code gives True. \$\endgroup\$ – xnor Dec 21 '16 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 Dec 21 '16 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\$
  • \$\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\$ – Kritixi Lithos Dec 23 '16 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, privacy policy and cookie policy

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