Yesterday while playing with my kid I noticed the number in his toy train:

4281

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!

  • 2
    @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 at 8:03
  • 3
    Suggested test case: 101 (falsy because of the 0) ... or should this still be true (1 - 01)? – Shieru Asakoto Oct 11 at 8:17
  • 1
    @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 at 8:21
  • 5
    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 at 8:37
  • 1
    "square-nrs" should be "powers of 2" in my comment above of course.. >.> – Kevin Cruijssen Oct 11 at 14:00

23 Answers 23

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],[0]]
      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)
  • 2
    Nice, my solution was .œ.²1%O0å (9 bytes as well). Mine failed 0, however. – Mr. Xcoder Oct 11 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 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), 69 64 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.

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.

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.

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!

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, 28 24 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 11 hours ago

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!

perl -pE, 41 bytes

$"="|";say/^(0*(@{[map 1<<$_,0..99]}))+$/

This will read a number from STDIN, and print 'something' for matching numbers, and an empty line for non matching numbers. (That 'something' is twice the last power of 2 in the string, proceeded by any leading zeros). Will do any length numbers, as long as the powers of 2 are \$2^{99} = 633825300114114700748351602688\$ or less. (This can easily be increased to \$2^{999}\$ by using an extra byte).

  • I am sneakily assuming you're using a Perl which can handle 128 bit integers (to deal with 1 << 99) – Abigail Oct 11 at 21:52
  • 1
    I think you could even add -Mbigint without affecting your score if anyone raises concerns! – Dom Hastings Oct 12 at 6:12

Python 2, 86 bytes

lambda n:re.match('^(%s)*$'%'|'.join('0*'+`1<<k`for 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.

Ruby, 49 bytes

->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[1]||f(+$m[1]):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[1]||f(+$m[1]):0
?~$m[1]?f(+$m[1]):1:0

PHP 5 or older, 95 bytes

function f($s){while($s>=$x=1<<$i++)if(ereg("^$x(.*)$",$s,$m)?$m[1]>""?f(+$m[1]):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.

More readable:

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

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 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*([1248]|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.

JavaScript (Node.js), 56 bytes

f=(x,c=v=1)=>x<v?x.match('^('+c+')+$'):f(x,c+'|'+(v*=2))

Try it online!

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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