Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It only takes a minute to sign up.
Sign up to join this community
Two positive integers a > b
The smallest integer c >= a so that c can be factored into two parts with one part an integer power of two (that is at least two) and the other part no larger than b.
If b = 100 and a = 101 , then the output should be 102 as 102 is 2 times 51.
For the same b, if a = 201 then the output should be 204 as that equals 4 times 51.
For the same b, if a = 256 then the output should be 256.
Expects (b)(a) as either numbers or BigInts (ES11).
b=>g=a=>a/(a&-a)>b?g(-~a):a
We recursively increment a while a / (a & -a) is greater than b.
The bitwise trick a & -a isolates the least significant 1 in the binary representation of a, i.e. the largest divisor or a which is a power of 2.
L/.²îoƶß
L/.²îïoƶß
ï is now needed due to a bug, since o takes forever without it.
Goes over all possible values \$d\$ in \$c = d 2^s\$, by looking at the first power of \$2\$ which is \$\geq \lceil \frac a d \rceil\$.
L range [1, 2, 3, ..., b]
/ [a/1, a/2, a/3, ..., a/b]
.² [log2(a/1), log2(a/2), ..., log2(a/b)]
î [ceil(log2(a/1)), ceil(log2(a/2)), ..., ceil(log2(a/b))]
o [2^ceil(log2(a/1)), 2^ceil(log2(a/2)), ..., 2^ceil(log2(a/b))]
ƶ [1*2^ceil(log2(a/1)), 2*2^ceil(log2(a/2)), ..., b*2^ceil(log2(a/b))]
ß min([1*2^ceil(log2(a/1)), 2*2^ceil(log2(a/2)), ..., b*2^ceil(log2(a/b))])
Saved 1 byte thanks to the comment of @xnor
(b,a)=>if((a/(-a&a))>b)f(b,a+1)else a
o=a=>a&1n?a:o(a/2n)
f=(a,b)=>o(a)<b?a:f(++a,b)
takes big integers as Input
o gets the odd part of a number (product of all odd prime factors)
f increments a until its odd part is less than b
Ｎθ≔±Ｘ²Ｌ↨⊕÷θ±Ｎ²ζＩ×ζ÷θζ
Try it online! Link is to verbose version of code. Explanation:
Ｎθ
Input a.
≔±Ｘ²Ｌ↨⊕÷θ±Ｎ²ζ
Calculate the smallest power of 2 not less than a/b.
Ｉ×ζ÷θζ
Round a up to that power of 2.
Họ¡2’<ð1#
A dyadic Link that accepts \$a\$ on the left and \$b\$ on the right and yields \$c\$ as a singleton list. Alternatively, a full program that prints the result.
Họ¡2’<ð1# - Link: integer, a; integer b
1# - starting at k=a and incrementing find the first k for which:
ð - dyadic chain - f(k, b):
¡ - repeat...
ọ 2 - ...times: order-multiplicity 2
H - ...action: halve
-> divides k by two until we have an odd number
’ - decrement
< - is less than {b}? (i.e. k <= b ?)
Same method Bt0Ḅ’<ð1# or BTṬḄ’<ð1# - remove trailing zeros from the binary representation and convert back.
-1, 7 bytesŇ+ᵖ{ʷ½≥
Ň+ᵖ{ʷ½≥
Ň Find a natural number
+ Plus the first input
ᵖ{ Check that:
ʷ½ Repeatedly divide by 2 until the number is odd
≥ The second input is greater than or equal to the result
-1 prints the first solution.
port of Arnauld's JavaScript (ES6) answer.
f(a,b){return(a&-a)*b<a?f(a+1,b):a;}
ommiting the return statement and the unchanged trailling parameter in the recursive call
f(a,b){a=(a&-a)*b<a?f(a+1):a;}
f(a,b)=min(2^{ceil(log_2a/L)}L)
L=[1...b]
Try It On Desmos! - Prettified
Port of 05AB1E
