Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Given a number determine if it is a folding number.

A folding number is a number such that if you take it binary representation and "fold" it in half, That is take the result of XNOR multiplication of the first half of the number and the second half with it digits in reverse, you will get zero.

If the number has a odd number of digits in binary its middle digit must be 1 and is ignored when folding.

Since that might be a bit confusing I will give some examples:

178

The binary representation of 178 is

10110010

To fold this we first split it in half

1011 0010

We reverse the second half

1011
0100

And we XNOR the two halves:

0000

This is zero so this is a folding number.

1644

The binary representation of 1644 is

11001101100

To fold this we first split it in half

11001 1 01100

The middle bit is 1 so we throw it out.

11001 01100

We reverse the second half

11001
00110

And we XNOR the two halves:

00000

This is zero so this is a folding number.

4254

The binary representation of 4254 is

1000010011110

To fold this we first split it in half

100001 0 011110

The middle bit is 0 so this is not a folding number.

Task

Your task is to take in a positive number and return a truthy if the number is folding and falsy if it is not. This is code golf so try to keep the byte count down.

Test Cases

Here are the first 99 folding numbers:

[1, 2, 6, 10, 12, 22, 28, 38, 42, 52, 56, 78, 90, 108, 120, 142, 150, 170, 178, 204, 212, 232, 240, 286, 310, 346, 370, 412, 436, 472, 496, 542, 558, 598, 614, 666, 682, 722, 738, 796, 812, 852, 868, 920, 936, 976, 992, 1086, 1134, 1206, 1254, 1338, 1386, 1458, 1506, 1596, 1644, 1716, 1764, 1848, 1896, 1968, 2016, 2110, 2142, 2222, 2254, 2358, 2390, 2470, 2502, 2618, 2650, 2730, 2762, 2866, 2898, 2978, 3010, 3132, 3164, 3244, 3276, 3380, 3412, 3492, 3524, 3640, 3672, 3752, 3784, 3888, 3920, 4000, 4032, 4222, 4318, 4462, 4558]
share|improve this question
    
Is 4 not a folding number? – Adnan Oct 6 at 13:23
1  
@Adnan The middle bit is 0, so no. (It might be worth having a third worked example like this though.) Same goes for 18. – Martin Ender Oct 6 at 13:24
    
@MartinEnder Ahh, I missed that part. Thanks :) – Adnan Oct 6 at 13:25
1  
why does the middle number have to be one (in odd digit binary #s)? was that arbitrary or was there a reason? – greyShift Oct 6 at 14:41
2  
@timrxd if you try to fold a number by adding up opposite digits, a number with a one in the center you will get a string of all ones. If it has a zero in the center you will end with a zero in the result. – Wheat Wizard Oct 6 at 14:45

23 Answers 23

Jelly, 9 bytes

Bœs2µḢ^UȦ

Try it online! or verify all test cases.

How it works

Bœs2µḢ^UȦ  Main link. Argument: n

B          Binary; convert n to base 2.
 œs2       Evenly split 2; split the base 2 array into chunks of equal-ish length.
           For an odd amount of digits, the middle digit will form part of the
           first chunk.
    µ      Begin a new, monadic chain. Argument: [A, B] (first and second half)
     Ḣ     Head; remove and yield A.
       U   Upend; reverse the digits in [B].
      ^    Perform vectorized bitwise XOR of the results to both sides.
           If A is longer than B, the last digit will remain untouched.
           n is a folding number iff the result contains only 1's.
        Ȧ  Octave-style all; yield 1 iff the result does not contain a 0.
share|improve this answer
    
Pretty sure I tried that, oh well :) – Jonathan Allan Oct 6 at 15:43

Java 7, 152 145 142 138 134 bytes

boolean f(Long a){byte[]b=a.toString(a,2).getBytes();int i=0,l=b.length,z=l%2<1?1:b[l/2]-48;for(;i<l/2;)z*=b[i]-b[l-++i];return z!=0;}

Loops over the string like it would for a palindrome, looking for zeroes. Keeps track by repeatedly multiplying, so all you have to do is check that it's not zero at the end.

Without scroll bars:

