Is it a Proth number?

Question

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!

Answer 1

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, 10011₂ + 1 = 10100₂.

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 2ⁿ, 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ⁿ.

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

Finally, if (2ⁿ)² = N = k2ⁿ + 1, 2ⁿ 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))² = 0 < 1 = N.

Therefore, ((N - 1) & (1 - N))² > 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 2

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, 10011₂ + 1 = 10100₂.

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 2ⁿ, 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ⁿ.

All that's left to test is if 2ⁿ > k. If k > 0, this is true if and only if (2ⁿ)² > k2ⁿ, which is true itself if and only if (2ⁿ)² &geq; k2ⁿ + 1 = N.

Finally, if (2ⁿ)² = N = k2ⁿ + 1, 2ⁿ 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))² = 0 < 1 = N.

Therefore, ((N - 1) & (1 - N))² > 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 3

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>#&

Answer 4

Python 2, 23 bytes

lambda n:(~-n&1-n)**2>n

Answer 5

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.

Answer 6

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:

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

Answer 7

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

Answer 8

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 y² > 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 9

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 10

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

Answer 11

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

Answer 12

Julia, 16 bytes

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

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

Answer 13

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

Answer 14

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$

Answer 15

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

Answer 16

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
([({}[{}(())])](<>)){({}())<>}{}{((<{}>))<>{}}{}<>{}

Answer 17

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

Answer 18

C (gcc), 29 30 bytes

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

Try it online!

Answer 19

Hy, 37 bytes

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

Try it online!

Port of @Dennis' answer.

Answer 20

Japt, 12 10 9 bytes

É&1-U)>Uq

Try it online!

Port of Dennis' Jelly answer again. - 1 thanks to @Shaggy.

Answer 21

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

Answer 22

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 23

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.

Answer 24

ink, 60 bytes

=p(n)
~n-=n>1
~temp x=1
-(k){n%2:{n<x}->->}
~x+=x
~n=n/2
->k

Try it online!

Based on @DSkoog's Maple answer - it wasn't the first of its kind to be posted, but it was the first of its kind that I saw.

Ungolfed

= is_proth(number) =

/* It's easy to check if a number is one less than a Proth number.
   We take the number and divide it by 2 until we can't.
   Once we can't, we've found the smallest possible "k".
   If we also keep track of how many times we divided, we have our corresponding "2^n"
   All we have to do then is compare those
*/

~ number -= (number > 1)            // So, we first subtract one. Except this implementation won't ever halt for 0, so we don't subtract if the input is 1 (this is fine since the desired outputs for inputs 1 and 2 are the same)
~ temp power_of_two = 1             // We declare a variable to store our "2^n"
- (check)
  {
  - number % 2:                     // Once we can't divide by 2 anymore, we've found the smallest possible "k"
    {number < power_of_two}         // At that point, we print whether it's smaller than the "2^n" we found
    ->->                            // And then we return to where we were called from
  }

  ~ number = number / 2             // We keep dividing by 2 until we can't.
  ~ power_of_two += power_of_two    // and update our "2^n" as we go
-> check

Answer 25

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!

It's a pretty straightforward solution—and conceptually similar to MegaTom's C version. 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 26

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 27

Cjam, 11 bytes

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

qi_(_W*&2#<

Try it online

Answer 28

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.