Ya hemos definido un número plegable aquí .

Pero ahora vamos a definir un Número Super Plegable. Un número Super Plegable es un número que, si se pliega suficientes veces, eventualmente alcanzará uno menos que una potencia de dos. El método de plegado es ligeramente diferente al de la pregunta de número de plegado.

El algoritmo de plegado es el siguiente:

• Toma la representación binaria

  por ejemplo 5882

  1011011111010
  

• Se derramó en tres particiones. Primera mitad, última mitad y medio dígito (si tiene un número impar de dígitos)

  101101 1 111010
  

• Si el dígito del medio es cero, este número no se puede plegar

• Invierta la segunda mitad y superpuesta en la primera mitad

  010111
  101101
  

• Agrega los dígitos en su lugar

  111212
  

• Si hay 2 en el resultado, el número no se puede plegar; de lo contrario, el nuevo número es el resultado del algoritmo de plegado.

Un número es un número Super Plegable si se puede plegar en una cadena continua de unos. (Todos los números plegables también son números súper plegables)

Su tarea es escribir código que tome un número y genere un valor verdadero si el número es un número Super Plegable y falso de lo contrario. Se le puntuará según el tamaño de su programa.

Ejemplos

5200

Convierte a binario:

1010001010000

Partir a la mitad:

101000 1 010000

El medio es uno, así que continuamos Superponiendo las mitades:

000010
101000

Los agregó:

101010

No hay dos, así que continuamos Split por la mitad:

101 010

Doblez:

010
101

111

El resultado es 111(7 en decimal), por lo que este es un Número Super Plegable.

Casos de prueba

Los primeros 100 números super plegables son:

[1, 2, 3, 6, 7, 8, 10, 12, 15, 20, 22, 28, 31, 34, 38, 42, 48, 52, 56, 63, 74, 78, 90, 104, 108, 120, 127, 128, 130, 132, 142, 150, 160, 170, 178, 192, 204, 212, 232, 240, 255, 272, 274, 276, 286, 310, 336, 346, 370, 400, 412, 436, 472, 496, 511, 516, 518, 524, 542, 558, 580, 598, 614, 640, 642, 648, 666, 682, 704, 722, 738, 772, 796, 812, 852, 868, 896, 920, 936, 976, 992, 1023, 1060, 1062, 1068, 1086, 1134, 1188, 1206, 1254, 1312, 1314, 1320, 1338, 1386, 1440, 1458, 1506, 1572, 1596]

Aquí está mi primer tiro en el golf de código:

Python 3, 167 bytes

167 bytes si se usan tabulaciones o espacios individuales para la sangría

def f(n):
 B=bin(n)[2:];L=len(B);M=L//2
 if'1'*L==B:return 1
 S=str(int(B[:M])+int(B[:-M-1:-1]))
 return 0if(~L%2==0and'0'==B[M])or'2'in S else{S}=={'1'}or f(int(S,2))

Editar: ¡Gracias a la ayuda de todos a continuación, el código anterior se ha reducido de un tamaño original de 232 bytes!

Java 7, 202 bytes

boolean g(Integer a){byte[]b=a.toString(a,2).getBytes();int i=0,l=b.length,o=0,c,z=(a+1&a)==0?-1:1;for(;i<l/2&z>0;o+=o+c*2,z*=c>1|(l%2>0&b[l/2]<49)?0:1)c=b[i]+b[l-++i]-96;return z<0?1>0:z<1?0>1:g(o/2);}

Hizo falta un poco de esfuerzo para hacer que la antigua función de plegado sea recurrente, pero aquí está. Es feo como el pecado, para ser honesto. Tendré que echar un vistazo por la mañana para ver si puedo seguir jugando al golf, ya que apenas puedo soportar mirarlo en este momento.

Con saltos de línea:

boolean g(Integer a){
    byte[]b=a.toString(a,2).getBytes();
    int i=0,l=b.length,o=0,c,z=(a+1&a)==0?-1:1;
    for(;i<l/2&z>0;o+=o+c*2,z*=c>1|(l%2>0&b[l/2]<49)?0:1)
        c=b[i]+b[l-++i]-96;
    return z<0?1>0:z<1?0>1:g(o/2);
}

CJam , 47 44 bytes

ri2b{_W%.+__0e=)\_,1>\0-X+:*3<*&}{_,2/<}w2-!

Pruébalo en línea! o generar una lista de números súper plegables hasta un número dado.
Los intentos de golf se pueden ver aquí .

El código se desglosa en las siguientes fases:

ri2b                e# get input in binary
{                   e# While fold is legal
 _W%.+_             e#   "fold" the whole number onto itself
 _0e=)\             e#   count zeros and add 1 (I)
 _,1>\              e#   size check, leave 0 if singleton (II)*
 0-X+:*3<           e#   product of 2s, leave 0 if too many (III)
 *&                 e#   (II AND III) AND parity of I
}{                  e# Do
 _,2/<              e#   slice opposite to the actual fold**
}w                  e# End while
2-!                 e# return 1 if "fold" ended in all 2s

EDITAR: Esta versión toma más o menos un enfoque de la Ley de De Morgan a la versión anterior.

* El problema con la ejecución en singletons es que nos quedamos atrapados con una cadena vacía después del corte.

** Si un número binario es super plegable, su imagen espejo (con ceros a la izquierda si es necesario) es. Esto ahorra un byte sobre tomar la mitad derecha.

JavaScript, 149 bytes

f=(i,n=i.toString(2),l=n.length,m=l/2|0)=>/^1*$/.test(n)?1:/[^01]/.test(n)|!+n[m]&l?0:f(0,+n.slice(0,m)+ +n.slice(m+l%2).split``.reverse().join``+"")

Define una función recursiva.

Explicación:

f=(i                       //Defines the function: i is input
,n=i.toString(2)           //n is the current number
,l=n.length                //l is the length of the number,
,m=l/2|0)=>                //m is the index of the center character
/^1*$/.test(n)?1:          //returns 1 if the number is all ones
/[^01]/.test(n)            //returns 0 if the number has any chars other than 0 or 1
|!+n[m]&l?0:               //or if the middle char is 0
f(0,+n.slice(0,m)+ +n.slice(m+l%2).split``.reverse().join``+"")
                           //otherwise recurses using the first half of the number plus the second half

JavaScript (ES6), 113 109 108 bytes

f=(n,[h,...r]=n.toString(2),b='')=>++n&-n-n?h?f(2,r,r[0]?b+(h- -r.pop()):+h?b:2):!isNaN(n=+('0b'+b))&&f(n):1

Formateado y comentado

f = (                               // given:
  n,                                // - n = integer to process
  [h, ...r] = n.toString(2),        // - h = highest bit, r = remaining low bits
  b = ''                            // - b = folded binary string
) =>                                //
  ++n & -n - n ?                    // if n is not of the form 2^N - 1:
    h ?                             //   if there's still at least one bit to process:
      f(                            //     do a recursive call with:
        2,                          //     - n = 2 to make the 2^N - 1 test fail
        r,                          //     - r = remaining bits
        r[0] ?                      //     - if there's at least one remaining low bit:
          b + (h - -r.pop())        //       append sum of highest bit + lowest bit to b
        : +h ? b : 2                //       else, h is the middle bit: let b unchanged
      )                             //       if it is set or force error if it's not
    : !isNaN(n = +('0b' + b)) &&    //   else, if b is a valid binary string:
      f(n)                          //     relaunch the entire process on it
  : 1                               // else: n is a super folding number -> success

Manifestación

f=(n,[h,...r]=n.toString(2),b='')=>++n&-n-n?h?f(2,r,r[0]?b+(h- -r.pop()):+h?b:2):!isNaN(n=+('0b'+b))&&f(n):1