boolean f(Long a){
    byte[]b=a.toString(a,2).getBytes();
    int i=0,l=b.length,z=l%2<1?1:b[l/2]-48;
    for(;i<l/2;)
        z*=b[i]-b[l-++i];
    return z!=0;
}
share|improve this answer
    
"but can surely be golfed down" I don't think your current answer can be golfed more, but I'd like to be proven wrong. +1 (PS: Your ungolfed part contains two closing brackets.) – Kevin Cruijssen Oct 6 at 14:09
    
byte[]b=(a+"").getBytes(); is shorter than the char[]b=a.toString(a,2).toCharArray(); and still seems to work (-12 bytes). – Kevin Cruijssen Oct 6 at 14:45
1  
@KevinCruijssen That's not a binary string AFAICT, but I think getBytes might still work over the char[]. Thanks :) – Geobits Oct 6 at 14:47
    
@KevinCruijssen Yeah, realized that and removed comment >_<. – carusocomputing Oct 6 at 14:48

Python 2, 94 79 72 67 bytes

F=lambda s:s in'1'or(s[0]!=s[-1])*F(s[1:-1])
lambda n:F(bin(n)[2:])

Saved 12 bytes thanks to @xnor

Defines an unnamed function on the second line.

Explanation (with some whitespace added):

F = lambda s:                                        # We define a function, F, which takes one argument, the string s, which returns the following:
             s in'1'                                 # Gives true if s is '' or s is '1', the first case is a base case and the second is for the middle bit case.
                     or(s[0] != s[-1])               # Or the first and last are different
                                      * F(s[1:-1])   # And check if s, without the first and last element is also foldable.
lambda n: F(bin(n)[:-2])                             # The main function, which calls F with the argument in binary form.

Try it here!

share|improve this answer
4  
s==''or s=='1' can be s in'1' – xnor Oct 6 at 17:18
    
Oh so similar - great minds... – Jonathan Allan Oct 6 at 17:34
1  
The and can be arithmetic *. Also, f is allowed to be unnamed. – xnor Oct 6 at 17:48

Python 2, 57 bytes

s=bin(input())[2:]
while''<s!='1':s[-1]==s[0]<_;s=s[1:-1]

Outputs via exit code: error for Falsey, and no error for Truthy.

Converts the input into binary. Checks whether the first and last character are unequal, keeps and repeating this after removing those characters.

The comparison s[-1]==s[0]<_ gives an error if the first and last character are unequal by trying to evaluate the unassigned variable named _. If they are equal, the chain of inequalities is short-circuited instead. When we get to the middle element of 1, the while loop is terminate to special-case it as OK.

I suspect a purely arithmetic approach will be shorter with a recursion like f=lambda n,r=0:...f(n/2,2*r+~n%2)... to chomp off binary digits from the end flipped and reversed, and detect when n and r are equal up to a center 1. There are subtleties though with leading zeroes and the center.

share|improve this answer

05AB1E, 13 12 bytes

Code:

