Ayer, mientras jugaba con mi hijo, noté el número en su tren de juguete:

Entonces tenemos que se pueden dividir en o 2 ^ 2-2 ^ 1-2 ^ 3-2 ^ 0

Desafío tan simple: dado un número no negativo como entrada, devuelve valores de verdad y falsey consistentes que representan si la representación de cadena del número (en base 10 y sin ceros a la izquierda) se puede dividir de alguna manera en números que son potencias de 2 .

Ejemplos:

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

Este es el código de golf , ¡así que puede ganar el código más corto para cada idioma!

05AB1E , 9 8 bytes

Ýos.œåPZ

-1 byte gracias a @Emigna usando Z(max) para la lista de 0s y 1s para imitar un anycomando para 1(verdadero).

Pruébelo en línea o verifique todos los casos de prueba . (NOTA: El тencabezado es 100solo para obtener la primera potencia de 100 números de 2, en lugar de la primera cantidad de potencia de entrada de 2 números. Funciona también con la cantidad de potencia de entrada de 2, pero es bastante ineficiente y podría tiempo de espera en TIO si la entrada es lo suficientemente grande).

Explicación:

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

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

Pruébalo en línea!

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)

Pruébalo en línea!

Ingresar como número. La parte lógica es bastante complicada, así que no tengo idea de cómo desenredarla y deshacerla q.

-11 bytes jugando al golf el cheque de potencia de 2.

JavaScript (Node.js) , 75 69 bytes

-6 bytes gracias @Arnauld. Como máximo, soporte de 32 bits

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

Pruébalo en línea!

Entrada como una cadena.

Jalea , 9 bytes

ŒṖḌl2ĊƑ€Ẹ

¡Mira el paquete de prueba!

Alternativa

No funciona para los casos de prueba grandes debido a problemas de precisión.

ŒṖḌæḟƑ€2Ẹ

¡Mira el paquete de prueba!

¿Cómo?

Programa 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.

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

Pruébalo en línea!

JavaScript, 59 bytes

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

Pruébalo en línea!

Crea una expresión regular /^(1|0*2|0*4|0*8|0*16|0*32|…|0*1)+$/de poderes de 2 y la prueba s.

Por supuesto, solo funciona con la precisión de los números de JavaScript: eventualmente, los términos en la expresión regular se verán como 1.2345678e30(o Inf). Pero dado que los poderes de 2 son fáciles de representar con precisión en coma flotante, nunca serán enteros incorrectos , lo que sería más descalificador, creo.

@tsh guardó 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)))

Pruébalo en línea!

Perl 6 , 28 24 23 bytes

-4 bytes gracias a Jo King

{?/^[0*@(2 X**^32)]+$/}

Pruébalo en línea!

Maneja potencias hasta 2 ³¹ .

APL (NARS), 154 caracteres, 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 ⍵}

La función para el ejercicio es h. El algoritmo no parece exponencial o factorial ... prueba:

  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

Pruébalo en línea!

Python 2 , 86 bytes

lambda n:re.match('^(%s)*$'%'|'.join('0*'+`1<<k`for k in range(n)),`n`)and 0;import re

Pruébalo en línea!

Ruby , 55 bytes

->n{a=*b=1;a<<b*=2until b>n;n.to_s=~/^(0*(#{a*?|}))*$/}

Pruébalo en línea!

La salida es 0si es verdadera y nilsi es falsa.

Ruby , 49 bytes

->n{n.to_s=~/^(0*(#{(0..n).map{|x|2**x}*?|}))*$/}

Pruébalo en línea!

Solo funciona en teoría. Toma para siempre grandes valores den

PHP, 101 bytes

Parece que no puedo conseguir esto por debajo de 100; pero podría llegar a 100 si 101fuera un caso falso.

function f($s){for($x=.5;$s>=$x*=2;)if(preg_match("/^$x(.*)$/",$s,$m)?!~$m[1]||f(+$m[1]):0)return 1;}

$NULL$$1$

variaciones:

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 o anterior, 95 bytes

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

Rojo , 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]

Pruébalo en línea!

Otra presentación larga, pero no estoy completamente insatisfecho, porque no hay una función integrada para encontrar todas las subcadenas en rojo.

Más legible:

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
]

Axioma, 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 y prueba

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

Toma la entrada como una cadena.

ÊÆòXÄÃex_&ZÉ

Intentalo

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

Puedes probarlo en línea

APL (NARS), 70 caracteres, 140 bytes

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

prueba:

  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

No trato de hacer otros números más grandes ... Tengo que tener en cuenta que P no es una partición normal, pero es una partición donde todos los elementos están subconjuntos que tienen miembros todos consecutivos, por ejemplo

  ⎕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
└∊──────────────────────────────────────────────────┘

tenga en cuenta que está ausente el elemento ((ac) (b)) o mejor ,, ¨ ('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))+

Esto es una trampa total, basada en los números grandes de texto (realmente no es necesario que su código los maneje) en la pregunta; maneja todos los valores en el rango de tamaño de los ejemplos. Obviamente se puede extender hasta el rango completo de tipos enteros de 32 o 64 bits a expensas del tamaño. Lo escribí principalmente como una demostración de cómo el problema encaja naturalmente en la herramienta. Un ejercicio divertido sería reescribirlo como un programa que genera el ERE para un rango arbitrario y luego coincide con él.

C (gcc) , -DA=asprintf(&c,+ 108 = 124 bytes

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

Pruébalo en línea!

Esto genera una expresión regular de las potencias de 2 hasta 2 ** 32, y luego hace coincidir la cadena de entrada con ella.

Powershell, 56 bytes

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

Script de prueba:

$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"
}

Salida:

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

Explicación:

Construye una expresión regular como ^(0*1|0*2|0*4|0*8|0*16|0*32|…)+$de potencias de 2, y la prueba con argumentos.

JavaScript (Node.js) , 56 bytes

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

Pruébalo en línea!