# Can the number be split into powers of 2?

Yesterday while playing with my kid I noticed the number in his toy train: So we have $$4281$$ that can be split into $$4-2-8-1$$ or $$2^2-2^1-2^3-2^0$$

So simple challenge: given a non-negative number as input, return consistent truthy and falsey values that represent whether or not the string representation of the number (in base 10 and without leading zeroes) can be somehow split into numbers that are powers of 2.

Examples:

4281      truthy (4-2-8-1)
164       truthy (16-4 or 1-64)
8192      truthy (the number itself is a power of 2)
81024     truthy (8-1024 or 8-1-02-4)
101       truthy (1-01)
0         falsey (0 cannot be represented as 2^x for any x)
1         truthy
3         falsey
234789    falsey
256323    falsey (we have 256 and 32 but then 3)
8132      truthy (8-1-32)

Tests for very large numbers (not really necessary to be handled by your code):
81024256641116  truthy (8-1024-256-64-1-1-16)
64512819237913  falsey


This is , so may the shortest code for each language win!

• @StewieGriffin initially I thought about limiting the input number to the range of a standard int type (4 bytes), but actually I do not mind if your code does not support very large numbers. Just state in your answer the limitations of your code. – Charlie Oct 11 '18 at 8:03
• Suggested test case: 101 (falsy because of the 0) ... or should this still be true (1 - 01)? – Shieru Asakoto Oct 11 '18 at 8:17
• @ShieruAsakoto I've been testing the 101 case with the current answers and they all return true, because it can be splitted into 1-01 that are both powers of 2, so I'll consider that case to be truthy. – Charlie Oct 11 '18 at 8:21
• Just leaving this here as tip for everyone. Here are three possible ways to check if a number is a power of 2: 1) Check if log2(n) doesn't contain decimal digits after the comma. 2) Check if n AND (n-1) == 0. 3) Create a list of square-nrs and check if n is in that list. – Kevin Cruijssen Oct 11 '18 at 8:37
• "square-nrs" should be "powers of 2" in my comment above of course.. >.> – Kevin Cruijssen Oct 11 '18 at 14:00

# 05AB1E, 9 8 bytes

Ýos.œåPZ


-1 byte thanks to @Emigna by using Z (max) for the list of 0s and 1s to mimic an any command for 1 (truthy).

Try it online or verify all test cases. (NOTE: The т in the header is 100 to only get the first 100 power of 2 numbers, instead of the first input amount of power of 2 numbers. It works with the input amount of power of 2 as well, but is pretty inefficient and might timeout on TIO if the input is large enough.)

Explanation:

Ý            # Create a list in the range [0,n], where n is the (implicit) input
# (or 100 in the TIO)
#  i.e. 81024 → [0,1,2,3,...,81024]
o           # Raise 2 to the i'th power for each i in the list
#  → [1,2,4,8,...,451..216 (nr with 24391 digits)]
s          # Swap to take the input
.œ        # Create each possible partition of this input
#  i.e. 81024 → [["8","1","0","2","4"],["8","1","0","24"],...,["8102","4"],["81024"]]
å       # Check for each if it's in the list of powers of 2
#  → [[1,1,0,1,1],[1,1,0,0],...,[0,1],]
P      # Check for each inner list whether all are truthy
#  → [0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0]
Z     # Take the maximum (and output implicitly)
#  → 1 (truthy)

• Nice, my solution was .œ.²1%O0å (9 bytes as well). Mine failed 0, however. – Mr. Xcoder Oct 11 '18 at 8:41
• @Mr.Xcoder Ah, .²1%O0 is pretty smart as well. I thought about using log2 like this .²DïQ, but it would require a map around it to do this for each number, and it indeed didn't work for edge-case 0. – Kevin Cruijssen Oct 11 '18 at 9:14

# JavaScript (Node.js), 54 bytes

f=(v,o=10)=>v&v-1|!v?v>o?f(v%o)&f(v/o|0)|f(v,o*10):0:1


Try it online!

# JavaScript (Node.js), 6964 58 bytes

