Folding Numbers

Question

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]

Answer 1

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.

Answer 2

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 2ä. 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.

Answer 3

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

Answer 4

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

Answer 5

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.

Answer 6

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!

Answer 7

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

Answer 8

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! :)}

Answer 9

><>, 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!

Answer 10

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?

Answer 11

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 $_

Answer 12

Brachylog, 16 bytes

ḃḍ{↔|h1&b↔}ᵗz₂≠ᵐ

It doesn't quite work online...

Takes input through the input variable and outputs through success or failure. It relies heavily on z₂, which has been in the language since April 30, but we forgot to ask to have it pulled on TIO so for the time being this only works on a local installation of the language. Either way it's probably an overly naive approach.

                    The input
ḃ                   's binary representation
 ḍ                  split in half
  {       }ᵗ        with its second half
   ↔|               either reversed, or
     h1             if it starts with 1
       &b           relieved of its first element
         ↔          and then reversed
              ≠     has no duplicate elements
            z  ᵐ    in any pair of elements zipped from the two halves
             ₂      which are equal in length.

Brachylog (on TIO), 19 bytes

ḃḍ{↔|h1&b↔}ᵗlᵛ↖Lz≠ᵐ

Try it online!

lᵛ↖Lz is functionally equivalent to z₂ (if you don't use the variable L anywhere else), but it's also three bytes longer.

Answer 13

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

Answer 14

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.

Answer 15

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.

Answer 16

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)

Answer 17

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

Answer 18

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

Answer 19

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.

Answer 20

C, 223 201 189 194 178 Bytes

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

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

}

Answer 21

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

Answer 22

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.

Answer 23

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.

Answer 24

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.

Answer 25

Python 2, 61 59 bytes

Saving two bytes for converting shifts to multiplications

m=n=input()
i=0
while m:i*=2;i+=m&1;m/=2
print(n+i+1)&(n+i)

Returns 0 for a folding number and anything else for non-folding. Uses the bit-twiddling approach.

Answer 26

C, 65 63 bytes

Two bytes for converting shifts to multiplications

i,m;
f(n){
 m=n;i=0;
 while(m)i*=2,i+=m&1,m/=2;
 return(n+i+1)&(n+i);
}

Whitespace is already excluded from bytecount, returns 0 for a folding number and anything else for non-folding. Uses the bit-twiddling approach.

Answer 27

k, 77 bytes

{X:2 0N#X@&:|\X:0b\:x;c:#:'X;$[(~*X 1)|(=). c;~|/(=).(::;|:)@'(-&/ c)#'X;0b]}

by way of explanation, a translation to q

{X:2 0N#X where maxs X:0b vs x;
  c:count each X;
  $[(not first last X)or(=). c;
    not any(=).(::;reverse)@'(neg min c)#'X;0b]
  };