Input

Two positive integers a > b

Output

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.

Examples

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.

• What's wrong with 202*1 for the second test case? Does the multiple of 2 need to be smaller than the other part? Commented Aug 6, 2023 at 8:24
• @TheThonnu 202 is greater than b in that case. It has to factorisable into two parts as described in the question
– Simd
Commented Aug 6, 2023 at 8:25
• 202 is the multiple of 2 and 1 is less than b if I'm understanding the question correctly Commented Aug 6, 2023 at 8:26
• There was a typo. It should have said power of two. Thank you for spotting that. Fixed now
– Simd
Commented Aug 6, 2023 at 8:35

JavaScript (ES6), 27 bytes

Expects (b)(a) as either numbers or BigInts (ES11).

b=>g=a=>a/(a&-a)>b?g(-~a):a


Try it online!

How?

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.

05AB1E (legacy), 8 bytes

L/.²îoƶß


Try it online!

05AB1E, 9 bytes

L/.²îïoƶß


Try it online!

ï is now needed due to a bug, since o takes forever without it.

Explanation

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


Thunno 2M, 9 bytes

R/Æḷ€ṃOż×


Try it online!

Port of Command Master's 05AB1E answer.

Explanation

R/Æḷ€ṃOż×  # Implicit input
R/         # Divide b by [1..a]
Æḷ       # Log base 2 of each
€ṃ     # Ceiling of each
O    # Two power of each
ż×  # Multiply by index
# Take the minimum
# Implicit output


Scala, 38 37 bytes

Saved 1 byte thanks to the comment of @xnor

Try it online!

(b,a)=>if((a/(-a&a))>b)f(b,a+1)else a

• It looks like you can write (-a&a)
– xnor
Commented Aug 6, 2023 at 18:30

JavaScript, 46 bytes

o=a=>a&1n?a:o(a/2n)
f=(a,b)=>o(a)<b?a:f(++a,b)


takes big integers as Input

Attempt This Online!

Explanation

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

Charcoal, 21 bytes

Ｎθ≔±Ｘ²Ｌ↨⊕÷θ±Ｎ²ζＩ×ζ÷θζ


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.

Jelly, 9 bytes

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.

Try it online!

How?

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.

Nekomata + -1, 7 bytes

Ň+ᵖ{ʷ½≥


Attempt This Online!

Ň+ᵖ{ʷ½≥
Ň           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.

Vyxalg, 57 bitsv2, 7.125 bytes

ɾ/2•⌈EÞż


Try it Online!

C89, 36 bytes

port of Arnauld's JavaScript (ES6) answer.

f(a,b){return(a&-a)*b<a?f(a+1,b):a;}


Try it online!

C (gcc), 30 bytes

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


Try it online!

Desmos, 41 bytes

f(a,b)=min(2^{ceil(log_2a/L)}L)
L=[1...b]


Try It On Desmos!

Try It On Desmos! - Prettified

Port of 05AB1E