f=(x,m=10,q=!(x%m&x%m-1|!x))=>x<m?q:q&&f(x/m|0)||f(x,10*m)


Try it online!

Input as number. The logic part is quite convoluted, so no idea how to untangle it and get rid of q.

-11 bytes by golfing the power-of-2 check.

# Jelly, 9 bytes

ŒṖḌl2ĊƑ€Ẹ


Check out the test suite!

### Alternative

Doesn't work for the large test cases due to precision issues.

ŒṖḌæḟƑ€2Ẹ


Check out the test suite!

### How?

Program I

ŒṖḌl2ĊƑ€Ẹ     Full program. N = integer input.
ŒṖ            All possible partitions of the digits of N.
Ḍ           Undecimal (i.e. join to numbers).
l2         Log2. Note: returns (-inf+nanj) for 0, so it doesn't fail.
ĊƑ€      For each, check if the logarithm equals its ceil.
Ẹ     Any. Return 0 if there are no truthy elements, 1 otherwise.


Program II

ŒṖḌæḟƑ€2Ẹ     Full program. N = integer input.
ŒṖ            All possible partitions of the digits of N.
Ḍ           Undecimal (i.e. join to numbers).
Ƒ€       For each partition, check whether its elements are invariant under...
æḟ  2      Flooring to the nearest power of 2.
Ẹ     Any. Return 0 if there are no truthy elements, 1 otherwise.


# JavaScript (Node.js), 75 69 bytes

-6 bytes thanks @Arnauld. At most 32-bit support

f=x=>+x?[...x].some((_,i)=>(y=x.slice(0,++i))&~-y?0:f(x.slice(i))):!x


Try it online!

Input as a string.

# Python 2, 72 70 bytes

f=lambda n,m=10:n>=m/10and(n%m&n%m-1<1and(n/m<1or f(n/m))or f(n,m*10))


Try it online!

# JavaScript, 59 bytes

s=>eval(/^(${(g=x=>x>s?1:x+'|0*'+g(x+x))(1)})+$/).test(s)


Try it online!

Builds a regex like /^(1|0*2|0*4|0*8|0*16|0*32|…|0*1)+$/ of powers of 2, and tests it on s. Only works up to the precision of JavaScript numbers, of course: eventually the terms in the regex will look like 1.2345678e30 (or Inf). But since powers of 2 are easy to represent accurately in floating-point, they'll never be wrong integers, which would be more disqualifying, I think. @tsh saved 14 bytes. Neato! • 59 bytes – tsh Oct 12 '18 at 1:39 # Python 2, 85 bytes f=lambda n:bin(int(n)).count('1')==1or any(f(n[:i])*f(n[i:])for i in range(1,len(n)))  Try it online! # Perl 6, 2824 23 bytes -4 bytes thanks to Jo King {?/^[0*@(2 X**^32)]+$/}


Try it online!

Handles powers up to 231.

• 24 bytes by moving the 0* out of the interpolated part – Jo King Oct 23 '18 at 7:45

# APL(NARS), 154 chars, 308 bytes

∇r←f w;g;b;z;k
g←{⍵≤0:1⋄t=⌊t←2⍟⍵}⋄→A×⍳∼w≤9⋄r←g w⋄→0
A: z←w⋄b←0⋄k←1
B: b+←k×10∣z⋄z←⌊z÷10
→C×⍳∼g b⋄r←∇z⋄→0×⍳r
C: k×←10⋄→B×⍳z≠0
r←0
∇
h←{⍵=0:0⋄f ⍵}


The function for the exercise it is h. The algorithm not seems exponential or factorial... test:

  h¨ 4281 164 8192 81024 101
1 1 1 1 1
h¨ 0 1 3 234789 256323 8132
0 1 0 0 0 1
h 81024256641116
1
h 64512819237913
0


# Python 2, 57 bytes

f=lambda n,k=10:k<11*n>n%k&n%k-1<(n<k)|f(n/k)|f(n,10*k)*n


Try it online!

lambda n:re.match('^(%s)*$'%'|'.join('0*'+1<<kfor k in range(n)),n)and 0;import re  Try it online! # Ruby, 55 bytes ->n{a=*b=1;a<<b*=2until b>n;n.to_s=~/^(0*(#{a*?|}))*$/}


