35
\$\begingroup\$

A Proth number, named after François Proth, is a number that can be expressed as

N = k * 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

(1 * 2^1) + 1

and 2^1 > 1 is satisfied. 5 Is also a Proth number because it can be written as

(1 * 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 * 2^n + 1 is

(3 * 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 postive 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)

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 * 2^13018586 + 1, which just so happens to also be a Proth number!

\$\endgroup\$

25 Answers 25

37
\$\begingroup\$

Jelly, 5 bytes

’&C²>

Try it online! or verify all test cases.

Background

Let j be a strictly positive integer. j + 1 toggles all trailing set bits of j and the adjacent unset bit. For example, 100112 + 1 = 101002.

Since ~j = -(j + 1) = -j - 1, -j = ~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 2n, the highest power of 2 that divides N - 1. If m = N - 1, -m = -(N - 1) = 1 - N, so (N - 1) & (1 - N) yields 2n.

All that's left to test is if 2n > k. If k > 0, this is true if and only if (2n)2 > k2n, which is true itself if and only if (2n)2 ≥ k2n + 1 = N.

Finally, if (2n)2 = N = k2n + 1, 2n 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.
\$\endgroup\$
  • \$\begingroup\$ woah. thats incredible \$\endgroup\$ – don bright Feb 21 at 5:18
46
\$\begingroup\$

Python, 22 bytes

lambda N:N-1&1-N>N**.5

This is a port of my Jelly answer. Test it on Ideone.

How it works

Let j be a strictly positive integer. j + 1 toggles all trailing set bits of j and the adjacent unset bit. For example, 100112 + 1 = 101002.

Since ~j = -(j + 1) = -j - 1, -j = ~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 2n, the highest power of 2 that divides N - 1. If m = N - 1, -m = -(N - 1) = 1 - N, so (N - 1) & (1 - N) yields 2n.

All that's left to test is if 2n > k. If k > 0, this is true if and only if (2n)2 > k2n, which is true itself if and only if (2n)2 ≥ k2n + 1 = N.

Finally, if (2n)2 = N = k2n + 1, 2n 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.

\$\endgroup\$
  • 23
    \$\begingroup\$ I frequent Math.SE, and my eyes really wish for beautiful LaTeX on this site instead of looking like a 90s site... \$\endgroup\$ – qwr Aug 11 '16 at 23:41
  • \$\begingroup\$ This one's my favorite. \$\endgroup\$ – Qix Aug 12 '16 at 21:47
9
\$\begingroup\$

Python 2, 23 bytes

lambda n:(~-n&1-n)**2>n
\$\endgroup\$
9
\$\begingroup\$

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's bitwise AND idea, I can get it down to 23 22 20 bytes.

Mathematica, 23 22 20 bytes (thanks A Simmons)

BitAnd[#-1,1-#]^2>#&
\$\endgroup\$
  • 2
    \$\begingroup\$ Welcome to Programming Puzzles and Code Golf! :) \$\endgroup\$ – Adnan Aug 10 '16 at 22:41
  • 1
    \$\begingroup\$ No need to begin with g=, a pure function is fine! \$\endgroup\$ – A Simmons Aug 11 '16 at 10:01
  • \$\begingroup\$ Oh, sweet. Fixed it now. \$\endgroup\$ – Michael Lee Aug 11 '16 at 14:04
  • \$\begingroup\$ By the way, your test can be significantly simplified to Select[Range@1000,f]. \$\endgroup\$ – numbermaniac May 20 '17 at 9:11
7
\$\begingroup\$

05AB1E, 14 10 bytes

Thanks to Emigna for saving 4 bytes!

Code:

<©Ó¬oD®s/›

Uses the CP-1252 encoding. Try it online!.

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.

\$\endgroup\$
  • \$\begingroup\$ <©Ó¬oD®s/› or <DÓ0èoDŠ/› for 10. \$\endgroup\$ – Emigna Aug 11 '16 at 20:50
  • \$\begingroup\$ @Emigna That is genius! Thanks :). \$\endgroup\$ – Adnan Aug 11 '16 at 23:06
7
\$\begingroup\$

Brain-Flak, 460 350 270 266 264 188 176 bytes

Try it online!

({}[()])(((<>()))){{}([(((({}<(({}){})>){}){})<>[({})(())])](<>)){({}())<>}{}<>{}{}<>(({})){{}{}<>(<(())>)}{}}(<{}{}>)<>{({}[()])<>(({}()[({})])){{}(<({}({}))>)}{}<>}{}<>({}<>)

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:

({}[()])(((<>()))){{}([(((({}<(({}){})>){}){})<>[({})(())])](<>)){({}())<>}{}<>{}{}<>(({})){{}{}<>(<(())>)}{}}(<{}{}>)<>{({}[()])<>(({}()[({})])){{}(<({}({}))>)}{}<>}{}<>({}<{}><>)
\$\endgroup\$
5
\$\begingroup\$

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!

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

Brachylog, 28 bytes

>N>0,2:N^P:K*+?,P>K:2%1,N:K=

Try it online!

Verify all testcases at once. (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
\$\endgroup\$
5
\$\begingroup\$

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]
\$\endgroup\$
  • 4
    \$\begingroup\$ Welcome to Programming Puzzles & Code Golf! \$\endgroup\$ – Dennis Aug 11 '16 at 3:00
  • \$\begingroup\$ Thanks man! Been a lurker here for a while. Big fan btw, jelly is super cool. Wish I could learn but alas, I don't really understand \$\endgroup\$ – X88B88 Aug 11 '16 at 15:16
  • 2
    \$\begingroup\$ A general tip: if you're just interested in the length of a list created by a comprehension, you can use sum[1| ... ]. Here we can go further and move the equality test in front of the | and check with or if any of them is true: f x=or[k*2^n+1==x|k<-...,n<-...,2^n>k]. \$\endgroup\$ – nimi Aug 11 '16 at 15:33
  • \$\begingroup\$ Wow. Great tips. I'll definitely revise. \$\endgroup\$ – X88B88 Aug 11 '16 at 15:50
  • 2
    \$\begingroup\$ If you're interested in learning Jelly, check out the wiki or join the Jelly room. \$\endgroup\$ – Dennis Aug 11 '16 at 18:00
5
\$\begingroup\$

ECMAScript Regex, 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 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). 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 Grimy 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!


 # 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*$
 

\$\endgroup\$
  • 1
    \$\begingroup\$ O_o wow, only 48 bytes \$\endgroup\$ – ASCII-only Jan 24 at 2:43
  • \$\begingroup\$ Neil's is more similar to mine than to Dennis' \$\endgroup\$ – H.PWiz Jan 24 at 8:24
4
\$\begingroup\$

Julia, 16 bytes

!x=~-x&-~-x>x^.5

Credits to @Dennis for the answer and some golfing tips!

\$\endgroup\$
  • \$\begingroup\$ That doesn't work. In Julia, & has the same precedence as *. \$\endgroup\$ – Dennis Aug 11 '16 at 2:58
  • 1
    \$\begingroup\$ Oh right. Fixed :P I should really test my code. \$\endgroup\$ – Mama Fun Roll Aug 11 '16 at 3:39
  • 2
    \$\begingroup\$ You can use -~-x instead of (1-x). Also, there's √x instead of x^.5, but it doesn't save any bytes. \$\endgroup\$ – Dennis Aug 11 '16 at 3:40
4
\$\begingroup\$

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^npart 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

\$\endgroup\$
  • 1
    \$\begingroup\$ You can pull the P= at the beginning, and change the end to 2^n>x and save like 5 or 6 bytes \$\endgroup\$ – user5957401 Aug 11 '16 at 23:14
4
\$\begingroup\$

Regex (ECMAScript), 40 38 bytes

-2 bytes thanks to Deadcode

^x(?=((xx)+?)(\1\1)*$)(?!(\1x\2*)\4*$)

Try it online!

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*$)
\$\endgroup\$
  • \$\begingroup\$ Wow, this is very cool. So many different ways to do this problem! \$\endgroup\$ – Deadcode Feb 21 at 20:55
  • 1
    \$\begingroup\$ 38 bytes: ^x(?=((xx)+?)(\1\1)*$)(?!(\1x\2*)\4*$) (Try it online) \$\endgroup\$ – Deadcode Feb 21 at 21:12
2
\$\begingroup\$

J, 10 bytes

%:<<:AND-.

Based on @Dennis' bitwise solution.

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))
\$\endgroup\$
  • \$\begingroup\$ Huh. I didn't know about AND. cool! \$\endgroup\$ – Conor O'Brien Nov 16 '16 at 16:24
2
\$\begingroup\$

Retina 0.8.2, 47 bytes