bS2ä`R0¸«s^P

Uses the CP-1252 encoding. Try it online!

Explanation:

First, we convert the number to binary using b. 1644 becomes 11001101100. We split this into two pieces with . For example, 11001101100 would become:

[1, 1, 0, 0, 1, 1]
[0, 1, 1, 0, 0]

If there is an uneven number of bits, the first part will receive the extra bit. We Reverse the last string and append a zero using 0¸«. The reason for this is to only give truthy results when the middle bit is a 1 (1 XOR 0 = 1 and 0 XOR 0 = 0). If there is no middle bit, 05AB1E will just ignore the last bit (the zero that was appended) :

[1, 1, 0, 0, 1, 1]
[0, 0, 1, 1, 0, 0]

The last thing we need to do is do an element-wise XOR and take the product of the result. If there is one element too many, the program will just leave the last element out ([1, 0, 0] XOR [0, 1] = [1, 1]) For example:

[1, 1, 0, 0, 1, 1]
[0, 0, 1, 1, 0, 0] XOR

Becomes:

[1, 1, 1, 1, 1, 1]

And the product of that is 1, which is truthy.

share|improve this answer
    
Very nice! Too bad the s is required. – Emigna Oct 6 at 14:22
    
@Emigna Yeah, I should fix that some time. This also gave me some inspiration for other commands :p – Adnan Oct 6 at 16:45
    
Awwh, I was halfway there, trying 05AB1E out for the first time, this one was rather tough. bÐg;ô was as far as I got before refreshing and seeing you nailed it. Great answer, helping me learn! – carusocomputing 2 days ago
    
@carusocomputing Thanks! It's always nice to see new people interested in 05AB1E :). If you have any questions, you can always ask in this chatroom. – Adnan 2 days ago
    
Oh crap! This was a different question! I was on the "super folding" question. I tried to extend the answer out to that solution as well, but iterating is even more challenging. – carusocomputing 2 days ago

JavaScript (ES6), 61 57 52 bytes

Recursively computes:

(bit(N) XOR bit(0)) AND (bit(N-1) XOR bit(1)) AND (bit(N-2) XOR bit(2)) etc.

where N is the rank of the highest bit set in the input.

If the input has an odd number of bits, the middle bit is XOR'ed with undefined (the value returned by pop() on an empty array), which lets it unchanged. So, a 0 middle bit clears the output and a 1 middle bit doesn't alter the result of the other operations -- which is consistent with the challenge definition of a folding number.

f=(n,[a,...b]=n.toString(2))=>a?(a^b.pop())&f(n,b):1

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

share|improve this answer
    
Nice! Can you explain how this takes the middle bit into account? – ETHproductions Oct 6 at 16:30
    
@ETHproductions - Sure. I've added a note about that. – Arnauld Oct 6 at 16:45

Haskell, 89 88 86 bytes

f n|n<2=[n]|1>0=mod n 2:f(div n 2)
g n=elem(product$zipWith(+)(f n)$reverse$f n)[1,2]

Works by summing bitwise the bit representation with its reverse and taking the product. If it's 1 or 2, the number is a folding number (1 if there are even bits that fold, 2 if there are odd bits and a one in the middle).

share|improve this answer

Python 2, 100 99 95 94 Bytes

This feels a bit long, but I'll keep working at it :) Prints a 1 if the number can be folded, 0 otherwise.

a=bin(input())[2:]
b=len(a)
print(a[b/2]>=`b%2`)*all(c!=d for c,d in zip(a[:b/2],a[:~b/2:-1]))

Test it here!

thanks to Wheat Wizard for the 1-byte save :)

thanks to Rod for the 5-byte save! :)

share|improve this answer
    
you can replace b-1 with ~b – Wheat Wizard Oct 6 at 13:50
    
@WheatWizard Awesome, thanks! – Shebang Oct 6 at 13:52
    
you can replace [1,a[b]>'0'][len(a)%2] with (a[b]>=`len(a)%2`) – Rod Oct 6 at 14:10
    
@Rod Nice find, thanks! – Shebang Oct 6 at 14:19
2  
@Rod Awesome :D Except now the other answer is crushing me ;) – Shebang Oct 6 at 16:35

Perl, 46 bytes

Includes +1 for -p

Run with the number on STDIN

folding.pl <<< 178

folding.pl:

#!/usr/bin/perl -p
$_=($_=sprintf"%b",$_)<s%.%!/\G1$/^$&^chop%eg

I consider it a perl bug that this even works. Internal $_ should not be getting match position updates once it is modified. In this program the match position actually moves beyond the end of $_

share|improve this answer
    
Nice one. Best I could do is 59 : perl -pe '$_=sprintf("%b",$_)=~/^(.*)1?(??{reverse$^N=~y%01%10%r})$/' :/ – Dada Oct 6 at 17:53

><>, 37+3 = 40 bytes

<,2-@:%2:v!?:
=2lrv?=1l<+={$r0?
0=n;>

Input is expected to be present on the stack at program start, so +3 bytes for the -v flag.

Try it online!

share|improve this answer

Jelly, 13 bytes

Bœs2U0¦z0^/€Ạ

TryItOnline
Or matching terms up to 4558

How?

Bœs2U0¦z0^/€Ạ - Main link: n
B             - binary
 œs2          - split into 2 slices (odd length will have first longer than second)
     0¦       - apply to index 0 (the right hand one)
    U         - reverse
       z0     - zip together with filler 0 (thus central 1 or 0 will pair with 0)
          /€  - reduce with for each
         ^    -     XOR
            Ạ - All truthy?
share|improve this answer

Python 2, 76 71 69 bytes

-5 bytes thanks to @Dennis ('' is present in '1', so replace in('','1') with in'1')
-2 bytes thanks to @xnor (use multiplication, (...)* in place of and)

f=lambda n:f(bin(n)[2:])if n<''else n in'1'or(n[0]!=n[-1])*f(n[1:-1])

Ideone

Recursive function, upon first call n is a number so it evaluates as less than the empty string, with if n<'', and the function is called again but with n cast to a binary string; the tail is either an empty string (even bit-length) or the middle bit, which returns true for empty or a '1'; on it's way down it tests the outer bits for inequality (equivalent to XOR) and recurses on the inner bits, n[1:-1].

share|improve this answer
1  
I think n in'1' works. – Dennis Oct 6 at 17:26
    
Brilliant, I would not think '' was present in 'blah', but yes it is :) – Jonathan Allan Oct 6 at 17:30
1  
The and can be arithmetic *. – xnor Oct 6 at 17:42
    
Thank you @xnor! – Jonathan Allan Oct 6 at 17:44

Python 2, 63 bytes

s=bin(input())[2:]
while s[0]!=s[-1]:s=s[1:-1]or'1'
print'1'==s

Prints True or False. Takes the binary representation of s and repeatedly removed the first and last characters as long as they are unequal. Checks whether what remains is the empty string or a central 1. This is done by converting '' to '1' and checking if the result equals '1', which also avoid an index error on the empty string.

share|improve this answer

PowerShell v2+, 143 bytes

Two possible approaches, both the same byte count.

Method 1:

param($n)if($n-eq1){$n++}$o=1;0..(($b=($n=[convert]::ToString($n,2)).length-1)/2-!($b%2))|%{$o*=$n[$_]-ne$n[$b-$_]};$o*(+"$($n[$b/2])",1)[$b%2]

Takes input $n, if it's -equal to 1 (a special case for this algorithm), increment it. Set $output to be 1 (i.e., assume truthy), then loop from 0 to the midway point of the input number that has been [convert]ed to binary. Note the -!($b%2) to account for odd length binary numbers.

Each iteration, we compare the current digit $n[$_] with the digit the same length from the end $n[$b-$_], and multiply the Boolean result into $o (essentially performing an -and on all of them). Once the loop is done, we need to potentially account for the middle binary digit, that's the pseudo-ternary at the end (array indexed via $b%2). That 1 or 0 is left on the pipeline, and output is implicit.


Method 2:

param($n)for($n=[convert]::ToString($n,2);$n.Length-gt2){if($n[0]-ne$n[-1]){$n=$n[1..($n.Length-2)]}else{0;exit}}($n-join'+'|iex)-eq1-or$n-eq10

Takes input and does the same process to [convert] the number to binary. Then we're in a for loop so long as the .length of the binary string is -greaterthan 2. When we're in the loop, if the first $n[0] and last $n[-1] digits are -notequal, slice those two digits off of $n and re-store it into $n. Otherwise, output 0 and exit. Once we're out of the loop, we either have (an array of 1, 1,0, 0,1, 1,1, or 0,0), or the binary string for two 10, or 3 11. So, we need to test those two possibilities. For the first, we -join $n together with + and evaluate the result and test that it's 1 (this is true for arrays 1, 1,0, and 0,1, but is $false for arrays 0,0 and 1,1 or strings 10 or 11). The other half of the -or is testing whether $n is -equal to 10 (i.e., input of 2). That Boolean is left on the pipeline, and output is implicit.

share|improve this answer

MATL, 16 bytes

tBn2/kW&\hBZ}P=~

Truthy is an array with all ones. Check truthy/falsy criteria here.

Try it online! Or Verify the first 20 test cases.

Explanation

Let's use input 1644 as an example.

t     % Imolicitly take input. Duplicate
      %   STACK: 1644, 1644
Bn    % Number of digits of binary expansion
      %   STACK: 1644, 11
2/k   % Divide by 2 and round down
      %   STACK: 1644, 5
W     % 2 raised to that
      %   STACK: 1644, 32
&\    % Divmod
      %   STACK: 12, 51
h     % Concatenate horizontally
      %   STACK: [12 51]
B     % Binary expansion. Each numnber gives a row, left-padded with zeros if needed
      %   STACK: [0 0 1 1 0 0; 1 1 0 0 1 1]
Z}    % Split into rows
      %   STACK: [0 0 1 1 0 0], [1 1 0 0 1 1]
P     % Reverse
      %   STACK: [0 0 1 1 0 0], [1 1 0 0 1 1]
=~    % True for entries that have different elements
      %   STACK: [1 1 1 1 1 1]
      % Implicitly display
share|improve this answer

PHP, 101 Bytes

for($r=1;$i<($l=strlen($b=decbin($argv[1])))>>1;)$r*=$b[$i]^1^$b[$l-++$i]^1;$r*=$l%2?$b[$i]:1;echo$r;

or with log

for($r=1,$s=log($n=$argv[1],2)^0;2*$i<$s;)$r*=($n>>$i)%2^($n>>$s-$i++)%2;$s%2?:$r*=($n>>$i)%2;echo$r;

108 Bytes with array

for($r=1,$a=str_split(decbin($argv[1]));$a;)$r*=array_pop($a)!=($a?array_shift($a):0);$r*=$a?$a[0]:1;echo$r;

True values <10000

1,2,6,10,12,22,28,38,42,52,56,78,90,108,120,142,150,170,178,204,212,232,240,286,310,346,370,412,436,472,496,542,558,598,614,666,682,722,738,796,812,852,868,920,936,976,992,1086,1134,1206,1254,1338,1386,1458,1506,1596,1644,1716,1764,1848,1896,1968,2016,2110,2142,2222,2254,2358,2390,2470,2502,2618,2650,2730,2762,2866,2898,2978,3010,3132,3164,3244,3276,3380,3412,3492,3524,3640,3672,3752,3784,3888,3920,4000,4032,4222,4318,4462,4558,4726,4822,4966,5062,5242,5338,5482,5578,5746,5842,5986,6082,6268,6364,6508,6604,6772,6868,7012,7108,7288,7384,7528,7624,7792,7888,8032,8128,8318,8382,8542,8606,8814,8878,9038,9102,9334,9398,9558,9622,9830,9894
share|improve this answer

C, 223 201 189 194 Bytes

i,j,k,m,l,r;f(n){for(m=j=1,i=n;i/=2;++j);k=j/2;for(l=r=i=0;i<k;i++)r|=n&m?1<<k-i-1:0,m*=2;if(j&1&&n&m)i++;else if(j&1)return 0;n>>=i;for(m=1;i<j;i++)l|=n&m,m*=2;return ((~(l^r))&((1<<k)-1))==0;}

Brute force algorithm. Let's see how far it can be golfed.

Better test setup bugfixes...

 main()
 {
    int t, s, u, testSet[] = 
    {
    1, 2, 6, 10, 12, 22, 28, 38, 42, 52, 56, 78, 90, 108, 120,
    142, 150, 170, 178, 204, 212, 232, 240, 286, 310, 346, 370,
    412, 436, 472, 496, 542, 558, 598, 614, 666, 682, 722, 738,
    796, 812, 852, 868, 920, 936, 976, 992, 1086, 1134, 1206,
    1254, 1338, 1386, 1458, 1506, 1596, 1644, 1716, 1764, 1848,
    1896, 1968, 2016, 2110, 2142, 2222, 2254, 2358, 2390, 2470,
    2502, 2618, 2650, 2730, 2762, 2866, 2898, 2978, 3010, 3132,
    3164, 3244, 3276, 3380, 3412, 3492, 3524, 3640, 3672, 3752,
    3784, 3888, 3920, 4000, 4032, 4222, 4318, 4462, 4558
    };


    for (u=s=0,t=1;t<=4558;t++)
    {
        if (f(t))
        {
          u++;            
          if (testSet[s++]!=t)
              printf("BAD VALUE %d %d\n", testSet[s-1], t);
        }
    }

    printf("%d == %d Success\n", u,
           sizeof(testSet)/sizeof(testSet[0]));

}
share|improve this answer

CJam, 13 bytes

ri2b_W%.+:*3&

Try it online! or generate a list of folding numbers up to a given number.


ri2b   e# convert input to binary
_W%.+  e# flip and sum (if folding all bits are 1 except middle)
:*     e# product is 0 or power of 2 (2 if middle folds)
3&     e# keep only 1 or 2, everything else becomes 0 (false)
share|improve this answer

Julia, 66 bytes

c(s)=s==""||s=="1"||(s[1]!=s[end]&&c(s[2:end-1]))
f(x)=c(bin(x))

My first golf! works the same way as the Python solution of the same length, minor differences due to language (I did come up with it on my own, though...).

Explanation:

c(s) = s == "" || # Base case, we compared all the digits from 
                  # both halves.
       s == "1" || # We compared everything but left a 1 in the middle
       (s[1] != s[end] &&  # First digit neq last digit (XNOR gives 0).
        c(s[2:end-1]))     # AND the XNOR condition is satisfied for the  
                           # 2nd to 2nd to last digit substring.
f(x) = c(bin(x))  # Instead of a string f takes an integer now.
share|improve this answer

MATL, 13 bytes

BttP=<~5Ms2<*

Truthy is an array with all ones. Check truthy/falsy criteria here.

Try it online! Or verify the first 20 test cases.

Explanation

Using input 1644 as an example:

B     % Implicit input. Convert to binary
      %   STACK: [1 1 0 0 1 1 0 1 1 0 0]
t     % Duplicate
      %   STACK: [1 1 0 0 1 1 0 1 1 0 0], [1 1 0 0 1 1 0 1 1 0 0]
tP=   % Element-wise compare each entry with that of the reversed array
      %   STACK: [1 1 0 0 1 1 0 1 1 0 0], [0 0 0 0 0 1 0 0 0 0 0]
<~    % True (1) if matching entries are equal or greater
      %   STACK: [1 1 1 1 1 1 1 1 1 1 1]
5M    % Push array of equality comparisons again
      %   STACK: [1 1 1 1 1 1 1 1 1 1 1], [0 0 0 0 0 1 0 0 0 0 0]
s     % Sum of array
      %   STACK: [1 1 1 1 1 1 1 1 1 1 1], 1
2<    % True (1) if less than 2
      %   STACK: [1 1 1 1 1 1 1 1 1 1 1], 1
*     % Multiply
      %   STACK: [1 1 1 1 1 1 1 1 1 1 1]
      % Implicitly display
share|improve this answer

JavaScript, 71 bytes

(i,n=i.toString(2))=>/^(1*)2?\1$/.test(+n+ +n.split``.reverse().join``)

Defines an anonymous function.

This method may not be the shortest, but as far as I know, it is unique. It adds the number in binary to itself reversed, treating them as decimal, then checking if the result is valid using a regex.

share|improve this answer

Retina, 92 bytes

Byte count assumes ISO 8859-1 encoding.

.+
$*
+`(1+)\1
${1}0
01
1
^((.)*?)1??((?<-2>.)*$.*)
$1¶$3
O$^`.(?=.*¶)

T`01`10`^.*
^(.*)¶\1

Try it online

Convert to unary. Convert that to binary. Cut the number in half and remove a middle 1 if there is. Reverse the first half. Switch its ones and zeros. Match if both halves are equal.

share|improve this answer

Retina, 71 70 60 bytes

.+
$*
+`^(1*)\1(1?)\b
$1 $.2
+`^ (.)(.*) (?!\1).$
$2
^( 1)?$

I probably still have a lot to learn about Retina (e.g. recursive regex?). Explanation: Step 1 converts from decimal to unary. Step 2 converts from unary to pseudo-binary. Step 3 removes digits from both ends as long as they mismatch. Step four matches an optional final central 1 if necessary. Edit: Saved 1 byte thanks to @mbomb007. Saved 10 bytes by improving my unary to binary conversion.

share|improve this answer
    
The first line can be .* or .+. – mbomb007 2 days ago

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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