소개

이 과제에서 우리는 양의 정수의 특정 순서를 다룰 것입니다. 순서는 다음과 같습니다.

   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

먼저 1보다 큰 모든 홀수를 오름차순으로 나열합니다. 모든 경우 : 다음 우리는 1보다 큰 정수 홀수 개의 시간 후, 4 배, 8 배 등 나열 K 우리 나열 2 ^유전율 승순 1 배 이상 홀수 정수를 더. 마지막으로, 우리는 2의 거듭 제곱을 내림차순으로 나열하고 1로 끝납니다. 모든 양의 정수는이 “목록”에서 정확히 한 번 발생합니다.

더 명확하게, 두 개의 양의 정수 A = n · 2 ^p 및 B = m · 2 ^{q를 고려하십시오} . 여기서 n, m ≥ 1 은 홀수이고 p, q ≥ 0 입니다. 그리고 A는 앞에 오는 B 다음 조건 중 하나가 보유하고있는 경우, 순서에 :

• n> 1 , m> 1 및 p <q
• 1 <n <m 및 p = q
• n> m = 1
• n = m = 1 이고 p> q

이 순서 는 동적 시스템의주기적인 점에 관한 Sharkovskii의 정리 로 알려진 놀라운 수학적 결과에 나타납니다 . 여기에 대해서는 자세히 설명하지 않겠습니다.

작업

이 과제의 임무는 위의 순서를 계산하는 것입니다. 입력 값은 양의 정수 A 와 B 두 개 이며 같을 수 있습니다. 순서대로 A 가 B 보다 앞에 오면 출력값이 참 값이고 , 그렇지 않으면 거짓 값입니다. A = B 인 경우 출력은 진실해야합니다. 일관된 한 A 와 B 를 어느 순서 로나 취할 수 있습니다 .

정수 오버플로에 대해 걱정할 필요는 없지만 이론적으로 알고리즘은 임의로 큰 입력에 작동해야합니다.

테스트 사례

진실한 사례

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

거짓 인스턴스

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

답변

k=lambda n:[n&~-n<1,(n&-n)*cmp(n&~-n,1),n/(n&-n)]
lambda a,b:k(a)<=k(b)

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

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

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

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

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

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

f=lambda a,b:b<2or[f(a/2,b/2),a>1,0,1<a<=b][a%2+b%2*2]

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