// testing integers in [1 .. 99]
for(var i = 1; i < 100; i++) {
  f(i) && console.log(i);
}

// testing integers in [1500 .. 1599]
for(var i = 1500; i < 1600; i++) {
  f(i) && console.log(i);
}

Perl, 71 70 bytes

Incluye +1 para -p

Dar número en STDIN

superfolding.pl:

#!/usr/bin/perl -p
$_=sprintf"%b",$_;s%.%/\G0$/?2:/.\B/g&&$&+chop%eg while/0/>/2/;$_=!$&

Python 2, 151 bytes

f=lambda n,r=0:f(bin(n)[2:],'')if r<''else(r==''and{'1'}==set(n)or(n in'1'and f(r,'')+2)or n!='0'and'11'!=n[0]+n[-1]and f(n[1:-1],r+max(n[0],n[-1])))%2

ideona

Una función doblemente recursiva que toma un número entero n, y devuelve 0o 1.

Se rmantiene una variable para permitir tanto el resultado del plegamiento como para saber si actualmente: tenemos un número entero (solo el primero); tener una nueva cadena binaria para intentar doblar (exterior); o son plegables (interior).

En el primer paso nes un número entero, que está <''en Python 2, por lo que la recursión comienza convirtiéndose en una cadena binaria.

La próxima ejecución tiene r=''y, por lo tanto, la prueba {'1'}==set(n)se ejecuta para verificar una cadena continua de 1s (el RHS no puede ser, {n}ya que es posible que necesitemos pasar este punto más adelante con r=''un vacío ncuando sería un diccionario que no sería igual {'1'}, un conjunto).

Si esto no se cumple, se prueba el criterio de la cola interna (incluso si no es necesario): si n in'1'se evaluará como Verdadero cuando se ntrata de una cadena vacía o una sola 1, con lo cual se inicia una nueva recursión externa colocando r, por la cadena binaria doblada, en ny ''dentro r. El literal 2se agrega al resultado de esta llamada de función para no permitir la caída a la siguiente parte (a la derecha de una lógica or) que se corrige más adelante.

Si ese no es un valor verdadero (todos los enteros distintos de cero son verdaderos en Python), se prueba el criterio de recursión de la cola externa: n!=0excluye el caso con un medio 0y se prueban los dos caracteres externos que no suman 2por la concatenación de cadenas '11'!=n[0]+n[-1]; si estos dos son verdaderos, los bits externos se descartan de ncon n[1:-1], y luego 1se agrega a rsi hay uno en el exterior; de lo contrario, a 0es, usando el hecho de que '1'>'0'en Python con max(n[0],n[-1]).

Finalmente, la adición de 2en cada recursión interna se corrige con %2.

PHP, 113 bytes

for($n=$argv[1];$n!=$c;$n=($a=$n>>.5+$e)|($b=$n&$c=(1<<$e/=2)-1))if($a&$b||($e=1+log($n,2))&!(1&$n>>$e/2))die(1);

sale con error (código 1) si el argumento no es superpliegue, codifique lo 0contrario. Corre con -r.
La entrada 0devolverá verdadero (código 0).

Descompostura

for($n=$argv[1];            
    $n!=$c;                 // loop while $n is != mask
                            // (first iteration: $c is null)
    $n=                     // add left half and right half to new number
        ($a=$n>>.5+$e)      // 7. $a=left half
        |
        ($b=$n&             // 6. $b=right half
            $c=(1<<$e/=2)-1 // 5. $c=mask for right half
        )
)
    if($a&$b                // 1. if any bit is set in both halves
                            // (first iteration: $a and $b are null -> no bits set)
        ||                  // or
        ($e=1+log($n,2))    // 2. get length of number
        &
        !(1&$n>>$e/2)       // 3. if the middle bit is not set -> 1
                            // 4. tests bit 0 in length --> and if length is odd
    )
    die(1);                 // -- exit with error

PHP, 197 bytes

