text:
Extended Truth Machine
Many people know what a truth machine in programming is. But is time we kick things up a notch. Introducing, the extended truth machine! An extended truth machine takes two things as input, a integer n and a nonempty string s. It outputs s n times with optional trailing whitespace. However, if n is equal to 0, you must output s until the program is manually stopped i.e. it should never terminate.
Also, if n is a negative number, then the string needs to be reversed. For example with s=hello and n=-1, output would be olleh.
Standard methods of input, any kind of output as long as it can handle infinite. If you have an answer that does not handle infinite, feel free to post it if it is interesting or in a language that cannot handle infinite output.
Test Cases
n, s, output

5, "hello world", "hello worldhello worldhello worldhello worldhello world"
0, "PPCG", "PPCGPPCGPPCGPPCG..."
-2, "truThY", "YhTurtYhTurt"
2000, "o", "oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo"

This is code-golf, so shortest code wins!
Here is the original Sandbox post. Edits have been made to it. Thanks go to @ComradeSparklePony for creating the idea of this challenge

Haskell, 57 54 bytes
f 0=cycle
f n|n<0=f(-n).reverse|n>0=concat.replicate n

Explanation:
f 0           -- If n=0 ..
 =cycle       -- infinitely repeat the input
f n|n<0       -- Otherwise, if n<0 ..
 =f(-n)       -- call f with the negative of n ..
 .reverse     -- and the reverse of the input
 |n>0         -- Finally, if n>0 ..
 concat       -- concatenate the result of ..
 .replicate n -- repeating the input n times

-3 bytes thanks to @nimi

You can use -n instead of abs n.

MATL, 37 bytes
jXJiXI0=?`1wtwDw]}I0>?I:"t]x}PI|:"t]x

Try it online!
Explanation:
j            % input string
XJ           % copy to clipboard J
i            % input
XI           % copy to clipboard I
0            % number literal
=            % is equal? (element-wise, singleton expansion)
?            % if
  `          % do...while
    1        % number literal
    w        % swap elements in stack
    t        % duplicate elements
    w        % swap elements in stack
    D        % convert to string and display / string representation
    w        % swap elements in stack
  ]          % end
}            % else
  I          % paste from clipboard I
  0          % number literal
  >          % is greater than? (element-wise, singleton expansion)
  ?          % if
    I        % paste from clipboard I
    :        % range; vector of equally spaced values
    "        % for
      t      % duplicate elements
    ]        % end
    x        % delete
  }          % else
    P        % flip the order of elements
    I        % paste from clipboard I
    |        % absolute value / norm / determinant
    :        % range; vector of equally spaced values
    "        % for
      t      % duplicate elements
    ]        % end
    x        % delete
             % (implicit) end
             % (implicit) end
             % (implicit) convert to string and display

PHP>=7.1, 67 Bytes
for([,$x,$y]=$argv,$z=$x<=>0;!$z||$x;$x-=$z)echo$x<0?strrev($y):$y;

Version with list(,$x,$y) instead of [,$x,$y]
Try it online!

05AB1E, 17 16 14 bytes
0‹iR}¹Ä×¹_i[²?

Try it online!
Explanation:
0‹iR}¹Ä×¹_i[²?
0‹             Is the input negative?
  iR}          If so, reverse the second input.
     ¹Ä        Get the absolute value of the first input.
       ×       Repeat the string that many times.
        ¹_     Boolean NOT the first input. (Is the first input 0?)
          i    If so...
           [   Do forever...
            ²? Print the second input without a newline.

Saved 2 bytes thanks to @EriktheOutgolfer

You can replace '-å with 0‹ and 0Q with _.

@EriktheOutgolfer Thanks, edited.

Python 3, 71 bytes
def f(n,s,k=1):
 if n<0:s=s[::-1];n=-n
 while n|k:print(end=s);n-=1;k=0

Try it online!
The variable k guarantees the loop is always run at least once. This means that if n=0, then n will be negative on the next iteration of the loop, so the loop will continue to be run forever.

Cubix, 41 Forty four 45 bytes
Takes input as <N> <String>
.uq.sB.p$IA;p?;ouu(..!q/o()uq?..@<w?q<<_)

Try it online!
Cubified:
      . u q
      . s B
      . p $
I A ; p ? ; o u u ( . .
! q / o ( ) u q ? . . @
< w ? q < < _ ) . . . .
      . . .
      . . .
      . . .

Watch it running
There is still an amount of no-ops in the code which I might be able to get a few more bytes out of, but wanted to get this up before I break it.
Basic procedure is

I get counter from input
A take the rest of input in as characters
;p? remove the space, bring the number up and test it

psuqB$) if the counter is negative, reverse the stack.  This involves handling the input number and EOI marker(-1).  Increment the counter.
;p;ouqu if the counter is zero, remove the counter and EOI marker and start perpetual output loop.
( if positive decrement the  counter

<<q?/o()u the output loop.  This will output each character of the stack until the EOI marker (-1) is reached.
... _ ... ?wq! on end EOI marker, go around the cube and reflect back to the ?, change lane, drop the EOI marker to the bottom and test the counter.
@ if zero, halt
?u( if positive u-turn and decrement, thie ends up hitting the beginning of the loop
? ... <) if negative, go around the cube to the otherside, redirect to the beginning of the loop while passing over a increment.
/)< if negative increment and carry on to output loop

doesn't this fail to work if the string starts with a number?

@DestructibleLemon fixed

Matlab, 87 bytes
n=input('')
s=input('','s')
a=repmat(s,1,abs(n))
while~n s=[s s]
end
if n<0,flip(a)
end

My first attempt at code-golf! Any suggestions for golfing are welcome.

Welcome to the site! :)

str, 30 bytes
I#Lbd0<[_u_][d0='e'u#?]#?xo;db

Try it online!
Explanation
I#Lbd0<[_u_][d0='e'u#?]#?xo;db
...........................;      preamble
I                                 read number
 #L                               read rest of STDIN
   b                              buffer the STDIN
    d                             duplicate number
     0<[   ]           #?         if the number is less than zero
        _                         negate that number
         u_                       and reverse STDIN from buffer
            [         ]           otherwise
             d0='e  #?            if its 0, push the empty string
                  'u              otherwise, push the unbuffered STDIN untouched
                         x        repeat STDIN by the TOS
                          o       and output
                           ;..    main program (only activates when input = 0)
                            d     duplicate the implicitly unbuffered STDIN
                             b    and rebuffer it
                                  implicitly displayed

JavaScript (ES6), 98 94 91 83 bytes
n=>s=>{s=n<0?[...s].reverse().join``:s;while(!n)l(s);l(s.repeat(n<0?-n:n))}

-4, -5 bytes thanks to Arjun
-3 bytes thanks to Rick Hitchcock
Started out different than the Java answer, but quickly became very similar after golfing. Alert is infinite, but if you want it to look nice, switch to console.log. l=alert; and writing out alert are the same length, but if you switch to console.log it's shorter to redefine it.

while(!n)l(s) instead of if(!n)for(;;)l(s).

[...s].reverse() instead of s.split''.reverse()