\d+
$*
+`(1+)\1
$+0
01
1
+`.10(0*1)$
1$1
^10*1$

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

ECMAScript Regex, 42 bytes

^x(?=(x(xx)*)\1*$)(?=(x+?)((\3\3)*$))\4\1x

Try it online! (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. I use x(xx)* instead of (x*)\2x. And I use a shorter method to check k < 2^n

\$\endgroup\$
  • \$\begingroup\$ Wow, this is awesome! Very nicely done. Note that you can make it a little bit faster by changing (\3\3)*)$ to (\3\3)*$) \$\endgroup\$ – Deadcode Jan 24 at 8:35
  • \$\begingroup\$ Nice job with that Retina code. I didn't know about $= and $.=. It can be improved even better. \$\endgroup\$ – Deadcode Jan 24 at 9:28
  • 2
    \$\begingroup\$ @Deadcode If you're going to nitpick the header and footer, then have some further improvements. \$\endgroup\$ – Neil Jan 24 at 10:42
  • \$\begingroup\$ @Neil That looks like good golf, but unfortunately it seems to have a bug. Try single numbers. They don't work. \$\endgroup\$ – Deadcode Jan 24 at 10:54
  • 1
    \$\begingroup\$ @Deadcode Sorry, I hadn't realised that single numbers were part of the "spec". \$\endgroup\$ – Neil Jan 24 at 10:59
2
\$\begingroup\$

Brain-Flak, 128 bytes

({<{({}[()]<(([{}]())<>{})<>>)}{}>{{}(<>)}{}}<><(())>){([()]{}<(({}){})>)}{}([({}[{}(())])](<>)){({}())<>}{}{((<{}>))<>{}}{}<>{}

Try it online!

I used a very different algorithm than the older Brain-Flak solution.

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
([({}[{}(())])](<>)){({}())<>}{}{((<{}>))<>{}}{}<>{}
\$\endgroup\$
1
\$\begingroup\$

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! (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' 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 :(

\$\endgroup\$
  • 1
    \$\begingroup\$ f = 47: boolean f(int p){return Math.sqrt(p--)<(p&-p);} \$\endgroup\$ – charlie Aug 15 '16 at 16:15
  • 1
    \$\begingroup\$ g = 43: boolean g(int p){return p--<(p&-p)*(p&-p);} \$\endgroup\$ – charlie Aug 15 '16 at 16:15
  • \$\begingroup\$ Nice one! I knew there had to be a way to get rid of the Math.* calls; just couldn't figure out how! Thanks! \$\endgroup\$ – MH. Aug 15 '16 at 18:32
1
\$\begingroup\$

C (gcc), 30 bytes

f(x){return--x<(x&-x)*(x&-x);}

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Hy, 37 bytes

(defn f[n](>(**(&(- n 1)(- 1 n))2)n))

Try it online!

Port of @Dennis' answer.

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

Cjam, 11 bytes

Like many of us, piggybacking off of Dennis's excellent solution:

qi_(_W*&2#<

Try it online

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

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.

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

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.

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

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!

\$\endgroup\$
  • \$\begingroup\$ n=x=>x-1&1-x>x**.5; n(3) gives me 0 (actually it gives me 0 regardless of input) \$\endgroup\$ – eithed Aug 11 '16 at 13:49
  • \$\begingroup\$ What browser? It may be just that. \$\endgroup\$ – Mama Fun Roll Aug 11 '16 at 20:03
  • \$\begingroup\$ Chrome 52. Firefox 48 gives the same answer for n=x=>x-1&1-x>Math.pow(x,0.5); n(3) \$\endgroup\$ – eithed Aug 11 '16 at 23:45
  • \$\begingroup\$ Ok - it's the operator precedence. It has to be (x-1&1-x) as without it the operator precedence is actually: (x-1)&((1-x)>x**.5) \$\endgroup\$ – eithed Aug 11 '16 at 23:55
  • 1
    \$\begingroup\$ -1 byte: x=>x--**.5<(x&-x) or x=>x**.5<(--x&-x) \$\endgroup\$ – charlie Aug 12 '16 at 8:55
0
\$\begingroup\$

C# (.NET Core), 17 bytes

x=>x--<(x=x&-x)*x

Try it online!

Port of MegaTom's C answer.

I attempted a LINQ based solution, but this was too good.

\$\endgroup\$

Your Answer

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

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