Skip to main content
Code Golf

Return to Answer

fixed tilde in latex code
Source Link
Leo
Leo
  • 12.9k
  • 1
  • 33
  • 63

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 \$~j = -(j + 1) = -j - 1\$\${\sim}j = -(j + 1) = -j - 1\$, \$-j = ~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.

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 \$~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^{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.

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.
deleted 157 characters in body
Source Link
caird coinheringaahing ♦
caird coinheringaahing ♦
  • 50.9k
  • 11
  • 133
  • 364

Jelly, 5 bytes

’&C²>

Try it online! or verify all test cases.

Background

Let j\$\newcommand{\&}[]{\text{ & }}j\$ be a strictly positive integer. j + 1\$j + 1\$ toggles all trailing set bits of j\$j\$ and the adjacent unset bit. For example, 100112 + 1 = 101002\$10011_{2} + 1 = 10100_{2}\$.

Since ~j = -(j + 1) = -j - 1\$~j = -(j + 1) = -j - 1\$, -j = ~j + 1\$-j = ~j + 1\$, so -n\$-n\$ applies the above to the bitwise NOT of j\$j\$ (which toggles all bits), thus toggling all bits before the last 1\$1\$.

By taking j & -j – the\$j \& (-j)\$ (the bitwise AND of j\$j\$ and -j –\$-j\$), all bits before and after the last set bit are nullified (since unequal in j\$j\$ and -j\$-j\$), thus yielding the highest power of 2\$2\$ that divides j\$j\$ evenly.

For input N\$N\$, we want to apply the above to N - 1\$N - 1\$ to find 2n\$2^{n}\$, the highest power of 2\$2\$ that divides N - 1\$N - 1\$. If m = N - 1\$m = N - 1\$, -m = -(N - 1) = 1 - N\$-m = -(N - 1) = 1 - N\$, so (N - 1) & (1 - N)\$(N - 1) \& (1 - N)\$ yields 2n\$2^{n}\$.

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

Finally, if (2n)2 = N = k2n + 1\$(2^{n})^{2} = N = k2^{n} + 1\$, 2n\$2^{n}\$ must be odd (1\$1\$) so the parities of both sides can match, implying that k = 0\$k = 0\$ and N = 1\$N = 1\$. In this case (N - 1) & (1 - N) = 0 & 0 = 0\$(N - 1) \& (1 - N) = 0 \& 0 = 0\$ and ((N - 1) & (1 - N))2 = 0 < 1 = N\$((N - 1) \& (1 - N))^{2} = 0 < 1 = N\$.

Therefore, ((N - 1) & (1 - N))2 > N\$((N - 1) \& (1 - N))^{2} > N\$ is true if and only if N\$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.

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.

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 \$~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^{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.
added 1783 characters in body
Source Link
Dennis
Dennis
  • 211.7k
  • 41
  • 380
  • 830

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.

Jelly, 5 bytes

’&C²>

Try it online! or verify all test cases.

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.
Source Link
Dennis
Dennis
  • 211.7k
  • 41
  • 380
  • 830