@RickHitchcock I always forget about that :(

l(s.repeat(Math.abs(n))) instead of for loop at last.

JavaScript (ES6), 79 bytes
 f=(n,s)=>n<0?f(-n,[...s].reverse().join``):(alert(!n?s:s.repeat(n)),!n&&f(n,s))

Snippet:

f=(n,s)=>n<0?f(-n,[...s].reverse().join``):(alert(!n?s:s.repeat(n)),!n&&f(n,s))

f(5, "hello world")
//f(0, "PPCG")  //uncomment this at your peril!!!
f(-2, "truThY")
f(2000, "o")

I was trying to do something recursive like this, but I didn't think of !n&& for looping infinitely. However, will this hit a StackOverflow eventually? it should never terminate.

It will alert the string PPCG repeatedly.  In Chrome (at least), I have to kill the browser to stop it.

I understand your point.  I think my code would take advantage of tail call recursion optimization in browsers that support it.

Test it with console.log. I get an error.

Hmm, you're absolutely correct : (

Java (OpenJDK 8), 137 bytes
void f(String[] a){for(long n=Long.valueOf(a[0]),i=0;n==0|i++<Math.abs(n);)System.out.print(n<0?new StringBuilder(a[1]).reverse():a[1]);}

Try it online!

This looks like a snippet rather than a full program, which is disallowed by community consensus.

According to the post you linked, "The default should be 'programs or functions'". Therefore, since OP did not explicitly state that they wanted a full program, I've updated my answer. It now consists of a method.

C (gcc), 115 112 109 107 104 bytes
f(n,s,l,p,d)char*s;{d=n<0?-1:1;do for(l=1,p=0;p>=0;p+=l)s[p]?d==l&&putchar(s[p]):l--;while(!n||(n-=d));}

Try it online!

Who said, we need strlen?

C (gcc), 115 bytes (134 with #include<string.h> in front)
#include<string.h>
f(n,s)char*s;{int l=strlen(s),d=n<0?0:2,m=d--,p;do for(p=m?0:l-1;p!=(m?l:-1);p+=d)putchar(s[p]);while(!n||(n-=d));}

Try it online!

Without #include<string.h> we get an implicit prototype for strlen that returns int, but strlen is size_t (at least nowadays, not perfectly sure about k&r or c89, but I believe, it returned int in the old days).
The missing #include <stdio.h> isn't a problem, because due to integer promotion, the default prototype will be int putchar(int) which is exactly what we want.

QBIC, 36 bytes
Lot ging on here, and QBIC/QBasic just doesn't have the syntax to deal with such conditions elegantly.
~:<0|;=_fA}[abs(a)|Z=Z+A]~a|_X}{?A';

Explanation:
~:<0|       IF cmd line arg 'a' is negative
  ;=_fA         Make cmd line arg A$ into its reverse
}           Close the IF (this eliminates the need for a | fuction terminator on _f)
[abs(a)|    FOR b = 1 to (abs(a) (hammering out negatives)
  Z=Z+A         Add A$ to Z$ (on exit, Z$ is printed explicitly)
]           NEXT
~a|_X       IF a is non-zero, terminate the program
}           END IF
{?A';       If we're here, just start a DO-loop and keep on printing the input.

Retina, 49 bytes
/¶-/&V`^.+
/¶0/&//+>G0`
~`(.+)¶-*(\d+)
.-$2+>K`$1

Input format: takes in the string, followed by a newline, followed by the number.
Try it online!
Explanation:
/¶-/&V`^.+

The /¶-/& runs this line only if the number is negative. V is the reverse stage, and it reverses ^.+, which matches the string (. matches every character apart from newlines).
/¶0/&//+>G0`

The /¶0/& runs this line only if the number is 0. //+> starts an infinite loop, which prints the working string after each iteration. G0 takes the string and discards the number; it does this infinitely, printing every time.
~`...

This marks code that will generate a string; the program evaluates the string as Retina code after.
(.+)¶-*(\d+)
.-$2+>K`$1

(.+)¶-*(\d+) matches the whole string and puts the string in capturing group 1 and the number in capturing group 2. .-$2+>K` $1 generates the Retina code to be run: .  turns implicit output off (otherwise the string would be printed n+1 times), -$2+ sets a repeat loop that repeats for {capturing group 2} times. The minus at the beginning turns the number into a negative number, as this disables the convergence functionality in the loop, which would stop it after the 1st iteration. > sets this loop to print after each iteration. The rest of the code is just to print the string.

Perl 6, 44 bytes
{[$^s.flip,$s,$s Zxx-$^n,Inf,$n][$n.sign+1]}

Try it online!
Anonymous code block that takes a number and a string and returns a (possibly infinite) list

Pip, 16 bytes
TaOba<0?RbbX:ABa

Replit! Or, here's a 17-byte equivalent in Pip Classic: Try it online!
Explanation
TaOba<0?RbbX:ABa
                  a and b are the two command-line arguments
Ta                Loop until a is truthy:
  Ob               Output b without a newline
                  If a=0, this loops infinitely; otherwise, it doesn't loop at all
    a<0?          If a is negative:
        Rb         b reversed
                  Else (if a is positive):
          b        b
           X:     Repeat that string this many times:
             ABa  Absolute value of a

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

sort: votes


text:
Reflective binary ordering
The reverse of an n-bit number is just its n binary digits in reverse order:

001010010 → 010010100

Given a number n, generate all n-bit integers ([0, 2n-1]) in an arbitrary order, with only one restriction: there must be a splitting point such that  the reverse of an integer is on the opposite side of the splitting point. Integers which are their own reverse must come before the splitting point.
Other than this single splitting point there are no restrictions, all the integers before or after it may come in whatever order you desire.
Example for 4 bits (you don't have to generate this order):
0000, 0001, 0010, 0011, 0101, 0110, 0111, 1001, 1011, 1111,
0100, 1000, 1010, 1100, 1101, 1110

You may output the integers as their binary digits or just as integers. You don't have to explicitly output the splitting point.

Could you add the splitting point to your example?

To clarify: you want all the n-bit numbers to be partitioned into two subsets, with the property that a number and its reverse are always in different subsets (other than numbers that are their own reverses). Is that right?

@Lembik It's already there: the newline.

@GregMartin Correct.

JavaScript (ES6), 129 114 bytes
f=n=>[...Array(p=1<<n)].map((_,i)=>(p+i).toString(2).slice(1)).sort((a,b)=>g(a)-g(b),g=a=>[...a].reverse().join``<a)

I appear to have stumbled on the code that happens to generate the given example for 4 bits. Edit: Saved 15 bytes thanks to @ConorO'Brien.

Jelly, 13 bytes
2ṗ’µżUṢ€QZ;/Q

Try it online!
Group with their reflections, uniquify and sort, then zip.

PHP, 80 Bytes
Make 2 Groups in a 2D Array
After the first Group is the splitting point
In the first group are the integers with their own reverse and the integers that are lower than their reverse
for(;$i<1<<$argn;)$r[strrev($b=sprintf("%0{$argn}b",$i++))<$b][]=$b;print_r($r);

Try it online!
PHP>=7.0, 82 Bytes
Make 3 Groups in a 2D Array
After the second Group is the splitting point
In the first group are the integers with their own reverse
In the second group are the integers that are lower than their reverse
Use the Spaceship Operator
for(;$i<2**$argn;)$r[strrev($b=sprintf("%0{$argn}b",$i++))<=>$b][]=$b;print_r($r);

Try it online!

Mathematica, 51 bytes (Windows ANSI encoding)
±n_:=SortBy[{0,1}~Tuples~n,(#-Reverse@#).Range@n!&]

Defines a unary function ± taking a positive integer argument and returning a list of lists of 0s and 1s. For example, ±4 returns
{{1, 1, 0, 0}, {1, 0, 0, 0}, {1, 1, 1, 0}, {1, 0, 1, 0}, {0, 1, 0, 0},
 {1, 1, 0, 1}, {0, 0, 0, 0}, {0, 1, 1, 0}, {1, 0, 0, 1}, {1, 1, 1, 1},
 {0, 0, 1, 0}, {1, 0, 1, 1}, {0, 1, 0, 1}, {0, 0, 0, 1}, {0, 1, 1, 1},
 {0, 0, 1, 1}}

SortBy[{0,1}~Tuples~n,...] takes the set of all length-n lists of 0s and 1s and sorts them according to the values that the function ... takes on each such list. It suffices to find a function whose values on a list and its reverse are negatives of each other and whose value is 0 only if the list is its own reverse. Taking the dot product of (the list minus its reverse) and (a sufficiently unbalanced vector, such as Range@n! which is {1!, 2!, ..., n!}) does the trick.

Pyth, 14 bytes
o&NcNijN2 .5^2

Try it online
How it works
Sort by x / f(x), where f(x0⋅20 + x1⋅21 + x2⋅22 + …) = x0⋅0.50 + x1⋅0.51 + x2⋅0.52 + … (for binary digits xi ∈ {0, 1}).  Interestingly, this same ordering works for all n, but with different splitting points.  If x is less than or equal to its n bit reversal, then x / f(x) ≤ 2n − 1, otherwise x / f(x) > 2n − 1.
o           ^2Q   sort values [0, …, 2**n-1] by this key:
 &N                 if value is 0, key is 0
   cN               else, key is value divided by
     i    .5          the base 0.5 number whose digits are
      j 2             the base 2 digits of
       N              value

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/


text:
Is there an unmatched parenthesis in this String?
Introduction
Given a String containing an arithmetic expression, your task is to output a truthy or falsey value based on whether it contains unmatched parentheses.

Input
Your program should take in a String containing an arithmetic expression. It may take input in any way except assuming it to be present in a pre-defined variable. Reading from file, input box, modal dialog box etc. is fine. Taking input as function argument is allowed as well!

Output
Your program should output a truthy or falsey value based on whether the input String contains any unmatched parentheses. It may output in any way except except writing to a variable. Writing to file, screen, console, terminal etc. is allowed. Outputting with function return is allowed as well!

Rules

For the purpose of this challenge, a parentheses is defined as any one of [, {, (, ), }, ]. A parentheses is said to be unmatched if it does not have any corresponding opening/closing parentheses. For example, [1+3 does contain unmatched parentheses.
Ordering of parentheses does not matter in this challenge. So, ]1+3[ does not contain any unmatched parentheses. {[)(}] doesn't, as well.
The input String will only contain following characters : {, [, (, ), ], }, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, +, -, *, / and ^.
Your program should output a truthy value if the input String contains an unmatched parentheses.
Your program should output a falsey value if the input String does not contain an unmatched parentheses.
You must specify the truthy and falsey values in your post.
The input String will never be empty.
If the input String does not contain any parentheses, your program should output falsey value.
Standard loopholes apply.

Test Cases
Input            ->            Output

"{"                            Truthy
"{{{{}}"                       Truthy
"{[]}"                         Falsey
"[]]["                         Falsey
")()()()("                     Falsey
"1+4"                          Falsey
"{)"                           Truthy
"([)]"                         Falsey
"(()"                          Truthy
"2*{10+4^3+(10+3)"             Truthy
"-6+[18-{4*(9-6)}/3]"          Falsey
"-6+[18-{4*)9-6](/3}"          Falsey

Winning Criterion
This is code-golf, so the shortest code in bytes wins!

Note
I'll be adding a similar challenge but in which order will matter, after some time! Stay Tuned!

I'm 99% sure this is a dupe but I can't find the older one.

@StephenS This one is the one that came to my mind, but I don't think it's quite a dupe...

Related

Can I use inconsistent values, given that they are always appropriately truthy or falsey?

@EriktheOutgolfer Yes, you can!

@EriktheOutgolfer I've received a different answer to that question in the past. Maybe we should clarify on this meta post for a consensus?

@StephenS I don't think that this one is a dupe but the order will matter one is almost definitely a dupe of the one ETHproductions linked to

Possible duplicate of Are the brackets fully matched?

@StephenS I think the fact that this is entirely orderless makes it quite different. Neither ][ or ([)] would be valid in the other challenge but are valid here.

This question's title should really make it clearer that order is irrelevant. That's not what most people think about when talking about unmatched parentheses.

Is (() truthy or falsey? The rules and test cases don't make it clear whether the count of parentheses is important. All answers seem to assume that the count matters though.

@Arjun The rules say that a paren is unmatched if "it doesn't have a corresponding opening/closing parentheses" in the string. In ((), each paren arguably has a corresponding pair; the ) is just used as a pair of two different (s. This interpretation of the task is not refuted by any test case, since the only case that has multiple parens of the same type happens to have a matching count.

@Zgarb Sorry, I misinterpreted your comment. (() should return truthy as it contains an unmatched paren. Thanks for pointing that out. I will add that to the test cases. :)

05AB1E, 14 10 bytes
žuS¢2ô€ËP_

Try it online!
-4 thanks to Adnan.
1 for truthy, 0 for falsey.
Its main power point is the žu builtin.
Explanation:
žuS¢2ô€ËP_
žu         Push '()<>[]{}'
  S        Split into individual chars
   ¢       Count occurrences of each char in the input. For <>, the count will always be 0
    2      Push 2
     ô     Split the array into pieces of that length, corresponding to respective matching brackets
      €    Map next command over the chunks
       Ë   Check if all elements are equal. If equal, it means that the corresponding bracket type is matched. <> will always be matched, since they will never occur in the input, so they'll both always have 0 occurrences
        P  Take the product of the boolean values. <> won't affect this, since it would always be 1
         _ Logically negate, convert 1 to 0 and non-1 (always 0 in this case) to 1

Who doesn't have a command that pushes ()<>[]{}?

@cairdcoinheringaahing CJam doesn't, but you can get it with [{(<>)}]` .

@Challenger5 You just correctly ordered the brackets so that the (<>) won't affect the stack since it's in a code block, and then the codeblock goes into the list? Well, this challenge doesn't have <>, so you could just use [{()}]\`` or {[()]}`or even{([])}`. Oh wait a sec, you can actually use {()}a``.

@EriktheOutgolfer Yeah, I forgot about that.

@Arjun They're not handled, since they'll never be in the input.

Python 2, 47 bytes
lambda s:map(s.count,'([{')!=map(s.count,')]}')

Try it online! Test cases from musicman523.
Checks if list of counts for each type of open paren matches that for the corresponding close parens.
The program is one byte longer
q=input().count
print map(q,'([{')!=map(q,')]}')

Python 2, 61 bytes
Saved 4 bytes thanks to WheatWizard!
lambda s:any(s.count(i)^s.count(j)for i,j in['{}','[]','()'])

Try it online!

This can be made slightly shorter by ditching r.  Try it online

Thanks! I changed it to match the two characters into separate variables, removing the indexing and therefore saving 4 more bytes.

Jelly, 17 bytes
ċÐ€“[]{}()”s2E€ẠṆ

Try it online!
1 is truthy, 0 is falsey.

Python 3, 62 61 bytes
Surprisingly pythonic for codegolf.
lambda x:all(x.count(y)-x.count(z)for y,z in("[]","()","{}"))

-1 byte thanks to @musicman523

You can use musicman's trick to make this shorter. TIO

And now we have the same answers :) Although your post came before my edit, I did come up with it independently

Yeah, I'll leave it as is.

You could change == to - and keep all, then we have the same byte count but different answers

@musicman523 Alright then!

MATL, 15 bytes
!'[](){}'=sHeda

This outputs 1 if unmatched, 0 if matched.
Try it online!
Explanation
!          % Implicitly input string. Tranpose into vertical vector of chars
'[](){}'   % Push this string
=          % Compare for equalty, with broadcast
s          % Sum of each column. This gives the count of each char of '[](){}'
He         % Reshape as a two-row column (in column-major order)
d          % Difference of the two entries of each column
a          % Any: gives true (1) if some entry is nonzero, false (0) otherwise
           % Implicitly display

Javascript, 71 bytes:
x=>['()','[]','{}'].some(a=>x.split(a[0]).length!=x.split(a[1]).length)

Ruby, 58+1 = 59 bytes
+1 byte for the -n flag.
f=->c{$_.count c}
p %w"() [] {}".any?{|s|f[s[0]]!=f[s[1]]}

Try it online!

Javascript 57 bytes
x=>(g=z=>x.split(z).length,g`(`-g`)`|g`[`-g`]`|g`{`-g`}`)

Starting from asgallant's solution.
Matching returns 0. Non-matching returns non-zero.

Python 2, 85 bytes
I can definitely golf this using subtraction instead but I'm running out of time. D:
lambda s,c=str.count:(c(s,'(')!=c(s,')'))or(c(s,'{')!=c(s,'}'))or(c(s,'[')!=c(s,']'))

Try it online!

All instances of != can be -.

This answer has already been out-golfed by a far better answer. Hence, I'd rather not try to golf this.

Retina, 26 bytes
O`.
+`\(\)|\[]|{}

[^*-9^]

Try it online!
Explanation
O`.

Sort all characters so that corresponding brackets are adjacent (since neither \ nor | can appear in the input).
+`\(\)|\[]|{}

Repeatedly remove pairs of matching brackets.
[^*-9^]