function f($b){if(!$b)return;if(!strpos($b,"0"))return 1;for($n="",$i=0;$i<($l=strlen($b))>>1;)$n.=$b[$i]+$b[$l-++$i];if($l%2&&!$b[$i]||strstr($n,"2"))return;return f($n);}echo f(decbin($argv[1]));

Expandido

function f($b){
    if(!$b)return; # remove 0
    if(!strpos($b,"0"))return 1; # say okay alternative preg_match("#^1+$#",$b)
    for($n="",$i=0;$i<($l=strlen($b))>>1;)$n.=$b[$i]+$b[$l-++$i]; #add first half and second reverse
    if($l%2&&!$b[$i]||strstr($n,"2"))return; #if middle == zero or in new string is a 2 then it's not a number that we search
    return f($n); #recursive beginning
}
echo f(decbin($argv[1]));

Valores verdaderos <10000

1, 2, 3, 6, 7, 8, 10, 12, 15, 20, 22, 28, 31, 34, 38, 42, 48, 52, 56, 63, 74, 78, 90, 104, 108, 120, 127, 128, 130, 132, 142, 150, 160, 170, 178, 192, 204, 212, 232, 240, 255, 272, 274, 276, 286, 310, 336, 346, 370, 400, 412, 436, 472, 496, 511, 516, 518, 524, 542, 558, 580, 598, 614, 640, 642, 648, 666, 682, 704, 722, 738, 772, 796, 812, 852, 868, 896, 920, 936, 976, 992, 1023, 1060, 1062, 1068, 1086, 1134, 1188, 1206, 1254, 1312, 1314, 1320, 1338, 1386, 1440, 1458, 1506, 1572, 1596, 1644, 1716, 1764, 1824, 1848, 1896, 1968, 2016, 2047, 2050, 2054, 2058, 2064, 2068, 2072, 2110, 2142, 2176, 2180, 2184, 2222, 2254, 2306, 2320, 2358, 2390, 2432, 2470, 2502, 2562, 2576, 2618, 2650, 2688, 2730, 2762, 2866, 2898, 2978, 3010, 3072, 3076, 3080, 3132, 3164, 3244, 3276, 3328, 3380, 3412, 3492, 3524, 3584, 3640, 3672, 3752, 3784, 3888, 3920, 4000, 4032,4095, 4162, 4166, 4170, 4176, 4180, 4184, 4222, 4318, 4416, 4420, 4424, 4462, 4558, 4674, 4688, 4726, 4822, 4928, 4966, 5062, 5186, 5200, 5242, 5338, 5440, 5482, 5578, 5746, 5842, 5986, 6082, 6208, 6212, 6216, 6268, 6364, 6508, 6604, 6720, 6772, 6868, 7012, 7108, 7232, 7288, 7384, 7528, 7624, 7792, 7888, 8032, 8128, 8191, 8202, 8206, 8218, 8232, 8236, 8248, 8318, 8382, 8456, 8460, 8472, 8542, 8606, 8714, 8744, 8814, 8878, 8968, 9038, 9102, 9218, 9222, 9234, 9248, 9252, 9264, 9334, 9398, 9472, 9476, 9488, 9558, 9622, 9730, 9760, 9830, 9894, 99848128, 8191, 8202, 8206, 8218, 8232, 8236, 8248, 8318, 8382, 8456, 8460, 8472, 8542, 8606, 8714, 8744, 8814, 8878, 8968, 9038, 9102, 9218, 9222, 9234, 9248, 9252, 9264, 9334, 9398, 9472, 9476, 9488, 9558, 9622, 9730, 9760, 9830, 9894, 99848128, 8191, 8202, 8206, 8218, 8232, 8236, 8248, 8318, 8382, 8456, 8460, 8472, 8542, 8606, 8714, 8744, 8814, 8878, 8968, 9038, 9102, 9218, 9222, 9234, 9248, 9252, 9264, 9334, 9398, 9472, 9476, 9488, 9558, 9622, 9730, 9760, 9830, 9894, 9984