[Question]
  [
A [Proth number](https://en.wikipedia.org/wiki/Proth_number), named after François Proth, is a number that can be expressed as
$$N = k \times 2^n + 1$$
Where \$k\$ is an odd positive integer and \$n\$ is a positive integer such that \$2^n > k\$. Let's use a more concrete example. Take 3. 3 is a Proth number because it can be written as
$$ 3 = (1 \times 2^1) + 1 $$
and \$2^1 > 1\$ is satisfied. 5 Is also a Proth number because it can be written as
$$ 5 = (1 \times 2^2) + 1 $$
and \$2^2 > 1\$ is satisfied. However, 7 is *not* a Proth number because the only way to write it in the form \$N = k \times 2^n + 1\$ is
$$ 7 = (3 \times 2^1) + 1 $$
and \$2^1 > 3\$ is not satisfied.
Your challenge is fairly simple: you must write a program or function that, given a positive integer, determines if it is a Proth number or not. You may take input in any reasonable format, and should output a truthy value if it is a Proth number and a falsy value if it is not. If your language has any "Proth-number detecting" functions, you *may* use them.
# Test IO
Here are the first 46 Proth numbers up to 1000. ([A080075](https://oeis.org/A080075))
```
3, 5, 9, 13, 17, 25, 33, 41, 49, 57, 65, 81, 97, 113, 129, 145, 161, 177, 193, 209, 225, 241, 257, 289, 321, 353, 385, 417, 449, 481, 513, 545, 577, 609, 641, 673, 705, 737, 769, 801, 833, 865, 897, 929, 961, 993
```
Every other valid input should give a falsy value.
As usual, this is code-golf, so standard loopholes apply, and the shortest answer in bytes wins!
---
*Number theory fun-fact side-note:*
The largest known prime that is *not* a Mersenne Prime is \$19249 \times 2^{13018586} + 1\$, which just so happens to also be a Proth number!
  
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 5 [bytes](https://github.com/DennisMitchell/jelly/wiki/Code-page)
```
’&C²>
```
[Try it online!](http://jelly.tryitonline.net/#code=4oCZJkPCsj4&input=&args=MzM) or [verify all test cases](http://jelly.tryitonline.net/#code=4oCZJkPCsj4KMTAwMFLDh8OQZg&input=).
Let \$\newcommand{\&}[]{\text{ & }}j\$ be a strictly positive integer. \$j + 1\$ toggles all trailing set bits of \$j\$ and the adjacent unset bit. For example, \$10011\_{2} + 1 = 10100\_{2}\$.
Since \${\sim}j = -(j + 1) = -j - 1\$, \$-j = {\sim}j + 1\$, so \$-n\$ applies the above to the bitwise NOT of \$j\$ (which toggles *all* bits), thus toggling all bits before the last \$1\$.
By taking \$j \& (-j)\$ (the bitwise AND of \$j\$ and \$-j\$), all bits before and after the last set bit are nullified (since unequal in \$j\$ and \$-j\$), thus yielding the highest power of \$2\$ that divides \$j\$ evenly.
For input \$N\$, we want to apply the above to \$N - 1\$ to find \$2^{n}\$, the highest power of \$2\$ that divides \$N - 1\$. If \$m = N - 1\$, \$-m = -(N - 1) = 1 - N\$, so \$(N - 1) \& (1 - N)\$ yields \$2^{n}\$.
All that's left to test is if \$2^{n} > k\$. If \$k > 0\$, this is true if and only if \$(2^{n})^{2} > k2^{n}\$, which is true itself if and only if \$(2^{n})^{2} \ge k2^{n} + 1 = N\$.
Finally, if \$(2^{n})^{2} = N = k2^{n} + 1\$, \$2^{n}\$ must be odd (\$1\$) so the parities of both sides can match, implying that \$k = 0\$ and \$N = 1\$. In this case \$(N - 1) \& (1 - N) = 0 \& 0 = 0\$ and \$((N - 1) \& (1 - N))^{2} = 0 < 1 = N\$.
Therefore, \$((N - 1) \& (1 - N))^{2} > N\$ is true if and only if \$N\$ is a Proth number.
### How it works
```
’&C²>  Main link. Argument: N
’      Decrement; yield N - 1.
  C    Complement; yield 1 - N.
 &     Take the bitwise AND of both results.
   ²   Square the bitwise AND.
    >  Compare the square to N.
```
[Answer]
# Python, 22 bytes
```
lambda N:N-1&1-N>N**.5
```
This is a port of [my Jelly answer](https://codegolf.stackexchange.com/a/89442/12012). Test it on [Ideone](http://ideone.com/yDI2FL).
### How it works
Let \$\newcommand{\&}[]{\text{ & }}j\$ be a strictly positive integer. \$j + 1\$ toggles all trailing set bits of \$j\$ and the adjacent unset bit. For example, \$10011\_{2} + 1 = 10100\_{2}\$.
Since \${\sim}j = -(j + 1) = -j - 1\$, \$-j = {\sim}j + 1\$, so \$-n\$ applies the above to the bitwise NOT of \$j\$ (which toggles *all* bits), thus toggling all bits before the last \$1\$.
By taking \$j \& (-j)\$ (the bitwise AND of \$j\$ and \$-j\$), all bits before and after the last set bit are nullified (since unequal in \$j\$ and \$-j\$), thus yielding the highest power of \$2\$ that divides \$j\$ evenly.
For input \$N\$, we want to apply the above to \$N - 1\$ to find \$2^{n}\$, the highest power of \$2\$ that divides \$N - 1\$. If \$m = N - 1\$, \$-m = -(N - 1) = 1 - N\$, so \$(N - 1) \& (1 - N)\$ yields \$2^{n}\$.
All that's left to test is if \$2^{n} > k\$. If \$k > 0\$, this is true if and only if \$(2^{n})^{2} > k2^{n}\$, which is true itself if and only if \$(2^{n})^{2} \ge k2^{n} + 1 = N\$.
Finally, if \$(2^{n})^{2} = N = k2^{n} + 1\$, \$2^{n}\$ must be odd (\$1\$) so the parities of both sides can match, implying that \$k = 0\$ and \$N = 1\$. In this case \$(N - 1) \& (1 - N) = 0 \& 0 = 0\$ and \$((N - 1) \& (1 - N))^{2} = 0 < 1 = N\$.
Therefore, \$((N - 1) \& (1 - N))^{2} > N\$ is true if and only if \$N\$ is a Proth number.
Ignoring floating point inaccuracies, this is equivalent to the code `N-1&1-N>N**.5` in the implementation.
[Answer]
# Python 2, 23 bytes
```
lambda n:(~-n&1-n)**2>n
```
[Answer]
# Mathematica, ~~50~~ ~~48~~ ~~45~~ ~~40~~ ~~38~~ ~~35~~ ~~31~~ 29 bytes
Mathematica generally sucks when it comes to code golf, but sometimes there's a built-in that makes things look really nice.
```
1<#<4^IntegerExponent[#-1,2]&
```
A test:
```
Reap[Do[If[f[i],Sow[i]],{i,1,1000}]][[2,1]]
{3, 5, 9, 13, 17, 25, 33, 41, 49, 57, 65, 81, 97, 113, 129, 145, 161, 177, 193, 209, 225, 241, 257, 289, 321, 353, 385, 417, 449, 481, 513, 545, 577, 609, 641, 673, 705, 737, 769, 801, 833, 865, 897, 929, 961, 993}
```
Edit: Actually, if I steal [Dennis](https://codegolf.stackexchange.com/users/12012/dennis)'s bitwise AND idea, I can get it down to ~~23~~ ~~22~~ 20 bytes.
# Mathematica, ~~23~~ ~~22~~ 20 bytes (thanks [A Simmons](https://codegolf.stackexchange.com/users/49583/a-simmons))
```
BitAnd[#-1,1-#]^2>#&
```
[Answer]
# [05AB1E](http://github.com/Adriandmen/05AB1E), ~~14~~ 10 bytes
Thanks to **Emigna** for saving 4 bytes!
### Code:
```
<©Ó¬oD®s/›
```
Uses the **CP-1252** encoding. [Try it online!](http://05ab1e.tryitonline.net/#code=PMOSwqkyUcK3MEtQwq4yS1DigLo&input=MTc3).
### Explanation:
For the explanation, let's use the number **241**. We first decrement the number by one with `<`. That results into **240**. Now, we calculate the prime factors (with duplicates) using `Ò`. The prime factors are:
```
[2, 2, 2, 2, 3, 5]
```
We split them into two parts. Using `2Q·0K`, we get the list of two's:
```
[2, 2, 2, 2]
```
With `®2K`, we get the list of the remaining numbers:
```
[3, 5]
```
Finally, take the product of both. `[2, 2, 2, 2]` results into **16**. The product of `[3, 5]` results into **15**.
This test case is truthy since **16** > **15**.
[Answer]
# [Brain-Flak](https://github.com/DJMcMayhem/Brain-Flak), ~~460~~ ~~350~~ ~~270~~ ~~266~~ ~~264~~ ~~188~~ 176 bytes
[Try it online!](http://brain-flak.tryitonline.net/#code=KHt9WygpXSkoKCg8PigpKSkpe3t9KFsoKCgoe308KCh7fSl7fSk-KXt9KXt9KTw-Wyh7fSkoKCkpXSldKDw-KSl7KHt9KCkpPD59e308Pnt9e308Pigoe30pKXt7fXt9PD4oPCgoKSk-KX17fX0oPHt9e30-KTw-eyh7fVsoKV0pPD4oKHt9KClbKHt9KV0pKXt7fSg8KHt9KHt9KSk-KX17fTw-fXt9PD4oe308Pik&input=MjA5)
```
({}[()])(((<>()))){{}([(((({}<(({}){})>){}){})<>[({})(())])](<>)){({}())<>}{}<>{}{}<>(({})){{}{}<>(<(())>)}{}}(<{}{}>)<>{({}[()])<>(({}()[({})])){{}(<({}({}))>)}{}<>}{}<>({}<>)
```
### Explanation
The program goes through powers of two and four until it finds a power of two greater than N-1. When it finds it it checks for the divisibility of N-1 by the power of two using modulo and outputs the result
```
({}[()])      #Subtract one from input
(((<>())))    #Put three ones on the other stack
{
 {}           #Pop the crap off the top
 ([(
  ((({}<(({}){})>){}){}) #Multiply the top by four and the bottom by two
  <>[({})(())])](<>)){({}())<>}{}<>{}{}<>(({})){{}{}<>(<(())>)}{} #Check if the power of four is greater than N-1
}
(<{}{}>) #Remove the power of 4
<>{({}[()])<>(({}()[({})])){{}(<({}({}))>)}{}<>}{}<>({}<{}><>) #Modulo N-1 by the power of two
```
This program is not stack clean. If you add an extra 4 bytes you can make it stack clean:
```
({}[()])(((<>()))){{}([(((({}<(({}){})>){}){})<>[({})(())])](<>)){({}())<>}{}<>{}{}<>(({})){{}{}<>(<(())>)}{}}(<{}{}>)<>{({}[()])<>(({}()[({})])){{}(<({}({}))>)}{}<>}{}<>({}<{}><>)
```
[Answer]
# Regex (ECMAScript), ~~48~~ ~~43~~ 41 bytes
Neil's and H.PWiz's regexes (both also ECMAScript flavour) are beautiful in their own right. There is another way to do it, which by a pretty neat coincidence was 1 byte more than Neil's, and now with H.PWiz's suggested golfing (thanks!), is 1 byte ~~more~~ less than H.PWiz's.
**Warning:** Despite this regex's small size, it contains a **major spoiler**. I highly recommend learning how to solve unary mathematical problems in ECMAScript regex by figuring out the initial mathematical insights independently. It's been a fascinating journey for me, and I don't want to spoil it for anybody who might potentially want to try it themselves, especially those with an interest in number theory. [See this earlier post](https://codegolf.stackexchange.com/a/178889/17216) for a list of consecutively spoiler-tagged recommended problems to solve one by one.
So **do not read any further if you don't want some advanced unary regex magic spoiled for you**. If you do want to take a shot at figuring out this magic yourself, I highly recommend starting by solving some problems in ECMAScript regex as outlined in that post linked above.
So, this regex works quite simply: It starts by subtracting one. Then it finds the largest odd factor, *k*. Then we divide by *k* (using the division algorithm briefly explained in a spoiler-tagged paragraph of my [factorial numbers regex post](https://codegolf.stackexchange.com/a/178952/17216)). We sneakily do a simultaneous assertion that the resultant quotient is greater than *k*. If the division matches, we have a Proth number; if not, we don't.
I was able to drop 2 bytes from this regex (43 → 41) using a trick found by [Grimmy](https://codegolf.stackexchange.com/users/6484/grimmy) that can futher shorten division in the case that the quotient is guaranteed to be greater than or equal to the divisor.
> 
>  `^x(?=(x(xx)*)\1*$)((\1x*)(?=\1\4*$)x)\3*$`
> 
> 
> 
[Try it online!](https://tio.run/##TY@9bsIwFEZfhUYI7g1NSFrKgGuYOrAwtGPTShZcHLfGsWwDLj/PnoahUtdzPunT@RIH4ddO2ZB5qzbkdo35pp/WcUPH3ivJl2gBTnw@TtvPCAsOEWLEFKsy7SNAVcYUO1yV1aQDEavHtN@m4xPmoXkLThkJmHut1gTT@2yCyDwv2LFWmgA0dyQ2WhkCxDtu9lrjWXKde6tVgGE2RKa2AIbLXJORocb5w@Wi/EqsQHErnKelCSDfiw/EP0H/hZmXi3J20xhq1xyTpTkIrTY9J4ykWS8ZabZtHDD1zImp0Qi7wyQmuSNLIoDCfCfCugaHePaDge2SAtwqSmb3wQfXTdj12hbZ9KkofgE "JavaScript (SpiderMonkey) – Try It Online")
> 
>  
> ```
> 
>  # Match Proth numbers in the domain ^x*$
>  ^
>  x                         # tail = tail - 1
>  (?=(x(xx)*)\1*$)          # \1 = largest odd factor of tail
> 
>  # Calculate tail / \1, but require that the quotient, \3, be > \1
>  # (and the quotient is implicitly a power of 2, because the divisor
>  # is the largest odd factor).
>  (                         # \3 = tail / \1, asserting that \3 > \1
>      (\1x*)                # \4 = \3-1
>      (?=\1\4*$)            # We can skip the test for divisibility by \1-1
>                            # (and avoid capturing it) because we've already
>                            # asserted that the quotient is larger than the
>                            # divisor.
>      x
>  )
>  \3*$
>  
> ```
> 
> 
> 
> 
[Answer]
# [MATL](https://github.com/lmendo/MATL), 9 bytes
```
qtYF1)EW<
```
Truthy output is `1`. Falsy is `0` or empty output. (The only inputs that produce empty output are `1` and `2`; the rest produce either `0` or `1`).
[**Try it online!**](http://matl.tryitonline.net/#code=cXRZRjEpRVc8&input=OTkz)
### Explanation
Let *x* denote the input. Let *y* be the largest power of 2 that divides *x*−1, and *z* = (*x*−1)/*y*. Note that *z* is automatically odd. Then *x* is a Proth number if and only if *y* > *z*, or equivalently if *y*2 > *x*−1.
```
q    % Input x implicitly. Subtract 1
t    % Duplicate
YF   % Exponents of prime factorization of x-1
1)   % First entry: exponent of 2. Errors for x equal to 1 or 2
E    % Duplicate
W    % 2 raised to that. This is y squared
<    % Is x-1 less than y squared? Implicitly display
```
[Answer]
# [Brachylog](https://github.com/JCumin/Brachylog), 28 bytes
```
>N>0,2:N^P:K*+?,P>K:2%1,N:K=
```
[Try it online!](http://brachylog.tryitonline.net/#code=Pk4-MCwyOk5eUDpLKis_LFA-SzoyJTEsTjpLPQ&input=ODI)
[Verify all testcases at once.](http://brachylog.tryitonline.net/#code=MTAwOjFmLgo-Lj4wLC4-Tj4wLDI6Tl5QOksqKy4sUD5LOjIlMSxOOks9&input=&args=Wg&debug=on)
(Slightly modified.)
### Explanation
Brachylog, being a derivative of Prolog, is very good at proving things.
Here, we prove these things:
```
>N>0,2:N^P:K*+?,P>K:2%1,N:K=
>N>0                           input > N > 0
     2:N^P                     2^N = P
         P:K*+?                P*K+1 = input
                P>K            P > K
                  K:2%1        K%2 = 1
                        N:K=   [N:K] has a solution
```
[Answer]
# Haskell, ~~55~~ 46 bytes
```
f x=length [x|k<-[1,3..x],n<-[1..x],k*2^n+1==x,2^n>k]>0
```
Edit: 
Thanks to nimi, now 46 bytes
```
f x=or[k*2^n+1==x|k<-[1,3..x],n<-[1..x],2^n>k]
```
[Answer]
# Julia, 16 bytes
```
!x=~-x&-~-x>x^.5
```
Credits to @Dennis for the answer and some golfing tips!
[Answer]
# R, ~~52~~ 50 bytes
```
x=scan()-1;n=0;while(!x%%2){x=x/2;n=n+1};2^(2*n)>x
```
The program begins by dividing `N-1` (called here `P` and `x`) by `2` as long as possible in order to find the `2^n`part of the equation, leaving `k=(N-1)/2^n`, and then computes wether or not `k` is inferior to `2^n`, using the fact that `2^n>x/2^n <=> (2^n)²>x <=> 2^2n>x`
[Answer]
# Regex (ECMAScript), ~~40~~ 38 bytes
*-2 bytes thanks to Deadcode*
```
^x(?=((xx)+?)(\1\1)*$)(?!(\1x\2*)\4*$)
```
[Try it online!](https://tio.run/##Tc0xb8IwEAXgvwJRJe6SxiQIMZCaTB1YGNqxoZIVDudaY0eOCymlvz1Nh0rd3nvf8N7UWXW15zakXcsH8idn3@lz8NLSZfJE@rFvAa5yM4@H1x5KCdD3mJQIVV7lGN8hlNMx99Uixmo59iGeX1EE9xw8Ww0oOsM1weo@XSIWl4YNARjpSR0MWwLEqbQfxuCXlkZ0reEAs3SGBR8BrNTCkNWhwc3iduNup3bAslW@o60NoF@yPeIf0H@wm7zM17@MofHuEm3tWRk@TLyymtaTKDHF0Xko@EFSwUmC42HUR8JTSyoAozipUDfgEWtnO2dIGKfHvfgesnSVZdkP)
Commented version:
```
# Subtract 1 from the input N
^x
# Assert N is even.
# Capture \1 = biggest power of 2 that divides N.
# Capture \2 = 2.
(?=((xx)+?)(\1\1)*$)
# Assert no odd number > \1 divides N
(?!(\1x\2*)\4*$)
```
[Answer]
# J, 10 bytes
```
%:<<:AND-.
```
Based on @Dennis' bitwise [solution](https://codegolf.stackexchange.com/a/89444/6710).
Takes an input `n` and returns 1 if it is Proth number else 0.
## Usage
```
   f =: %:<<:AND-.
   f 16
0
   f 17
1
   (#~f"0) >: i. 100  NB. Filter the numbers [1, 100]
3 5 9 13 17 25 33 41 49 57 65 81 97
```
## Explanation
```
%:<<:AND-.  Input: n
        -.  Complement. Compute 1-n
   <:       Decrement. Compute n-1
     AND    Bitwise-and between 1-n and n-1
%:          Square root of n
  <         Compare sqrt(n) < ((1-n) & (n-1))
```
[Answer]
# [Retina 0.8.2](https://github.com/m-ender/retina/wiki/The-Language/a950ad7d925ec9316e3e2fb2cf5d49fd15d23e3d), 47 bytes
```
\d+
$*
+`(1+)\1
$+0
01
1
+`.10(0*1)$
1$1
^10*1$
```
[Try it online!](https://tio.run/##DY07akNBEATzOscK3gfE9Mzs7wS6hDAy2IETB8b3f9qsqaa6/77/f34/r9v2eF3Pr5NycL42nftTlNMwoUXuss0O7QUV8aGVy3XZ6pwgqTQ6g4kWXI6jQIkqaqijgSZu@HIcDzzxije84wOfhBEi1mQQSVSiEZ0YxCSNFOnkekyyko3s5CAn1d4 "Retina 0.8.2 – Try It Online") Explanation: Given a Proth number \$ k · 2^n + 1 \$, you can derive two new Proth numbers \$ (2k±1) · 2^{n + 1} + 1 \$. We can run this in reverse until we obtain a Proth number where \$ k = 1 \$. This is readily performed by transforming the binary representation.
```
\d+
$*
```
Convert to unary.
```
+`(1+)\1
$+0
01
1
```
Convert to binary.
```
+`.10(0*1)$
1$1
```
Repeatedly run the Proth generation formula in reverse.
```
^10*1$
```
Match the base case of the Proth generation formula.
Edit: I think it's actually possible to match a Proth number directly against a unary number with a single regex. This currently takes me 47 bytes, 7 bytes more than my current Retina code for checking whether a unary number is a Proth number:
```
^.(?=(.+?)(\1\1)*$)(?=((.*)\4.)\3*$).*(?!\1)\3$
```
[Answer]
# ECMAScript Regex, 42 bytes
```
^x(?=(x(xx)*)\1*$)(?=(x+?)((\3\3)*$))\4\1x
```
[Try it online!](https://tio.run/##HYwxCsMwEAT7fYcMdydkpDitcZlPHEIBu3DjIqTYl@UB@ZgiUs7AzOt4n9ezdN8jjIhTq0LT5IURoXw/DBnTIS3R0CtlW4VCqqkXC/rnuKmIL77oMOr3Efcwr9A2V@DRfMe49ZxuOf8A) (Using Retina)
I essentially subtract 1, divide by the largest possible odd number `k`, then check that at least `k+1` is left over.
It turns out that my regex is very similar to the one Neil gives at the end of his [answer](https://codegolf.stackexchange.com/a/179066/71256). I use `x(xx)*` instead of `(x*)\2x`. And I use a shorter method to check `k < 2^n`
[Answer]
# [Brain-Flak](https://github.com/DJMcMayhem/Brain-Flak), 128 bytes
```
({<{({}[()]<(([{}]())<>{})<>>)}{}>{{}(<>)}{}}<><(())>){([()]{}<(({}){})>)}{}([({}[{}(())])](<>)){({}())<>}{}{((<{}>))<>{}}{}<>{}
```
[Try it online!](https://tio.run/##JYwxCsRADAO/IxVXpQoYfyRskRSBcEeKtMJv32j3wFi2Jc/x7Nf9OX/7t3coBNUGtgA2VQMZqXJLliqlQsyxIp0hk8J4UHl10jV9H02yOtPYxhcHfBLtCwgD/3zvQ3pf1@UF "Brain-Flak – Try It Online")
I used a very different algorithm than the [older Brain-Flak solution](https://codegolf.stackexchange.com/a/89453/31203).
Basically, I divide by 2 (rounding up) until I hit an even number. Then I just compare the result of the last division with the two to the power of the number of times I divided.
## Explanation:
```
({
  # (n+1)/2 to the other stack, n mod 2 to this stack
  <{({}[()]<(([{}]())<>{})<>>)}{}>
  # if 1 (n was odd) jump to the other stack and count the one
  {{}(<>)}{}
#end and push the sum -1, with a one under it
}<>[(())])
#use the one to get a power of two
{([()]{}<(({}){})>)}{}
#compare the power of two with the remainder after all the divisions
([({}[{}(())])](<>)){({}())<>}{}{((<{}>))<>{}}{}<>{}
```
[Answer]
# [Bitwise Fuckery](https://github.com/cairdcoinheringaahing/Bitwise-Fuckery), 56 bytes
```
,-@|~+&[>+>+<<-]>%>[<|[<+>-]>-]<<[>+<-]|+[-(>.<)>-(.>)<]
```
[Try it online!](https://tio.run/##rVbbbqMwEH2Gr7AqNdjiomT3LSKo/8FSxGK3QUoMMmS30Wb761lfSD11A5tKjRQJ5nJmzhgfuzsO25Z/P5@bfdeKAfXH3vcpe0L7quG4Es@/ItQPtOFk7XtPjeiHcqg6hjYoXxa@17O65fSdqW6pelap@apIBOt2Vc1w8IMHEQoCAiyDa0HG4HsKsJcod/Fwhxpu0L6tJTxlPw/P2kMdDz/smWhq7eOOT@GVW1ZR6V2aHsuGU/Zi3ndt25WUdcPWvDe8OwwwwPd@b5sdQyAxRTvGsTKo0Xj1thIyVr3nNkqW9ponZJyyscc7FQsGmb91VqDHDQLzBB4HZDEHsrgR5DQHcroR5HUOZINerzocjAcXI0LvvyrwFiEb5sDcz7QSTbBBUzRhncnOgz/BDPs0vW2Gwd85lCybRHH4h3NLEW7QyomP5@Ljj/GZibcbacT0BnFcT47LYy@13FY6FdRKqq5jnOIl0Q7A8J0H1k/d@mOPKsgaU7Q0tazpfqM3qi3uIicGWZpGBZF0DlzpSD8IzWHXszdbvdW2TjR8wLLTjbLj6mePleHqHIj8OTWj@Y3TCoq16uZAiQqCJASUJiNBRp6R6hLFZiQgRi@TMo5/2EVuugDqF9qh8na4vqzrcc0qUSu51PGjPBqjCYAie4E15R2J1LsgD9Zj9g3BhQ2@fAUuteJtUb@KQ/yZtj5F@IKsvzOdBVZkiiD@coL/7xl/hiD5QNCtZRjpA31t95RiGIGDNrLbG8pyNHUugCEsVsqx04fIsU/kRmFCEFl31IxelTVDAVebilMIF680nyUUuaRrO0x8O1F7XqlsqNg2HarcJd9Qhqyu9HsJcwh/5CVplSWv9qws9RKUpbrFlaU6YfR9TkWPdzqT13B5@aooJuR8Jucofji9hos8C7MwTeMiu8/y9JSnYSaf4yJNpUeaT2Ee4yxJSRbjJCNp8Q8)
Uses the [latest version](https://github.com/cairdcoinheringaahing/Bitwise-Fuckery) of the language, in which I finally fixed the `[]` and `()` loops.
Inputs via char code. Outputs a null byte if the input is not a Proth number, outputs a non-null byte otherwise. Add the `-n` flag to output an an integer.
## How it works
Bitwise Fuckery is, unsurprisingly, an extension of brainfuck with bitwise commands, an "if zero" loop and a second tape. As [demonstrated by Dennis](https://codegolf.stackexchange.com/a/89442/66833), bitwise operations are helpful in this challenge, so I thought I'd fix up the language and give it a go.
Bitwise Fuckery's second tape has the same tape head as the first tape, and certain commands operate on the two values under the tape head on each tape. I've marked the tape heads with `(...)` in the explanation.
I'll work through the program with an example input of `5` (that's the char code of the character, not the character `5`)
```
,	# Take a byte of input
	#   Tapes: [( 5)  0   0 ...] [( 0)  0   0 ...]
-	# Decrement it
	#   Tapes: [( 4)  0   0 ...] [( 0)  0   0 ...]
@	# Swap tapes
	#   Tapes: [( 0)  0   0 ...] [( 4)  0   0 ...]
|	# Bitwise OR, copying across
	#   Tapes: [( 4)  0   0 ...] [( 4)  0   0 ...]
~+	# Bitwise NOT and increment
	#   Tapes: [(-4)  0   0 ...] [( 4)  0   0 ...]
&	# Bitwise AND
	#   Tapes: [( 4)  0   0 ...] [( 4)  0   0 ...]
[>+>+	# Copy the first cell into cells 2 and 3
 <<-]	#   Tapes: [( 0)  4   4 ...] [( 4)  0   0 ...]
>	# Move along one cell
	#   Tapes: [  0 ( 4)  4 ...] [  4 ( 0)  0 ...]
%>	# Swap the cells under the tape head and move
	#   Tapes: [  0   0 ( 4)...] [  4   4 ( 0)...]
[	# Square the value under the tape head:
 <|	# Move left and Bitwise XOR
	#   Tapes: [  0 ( 4)  4 ...] [  4 ( 4)  0 ...]
 [<+>-]	# Copy into the first cell
	#   Tapes: [  4 ( 0)  4 ...] [  4 ( 4)  0 ...]
 >-	# Move right and decrement
	#   Tapes: [  4   0 ( 3)...] [  4   4 ( 0)...]
]	# Repeat while the tape head is non-zero
	#   Tapes: [ 16   0 ( 0)...] [  4   4 ( 0)...]
<<	# Move to the first cell
	#   Tapes: [(16)  0   0 ...] [( 4)  4   0 ...]
[>+<-]	# Copy into the second cell
	#   Tapes: [( 0) 16   0 ...] [( 4)  4   0 ...]
|+	# Logical OR and increment, restoring N to the tape
	#   Tapes: [( 5) 16   0 ...] [( 4)  4   0 ...]
[	# Check that N is less than the second cell
 -	# Decrement N
	#   Tapes: [( 4) 16   0 ...] [( 4)  4   0 ...]
 (	# If zero:
  >.<	#  Output the value in the second cell
	#    Tapes: [( 4) 16   0 ...] [( 4)  4   0 ...]
 )
 >-	# Move right and decrement
	#    Tapes: [  4 (15)  0 ...] [  4 ( 4)  0 ...]
 (	# If zero:
  .>	#   Output and move right
	#    Tapes: [  4  15 ( 0)...] [  4   4 ( 0)...]
 )
 <	# Move left
	#    Tapes: [  4 (15)  0 ...] [  4 ( 4)  0 ...]
]
```
[Answer]
# [Pyt](https://github.com/mudkip201/pyt), 7 bytes
```
Đ⁻Đ~∧²<
```
[Try it online!](https://tio.run/##K6gs@f//yIRHjbuPTKh71LH80Cab//8NjQE "Pyt – Try It Online")
Port of [Dennis's Jelly answer](https://codegolf.stackexchange.com/a/89444/116013)
[Answer]
# Maple, 100 bytes (including spaces)
```
IsProth:=proc(X)local n:=0;local x:=X-1;while x mod 2<>1 do x:=x/2;n:=n+1;end do;is(2^n>x);end proc:
```
Nicely spaced for readbility:
```
IsProth := proc( X )
    local n := 0;
    local x := X - 1;
    while x mod 2 <> 1 do
        x := x / 2;
        n := n + 1;
    end do;
    is( 2^n > x );
end proc:
```
Same idea as several others; divide X by 2 until X is no longer evenly divisible by 2, then check the criteria 2^n > x.
[Answer]
# Java 1.7, ~~49~~ 43 bytes
*Another 6 bytes the dust thanks to @charlie.*
```
boolean g(int p){return p--<(p&-p)*(p&-p);}
```
[Try it!](https://ideone.com/pmqMI0) (ideone)
~~Two ways, equally long. As with most answers here, credits go to @Dennis of course for the expression.~~
Taking the root of the righthand side of the expression:
```
boolean f(int p){return(p-1&(1-p))>Math.sqrt(p);}
```
Applying power of two to the lefthand side of the expression:
```
boolean g(int p){return Math.pow(p-1&(1-p),2)>p;}
```
Can shave off a single byte if a positive numeric value is allowed to represent 'truthy', and a negative value 'falsy':
```
double g(int p){return Math.pow(p-1&(1-p),2)-p;}
```
Unfortunately because of ['Narrowing Primitive Conversion'](https://docs.oracle.com/javase/specs/jls/se7/html/jls-5.html#jls-5.1.3) one cannot simply write this in Java and get correct results:
```
((p - 1 & (1 - p))^2) > p;
```
And any attempt to widen 'p' will lead to a compile error because bitwise operators are not supported on i.e. floats or doubles :( 
[Answer]
# [Hy](http://hylang.org/), 37 bytes
```
(defn f[n](>(**(&(- n 1)(- 1 n))2)n))
```
[Try it online!](https://tio.run/##FYsxCoAwFEN3T5FJ8gWh9QBepHQQ7NcuXykunr5@MyQvhJxv79yLGjRZ5spp4sgZhigeESayiFunXg2pgm2zo/gSQwiSB4BVQUUV51@8W7XHu78@ "Hy – Try It Online")
Port of @Dennis' answer.
[Answer]
# [C (gcc)](https://gcc.gnu.org/), 29 ~~30~~ bytes
```
z;f(x){return--x<(z=x&-x)*z;}
```
[Try it online!](https://tio.run/##FYpBDoIwEEXXcooJBjMj1MC6oBdxY1oqk0hLakkaCGevdfVf3vtKvJVKZ7bqs@oR@m/Q7G7TPW3SYKTdj2H1VojY4zbEi4h03eSR2AaYX2yRYC8AwDiPf8cwQCfz9NC1bYa6puK0@NwMlot3YXpgpSnfKv20ZQPcgEEmksWRfg "C (gcc) – Try It Online")
[Answer]
# [Japt](https://github.com/ETHproductions/japt), ~~12~~ ~~10~~ 9 bytes
```
É&1-U)>Uq
```
[Try it online!](https://tio.run/##y0osKPn//3CnmqFuqKZdaOH//4bmAA "Japt – Try It Online")
Port of Dennis' Jelly answer again. - 1 thanks to @Shaggy.
[Answer]
# x86 Machine Code, 15 bytes
```
4F 89 F8 F7 D8 21 F8 0F AF C0 39 C7 19 C0 C3
```
These bytes define a function that takes the input argument (an unsigned integer) in the `EDI` register, following the standard System V calling convention for x86 systems, and it returns the result in the `EAX` register, like *all* x86 calling conventions.
In assembler mnemonics:
```
4F          dec   edi            ; input -= 1
89 F8       mov   eax, edi       ; \ temp
F7 D8       neg   eax            ; |      =
21 F8       and   eax, edi       ; /        (input & -input)
0F AF C0    imul  eax, eax       ; temp *= temp
39 C7       cmp   edi, eax       ; set CF if (input < temp)
19 C0       sbb   eax, eax       ; EAX = -CF
C3          ret                  ; return with result in EAX
                                 ;  (-1 for Proth number; 0 otherwise)
```
**[Try it online!](https://tio.run/##jVJNa8JAED0nv2LYImw01nitplCwBy@lxx6EsCabOLDZhP2QYvGvN91EG0xV6LAw7Mx7bx8zm05TwWTRNFZqLCTPYK3fVWV2b7bcckX78p4JywP/ywcXfVVxbYVZdMUkYbpMEko2JuOpcJXRiGe4kaRr/4Zrl9W@b4dtYp83UJIXZ9TNNpPZP0SwtEKcRe6j0rLunwrv2tbb7RB1pfUEJGYE6GksAcBsDJU1tTVuUgVqwxWghteXDxjP/hBXBICepgwdEWXLGxJX6yvi5S04bUJxY5Xsl3NsHlCmwmYcltpkWD3unn0fpYGSoaTtUr28UkA1HnhiACGG@cKlJcyjKFrAZIKB7zmUhznQ4QfBAOIYpnMH6BBerZxyTsnoYEMgIaAz5XlHvz1nY1Hr6TvNBSt08wM "C (clang) – Try It Online")**
It's a pretty straightforward solution—and conceptually similar to [MegaTom's C version](https://codegolf.stackexchange.com/a/179088). In fact, you could write this in C as something like the following:
```
unsigned IsProthNumber(unsigned input)
{
    --input;
    unsigned temp  = (input & -input);
    temp          *= temp;
    return (input < temp) ? -1 : 0;
}
```
but the machine code above is better golfed than what you'll get out of a C compiler, even when it's set to optimize for size.
The only "cheat" here is returning -1 as a "truthy" value and 0 as a "falsy" value. This trick allows the use of the 2-byte `SBB` instruction as opposed to the 3-byte `SETB` instruction.
[Answer]
# [Thunno](https://github.com/Thunno/Thunno), \$ 12 \log\_{256}(96) \approx \$ 9.88 bytes
```
zt1-s1_A&2^q
```
[Attempt This Online!](https://ato.pxeger.com/run?1=m72sJKM0Ly9_wYKlpSVpuhZrqkoMdYsN4x3VjOIKIUJQmQWLjI0hLAA) or [generate all values up to 100](https://ato.pxeger.com/run?1=m72sJKM0Ly9_abRSilLssiijakNtl6WlJWm6FmuqSgx1iw3jHdWM4gohQovto7whrAULIDQA).
Port of Dennis's Jelly answer
#### Explanation
```
zt1-s1_A&2^q  # Implicit input
zt            # Triplicate
  1-s         # Decrement and swap
     1_       # Subtract from 1
       A&     # Bitwise AND
         2^   # Squared
           q  # Is greater than the input?
```
[Answer]
# Cjam, 11 bytes
Like many of us, piggybacking off of Dennis's excellent solution:
```
qi_(_W*&2#<
```
[Try it online](http://cjam.aditsu.net/#code=qi_(_W*%262%23%3C&input=9)
[Answer]
# C (137 bytes)
```
int P(int N){int x=1,n=0,k=1,e=1,P=0;for(;e;n++){for(x=1,k=1;x&&x<N;k+=2){x=2<<n;x=x>k?x*k+1:0;if(x>N&&k==1)e=0;}if(x==N)P=1;}return P;}
```
Only came to read the answers after I tried it.
Considering `N=k*2^n+1` with the conditional of `k<2^n` (`k=1,3,5..` and `n=1,2,3..`
With `n=1` we have one `k` available to test. As we increase `n` we get a few more `k's` to test like so:
n=1 ; k=1
n=2 ; k=1 k=3
n=3 ; k=1 k=3 k=5 k=7
...
Iterating through those possibilities we can be sure N is not a Prouth number if for a given `n` the `k=1` number obtained is larger than N and no other iteration was a match.
So my code basically "brute-forces" its way into finding N.
After reading the other answers and realizing you can factor N-1 with 2 to find `n` and then make the conditional of `k<2^n`, I think my code could be smaller and more efficient using this method.
It was worth a try!
*Tested all numbers given and a few "non-Prouth" numbers. Function returns 1 if the number is a Prouth number and 0 if it's not.*
[Answer]
# Javascript ES7, 16 bytes
```
x=>x--<(-x&x)**2
```
Port of my Julia answer, which is a port of @Dennis's Jelly answer.
*Thanks @Charlie for 2 bytes saved!*
[Answer]
# [C# (.NET Core)](https://www.microsoft.com/net/core/platform), 17 bytes
```
x=>x--<(x=x&-x)*x
```
[Try it online!](https://tio.run/##NY2xCsIwFEX3fsWjiCSmKe1qmi6Ck4Lg4FxjAoGaQBPlldJvjwF1vOdyOCpw5Sed1DiEABdYihCHaBW8vX3AebCO0AwBjJ@IdRFQttUsW4Fd2zSNQMZofgGsIYYg/Q6A6xyiftYH74IfdX2bbNQn6zTZlMvM2LqHBdeSimIt/sWfcnw51eVSBXfvxx4MyISyR847ghK3HOkOUxbTBw "C# (.NET Core) – Try It Online")
Port of [MegaTom's C answer](https://codegolf.stackexchange.com/a/179088/8340).
I attempted a LINQ based solution, but this was too good.
]