Try to match any remaining brackets (the regex matches anything that isn't a ^ or in the ASCII range from * to 9 which, among the valid input characters, are only the 6 brackets). If we find any, that means that there was an unmatched one. The result will be a positive integer if the input was unbalanced, 0 otherwise.

{{{{}} is matched? Your code return 0 on that input.

@user202729 Thanks, it should be fixed now (luckily at the same byte count).

PowerShell, 95 86 bytes
param($s)$h=@{};[char[]]$s|%{$h["$_"]++};$h.'['-$h.']'-or$h.'('-$h.')'-or$h.'{'-$h.'}'

Try it online!
Previous version
param($s)switch([char[]]$s){'('{$k++}')'{$k--}'['{$l++}']'{$l--}'{'{$m++}'}'{$m--}}$k-or$l-or$m

Try it online!

Visual Basic.Net, 218 192 Bytes
function t(m as string,v as string)
return Len(m)-Len(m.Replace(v,""))
end function
function b(q as String)
return not(t(q,"{")=t(q,"}")and t(q,"[")=t(q,"]")and t(q,"(")=t(q,")"))
end function

"around 218 bytes" I count 217. Also, if (expr) then return false else return true can be return not (expr).

"around 218 bytes" I count 192. Do you have a trailing newline?

I dont know how to put line through 218

<s>218</s> works.

well I don't have trailing newline

PHP>7.1, 124 Bytes
$t=!!$p=preg_replace("#[\d+/*^-]#","",$argn);for(;$p;$p=substr($p,1,-1))$t*=chr(($o=ord($p[0]))%5?$o+2:$o+1)==$p[-1];echo$t;

Instead of #[\d+/*^-] you can use [^]{()}[] or [^\p{Pe}\p{Ps}]
IntlChar::charMirror IntlChar::charMirror($p[0])==$p[-1] instead of chr(($o=ord($p[0]))%5?$o+2:$o+1)==$p[-1] checks not if the char is an openining or closing punctation so we can not use it without additional check &$p[0]<$p[-1] +8 Bytes
Online Version
PHP, 151 bytes
A full Regex Solution
for($c=$t=!!$p=($r=preg_replace)("#[^]{()}[]#","",$argn);$p&&$c;)$p=$r(["#^{(.*)}$#","#^\[(.*)]$#","#^\((.*)\)$#"],[$a="$1",$a,$a],$p,1,$c);echo$t&!$p;

Try it online!

Clojure, 65 bytes
 #(let[f(frequencies %)](some not(map =(map f"[{(")(map f"]})"))))

So long keywords :/ Returns nil for falsy and true for truthy.

Javascript, 149 140 bytes
New solution incorporates bitwise operators (Thanks, arjun) and calculates if they are not equal, and uses or instead of and.
function f(x){return x.split("(").length!=x.split(")").length|x.split("{").length!=x.split("}").lengt|x.split("[").length!=x.split("]").length}

I don't yet have a snippet for this, so I'm not sure it works yet.
OLD SOLUTION:
function f(x){return !(x.split("(").length==x.split(")").length&&x.split("{").length==x.split("}").length&&x.split("[").length==x.split("]").length)}

Checks if there are the same amount of one bracket and another, and then returns the opposite.

function f(x){return !(x.split("(").length==x.split(")").length&&x.split("{").length==x.split("}").length&&x.split("[").length==x.split("]").length)}

/*"{"                            Truthy
"{[]}"                         Falsey
"[]]["                         Falsey
")()()()("                     Falsey
"1+4"                          Falsey
"{)"                           Truthy
"([)]"                         Falsey
"2*{10+4^3+(10+3)"             Truthy
"-6+[18-{4*(9-6)}/3]"          Falsey
"-6+[18-{4*)9-6](/3}"          Falsey*/

console.log(f("{"));
console.log(f("{[]}"));
console.log(f("[]]["));
console.log(f(")()()()("));
console.log(f("1+4"));
console.log(f("{)"));
console.log(f("([)]"));
console.log(f("2*{10+4^3+(10+3)"));
console.log(f("-6+[18-{4*(9-6)}/3]"));
console.log(f("-6+[18-{4*)9-6](/3}"));

I can save 3 bytes by making every == into a != And changing && to || but I'm on mobile

I think, bitwise operators instead of logical ones will do fine. Like & instead of && and | instead of ||.

You can remove the outermost paren after return !.

Do you even need a space after return?

I think you need that space otherwise JavaScript will count it as rerurnx and throw an error

C#, 87 bytes
using System.Linq;s=>s.Count(c=>c=='['|c=='{'|c=='(')==s.Count(c=>c==']'|c=='}'|c==')')

Pretty self explanatory, just test to see if the of left parenthesis equals the count of right parenthesis.

Please check on {).


text:
Output the nth Even Perfect Number
Challenge
Given an integer, n, as input where 0 <= n <= 2^10, output the nth even perfect number.
Perfect Numbers
A perfect number is a number, x where the sum of its factors (excluding itself) equals x. For example, 6:
6: 1, 2, 3, 6

And, of course, 1 + 2 + 3 = 6, so 6 is perfect.
If a perfect number, x, is even, x mod 2 = 0.
Examples
The following are the first 10 even perfect numbers:
6
28
496
8128
33550336
8589869056
137438691328
2305843008139952128
2658455991569831744654692615953842176
191561942608236107294793378084303638130997321548169216

Note that you may index this however you wish: 6 may be the 1st or the 0th even perfect number.
Winning
Shortest code in bytes wins.

Is there any odd perfect number?

@LeakyNun Yes, it appears there is

@LeakyNun I think, that is an open question. If this question was output the nth odd perfect number... You would need a billion rep bounty to get it solved. http://blogs.ams.org/mathgradblog/2013/07/25/odd-perfect-numbers-exist/ (none exist below 10^300)

What is the smallest odd perfect number?

Can we assume that there are no odd perfect numbers?

Is there an efficient implementation of this possible, I would imagine some intersting math can happen here.

@RohanJhunjhunwala There's an efficient-ish formula for even perfect numbers that involves Mersenne primes.

@Dennis What does an even perfect number mean here?

A perfect number that is divisible by 2.

@Dennis It's that simple? Oh.

An even number n is perfect iff there is a Mersenne prime p such that n = p(p+1)/2. There is no such formula for odd perfect numbers; moreover, it is unknown if odd perfect numbers even exist.

@Dennis So, for the range 0 <= n <= 2^10 it's perfectly acceptable to use that formula

Related. Related.

Not quite. There are only 49 known Mersenne primes.

If our language is bounded for a maximum number of 2^64-1, are we allowed to assume that the output will never be larger than that?

How should one respond to an input of $n=60?$

@RossMillikan What's special about n=60?

@BetaDecay:  it is greater than $49$, so the 60th perfect number is not known.

Jelly, 7 bytes
6Æṣ=$#Ṫ

Try it online!
How it works
6Æṣ=$#Ṫ  Main link. Argument: n

6        Set the return value to 6.
     #   Execute the link to the left with argument k = 6, 7, 8, ... until n
         values of k result in a truthy value. Yield the array of matches.
    $        Combine the two links to the left into a monadic chain.
 Æṣ              Compute the sum of k's proper divisors.
   =             Compare the result with k.
      Ṫ  Tail; extract the last match.

So many builtins regarding divisors...

Mathematica, 13 bytes
Not surprisingly, there is a built-in.
PerfectNumber

Example:
In[1]:= PerfectNumber[18]

Out[1]= 33570832131986724437010877211080384841138028499879725454996241573482158\

>    45044404288204877880943769038844953577426084988557369475990617384115743842\

>    47301308070476236559422361748505091085378276585906423254824947614731965790\

>    74656099918600764404702181660294469121778737965822199901663478093006075022\

>    35922320184998563614417718592540207818507301504509772708485946474363553778\

>    15002849158802448863064617859829560720600134749556178514816801859885571366\

>    09224841817877083608951191123174885226416130683197710667392351007374503755\

>    40335253147622794359007165170269759424103195552989897121800121464177467313\

>    49444715625609571796578815564191221029354502997518133405151709561679510954\

>    53649485576150660101689160658011770193274226308280507786835049549112576654\

>    51011967045674593989019420525517538448448990932896764698816315598247156499\

>    81962616327512831278795091980742531934095804545624886643834653798850027355\

>    06153988851506645137759275553988219425439764732399824712438125054117523837\

>    43825674443705501944105100648997234160911797840456379499200487305751845574\

>    87014449512383771396204942879824895298272331406370148374088561561995154576\

>    69607964052126908149265601786094447595560440059050091763547114092255371397\

>    42580786755435211254219478481549478427620117084594927467463298521042107553\

>    17849183589266903954636497214522654057134843880439116344854323586388066453\

>    13826206591131266232422007835577345584225720310518698143376736219283021119\

>    28761789614688558486006504887631570108879621959364082631162227332803560330\

>    94756423908044994601567978553610182466961012539222545672409083153854682409\

>    31846166962495983407607141601251889544407008815874744654769507268678051757\

>    74695689121248545626112138666740771113961907153092335582317866270537439303\

>    50490226038824797423347994071302801487692985977437781930503487497407869280\

>    96033906295910199238181338557856978191860647256209708168229116156300978059\

>    19702685572687764976707268496046345276316038409383829227754491185785965832\

>    8888332628525056

I think there is a standard loophole for that?

@PaŭloEbermann correct, with 19 downvotes and a comment with 94 upvotes approving of it: https://codegolf.meta.stackexchange.com/a/1078/32933

MATL, 15 bytes
`@Z\s@E=vtsG<}n

Very slow. It keeps trying increasing numbers one by one until the n-th perfect number is found.
Try it online!
Explanation
`        % Do...while
  @      %   Push iteration index, k (starting at 1)
  Z\     %   Array of divisors
  s      %   Sum
  @E     %   Push k. Multiply by 2
  =      %   Equal? If so, k is a perfect number
  v      %   Concatenate vertically. This gradually builds an array which at the k-th
         %   iteration contains k zero/one values, where ones indicate perfect numbers
  ts     %   Duplicate. Sum of array
  G<     %   Push input. Less than? This is the loop condition: if true, proceed with
         %   next iteration
}        % Finally (execute right before exiting loop)
  n      %   Number of elements of the array
         % End (implicit). Display (implicit)

Pyth, 13 bytes
e.fqsf!%ZTStZ

Try it online!
Please do not try any higher number. It just tests the even numbers one by one.

05AB1E, 8 bytes
µNNÑ¨OQ½

Try it online!
Explanation
µ          # loop over increasing N until counter equals input
 N         # push N
  NÑ       # push factors of N
    ¨      # remove last factor (itself)
     O     # sum factors
      Q    # compare the sum to N for equality
       ½   # if true, increase counter

Python 2,  198  153 83 78 77 75 74 bytes
i=input()
j=0
while i:j+=1;i-=sum(x*(j%x<1)for x in range(1,j))==j
print j

Try it online!
Now it just reads like psuedocode.

Saved 45 Countless Bytes because @Leaky Nun taught me about the sum function and list comprehension.
Saved 2 bytes thanks to @shooqie's suggestion to remove the uncessary brackets.

We just iterate through every even number until we have found n perfect numbers.

notice that your g is actually just sum.

@LeakyNun serves me right, for not knowing the python libraries. I really should learn more than just java and SILOS.

Also, I've replaced your f with a list comprehension

more golfings

no need for k, just decrement i.

@LeakyNun \o/ we you broke 80 bytes!

time to learn more about list comprehension

And you can replace ==0 by <1

@LeakyNun Does python have any standard libraries to factorize a number?

Also, you don't need square brackets (at least in Python 3)

It doesn't have a standard library to factorize a number; if it had, it would probably cost more bytes to import it.

74 bytes

\o/ but it,s a shame we are still 6 bytes away from java script. Perhaps this can become an anonymous function or something?

PHP, 111 Bytes
0-Indexing
Works with the concept that a perfect number is a number where n=x*y
x=2^i and y=2^(i+1)-1 and y must be prime
for(;!$r[$argn];$u?:$r[]=$z)for($z=2**++$n*($y=2**($n+1)-1),$u=0,$j=1;$j++<sqrt($y);)$y%$j?:$u++;echo$r[$argn];

Try it online!

Python 3, 69 bytes
f=lambda n,k=1:n and-~f(n-(sum(j>>k%j*j for j in range(1,k))==k),k+1)

Try it online!

Scala, 103 bytes
n=>Stream.from(1).filter(_%2==0).filter(x=>Stream.from(1).take(x-1).filter(x%_==0).sum==x).drop(n).head

Haskell, 61 Bytes
(!!)(filter(\x->x==sum[n|n<-[1..x-1],x`mod`n==0]||x==1)[1..])

Since the index can start at 0, you don't need the ||x==1. You can also save bytes by moving the !! just before the closing parenthesis to make an operator section, and by replacing the filter with another list comprehension.

Haskell, 52 bytes
([n|n<-[1..],n==sum[d|d<-[1..div n 2],mod n d<1]]!!)

Try it online!
Starts at n = 0. Not particularly fast

By our consensus, it's valid to omit the f= from the byte count.

JavaScript (ES6), 68 bytes
n=>eval(`for(x=5;n;s||n--)for(f=s=++x;f--;)(x/f-(x/f|0))||(s-=f);x`)

F=n=>eval('for(x=5;n;s||n--)for(f=s=++x;f--;)(x/f-(x/f|0))||(s-=f);x')

console.log(
  F(1),
  F(2),
  F(3),
  //F(4),
  //F(5),
)

Perl 6, 42 bytes
{(grep {$_==[+] grep $_%%*,^$_},^∞)[$_]}

The input index is 1-based.

Clojure, 79 bytes
#(nth(for[i(range):when(=(apply +(for[j(range 1 i):when(=(mod i j)0)]j))i)]i)%)

Following the spec, heavy usage of for's :when condition.

PowerShell, 152 bytes
$ErrorActionPreference='SilentlyContinue'
function p{param($x)(1..($x-1)|?{!($x%$_)})|%{$s+=$_};$s}
1..$args[0]|%{if(((p -x $_)-eq$_)-and(!($_%2))){$_}}

Try it online!


text:
Evaluate modular power towers
Given two numbers n and m, evaluate the infinite power tower:

n^(n+1)^(n+2)^(n+3)^(n+4)^... mod m

Keep in mind that ^ is right-associative. So 2^3^4 = 2^(3^4). Now how can  you possibly assign a value to an infinite sequence of right-associative operators?
Define f(n,m,i) as the power tower containing the first i terms of the infinite power tower. Then there is some constant C such that for every i > C, f(n,m,i) = f(n,m,C). So you could say the infinite power tower converges on a certain value. We're interested in that value.

Your program must be able to compute n = 2017, m = 10^10 in under 10 seconds on a reasonable modern PC. That is, you should implement an actual algorithm, no bruteforcing.
You may assume that n < 230 and m < 250 for the numerical limits in your programming language, but your algorithm must theoretically work for any size n, m. However your program must be correct for inputs within these size limits, intermediate value overflows are not excused if the inputs are within these limits.
Examples:
2, 10^15
566088170340352

4, 3^20
4

32, 524287
16

Tip (for contenders): n and m are not guaranteed to be co-prime.

10^10 (and 10^20, and potentially 3^20 for signed integers) is larger than many languages' default integer types. Is it required that this large of an input be supported?

@orlp Does that "yes" include 10^20? Because that doesn't fit in a 64-bit integer, so if you want to require it, I'd suggest pointing it out explicitly, because otherwise you're going to get a lot of invalid answers by people just assuming that 64 bit integers are going to be accurate enough.

Either way, what is the largest input we need to support?

@Doorknob I added more lenient limits to the challenge. However your algorithm must theoretically work for any size m, n.

Pyth, 23 bytes
M&tG.^HsgBu-G/GH{PGGhHG

Defines a function g, taking m and n in that order.
Try it online
How it works
M&tG.^HsgBu-G/GH{PGGhHG
M                         def g(G, H):
 &tG                        0 if G == 1, else …
                 PG         prime factors of G
                {           deduplicate that
          u-G/GH   G        reduce that on lambda G,H:G-G/H, starting at G
                              (this gives the Euler totient φ(G))
        gB          hH      bifurcate: two-element list [that, g(that, H + 1)]
       s                    sum
    .^H               G     H^that mod G

Python 2, 109 76 bytes
import sympy
def g(n,m):j=sympy.totient(m);return m-1and pow(n,j+g(n+1,j),m)

Try it online!
Why it works
We use the following generalization of Euler’s theorem.
Lemma. n2φ(m) ≡ nφ(m) (mod m) for all n (whether or not n is coprime to m).
Proof: For all prime powers pk dividing m,

If p divides n, then because φ(m) ≥ φ(pk) = pk − 1(p − 1) ≥ 2k − 1 ≥ k, we have n2φ(m) ≡ 0 ≡ nφ(m) (mod pk).
Otherwise, because φ(pk) divides φ(m), Euler’s theorem gives n2φ(m) ≡ 1 ≡ nφ(m) (mod pk).

Therefore, n2φ(m) ≡ nφ(m) (mod m).
Corollary. If k ≥ φ(m), then nk ≡ nφ(m) + (k mod φ(m)) (mod m).
Proof: If k ≥ 2φ(m), the lemma gives nk = n2φ(m)nk - 2φ(m) ≡ nφ(m)nk - 2φ(m) = nk - φ(m) (mod m) and we repeat until the exponent is less than 2φ(m).

How does this handle the case where the base and modulo isn't coprime? P.S. sympy has totient function.

@orlp I’ve added a proof. Not sure how I missed sympy.totient.

I see now. Nice method!

Haskell, 156 bytes
(?) takes two Integers and returns an Integer, use as (10^10)?2017 (reversed order compared to OP.)
1?n=0
m?n=n&m$m#2+m#2?(n+1)
1#_=1
n#p|m<-until((<2).gcd p)(`div`p)n=m#(p+1)*1`max`div(n*p-n)(p*m)
(_&_)0=1
(x&m)y|(a,b)<-divMod y 2=mod(x^b*(mod(x*x)m&m)a)m

Try it online! (I put the cases to test in the header this time, since they use exponentiation notation.)
Curiously the slowest test case isn't the one with a speed limit (that's almost instant), but the 524287 ? 32 one, because 524287 is a much larger prime than appears in the factors of the other test cases.
How it works

(x&m)y is x^y `mod` m, or power mod, using exponentiation by squaring.
n#p is the Euler totient function of n, assuming n has no smaller prime factors than p.

m is n with all p factors divided out.
If there are k such factors, the totient should itself get a corresponding factor (p-1)*p^(k-1), which is calculated as div(n*p-n)(p*m).
1`max`... handles the case where n wasn't actually divisible by p, which makes the other argument of max equal to 0.

The main function m?n uses that when y is large enough, n^y `mod` m is the same as n^(t+(y`mod`t)) `mod` m, when t is the totient of m. (The t+ is needed for those prime factors n and m have in common, which all get maximized.)
The algorithm stops because iterated totient functions eventually hit 1.

Mathematica, 55 bytes
n_~f~1=0;n_~f~m_:=PowerMod[n,(t=EulerPhi@m)+f[n+1,t],m]

Examples:
In[1]:= n_~f~1=0;n_~f~m_:=PowerMod[n,(t=EulerPhi@m)+f[n+1,t],m]

In[2]:= f[2, 10^15]

Out[2]= 566088170340352

In[3]:= f[4, 3^20]

Out[3]= 4

In[4]:= f[32, 524287]

Out[4]= 16

In[5]:= f[2017, 10^10]

Out[5]= 7395978241

Pari/GP, 56 bytes
f(n,m)=if(m-1,lift(Mod(n,m)^((t=eulerphi(m))+f(n+1,t))))

Try it online!


text:
Dankify this string
Challenge
An ascii string is made 'dank' when exactly one space is inserted between any two consecutive letters and all capital letters are replaced with lowercase ones. In this challenge I would like you to write a program that takes a string (not necessarily 'dank') as input and outputs a 'dank' version of that string.
Specification
Your program should take as input an ascii string of arbitrary length and output another ascii string.
A string is classed as dank when it contains only spaces and lowercase letters such that there is exactly one space between any two consecutive letters. To make a string dank you'll have to strip all non-alphabetical characters, replace capital letters with their lowercase counterparts, then insert spaces between all the characters.
Example
"aesthetic" > "a e s t h e t i c"
"How are you?" > "h o w a r e y o u"
"drop // top" > "d r o p t o p"

Winning criterion
Code golf so the shortest code in bytes wins.
g o o d l u c k

Highly related

Hey! I would try putting your challenges on the Sandbox first so that people who have been around for years can recognize them as dupes before you post them :)

Differences: the string has to be converted to lowercase, all non-alphabetical characters have to be removed, there's no need for a trailing space. I personally would not close this as a dupe.

@Stephen Ah, sorry, will do so next time. :)

Can you add a test case where the input has multiple spaces in a row? I can imagine some algorithms giving the wrong output on that one.

May we assume the input contains at least one alphabetical char?

@ETH No, it should be able to take a string of any length.

Oh, OK, you should probably clarify that in the post. Welcome to the site, btw! Not sure why this is getting so many downvotes, it's a pretty good first challenge...

@xnor - could you explain your reasoning? I do agree that the target is very similar, but am not 100% sure that they are duplicates (see ETH's differences). However, a reopen vote from me would (I believe) hammer it back open (not the most productive thing to do).

@JonathanAllan I think people's difference of opinion on the dupe is whether lowercasing and removing non-letters make the challenge different enough. I think these things should be judged on an absolute metric. If two meaty challenges differed in that output processing, people would surely find them very similar and that code from one could be minimally modified to submit to the other. Here, the task is so simple that the changes look significant only by comparison. As for hammering, I'm just stuck with my dupe votes doing that. Feel free to hammer it open.

05AB1E, 6 5 bytes
-1 byte thanks to Erik
láSðý

Explanation:
l        Convert to lowercase
 á       Remove all non-alphabetic characters
  S      Get characters as array
   ðý    Join by spaces

Try it online!

á is a builtin to do AuA«Ã, so láSðý or álSðý should suffice...yet the challenge turned out to be a dupe.

Decimal, 92 bytes
91D31030012090D415D56112032D41D625230012122D416D5291D5230012097D417D5291D52301212032D301291D

Whew, that was fun. Thanks for the challenge - it helped me develop Decimal into a fully working language. (While writing this, I realized a few flaws. Just bugs and such.)
Ungolfed:
91D
 310 300    ; input to stack, duplicate
 12090D     ; push CHAR 'Z' to stack
 415D       ; compare <, pop values used, push result

 5          ; if truthy
  61        ;  put result into memory
  12032D    ;  push CHAR 32 to stack
  41D       ;  math +, pop values used, push result
  62        ;  pop memory to stack
 5          ; endif

 2          ; pop

 300        ; duplicate DSI
 12122D     ; push CHAR 'z' to stack
 416D       ; compare >, pop values used, push result
 5          ; if truthy
  291D      ; pop, restart
 5          ; endif

 2          ; pop

 300        ; duplicate DSI
 12097D     ; push CHAR 'a' to stack
 417D       ; compare <, pop values uesd, push result
 5          ; if truthy
  291D      ; pop, restart
 5          ; endif

 2          ; pop

 3012       ; print, pop
 12032D3012 ; push CHAR ' ', print, pop
91D

Try it online!

Japt, 16 5 + 1 (-S flag) = 6 bytes
Thanks to obakaron for saving 10 bytes
;v fE

Try it online!

What if you put the v first? ;)

Also, you can replace the "[^A-Z]"'i with "%l" to save a few bytes

@ETHproductions if he puts the v first, trump wins the election.

@cairdcoinheringaahing like that would change anything... :P

@ETHproductions what do you mean? The election is happening tomorrow. Time difference, man...

;v fF + -S flag for 6 bytes http://ethproductions.github.io/japt/?v=1.4.5&code=O3YgZkY=&input=IkhvdyBhcmUgeW91PyItUw==

Wow, thanks a lot for that.

Python 3.5, 46 49 47 bytes
print(*[i for i in input().lower()if'`'<i<'{'])

Try it online!

Jelly, 6 bytes
ŒlfØaK

A monadic link taking and returning lists of characters (or a program that prints the result).
Try it online!
How?
ŒlfØaK - Main link: list of characters, s
Œl     - convert to lowercase (vectorises)
   Øa  - yield lowercase alphabet: "abcdefghijklmnopqrstuvwxyz"
  f    - filter keep
     K - join with spaces
       - if running as a program implicit print

Perl 6, 18 bytes
{m:g/<:L>/.Str.lc}

m:g/<:L>/ produces a list of all of the letters in the input string; .Str converts the list into a string with a space between each element; and .lc converts the string to lower case.

Pyth, 6 bytes
jd@Gr0

Try it here!

Python 2, 55 50 53 50 bytes
-3 bytes thanks to ETHproductions.
lambda s:' '.join(i for i in s.lower()if'`'<i<'{')

Try it online!

Can you not do if"`"<i<"{", since i is already lowercase?

@ETHproductions I should really take a closer look at the ASCII table... Thanks!

C, 65 bytes
c;f(){for(;~c;c=getchar())!isalpha(c)?:printf("%c ",tolower(c));}

How it works:

c declares an integer c, and sets it to 0 by default.
for(;~c; declares a loop that will only continue if performing a bitwise NOT on c is true. NOT will return false only if c is EOF (meaning there is no more input).
c=getchar() reads a character from input into c.
!isalpha(c)?: checks if c is in the alphabet. If so...
printf("%c ",tolower(c)); prints the character in lowercase, then a space.

Try it online!

shortC, 40 bytes
c;AO;~c;c=G)!isalpha(c)?:R"%c ",tolower(c

Conversions in this program:

A -> int main(int argc, char **argv){
O -> for(
G -> getchar()
R -> printf(
Auto-inserted closing ));}

Try it online!

PHP, 68 Bytes
<?=chunk_split(preg_replace("#[^a-z]#","",strtolower($argn)),1," ");

Try it online!
PHP, 70 Bytes
<?=join(" ",str_split(preg_replace("#[^a-z]#","",strtolower($argn))));

Try it online!
or

<?=preg_replace(["#[^a-z]#","#.(?=.)#"],["","$0 "],strtolower($argn));

Try it online!

Retina, 14 bytes
T`Llp`ll_
\B

Try it online! This is so simple I don't even need a header to run multiple testcases. All uppercase letters are lowercased, lowercase letters are also lowercased for consistency, and everything else is deleted. Then spaces are inserted between every pair of letters.

JavaScript (ES6), 53 bytes
s=>[...s.toLowerCase().replace(/[^a-z]/g,'')].join` `

Sometimes the straightforward way is the shortest...
Here are a few successively more fun versions using array comprehensions (only works in Firefox 30+):
s=>[for(x of s.toLowerCase())if('`'<x&x<'{')x].join` `
s=>[for(x of s)if(parseInt(x,36)>9)x.toLowerCase()].join` `
s=>[for(x of s)if((x=parseInt(x,36))>9)x.toString(36)].join` `

If we can assume the input contains at least one letter, this will work for 42:
s=>s.toLowerCase().match(/[a-z]/g).join` `


text:
Multiply using ***Real*** numbers
Inspired by a restriction on What do you get when you multiply 6 by 9? (42)
By order of the President, we are no longer permitted to use confusing fake numbers (i.e. numbers other than integers from 0 to 99 inclusive), and are instead to use only real numbers, that is, those that are not fake.
Unfortunately, most maths are very unpatriotic at present and thus it is necessary to revolutionalize a new, revised, mathematics for the glory of the State.
Your task is to create a program or function which takes as its input two numbers and provides as its output their product.  Your program, obviously, must be consistent with Minitrue's standards for programmatic excellence.  Specifically:

You may use real numbers in your code; users of fake numbers will be referred to Miniluv
If a fake number is provided as input, you are to raise an error to that effect raised only in this case.  If your chosen language is incapable of error, you are to write a consistent Truthy or Falsy value to a different output stream than normal, this value being written to that output stream only in this case.
Your program must never output any fake numbers; users of fake numbers will by referred to Miniluv
Your program must output consistently with pre-Ministry math texts, except where those texts are influenced by thoughtcrime (i.e. where the input or output would be a fake number).  In those cases, you are free to define whatever truth you think best furthers the Party's goals, provided your output is consistent with above principles.
Your input is guaranteed to be either two real numbers, two fake numbers, or one real and one fake number

This is code golf; the shortest code in bytes wins.
Some test cases:
Input: 0, 3 Output: 0
Input: 2, 5 Output: 10
Input: 9, 11 Output: 99
Input: 10, 10 Output*: 5
Input: -1, 0 Output*: ERROR: THOUGHTCRIME COMMITTED
Input: 2, 2.5 Output*: ERROR: THOUGHTCRIME COMMITTED
Input: 99, 2 Output*: 5
Input: -1, 53 Output*: ERROR: THOUGHTCRIME COMMITTED

Test cases with an 'Output*' indicate that there are multiple valid outputs for that test case.
Please note that while your output in the case of a fake product from real numbers may be an error, it cannot be the same error as for fake input (unless both cases trigger), as explained in rule #2.

This is my first question here; advice is welcomed

Is the input guaranteed to be two numbers, even if they are fake? Will they be of our language's integer type? Can they be negative?

@thedarkwanderer people really don't like having to do input validation. If the input is out of scope (letters) we don't want to deal with that. Lemme find the meta post about that real quick. Here it is: invalid inputs meta. The fake numbers are OK because that's part of the challenge, but trying to multiply "Hello" and "World" should not be our business.

@StephenS better?

It's late so maybe I'm being simple but product is multiplication right? So how can 10*10=5?

@Notts90 newMath is a little like newspeak.  (When the output would be fake you can output anything except reporting the input as fake unless it is)

Do we have to handle inputs like 5.0 as fake inputs?

@xnor no, but you totally can.  you could call it a fake number and report it because '.0' implies the existence of fake numbers (so you can safely report all doubles), but you could also give them the benefit of the doubt and assume it's just an integer. Either way's fine, and there's no need to be consistent.  Your language must support real number imputs, though.

Is this ban on fake numbers only limited to the actual code-page representations?

Can we use -1 if our language processes it as negate(1)?

@xnor I don't know.  I mean, people are already doing that via stuff like '99+1' and '10*10' so I guess it's fine.  I'm not sure how to say you can't do that and also I'm not sure it's ok with site policy to invalidate answers that way.

@JonathanAllan I don't know. I mean, people are already doing that via stuff like '99+1' and '10*10' so I guess it's fine. I'm not sure how to say you can't do that and also I'm not sure it's ok with site policy to invalidate answers that way.

In some languages there are literals that would actually be interpreted as fake numbers - e.g. in Jelly ȷ2 is parsed as meaning 100, as is ³ if no command line argments are used (equally, for example, ⁾ab is parsed as 25349) - there is calculation occurring at a deeper level of course (but at the bottom it's all bits, so nothing is using fake numbers...)

@JonathanAllan Well, what would you suggest, then?  A single character euphemism for '100' hardly seems fair; I'd like not to allow that.  Is there a good way to do that?

Then you should ban the use of fake literals then I believe.

What about covfefe numbers?

Does the fake number error need to be consistent? As in, must 1.3 and -1 output the same error?

@ValueInk Not at all, but you can't output any of those errors you reserve for fake input unless there's fake input.

What about something non-truthy/falsey, like Nothing?

Python 2, 41 38 41 39 bytes
lambda a,b:a*b%-~99/(chr(a)<'d'>chr(b))

-2 bytes from xnor.
Uses -~99 to get 100 legally.
Relies on u<v>w is equivalent to u<v and v>w.
If a or b are not integers chr throws a TypeError. If either are less than 0, chr throws a ValueError.
If a or b are greater than or equal to 100 (ord('d')), then the denominator will evaluate to 0, and throws a ZeroDivisionError.
Otherwise, the denominator will evaluate to 1; and returns the modded product.

I think the first set of parens aren't needed.

@xnor, thanks! Was thinking about order of operations, but doesn't matter when dividing by 1 or 0.

Python,  54  52 bytes
lambda a,b:[v for v in(a,b,a*b%-~99)if'd'>chr(v)][2]

An unnamed function raising an error if either of the inputs are fake otherwise returning the product of the inputs modulo 100 (always real and correct if the product itself is real).
Try it online!
How?
First creates a tuple of the inputs and their product modulo 100 using (a,b,a*b%-~99) where ~x computes -1-x and % is the modulo operator.
Then traverses that tuple creating a list of those values which are real numbers.
The test for real-ness is performed by first attempting to cast each value, v, to characters with chr(v) - which will raise a ValueError if v is not a non-negative integer less than 256, then checking the value is less than 100 by a less-than-comparison, <, to the 100th character, 'd'.
If both a and b are real the list will have three entries (the product modulo 100 is alway real), otherwise it will have less. The [...][2] attempts to get the item at the second index (third item), raising an IndexError if it does not exist.
Thus either input being fake results in either a ValueError or IndexError, while both inputs being real always succeeds and returns a real number, and if that product is itself real it is the returned value.

JavaScript (ES6), 61 57 bytes
g=x=>x<0|x>99|x%1!=0
f=(a,b)=>g(a)|g(b)|g(a*b)?f(a,b):a*b

Similar to the Haskell answer, creates a validation function, called g. g returns false iff x is not a fake number. f checks if the either number or the product is fake. If either number or the product is fake, it calls f again, which will hit a StackOverflow relatively quickly. Otherwise, it returns the product. Same length, with currying:
g=x=>x<0|x>99|x%1!=0
f=a=>b=>g(a)|g(b)|g(a*b)?f(a)(b):a*b

g=x=>x<0|x>99|x%1!=0
f=(a,b)=>g(a)|g(b)|g(a*b)?f(a,b):a*b

//Note that once one console.log crashes, none of the rest will execute
console.log(f(0,3))
console.log(f(2,5))
console.log(f(9,11))
console.log(f(10,10))
console.log(f(-1,0))
console.log(f("Hello"," World"))
console.log(f("Help",""))
console.log(f(2,2.5))

Python 3, 74 69 bytes
-5 bytes thanks to @Adnan
lambda a,b,h=99+1:a*b%h if type(a)==int==type(b)and 0<=a<h>b>=0else c

Try it online!

@thedarkwanderer fixed it

Well this technically works :P  I think the fact you rely on 1010 being something other than what 1010 is according to you is a little silly, but we can go ahead and call it doublespeak

I think 0<=b<h>a>=0 instead of h>a>=0and h>b>=0 should work.

Python 3 111 101 75 77 59 bytes
EDIT: -10 bytes because of Python's "ternary" operator
EDIT 2: -26 bytes because of lambda and really obfuscating with the ternary operator.
EDIT 3: +2 bytes because range is exclusive. Thanks @ovs for catching that
EDIT 4: -18 bytes thanks to @ovs's suggestion
lambda a,b,s={*range(99+1)}:{a,b}-s and c or max({0,a*b}&s)

Try it online!
Raises a Zero Division Error for fake numbers, returns 0 for a fake product
Works by first checking if a and b are in the range of real numbers. If not, try to access the undefined variable c, resulting in an error. Otherwise, return either 0 or a * b depending on whether a * b is fake or real.

@thedarkwanderer: "a" is a literal a as the return if the product is a fake number. a the variable is the integers from 0-99. I'll change the variable to b to make it clearer.

@ovs nice catch, I will fix that

@thedarkwanderer: Yes, I could use another variable instead, but then I would need spaces on either side of the name in order for the else and if to work, resulting in the same byte count

Jelly,  (16?) 17  (13?) 15 bytes
⁶Pḟ0r99¤Ȧ$?Dṫ-Ḍ

Monadic link taking a list of numbers, yielding the real answer if the inputs and the result are real, yielding the product modulo 100 if the inputs are real but the product would not be, and raising a TypeError if either of the inputs are fake.
Try it online!
13 byte possible alternative (debatable), works in a similar fashion, but uses:
⁶Pḟȷ2Ḷ¤Ȧ$?%ȷ2
   ȷ2          - literal 100 (interpreted as 10 raised to the power of 2)
     Ḷ         - lowered range -> [0,1,2,...99] (all the *real* numbers)
           ȷ2  - literal 100 (again)
          %    - modulo

How?
⁶Pḟ0r99¤Ȧ$?Dṫ-Ḍ - Main link: list of numbers, [a1, a2]
          ?     - if:
                - ...the if condition:
         $      -   last two links as a monad:
  ḟ             -     filter discard if in:
       ¤        -       nilad followed by link(s) as a nilad:
   0            -         literal zero
     99         -         literal ninety-nine
    r           -         inclusive range -> [0,1,2,...99] - all the *real* numbers
        Ȧ       -     any and all (for our purposes: 0 if empty, 1 otherwise [since zeros were filtered out])
                - ...then:
⁶               -   literal space character
                - ...else:
 P              -   product of [a1, a2]
           D    - convert to a list of it's decimal digits (Type Error
            ṫ-  - tail from index -1 (keep only the last two (or less) digits)
              Ḍ - convert back to a number

I would assume the 17 byte solution is allowed, since 100 is represented as a result and not the literal. Likewise for 99+1.

@NeilA. ȷ2 is a literal 100 - this is why it is debatable.

Perl 6,  57 54  41 bytes
{all(@_ X~~Int,$(0..99))??+([*](@_)~~0..99)&&[*] @_!!die}

Try it
{all(@_ X~~Int,$/=0..99)??+([*](@_)~~$/)&&[*] @_!!die}

Try it
{all(@_ X~~Int,0..99)??[*](@_)%10²!!die}

Try it
Throws an error with the message of Died if given a non-Real number.
(left intentionally vague to confuse the perpetrator, which gives more time to collect them for re-education)
The first two examples return 0 rather than produce a non-Real number.
The third one constrains its result to a Real number using the modulus operator.
Expanded:
{  # bare block lambda with implicit parameter list of ｢@_｣

    all(           # check if all tests pass
        @_         # the input
      X~~          # cross ｢X｣ smartmatched ｢~~｣ with the following
        Int,       # All **Real** numbers are Ints
        0..99      # Range of all **Real** numbers
    )

  ??               # if all inputs are **Real** numbers
      [*](@_)      # reduce using &infix:« * » operator
      %            # modulus
      10²          # 10 to the power of 2
  !!               # die if any input was not a **Real** number
    die
}

Note that 10² is parsed as 10 followed by a postfix operator.

Haskell, 67 bytes
v a=not$0<=a&&a<=99
a#b|(v a)||(v b)=error""|v$a*b=error""|True=a*b

Does your program handle floats between 0 and 99? integers from 0 to 99 inclusive

Haskell, 35 41 bytes
a#b|all(`elem`[0..99])[a,b]=mod(a*b)$1+99

Try it online!
Example usage: 3#4 returns 12, while fake numbers like 3.5#4, 300#4 and (-3)#4 all yield the error non-exhaustive pattern in function #. Non-fake inputs whose product would be greater than 99 result in the product modulus 100.
Edit: Thanks to Jonathan Allan for pointing out that I initially missed a part of the challenge.

You misinterpreted just like I did - if both inputs are real but their product is fake we may not raise the same error as we do in the case of a fake input. So, for example, 10#10 should result in either a real number (even if it is "wrong"- like 5 in OPs examples), or a different error to those that could be raised by the presence of fake input.

@JonathanAllan Thanks! It should be fixed now.

Ruby, 52 bytes
Returns NoMethodError if the input has a fake number.
->a,b{a.chr;b.chr;(r=0..99)===a&&r===b ?a*b%-~99:+p}

Try it online!

Java 8, 58 bytes
(x,y)->new Long(0>x||x>99||0>y||y>99?"":x*y>99?"0":x*y+"")

Try it online!

Throws a NumberFormatException for fake inputs, returns 0 for fake outputs. I added a small easter egg to the TIO example that prints "ERROR: THOUGHTCRIME COMMITTED" if a NumberFormatException is thrown, just for fun.

R, 70 bytes
Probably a cleverer way to do this all the conditionals.
function(a,b)`if`(`if`(a<0|a>99|b<0|b>99|a%%1>0|b%%1>0,,a*b)>99,5,a*b)

Try it online!


text:
Finding approximate correlations
Consider a binary string S of length n.  Indexing from 1, we can compute the Hamming distances between S[1..i+1] and S[n-i..n] for all i in order from 0 to n-1.    The Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different. For example,
S = 01010

gives
[0, 2, 0, 4, 0].

This is because 0 matches 0, 01 has Hamming distance two to 10, 010 matches 010, 0101 has Hamming distance four to 1010  and finally 01010 matches itself.
We are only interested in outputs where the Hamming distance is at most 1, however. So in this task we will report a Y if  the Hamming distance is at most one and an N otherwise.  So in our example above we would get
[Y, N, Y, N, Y]

Define f(n) to be the number of distinct arrays of Ys and Ns one gets when iterating over all 2^n different possible bit strings S of length n.
Task
For increasing n starting at 1, your code should output f(n).
Example answers
For n = 1..24, the correct answers are:
1, 1, 2, 4, 6, 8, 14, 18, 27, 36, 52, 65, 93, 113, 150, 188, 241, 279, 377, 427, 540, 632, 768, 870

Scoring
Your code should iterate up from n = 1 giving the answer for each n in turn. I will time the entire run, killing it after two  minutes.
Your score is the highest n you get to in that time.
In the case of a tie, the first answer wins.
Where will my code be tested?
I will run your code on my (slightly old) Windows 7 laptop under cygwin.  As a result, please give any assistance you can to help make this easy.
My laptop has 8GB of RAM and an Intel i7 5600U@2.6 GHz (Broadwell) CPU with 2 cores and 4 threads. The instruction set includes SSE4.2, AVX, AVX2, FMA3 and TSX.
Leading entries per language

n = 40 in Rust using CryptoMiniSat, by Anders Kaseorg. (In Lubuntu guest VM under Vbox.)
n = 35 in C++ using the BuDDy library, by Christian Seviers. (In Lubuntu guest VM under Vbox.)
n = 34 in Clingo by Anders Kaseorg. (In Lubuntu guest VM under Vbox.)
n = 31 in Rust by Anders Kaseorg.
n = 29 in Clojure by  NikoNyrh.
n = 29 in C by bartavelle.
n = 27 in Haskell by  bartavelle
n = 24 in Pari/gp by  alephalpha.
n = 22 in Python 2 + pypy by me.
n = 21 in Mathematica by  alephalpha. (Self reported)

Future bounties
I will now give a bounty of 200 points for any answer that gets up to n = 80 on my machine in two minutes.

Do you know of some trick that will allow someone to find a faster algorithm than a naive brute force? If not this challenge is "please implement this in x86" (or maybe if we know your GPU...).

@JonathanAllan It is certainly possible to speed up a very naive approach.  Exactly how fast you can get I am not sure.  Interestingly, if we changed the question so that you get a Y if the Hamming distance is at most 0 and an N otherwise, then there is a known closed form formula.

@Lembik Do we measure CPU time or real time?

@flawr I am measuring real time but running it a few times and taking the minimum to eliminate oddities.

Rust + CryptoMiniSat, n ≈ 41
src/main.rs
extern crate cryptominisat;
extern crate itertools;

use std::iter::once;
use cryptominisat::{Lbool, Lit, Solver};
use itertools::Itertools;

fn make_solver(n: usize) -> (Solver, Vec<Lit>) {
    let mut solver = Solver::new();
    let s: Vec<Lit> = (1..n).map(|_| solver.new_var()).collect();
    let d: Vec<Vec<Lit>> = (1..n - 1)
        .map(|k| {
                 (0..n - k)
                     .map(|i| (if i == 0 { s[k - 1] } else { solver.new_var() }))
                     .collect()
             })
        .collect();
    let a: Vec<Lit> = (1..n - 1).map(|_| solver.new_var()).collect();
    for k in 1..n - 1 {
        for i in 1..n - k {
            solver.add_xor_literal_clause(&[s[i - 1], s[k + i - 1], d[k - 1][i]], true);
        }
        for t in (0..n - k).combinations(2) {
            solver.add_clause(&t.iter()
                                   .map(|&i| d[k - 1][i])
                                   .chain(once(!a[k - 1]))
                                   .collect::<Vec<_>>()
                                   [..]);
        }
        for t in (0..n - k).combinations(n - k - 1) {
            solver.add_clause(&t.iter()
                                   .map(|&i| !d[k - 1][i])
                                   .chain(once(a[k - 1]))
                                   .collect::<Vec<_>>()
                                   [..]);
        }
    }
    (solver, a)
}

fn search(n: usize,
          solver: &mut Solver,
          a: &Vec<Lit>,
          assumptions: &mut Vec<Lit>,
          k: usize)
          -> usize {
    match solver.solve_with_assumptions(assumptions) {
        Lbool::True => search_sat(n, solver, a, assumptions, k),
        Lbool::False => 0,
        Lbool::Undef => panic!(),
    }
}

fn search_sat(n: usize,
              solver: &mut Solver,
              a: &Vec<Lit>,
              assumptions: &mut Vec<Lit>,
              k: usize)
              -> usize {
    if k >= n - 1 {
        1
    } else {
        let s = solver.is_true(a[k - 1]);
        assumptions.push(if s { a[k - 1] } else { !a[k - 1] });
        let c = search_sat(n, solver, a, assumptions, k + 1);
        assumptions.pop();
        assumptions.push(if s { !a[k - 1] } else { a[k - 1] });
        let c1 = search(n, solver, a, assumptions, k + 1);
        assumptions.pop();
        c + c1
    }
}

fn f(n: usize) -> usize {
    let (mut solver, proj) = make_solver(n);
    search(n, &mut solver, &proj, &mut vec![], 1)
}

fn main() {
    for n in 1.. {
        println!("{}: {}", n, f(n));
    }
}

Cargo.toml
[package]
name = "correlations-cms"
version = "0.1.0"
authors = ["Anders Kaseorg <andersk@mit.edu>"]

[dependencies]
cryptominisat = "5.0.1"
itertools = "0.6.0"

How it works
This does a recursive search through the tree of all partial assignments to prefixes of the Y/N array, using a SAT solver to check at each step whether the current partial assignment is consistent and prune the search if not.  CryptoMiniSat is the right SAT solver for this job due to its special optimizations for XOR clauses.
The three families of constraints are
Si ⊕ Sk + i ⊕ Dki, for 1 ≤ k ≤ n − 2, 0 ≤ i ≤ n − k;
Dki1 ∨ Dki2 ∨ ¬Ak, for 1 ≤ k ≤ n − 2, 0 ≤ i1 < i2 ≤ n − k;
¬Dki1 ∨ ⋯ ∨ ¬Dkin − k − 1 ∨ Ak, for 1 ≤ k ≤ n − 2, 0 ≤ i1 < ⋯ < in − k − 1 ≤ n − k;
except that, as an optimization, S0 is forced to false, so that Dk0 is simply equal to Sk.

Woohoooooo ! :)

I am still trying to compile this in Windows (using cygwin + gcc).  I cloned cryptominisat and compiled it.  But I still don't know how to compile the rust code. When  I do cargo build I get --- stderr CMake Error: Could not create named generator Visual Studio 14 2015 Win64

Even though I can't run your code yet, I will award you the bounty as other people can. I may just give in and use a VM.

It would be great if you could explain fully how you can use a SAT solver to solve this problem. I think people would be very interested.

@Lembik I added a quick explanation of how I’m using SAT. The build process should be simply cargo build --release. There’s no need to separately clone and install CryptoMiniSat: the Rust bindings will ignore that and use a vendored copy anyway.

Thanks. The problem is that cargo build fails to compile it in cygwin. If there is some other way to get it to compile in Windows I will happily try it.

@Lembik Hmm, obviously I haven’t tried this on Windows, but a comment on a similar-looking issue for a different project suggests that you might need the Windows version of CMake instead of the Cygwin version? (Or maybe vice versa?)

@Lembik Here are standalone rust installers for windows 32 bit(i686) and 64 bit(x86_64)

@rahnema1 Thanks, but it sounds like the issue is with the CMake build system of the embedded C++ library in the cryptominisat crate, not with Rust itself.

Great job! I had completely different sets of clauses for the Y and N cases that I kept adding and removing in my attempt. No wonder it didn't work out.

@rahnema1 This is the problem https://bpaste.net/show/4f22dd76bb6d .  I have cygwin + gcc + cygwin's cmake installed.  If there is some other to compile this code in Windows I would  be happy to try it.

@Lembik I'm getting a 404 from that paste.

@Mego I have posted a question to https://stackoverflow.com/questions/44520572/failed-to-run-custom-build-command-for-cryptominisat-on-windows which lists all my woes.

https://gist.github.com/somebody1234/712315377b26deb25a2a2417b5de02ed

I gave up on windows in the end (although @feersum managed to get it to compile with some effort).  I still really like your answer. Am thinking of posing  https://oeis.org/A005434 as fastest code as there doesn't seem to be an obvious closed form answer.. although I suspect it is much easier.

I wonder if this solution needs the backtracking. Alternatively, just find a solution, count it, add a clause to forbid its combination of A literals, repeat.

@ChristianSievers Good question. That works but it seems to be a bit slower (2× or so). I’m not sure why it shouldn’t be just as good, so maybe CryptoMiniSat just hasn’t been well optimized for that kind of incremental workload.

Rust, n ≈ 30 or 31 or 32
On my laptop (two cores, i5-6200U), this gets through n = 1, …, 31 in 53 seconds, using about 2.5 GiB of memory, or through n = 1, …, 32 in 105 seconds, using about 5 GiB of memory.  Compile with cargo build --release and run target/release/correlations.
src/main.rs
extern crate rayon;

type S = u32;
const S_BITS: u32 = 32;

fn cat(mut a: Vec<S>, mut b: Vec<S>) -> Vec<S> {
    if a.capacity() >= b.capacity() {
        a.append(&mut b);
        a
    } else {
        b.append(&mut a);
        b
    }
}

fn search(n: u32, i: u32, ss: Vec<S>) -> u32 {
    if ss.is_empty() {
        0
    } else if 2 * i + 1 > n {
        search_end(n, i, ss)
    } else if 2 * i + 1 == n {
        search2(n, i, ss.into_iter().flat_map(|s| vec![s, s | 1 << i]))
    } else {
        search2(n,
                i,
                ss.into_iter()
                    .flat_map(|s| {
                                  vec![s,
                                       s | 1 << i,
                                       s | 1 << n - i - 1,
                                       s | 1 << i | 1 << n - i - 1]
                              }))
    }
}

fn search2<SS: Iterator<Item = S>>(n: u32, i: u32, ss: SS) -> u32 {
    let (shift, mask) = (n - i - 1, !(!(0 as S) << i + 1));
    let close = |s: S| {
        let x = (s ^ s >> shift) & mask;
        x & x.wrapping_sub(1) == 0
    };
    let (ssy, ssn) = ss.partition(|&s| close(s));
    let (cy, cn) = rayon::join(|| search(n, i + 1, ssy), || search(n, i + 1, ssn));
    cy + cn
}

fn search_end(n: u32, i: u32, ss: Vec<S>) -> u32 {
    if i >= n - 1 { 1 } else { search_end2(n, i, ss) }
}

fn search_end2(n: u32, i: u32, mut ss: Vec<S>) -> u32 {
    let (shift, mask) = (n - i - 1, !(!(0 as S) << i + 1));
    let close = |s: S| {
        let x = (s ^ s >> shift) & mask;
        x & x.wrapping_sub(1) == 0
    };
    match ss.iter().position(|&s| close(s)) {
        Some(0) => {
            match ss.iter().position(|&s| !close(s)) {
                Some(p) => {
                    let (ssy, ssn) = ss.drain(p..).partition(|&s| close(s));
                    let (cy, cn) = rayon::join(|| search_end(n, i + 1, cat(ss, ssy)),
                                               || search_end(n, i + 1, ssn));
                    cy + cn
                }
                None => search_end(n, i + 1, ss),
            }
        }
        Some(p) => {
            let (ssy, ssn) = ss.drain(p..).partition(|&s| close(s));
            let (cy, cn) = rayon::join(|| search_end(n, i + 1, ssy),
                                       || search_end(n, i + 1, cat(ss, ssn)));
            cy + cn
        }
        None => search_end(n, i + 1, ss),
    }
}

fn main() {
    for n in 1..S_BITS + 1 {
        println!("{}: {}", n, search(n, 1, vec![0, 1]));
    }
}

Cargo.toml
[package]
name = "correlations"
version = "0.1.0"
authors = ["Anders Kaseorg <andersk@mit.edu>"]

[dependencies]
rayon = "0.7.0"

Try it online!
I also have a slightly slower variant using very much less memory.

What optimisations have you used?

@Lembik The biggest optimization, besides doing everything with bitwise arithmetic in a compiled language, is to use only as much nondeterminism as needed to nail down a prefix of the Y/N array. I do a recursive search on possible prefixes of the Y/N array, taking along a vector of possible strings achieving that prefix, but only the strings whose unexamined middle is filled with zeros. That said, this is still an exponential search, and these optimizations only speed it up by polynomial factors.

It's a nice answer. Thank you.  I am hoping someone will dig into the combinatorics to get a significant speed up.

@Lembik I’ve fixed a memory wasting bug, done more micro-optimization, and added parallelism. Please retest when you get a chance—I’m hoping to increase my score by 1 or 2. Do you have combinatorial ideas in mind for larger speedups? I haven’t come up with anything.

It doesn't run for me. I get 1: 1
2: 1
thread 'main' panicked at 'attempt to subtract with overflow', src\main.rs:40

@Lembik Ah, that’s a bug, which I’ve now corrected. However, it also means that you’re compiling without optimization, since Rust only does overflow checking in debug mode. Please make sure you’re building with --release for benchmarking.

I was benchmarking with --release, never fear.  Re: combinatorics... if we change the bound from 1 to 0 (that is look for exact matches) we get https://oeis.org/A005434 .  This has a closed form formula.  I was hoping this could be extended somehow.

@Lembik There is no formula given at the OEIS entry. (The Mathematica code there also seem to use brute-force.) If you know of one, you might want to tell them about it.

@ChristianSievers Hmmm... maybe I am wrong!

C++ using the BuDDy library
A different approach: have a binary formula (as binary decision diagram) that takes the bits of S as input and is true iff that gives some fixed values of Y or N at certain selected positions. If that formula is not constant false, select a free position and recurse, trying both Y and N. If there is no free position, we have found a possible output value. If the formula is constant false, backtrack.
This works relatively reasonable because there are so few possible values so that we can often backtrack early. I tried a similar idea with a SAT solver, but that was less successful.
#include<vector>
#include<iostream>
#include<bdd.h>

// does vars[0..i-1] differ from vars[n-i..n-1] in at least two positions?
bdd cond(int i, int n, const std::vector<bdd>& vars){
  bdd x1 { bddfalse };
  bdd xs { bddfalse };
  for(int k=0; k<i; ++k){
    bdd d { vars[k] ^ vars[n-i+k] };
    xs |= d & x1;
    x1 |= d;
  }
  return xs;
}

void expand(int i, int n, int &c, const std::vector<bdd>& conds, bdd x){
  if (x==bddfalse)
    return;
  if (i==n-2){
    ++c;
    return;
  }

  expand(i+1,n,c,conds, x & conds[2*i]);
  x &= conds[2*i+1];
  expand(i+1,n,c,conds, x);
}

int count(int n){
  if (n==1)   // handle trivial case
    return 1;
  bdd_setvarnum(n-1);
  std::vector<bdd> vars {};
  vars.push_back(bddtrue); // assume first bit is 1
  for(int i=0; i<n-1; ++i)
    if (i%2==0)            // vars in mixed order
      vars.push_back(bdd_ithvar(i/2));
    else
      vars.push_back(bdd_ithvar(n-2-i/2));
  std::vector<bdd> conds {};
  for(int i=n-1; i>1; --i){ // handle long blocks first
    bdd cnd { cond(i,n,vars) };
    conds.push_back( cnd );
    conds.push_back( !cnd );
  }
  int c=0;
  expand(0,n,c,conds,bddtrue);
  return c;
}

int main(void){
  bdd_init(20000000,1000000);
  bdd_gbc_hook(nullptr); // comment out to see GC messages
  for(int n=1; ; ++n){
    std::cout << n << " " << count(n) << "\n" ;
  }
}

To compile with debian 8 (jessie), install libbdd-dev and do g++ -std=c++11 -O3 -o hb hb.cpp -lbdd. It might be useful to increase the first argument to bdd_init even more.

This looks interesting. What do you get to with this?

@Lembik I get 31 in 100s on very old hardware that won't let me answer faster

Any help you can give on how to compile this on Windows (e.g. using cygwin) gratefully received.

@Lembik I don't know about Windws but https://github.com/fd00/yacp/tree/master/buddy seems helpful w.r.t. cygwin

I tried this on my i7 6700K, although this uses just a single thread it would run up-to 29, 30 and 31 in 9, 16 and 21 seconds! OTOH 35, 36 and 37 were completed in 1.5, 3.5 and 11.5 minutes. I guess if compilation is an issue you could run this inside a VM.

Wow, okay, you’ve got me convinced that I need to add this library to my toolkit. Well done!

I like the idea of a SAT based solution.  Which solver did you try?

@AndersKaseorg The BuDDy authors seem to have done a fine job, but I can't say anything about how it compares to other BDD libraries. It was just the first one that seemed to work for me. Maybe the important thing is just the BDD technique.

@Lembik I used picosat.

Clingo, n ≈ 30 or 31 34
I was a little surprised to see five lines of Clingo code overtake my brute-force Rust solution and come really close to Christian’s BuDDy solution—it looks like it would beat that too with a higher time limit.
corr.lp
{s(2..n)}.
d(K,I) :- K=1..n-2, I=1..n-K, s(I), not s(K+I).
d(K,I) :- K=1..n-2, I=1..n-K, not s(I), s(K+I).
a(K) :- K=1..n-2, {d(K,1..n-K)} 1.
#show a/1.

corr.sh
#!/bin/bash
for ((n=1;;n++)); do
    echo "$n $(clingo corr.lp --project -q -n 0 -c n=$n | sed -n 's/Models *: //p')"
done

This is great!  It looks from your graph that the BuDDy solution suddenly gets worse. Any idea why?

@Lembik I haven’t investigated BuDDy enough to be sure, but maybe it runs out of cache at that point?

Wow! I think a higher first value to bdd_init might help, or allowing to increase the node table more by calling bdd_setmaxincrease with a value much above the default of 50000. - Are you using the changed version of my program?

@ChristianSievers I’m using your current version.

I do love your graph.

You get a shocking performance boost by using the option --configuration=crafty (jumpy and trendy give similar results).

@ChristianSievers How much of a boost?

@Anush I think it was just enough to make me wonder which program will be the fastest.

Clojure, 29 in 75 38 seconds, 30 in 80 and 31 in 165
Runtimes from Intel i7 6700K, memory usage is less than 200 MB.
project.clj (uses com.climate/claypoole for multithreading):
(defproject tests "0.0.1-SNAPSHOT"
  :description "FIXME: write description"
  :dependencies [[org.clojure/clojure "1.8.0"]
                 [com.climate/claypoole "1.1.4"]]
  :javac-options ["-target" "1.6" "-source" "1.6" "-Xlint:-options"]
  :aot [tests.core]
  :main tests.core)

Source code:
(ns tests.core
  (:require [com.climate.claypoole :as cp]
            [clojure.set])
  (:gen-class))

(defn f [N]
  (let [n-threads   (.. Runtime getRuntime availableProcessors)
        mask-offset (- 31 N)
        half-N      (quot N 2)
        mid-idx     (bit-shift-left 1 half-N)
        end-idx     (bit-shift-left 1 (dec N))
        lower-half  (bit-shift-right 0x7FFFFFFF mask-offset)
        step        (bit-shift-left 1 12)
        bitcount
          (fn [n]
            (loop [i 0 result 0]
              (if (= i N)
                result
                (recur
                  (inc i)
                  (-> n
                      (bit-xor (bit-shift-right n i))
                      (bit-and (bit-shift-right 0x7FFFFFFF (+ mask-offset i)))
                      Integer/bitCount
                      (< 2)
                      (if (+ result (bit-shift-left 1 i))
                          result))))))]
    (->>
      (cp/upfor n-threads [start (range 0 end-idx step)]
        (->> (for [i      (range start (min (+ start step) end-idx))
                   :when  (<= (Integer/bitCount (bit-shift-right i mid-idx))
                              (Integer/bitCount (bit-and         i lower-half)))]
               (bitcount i))
             (into #{})))
      (reduce clojure.set/union)
      count)))

(defn -main [n]
  (let [n-iters 5]
    (println "Calculating f(n) from 1 to" n "(inclusive)" n-iters "times")
    (doseq [i (range n-iters)]
      (->> n read-string inc (range 1) (map f) doall println time)))
  (shutdown-agents)
  (System/exit 0))

A brute-force solution, each thread goes over a subset of the range (2^12 items) and builds a set of integer values which indicate detected patterns. These are then "unioned" together and thus the distinct count is calculated. I hope the code isn't too tricky to follow eventhough it uses threading macros a lot. My main runs the test a few times to get JVM warmed up.
Update: Iterating over only half of the integers, gets the same result due to symmetry. Also skipping numbers with higher bit count on lower half of the number as they produce duplicates as well.
Pre-built uberjar (v1) (3.7 MB):
$ wget https://s3-eu-west-1.amazonaws.com/nikonyrh-public/misc/so-124424-v2.jar
$ java -jar so-124424-v2.jar 29
Calculating f(n) from 1 to 29 (inclusive) 5 times
(1 1 2 4 6 8 14 18 27 36 52 65 93 113 150 188 241 279 377 427 540 632 768 870 1082 1210 1455 1656 1974)
"Elapsed time: 41341.863703 msecs"
(1 1 2 4 6 8 14 18 27 36 52 65 93 113 150 188 241 279 377 427 540 632 768 870 1082 1210 1455 1656 1974)
"Elapsed time: 37752.118265 msecs"
(1 1 2 4 6 8 14 18 27 36 52 65 93 113 150 188 241 279 377 427 540 632 768 870 1082 1210 1455 1656 1974)
"Elapsed time: 38568.406528 msecs"
[ctrl+c]

Results on different hardwares, expected runtime is O(n * 2^n)?
i7-6700K  desktop: 1 to 29 in  38 seconds
i7-6820HQ laptop:  1 to 29 in  43 seconds
i5-3570K  desktop: 1 to 29 in 114 seconds

You can easily make this single-threaded and avoid that 3rd party dependency by using the standard for:
(for [start (range 0 end-idx step)]
  ... )

Well the built-in pmap also exists but claypoole has more features and tunability.

Yeah, it makes it trivial to distribute. Would you have time to re-evaluate my solution, I'm quite sure you'd get it up-to 30 now. I do not have further optimizations in sight.

Sadly it's a no for 30. Elapsed time: 217150.87386 msecs

Ahaa, thanks for giving it a try :D It might have been better to fit a curve on this and interpolate that at which decimal value 120 seconds is spent but even as it is this is a nice challgenge.

Pari/GP, 23
By default, Pari/GP limits its stack size to 8 MB. The first line of the code, default(parisize, "4g"), sets this limit to 4 GB. If it still gives a stackoverflow, you can set it to 8 GB.
default(parisize, "4g")
f(n) = #vecsort([[2 > hammingweight(bitxor(s >> (n-i) , s % 2^i)) | i <- [2..n-1]] | s <- [0..2^(n-1)]], , 8)
for(n = 1, 100, print(n " -> " f(n)))

Reaches 22 and then gives a stackoverflow.

Gets to 24 now.

Mathematica, n=19
press alt+. to abort and the result will be printed
k = 0;
For[n = 1, n < 1000, n++,
Z = Table[HammingDistance[#[[;; i]], #[[-i ;;]]], {i, Length@#}] & /@
Tuples[{0, 1}, n];
Table[If[Z[[i, j]] < 2, Z[[i, j]] = 0, Z[[i, j]] = 1], {i,
Length@Z}, {j, n}];
k = Length@Union@Z]
Print["f(", n, ")=", k]

I can't run this so could you explain how it avoids taking exponential time? 2^241 is a very big number!

Can you show the output of the code?

I meant f(n)... fixed

Haskell, (unofficial n=20)
This is just the naive approach - so far without any optimizations. I wondered how well it would fare against other languages.
How to use it (assuming you have haskell platform installed):

Paste the code in one file approx_corr.hs (or any other name, modify following steps accordingly)
Navigate to the file and execute ghc approx_corr.hs
Run approx_corr.exe
Enter the maximal n
The result of each computation is displayed, as well as the cumulative real time (in ms) up to that point.

Code:
import Data.List
import Data.Time
import Data.Time.Clock.POSIX

num2bin :: Int -> Int -> [Int]
num2bin 0 _ = []
num2bin n k| k >= 2^(n-1) = 1 : num2bin (n-1)( k-2^(n-1))
           | otherwise  = 0: num2bin (n-1) k

genBinNum :: Int -> [[Int]]
genBinNum n = map (num2bin n) [0..2^n-1]

pairs :: [a] -> [([a],[a])]
pairs xs = zip (prefixes xs) (suffixes xs)
   where prefixes = tail . init . inits
         suffixes = map reverse . prefixes . reverse

hammingDist :: (Num b, Eq a) => ([a],[a]) -> b
hammingDist (a,b) = sum $ zipWith (\u v -> if u /= v then 1 else 0) a b

f :: Int -> Int
f n = length $ nub $ map (map ((<=1).hammingDist) . pairs) $ genBinNum n
--f n = sum [1..n]

--time in milliseconds
getTime = getCurrentTime >>= pure . (1000*) . utcTimeToPOSIXSeconds >>= pure . round

main :: IO()
main = do
    maxns <- getLine
    let maxn = (read maxns)::Int
    t0 <- getTime
    loop 1 maxn t0
     where loop n maxn t0|n==maxn = return ()
           loop n maxn t0
             = do
                 putStrLn $ "fun eval: " ++ (show n) ++ ", " ++ (show $ (f n))
                 t <- getTime
                 putStrLn $ "time: " ++ show (t-t0);
                 loop (n+1) maxn t0

The code appears not to give output as it runs.  This makes it a little hard to test.

Strange, does it compile without error?  What happens if you try to compile the program main = putStrLn "Hello World!" ?

The Data.Bits module might be useful. For your main loop, you could use something like main = do maxn <- getmax; t0 <- gettime; loop 1 where loop n|n==maxn = return () and loop n = do printresult n (f n); t <- gettime; printtime (t-t0); loop (n+1). getmax could for example use getArgs to use the program arguments.

@ChristianSievers Thanks a lot!!! I asked this question at stackoverflow, I think it would be great if you could add that there too!

I don't see how to answer there. You have a similar loop there already, and I didn't say anything about getting the time: that you already had here.

Anyway, you helped me a lot finding a solution, thank you very much=)

You're welcome. Since loop is local to main, it has access to main's bindings, so loop doesn't need maxn and and t0 as parameters. The "do some action or nothing according to some condition" idiom is so common that there are the functions when and unless for it in the Control.Monad module. The problem with the output can be fixed by copying the line about buffering from the other haskell solution.

A Haskell solution, using popCount and manually managed parallelism
Compile: ghc -rtsopts -threaded -O2 -fllvm -Wall foo.hs
(drop the -llvm if it doesn't work)
Run : ./foo +RTS -N
module Main (main) where

import Data.Bits
import Data.Word
import Data.List
import qualified Data.IntSet as S
import System.IO
import Control.Monad
import Control.Concurrent
import Control.Exception.Base (evaluate)

pairs' :: Int -> Word64 -> Int
pairs' n s = fromIntegral $ foldl' (.|.) 0 $ map mk [1..n]
  where mk d = let mask = 1 `shiftL` d - 1
                   pc = popCount $! xor (s `shiftR` (n - d)) (s .&. mask)
               in  if pc <= 1
                     then mask + 1
                     else 0

mkSet :: Int -> Word64 -> Word64 -> S.IntSet
mkSet n a b = S.fromList $ map (pairs' n) [a .. b]

f :: Int -> IO Int
f n
   | n < 4 = return $ S.size $ mkSet n 0 mxbound
   | otherwise = do
        mvs <- replicateM 4 newEmptyMVar
        forM_ (zip mvs cpairs) $ \(mv,(mi,ma)) -> forkIO $ do
          evaluate (mkSet n mi ma) >>= putMVar mv
        set <- foldl' S.union S.empty <$> mapM readMVar mvs
        return $! S.size set
   where
     mxbound = 1 `shiftL` (n - 1)
     bounds = [0,1 `shiftL` (n - 3) .. mxbound]
     cpairs = zip bounds (drop 1 bounds)

main :: IO()
main = do
    hSetBuffering stdout LineBuffering
    mapM_ (f >=> print) [1..]

There is a buffering problem it seems in that I don't get any output at all if I run it from the cygwim command line.

I just updated my solution, but I don't know if it will help much.

@Lembik Unsure if that is obvious, but that should be compiled with -O3, and might be faster with -O3 -fllvm ...

(And all build files should be removed before recompiling, if not source code change happened)

@Lembik : I introduced parallelism. It should be a bit faster.

Still gets up to 1455.

@Lembik did you run it with +RTS -N  and does it use all the cores?

It's a lot slower with +RTS -N

@Lembik, too bad, I suppose the runtime doesn't work so well under Cygwin :( thanks anyway for trying it!

@Lembik How many threads does it use? If 4, maybe it's better to use only 2 by using -N2

A C version, using builtin popcount
Works better with clang -O3, but also works if you only have gcc.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

unsigned long pairs(unsigned int n, unsigned long s) {
  unsigned long result = 0;

  for(int d=1;d<=n;d++) {
    unsigned long mx = 1 << d;
    unsigned long mask = mx - 1;

    unsigned long diff = (s >> (n - d)) ^ (s & mask);
    if (__builtin_popcountl(diff) <= 1)
      result |= mx;
  }
  return result;

}

unsigned long f(unsigned long  n) {
  unsigned long max = 1 << (n - 1);
#define BLEN (max / 2)
  unsigned char * buf = malloc(BLEN);
  memset(buf, 0, BLEN);
  unsigned long long * bufll = (void *) buf;

  for(unsigned long i=0;i<=max;i++) {
    unsigned int r = pairs(n, i);
    buf[r / 8] |= 1 << (r % 8);
  }

  unsigned long result = 0;

  for(unsigned long i=0;i<= max / 2 / sizeof(unsigned long long); i++) {
    result += __builtin_popcountll(bufll[i]);
  }

  free(buf);

  return result;
}

int main(int argc, char ** argv) {
  unsigned int n = 1;

  while(1) {
    printf("%d %ld\n", n, f(n));
    n++;
  }
  return 0;
}

It gets to 24 very quickly and then ends. You need to increase the limit.

Oh god, I forgot to remove the benchmark code! I'll remove the two offending lines :/

@Lembik should be fixed now

Mathematica, 21

f[n_] := Length@
     DeleteDuplicates@
      Transpose@
       Table[2 > Tr@IntegerDigits[#, 2] & /@
         BitXor[BitShiftRight[#, n - i], Mod[#, 2^i]], {i, 1,
         n - 1}] &@Range[0, 2^(n - 1)];
Do[Print[n -> f@n], {n, Infinity}]

For comparison, Jenny_mathy's answer gives n = 19 on my computer.
The slowest part is Tr@IntegerDigits[#, 2] &. It is a shame that Mathematica doesn't have a built-in for Hamming weight.

If you want to test my code, you can download a free trial of Mathematica.

Python 2 + pypy, n = 22
Here is a really simple Python solution as a sort of baseline benchmark.
import itertools
def hamming(A, B):
    n = len(A)
    assert(len(B) == n)
    return n-sum([A[i] == B[i] for i in xrange(n)])

def prefsufflist(P):
    n = len(P)
    return [hamming(P[:i], P[n-i:n]) for i in xrange(1,n+1)]

bound = 1
for n in xrange(1,25):
    booleans = set()
    for P in itertools.product([0,1], repeat = n):
        booleans.add(tuple(int(HD <= bound) for HD in prefsufflist(P)))
    print "n = ", n, len(booleans)