10
\$\begingroup\$

We have already defined a folding number here.

But now we are going to define a Super Folding Number. A Super Folding number is a number that if folded enough times it will eventually reach one less than a power of two. The method of folding is slightly different than in the folding number question.

The folding algorithm goes as follows:

  • Take the binary representation

    e.g. 5882

    1011011111010
    
  • Spilt it into three partitions. First half, last half and middle digit (iff it has a odd number of digits)

    101101 1 111010
    
  • If the middle digit is zero this number cannot be folded

  • Reverse the second half and superimposed on the first half

    010111
    101101
    
  • Add the digits in place

    111212
    
  • Iff there are any 2s in the result the number cannot be folded otherwise the new number is the result of the folding algorithm.

A number is a Super Folding number if it can be folded to a continuous string of ones. (All Folding numbers are also Super Folding Numbers)

Your task is to write code that takes in a number and outputs a truthy value if the number is a Super Folding number and falsy otherwise. You will be scored on the size of your program.

Examples

5200

Convert to binary:

1010001010000

Split in half:

101000 1 010000

The middle is one so we continue Superimpose the halves:

000010
101000

Added them:

101010

No twos so we continue Split in half:

101 010

Fold:

010
101

111

The result is 111 (7 in decimal) so this is a Super Folding Number.

Test Cases

The first 100 Super Folding Numbers are:

[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]
\$\endgroup\$
  • 2
    \$\begingroup\$ Unless I'm mistaken, how did 3 sneak into the test cases again? I can't see how it can be folded, since it splits to 1 1, immediately giving a 2. Or are you saying that folding it zero times counts also? \$\endgroup\$ – Geobits Oct 7 '16 at 2:11
  • \$\begingroup\$ @geobits 3 is supposed to be there. I checked this time ;). Three is 11 so it gets to only ones in zero files \$\endgroup\$ – Wheat Wizard Oct 7 '16 at 2:12
  • \$\begingroup\$ I think it may be worth putting a note right near the top, just after you link to the other folding number question that points out that the individual folds in this question will use a different method. \$\endgroup\$ – Jonathan Allan Oct 7 '16 at 5:40
8
\$\begingroup\$

Here's my first ever shot at code golf:

Python 3, 167 bytes

167 bytes if tabs or single spaces are used for indentation

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

Edit: Thanks to everyone's help below, the code above has been reduced from an original size of 232 bytes!

\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to PPCG! You can save a bunch of bytes by removing the spaces after the :s, and returning 0 and 1 instead of True and False. \$\endgroup\$ – Steven H. Oct 7 '16 at 5:09
  • \$\begingroup\$ Thank you Steven. Also, I'm not 100% sure I counted the byte length correctly. \$\endgroup\$ – Kapocsi Oct 7 '16 at 5:10
  • 1
    \$\begingroup\$ I'm seeing 232 bytes. Give me a second and I can try to golf it a little further. \$\endgroup\$ – Steven H. Oct 7 '16 at 5:12
  • \$\begingroup\$ I used this to measure: bytesizematters.com \$\endgroup\$ – Kapocsi Oct 7 '16 at 5:13
  • 1
    \$\begingroup\$ @Kapocsi, bytesizematters.com counts newlines wrong. Compare with mothereff.in, 5 digits and 5 newlines should be 10 bytes, not the 14 I got on bytesize... its 232. \$\endgroup\$ – Linus Oct 7 '16 at 5:24
5
\$\begingroup\$

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

It took a bit of effort to make the old folding function recursable, but here it is. It's ugly as sin, to be honest. I'll have to take a look in the morning to see if I can golf it further, since I can barely stand to look at it right now.

With line breaks:

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);
}
\$\endgroup\$
3
\$\begingroup\$

CJam, 47 44 bytes

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

Try it online! or generate a list of super folding numbers up to a given number.
Golfing attempts can be seen here.


The code breaks down to the following phases:

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

EDIT: This version more or less takes a De Morgan's Law approach to the previous version.

*The problem with running on singletons is that we get stuck with an empty string after the slice.

** If a binary number is super folding, its mirror image (with leading 0s if needed) is. This saves a byte over taking the right half.

\$\endgroup\$
2
\$\begingroup\$

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``+"")

Defines a recursive function.

Explanation:

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
\$\endgroup\$
  • \$\begingroup\$ m=l>>1, /2/.test(n), n.slice(l-m) (or slice the reversed string). I think if you switch the failure and success cases then you can use /0/.test(n)?f(...):1. \$\endgroup\$ – Neil Oct 7 '16 at 8:00
2
\$\begingroup\$

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

Formatted and commented

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

Demo

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

\$\endgroup\$
2
\$\begingroup\$

Perl, 71 70 bytes

Includes +1 for -p

Give number on STDIN

superfolding.pl:

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

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

ideone

A doubly-recursive function which takes an integer, n, and returns 0 or 1.

A variable r is maintained to allow both the result of folding and to know if we currently: have an integer (first only); have a new binary string to try to fold (outer); or are folding (inner).

On the first pass n is and integer, which is <'' in Python 2 so the recursion starts by casting to a binary string.

The next execution has r='' and so the test {'1'}==set(n) is executed to check for a continuous string of 1s (the RHS cannot be {n} as we may need to pass this point later with r='' and an empty n when that would be a dictionary which wont equal {'1'}, a set).

If this is not satisfied the inner tail criteria is tested for (even if unnecessary): if n in'1' will evaluate to True when n is an empty string or a single 1, whereupon a new outer recursion is begun by placing r, by the then folded, binary string into n and '' into r. The literal 2 is added to the result of this function call to allow no fall through to the next part (to the right of a logical or) that is corrected later.

If that is not a truthy value (all non-zero integers are truthy in Python) the outer tail recursion criteria is tested for: n!=0 excludes the case with a middle 0 and the outer two characters are tested they do not sum to 2 by the string concatenation '11'!=n[0]+n[-1]; if these both hold true the outer bits are discarded from n with n[1:-1], and then a 1 is appended to r if there is one on the outside otherwise a 0 is, using the fact that '1'>'0' in Python with max(n[0],n[-1]).

Finally the addition of 2 at each inner recursion is corrected with %2.

\$\endgroup\$
0
\$\begingroup\$

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

exits with error (code 1) if argument is not super-folding, code 0 else. Run with -r.
Input 0 will return true (code 0).

breakdown

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
\$\endgroup\$
0
\$\begingroup\$

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

Expanded

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

True values < 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, 9984

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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