40
\$\begingroup\$

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

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!

\$\endgroup\$
0

32 Answers 32

48
\$\begingroup\$

Jelly, 5 bytes

’&C²>

Try it online! or verify all test cases.

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.
\$\endgroup\$
1
  • \$\begingroup\$ woah. thats incredible \$\endgroup\$
    – don bright
    Feb 21, 2019 at 5:18
48
\$\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 \$\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.

\$\endgroup\$
2
  • 26
    \$\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, 2016 at 23:41
  • \$\begingroup\$ This one's my favorite. \$\endgroup\$ Aug 12, 2016 at 21:47
10
\$\begingroup\$

Python 2, 23 bytes

lambda n:(~-n&1-n)**2>n
\$\endgroup\$
10
\$\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\$
4
  • 2
    \$\begingroup\$ Welcome to Programming Puzzles and Code Golf! :) \$\endgroup\$
    – Adnan
    Aug 10, 2016 at 22:41
  • 1
    \$\begingroup\$ No need to begin with g=, a pure function is fine! \$\endgroup\$
    – A Simmons
    Aug 11, 2016 at 10:01
  • \$\begingroup\$ Oh, sweet. Fixed it now. \$\endgroup\$
    – Michael L.
    Aug 11, 2016 at 14:04
  • \$\begingroup\$ By the way, your test can be significantly simplified to Select[Range@1000,f]. \$\endgroup\$ May 20, 2017 at 9:11
8
\$\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\$
2
  • \$\begingroup\$ <©Ó¬oD®s/› or <DÓ0èoDŠ/› for 10. \$\endgroup\$
    – Emigna
    Aug 11, 2016 at 20:50
  • \$\begingroup\$ @Emigna That is genius! Thanks :). \$\endgroup\$
    – Adnan
    Aug 11, 2016 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\$
0
7
\$\begingroup\$

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


 # 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\$
2
  • 1
    \$\begingroup\$ O_o wow, only 48 bytes \$\endgroup\$
    – ASCII-only
    Jan 24, 2019 at 2:43
  • \$\begingroup\$ Neil's is more similar to mine than to Dennis' \$\endgroup\$
    – H.PWiz
    Jan 24, 2019 at 8:24
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\$
5
  • 4
    \$\begingroup\$ Welcome to Programming Puzzles & Code Golf! \$\endgroup\$
    – Dennis
    Aug 11, 2016 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, 2016 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, 2016 at 15:33
  • \$\begingroup\$ Wow. Great tips. I'll definitely revise. \$\endgroup\$
    – X88B88
    Aug 11, 2016 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, 2016 at 18:00
4
\$\begingroup\$

Julia, 16 bytes

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

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

\$\endgroup\$
3
  • \$\begingroup\$ That doesn't work. In Julia, & has the same precedence as *. \$\endgroup\$
    – Dennis
    Aug 11, 2016 at 2:58
  • 1
    \$\begingroup\$ Oh right. Fixed :P I should really test my code. \$\endgroup\$ Aug 11, 2016 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, 2016 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
  • 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\$ Aug 11, 2016 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\$
2
  • \$\begingroup\$ Wow, this is very cool. So many different ways to do this problem! \$\endgroup\$
    – Deadcode
    Feb 21, 2019 at 20:55
  • 1
    \$\begingroup\$ 38 bytes: ^x(?=((xx)+?)(\1\1)*$)(?!(\1x\2*)\4*$) (Try it online) \$\endgroup\$
    – Deadcode
    Feb 21, 2019 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\$
1
  • \$\begingroup\$ Huh. I didn't know about AND. cool! \$\endgroup\$ Nov 16, 2016 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\$
5
  • \$\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, 2019 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, 2019 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, 2019 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, 2019 at 10:54
  • 1
    \$\begingroup\$ @Deadcode Sorry, I hadn't realised that single numbers were part of the "spec". \$\endgroup\$
    – Neil
    Jan 24, 2019 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\$
2
\$\begingroup\$

Bitwise Fuckery, 56 bytes

,-@|~+&[>+>+<<-]>%>[<|[<+>-]>-]<<[>+<-]|+[-(>.<)>-(.>)<]

Try it online!

Uses the latest version 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, 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 ...]
]
\$\endgroup\$
2
\$\begingroup\$

Pyt, 7 bytes

Đ⁻Đ~∧²<

Try it online!

Port of Dennis's Jelly answer

\$\endgroup\$
1
\$\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\$
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\$
3
  • 1
    \$\begingroup\$ f = 47: boolean f(int p){return Math.sqrt(p--)<(p&-p);} \$\endgroup\$
    – charlie
    Aug 15, 2016 at 16:15
  • 1
    \$\begingroup\$ g = 43: boolean g(int p){return p--<(p&-p)*(p&-p);} \$\endgroup\$
    – charlie
    Aug 15, 2016 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, 2016 at 18:32
1
\$\begingroup\$

Hy, 37 bytes

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

Try it online!

Port of @Dennis' answer.

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

C (gcc), 29 30 bytes

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

Try it online!

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

Japt, 12 10 9 bytes

É&1-U)>Uq

Try it online!

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

\$\endgroup\$
1
  • \$\begingroup\$ -1 can be É. \$\endgroup\$
    – Shaggy
    Oct 26, 2019 at 1:36
1
\$\begingroup\$

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.

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

Thunno, \$ 12 \log_{256}(96) \approx \$ 9.88 bytes

zt1-s1_A&2^q

Attempt This Online! or generate all values up to 100.

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?
\$\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\$

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\$
8
  • \$\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, 2016 at 13:49
  • \$\begingroup\$ What browser? It may be just that. \$\endgroup\$ Aug 11, 2016 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, 2016 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, 2016 at 23:55
  • 1
    \$\begingroup\$ -1 byte: x=>x--**.5<(x&-x) or x=>x**.5<(--x&-x) \$\endgroup\$
    – charlie
    Aug 12, 2016 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 and acknowledge you have read our privacy policy.

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