Try it online!

Output is 0 if true and nil if false.

->n{n.to_s=~/^(0*(#{(0..n).map{|x|2**x}*?|}))*$/}  Try it online! Only works in theory. Takes forever for large values of n # PHP, 101 bytes Can´t seem to get this below 100; but I could get it to 100 if 101 was a falsy case. function f($s){for($x=.5;$s>=$x*=2;)if(preg_match("/^$x(.*)$/",$s,$m)?!~$m||f(+$m):0)return 1;}  returns $$\NULL\$$ for falsy and $$\1\$$ for truthy. Try it online. variations: for($x=.5;$s>=$x*=2;)
while($s>=$x=1<<$i++) # yields notices "undefined variable$i"

?!~$m||f(+$m):0
?~$m?f(+$m):1:0


# PHP 5 or older, 95 bytes

function f($s){while($s>=$x=1<<$i++)if(ereg("^$x(.*)$",$s,$m)?$m>""?f(+$m):1:0)return 1;}


# Red, 212 211 bytes

func[n][g: func[x][(log-2 do x)% 1 = 0]repeat i 2 **((length? s: form n)- 1)[b: a:
copy[] k: i foreach c s[append b c if k % 2 = 0[alter a g rejoin b
b: copy[]]k: k / 2]append a g form c if all a[return on]]off]


Try it online!

Another long submission, but I'm not comletely dissatisfied, because there is no built-in for finding all substrings in Red.

f: func [ n ] [
g: func [ x ] [ (log-2 do x) % 1 = 0 ]
repeat i 2 ** ((length? s: form n) - 1) [
b: a: copy []
k: i
foreach c s [
append b c
if k % 2 = 0 [
append a g rejoin b
b: copy []
]
k: k / 2
]
append a g form c
if all a[ return on ]
]
off
]


# Axiom, 198 bytes

G(a)==(a<=1=>2>1;x:=log_2 a;x=floor x)
F(n)==(n<=9=>G n;z:=n;b:=0;k:=1;repeat(b:=b+k*(z rem 10);z:=z quo 10;if G b and F z then return 2>1;k:=k*10;z<=0=>break);1>1)
H(n:NNI):Boolean==(n=0=>1>1;F n)


ungolf and test

g(a)==(a<=1=>2>1;x:=log_2 a;x=floor x)
f(n)==
n<=9=>g n
z:=n;b:=0;k:=1
repeat
b:=b+k*(z rem 10);z:=z quo 10;
if g b and f z then return 2>1
k:=k*10
z<=0=>break
1>1
h(n:NNI):Boolean==(n=0=>1>1;f n)

(15) -> [[i,h i] for i in [4281,164,8192,81024,101]]
(15)  [[4281,true],[164,true],[8192,true],[81024,true],[101,true]]
Type: List List Any
(16) -> [[i,h i] for i in [0,1,3,234789,256323,8132]]
(16)  [[0,false],[1,true],[3,false],[234789,false],[256323,false],[8132,true]]
Type: List List Any
(17) -> [[i,h i] for i in [81024256641116, 64512819237913]]
(17)  [[81024256641116,true],[64512819237913,false]]
Type: List List Any
(18) -> h 44444444444444444444444444
(18)  true
Type: Boolean
(19) -> h 44444444444444444128444444444
(19)  true
Type: Boolean
(20) -> h 4444444444444444412825444444444
(20)  false
Type: Boolean
(21) -> h 2222222222222244444444444444444412822222222222210248888888888882048888888888888888
(21)  true
Type: Boolean
(22) -> h 222222222222224444444444444444441282222222222225128888888888882048888888888888888
(22)  true
Type: Boolean


# Powershell, 56 bytes

$x=(0..63|%{1-shl$_})-join'|0*'
"$args"-match"^(0*$x)+$"  Test script: $f = {

$x=(0..63|%{1-shl$_})-join'|0*'
"$args"-match"^(0*$x)+$" } @( ,(4281 ,$true)
,(164             ,$true) ,(8192 ,$true)
,(81024           ,$true) ,(101 ,$true)
,(0               ,$false) ,(1 ,$true)
,(3               ,$false) ,(234789 ,$false)
,(256323          ,$false) ,(8132 ,$true)
,("81024256641116"  ,$true) ,("64512819237913" ,$false)
) | % {
$n,$expected = $_$result = &$f$n
"$($result-eq$expected):$result <- $n" }  Output: True: True <- 4281 True: True <- 164 True: True <- 8192 True: True <- 81024 True: True <- 101 True: False <- 0 True: True <- 1 True: False <- 3 True: False <- 234789 True: False <- 256323 True: True <- 8132 True: True <- 81024256641116 True: False <- 64512819237913  Explanation: Builds a regex like ^(0*1|0*2|0*4|0*8|0*16|0*32|…)+$ of powers of 2, and tests it on arguments.

# Japt -!, 12 bytes

Takes input as a string.

ÊÆòXÄÃex_&ZÉ


Try it

• The 0 case outputs true and hence cases such as 1010 also output true. – Charlie Oct 11 '18 at 13:19

## C# 157 bytes

bool P(string s,int i=1)=>i>=s.Length?((Func<ulong,bool>)((x)=>(x!=0)&&((x&(x-1))==0)))(ulong.Parse(s)):(P(s,i+1)||(P(s.Substring(0,i))&&P(s.Substring(i))));


You can Try it online

# APL(NARS), 70 chars, 140 bytes

P←{k←↑⍴⍵⋄x←11 1‼k k⋄y←⍵⋄∪{x[⍵;]⊂y}¨⍳↑⍴x}
f←{⍵=0:0⋄∨/∧/¨y=⌊y←2⍟⍎¨¨P⍕⍵}


test:

  f¨ 4281 164 8192 81024 101
1 1 1 1 1
f¨ 0 1 3 234789 256323 8132
0 1 0 0 0 1
f 126
0


i not try to do other more big numbers... i have to note that P is not normal partition, but it is one partition where all element are subset that have member all consecutive, for example

  ⎕fmt P 'abc'
┌4──────────────────────────────────────────────────┐
│┌1─────┐ ┌2─────────┐ ┌2─────────┐ ┌3─────────────┐│
││┌3───┐│ │┌2──┐ ┌1─┐│ │┌1─┐ ┌2──┐│ │┌1─┐ ┌1─┐ ┌1─┐││
│││ abc││ ││ ab│ │ c││ ││ a│ │ bc││ ││ a│ │ b│ │ c│││
││└────┘2 │└───┘ └──┘2 │└──┘ └───┘2 │└──┘ └──┘ └──┘2│
│└∊─────┘ └∊─────────┘ └∊─────────┘ └∊─────────────┘3
└∊──────────────────────────────────────────────────┘


note that is absent the element ((ac) (b)) or better ,,¨('ac')'b'

  ⎕fmt ,,¨('ac')'b'
┌2─────────┐
│┌2──┐ ┌1─┐│
││ ac│ │ b││
│└───┘ └──┘2
└∊─────────┘


# POSIX ERE, 91 bytes

(0*(|16|32|64|128|256|512|1024|2048|4096|8192|16384|32768|65536|131072|262144|524288))+


This is totally cheating, based on the text large numbers (not really necessary to be handled by your code) in the question; it handles all values in the size range of the examples. Obviously can be extended up to full range of 32- or 64-bit integer types at the expense of size. I mainly wrote it as a demonstration of how the problem naturally fits the tool. A fun exercise would be rewriting it as a program that generates the ERE for arbitrary range then matches against it.

p,c;f(a,i){c="^(0*(1";for(i=0;i<31;)A"%s|%d",c,1<<++i);A"%s))+$",c);regcomp(&p,c,1);a=!regexec(&p,a,0,0,0);}  Try it online! This builds a regex of the powers of 2 up to 2**32, and then matches the input string against it. # JavaScript (Node.js), 56 bytes f=(x,c=v=1)=>x<v?x.match('^('+c+')+$'):f(x,c+'|'+(v*=2))


Try it online!