Eine Proth-Nummer , benannt nach François Proth, ist eine Zahl, die ausgedrückt werden kann als

N = k * 2^n + 1

Dabei kist eine ungerade positive ganze Zahl und nist eine positive ganze Zahl, so dass 2^n > k. Lassen Sie uns ein konkreteres Beispiel verwenden. Nehmen Sie 3. 3 ist eine Proth-Nummer, weil es als geschrieben werden kann

(1 * 2^1) + 1

und 2^1 > 1ist zufrieden. 5 Ist auch eine Proth-Nummer, weil sie geschrieben werden kann als

(1 * 2^2) + 1

und 2^2 > 1ist zufrieden. 7 ist jedoch keine Proth-Nummer, da die einzige Möglichkeit ist, sie in das Formular N = k * 2^n + 1einzutragen

(3 * 2^1) + 1

und 2^1 > 3ist nicht zufrieden.

Ihre Herausforderung ist recht einfach: Sie müssen ein Programm oder eine Funktion schreiben, die anhand einer positiven Ganzzahl bestimmt, ob es sich um eine Proth-Zahl handelt oder nicht. Sie können Eingaben in jedem vernünftigen Format vornehmen und sollten einen Wahrheitswert ausgeben, wenn es sich um eine Proth-Zahl handelt, und einen falschen Wert, wenn dies nicht der Fall ist. Wenn Ihre Sprache hat, jede „Proth Zahl - Erfassungs“ -Funktionen Sie können sie verwenden.

Testen Sie IO

Hier sind die ersten 46 Proth-Nummern bis 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

Jede andere gültige Eingabe sollte einen falschen Wert ergeben.

Wie üblich ist dies Codegolf, daher gelten Standardlücken, und die kürzeste Antwort in Bytes gewinnt!

Zahlentheorie Fun-Fact-Randnotiz:

Die größte bekannte Primzahl, die keine Mersenne-Primzahl ist 19249 * 2^13018586 + 1, ist eine Proth-Zahl!

Gelee , 5 Bytes

’&C²>

Probieren Sie es online! oder überprüfen Sie alle Testfälle .

Hintergrund

Sei j eine streng positive ganze Zahl. j + 1 schaltet alle nachfolgenden gesetzten Bits von j und das benachbarte nicht gesetzte Bit um . Zum Beispiel 10011 ₂ + 1 = 10100 ₂ .

Da ~ j = - (j + 1) = -j - 1 , -j = ~ j + 1 ist , wendet -n das obige auf das bitweise NICHT von j an (wodurch alle Bits umgeschaltet werden ), wodurch alle Bits vor dem letzten umgeschaltet werden 1 .

Indem Sie j & -j - das bitweise UND von j und -j - nehmen, werden alle Bits vor und nach dem zuletzt gesetzten Bit auf Null gesetzt (da ungleich in j und -j ), wodurch sich die höchste Potenz von 2 ergibt , die j gleichmäßig teilt .

Für Eingabe N wollen wir das Obige auf N - 1 anwenden , um 2 ⁿ zu finden , die höchste Potenz von 2 , die N - 1 teilt . Wenn m = N - 1 , -m = - (N - 1) = 1 - N , so ergibt (N - 1) & (1 - N) 2 ⁿ .

Alles, was zu testen bleibt, ist, ob 2 ⁿ > k ist . Wenn k> 0 ist , ist dies genau dann wahr, wenn (2 ⁿ ) ² > k2 ^{n ist} , was selbst genau dann gilt, wenn (2 ⁿ ) ² ≥ k2 ⁿ + 1 = N ist .

Schließlich, wenn (2 ^N ) ² = N = k2 ⁿ + 1 , 2 ⁿ muß ungerade sein ( 1 ) , so dass die Paritäten der beiden Seiten kann übereinstimmen, was impliziert , dass k = 0 und N = 1 . In diesem Fall (N - 1) & (1 - N) = 0 0 = 0 und ((N - 1) & (1 - N)) ² = 0 <1 = N .

Daher ist ((N - 1) & (1 - N)) ² > N genau dann wahr, wenn N eine Proth-Zahl ist.

Wie es funktioniert

’&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.

Python, 22 Bytes

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

Dies ist eine Portierung meiner Gelee-Antwort . Teste es auf Ideone .

Wie es funktioniert

Sei j eine streng positive ganze Zahl. j + 1 schaltet alle nachfolgenden gesetzten Bits von j und das benachbarte nicht gesetzte Bit um . Zum Beispiel 10011 ₂ + 1 = 10100 ₂ .

Da ~ j = - (j + 1) = -j - 1 , -j = ~ j + 1 ist , wendet -n das obige auf das bitweise NICHT von j an (wodurch alle Bits umgeschaltet werden ), wodurch alle Bits vor dem letzten umgeschaltet werden 1 .

Indem Sie j & -j - das bitweise UND von j und -j - nehmen, werden alle Bits vor und nach dem zuletzt gesetzten Bit auf Null gesetzt (da ungleich in j und -j ), wodurch sich die höchste Potenz von 2 ergibt , die j gleichmäßig teilt .

Für Eingabe N wollen wir das Obige auf N - 1 anwenden , um 2 ⁿ zu finden , die höchste Potenz von 2 , die N - 1 teilt . Wenn m = N - 1 , -m = - (N - 1) = 1 - N , so ergibt (N - 1) & (1 - N) 2 ⁿ .

Alles, was zu testen bleibt, ist, ob 2 ⁿ > k ist . Wenn k> 0 ist , ist dies genau dann wahr, wenn (2 ⁿ ) ² > k2 ^{n ist} , was selbst genau dann gilt, wenn (2 ⁿ ) ² ≥ k2 ⁿ + 1 = N ist .

Schließlich, wenn (2 ^N ) ² = N = k2 ⁿ + 1 , 2 ⁿ muß ungerade sein ( 1 ) , so dass die Paritäten der beiden Seiten kann übereinstimmen, was impliziert , dass k = 0 und N = 1 . In diesem Fall (N - 1) & (1 - N) = 0 0 = 0 und ((N - 1) & (1 - N)) ² = 0 <1 = N .

Daher ist ((N - 1) & (1 - N)) ² > N genau dann wahr, wenn N eine Proth-Zahl ist.

Ohne Berücksichtigung von Gleitkommaungenauigkeiten entspricht dies dem Code N-1&1-N>N**.5in der Implementierung.

Python 2, 23 Bytes

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

Mathematica, 50 48 45 40 38 35 31 29 Bytes

Mathematica ist im Allgemeinen schlecht, wenn es um Code-Golf geht, aber manchmal gibt es eine integrierte Funktion, mit der die Dinge wirklich gut aussehen.

1<#<4^IntegerExponent[#-1,2]&

Ein 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}

Bearbeiten: Eigentlich, wenn ich Dennis 'bitweise UND Idee stehle , kann ich es auf 23 22 20 Bytes reduzieren.

Mathematica, 23 22 20 Bytes (danke A Simmons )

BitAnd[#-1,1-#]^2>#&

05AB1E , 14 10 Bytes

Dank Emigna für das Speichern von 4 Bytes!

Code:

<©Ó¬oD®s/›

Verwendet die CP-1252- Codierung. Probieren Sie es online! .

Erläuterung:

Für die Erklärung verwenden wir die Nummer 241 . Wir dekrementieren zuerst die Zahl um eins mit <. Das ergibt 240 . Nun berechnen wir die Primfaktoren (mit Duplikaten) mit Ò. Die Hauptfaktoren sind:

[2, 2, 2, 2, 3, 5]

Wir haben sie in zwei Teile geteilt. Mit erhalten 2Q·0Kwir die Liste von zwei:

[2, 2, 2, 2]

Mit erhalten ®2Kwir die Liste der verbleibenden Nummern:

[3, 5]

Schließlich nehmen Sie das Produkt von beiden. [2, 2, 2, 2]ergibt 16 . Das Produkt der [3, 5]Ergebnisse in 15 .

Dieser Testfall ist seit 16 > 15 wahr .

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

Probieren Sie es online!

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

Erläuterung

Das Programm durchläuft Potenzen von zwei und vier, bis es eine Potenz von zwei größer als N-1 findet. Wenn es gefunden wird, überprüft es mit modulo die Teilbarkeit von N-1 durch die Zweierpotenz und gibt das Ergebnis aus

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

Dieses Programm ist nicht stapelrein. Wenn Sie weitere 4 Bytes hinzufügen, können Sie den Stapel bereinigen:

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

MATL , 9 Bytes

qtYF1)EW<

Wahrheitsausgabe ist 1. Falsch ist 0oder leere Ausgabe. (Die einzigen Eingaben, die eine leere Ausgabe erzeugen, sind 1und 2; der Rest erzeugt entweder 0oder 1).

Probieren Sie es online!

Erläuterung

Sei x die Eingabe. Sei y die größte Potenz von 2, die x −1 teilt , und z = ( x −1) / y . Beachten Sie, dass z automatisch ungerade ist. Dann ist x genau dann eine Proth-Zahl, wenn y > z ist , oder äquivalent, wenn y ² > x −1 ist.

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

Brachylog , 28 Bytes

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

Probieren Sie es online!

Überprüfen Sie alle Testfälle auf einmal. (Leicht verändert.)

Erläuterung

Brachylog, ein Derivat von Prolog, ist sehr gut darin, Dinge zu beweisen.

Hier beweisen wir diese Dinge:

>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

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: Dank nimi jetzt 46 Bytes

f x=or[k*2^n+1==x|k<-[1,3..x],n<-[1..x],2^n>k]

ECMAScript Regex, 48 43 41 Bytes

Die regulären Ausdrücke von Neil und H.PWiz (beide auch ECMAScript) sind für sich genommen wunderschön. Es gibt einen anderen Weg , es zu tun, die von einem recht ordentlich Zufall war 1 Byte mehr als Neils, und jetzt mit H.PWiz vorgeschlagenen Golf (danke!), Ist 1 Byte mehr weniger als H.PWiz ist.

Warnung: Trotz der geringen Größe dieses Regex enthält er einen großen Spoiler . Ich empfehle dringend zu lernen, wie man unäre mathematische Probleme in ECMAScript Regex löst, indem man die anfänglichen mathematischen Einsichten unabhängig voneinander herausfindet. Es war eine faszinierende Reise für mich, und ich möchte sie keinem verderben, der sie möglicherweise selbst ausprobieren möchte, insbesondere nicht jenen, die sich für Zahlentheorie interessieren. In diesem früheren Beitrag finden Sie eine Liste der nacheinander mit Spoiler-Tags gekennzeichneten empfohlenen Probleme, die nacheinander gelöst werden müssen.

So lesen keine weiteren , wenn Sie nicht einige erweiterte einstellige regex Magie für Sie verwöhnen wollen . Wenn Sie versuchen möchten, diese Magie selbst herauszufinden, empfehle ich dringend, zunächst einige Probleme in ECMAScript regex zu lösen, wie in dem oben verlinkten Beitrag beschrieben.

Dieser reguläre Ausdruck funktioniert also ganz einfach: Er subtrahiert zunächst einen. Dann findet es den größten ungeraden Faktor, k . Dann dividieren wir durch k (unter Verwendung des Divisionsalgorithmus, der kurz in einem mit einem Spoiler-Tag versehenen Absatz meines Postings mit Regex-Fakultätszahlen erklärt wird ). Wir machen schleichend eine gleichzeitige Behauptung, dass der resultierende Quotient größer als k ist . Wenn die Division übereinstimmt, haben wir eine Proth-Nummer. wenn nicht, machen wir nicht.

Ich konnte 2 Bytes aus dieser Regex (43 → 41) mit einem von Grimy gefundenen Trick löschen , der die Division weiter verkürzen kann, falls der Quotient garantiert größer oder gleich dem Divisor ist.

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

Probieren Sie es 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*$
 

Julia, 16 Bytes

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

Dank an @Dennis für die Antwort und einige Golftipps!

R 52 50 Bytes

x=scan()-1;n=0;while(!x%%2){x=x/2;n=n+1};2^(2*n)>x

Das Programm beginnt , indem man N-1(hier genannt Pund x) durch 2so lange wie möglich, um das zu finden , einen 2^nTeil der Gleichung, so dass k=(N-1)/2^n, und berechnet dann , ob oder nicht kschlechter ist als 2^n, mit der Tatsache , dass2^n>x/2^n <=> (2^n)²>x <=> 2^2n>x

Regex (ECMAScript), 40 38 Bytes

-2 Bytes dank Deadcode

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

Probieren Sie es online!

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

J, 10 Bytes

%:<<:AND-.

Basierend auf der bitweisen Lösung von @Dennis .

Übernimmt eine Eingabe nund gibt 1 zurück, wenn es sich um die Proth-Nummer handelt, ansonsten 0.

Verwendung

   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

Erläuterung

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

Retina 0.8.2 , 47 Bytes

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

$k · 2^n + 1$$(2k±1) · 2^{n + 1} + 1$$k = 1$

\d+
$*

In Unary konvertieren.

+`(1+)\1
$+0
01
1

In Binärdatei konvertieren.

+`.10(0*1)$
1$1

Führen Sie die Proth-Generierungsformel wiederholt in umgekehrter Reihenfolge aus.

^10*1$

Passen Sie den Basisfall der Proth-Generierungsformel an.

Bearbeiten: Ich denke, es ist tatsächlich möglich, eine Proth-Nummer direkt mit einer unären Nummer mit einem einzelnen Regex abzugleichen. Ich benötige derzeit 47 Bytes, 7 Bytes mehr als mein aktueller Retina-Code, um zu überprüfen, ob eine unäre Nummer eine Proth-Nummer ist:

^.(?=(.+?)(\1\1)*$)(?=((.*)\4.)\3*$).*(?!\1)\3$

ECMAScript Regex, 42 Bytes

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

Probieren Sie es online! (Mit Retina)

Ich subtrahiere im Wesentlichen 1, dividiere durch die größtmögliche ungerade Zahl kund überprüfe dann, ob mindestens k+1noch etwas übrig ist.

Es stellt sich heraus, dass mein regulärer Ausdruck dem von Neil am Ende seiner Antwort sehr ähnlich ist . Ich benutze x(xx)*statt (x*)\2x. Und ich benutze eine kürzere Methode, um zu überprüfenk < 2^n

Brain-Flak , 128 Bytes

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

Probieren Sie es online!

Ich habe einen ganz anderen Algorithmus verwendet als die ältere Brain-Flak-Lösung .

Grundsätzlich dividiere ich durch 2 (aufrunden), bis ich eine gerade Zahl treffe. Dann vergleiche ich einfach das Ergebnis der letzten Division mit den beiden mit der Häufigkeit, mit der ich geteilt habe.

Erläuterung:

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

Ahorn, 100 Bytes (einschließlich Leerzeichen)

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:

Gut verteilt für Lesbarkeit:

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:

Gleiche Idee wie mehrere andere; Teilen Sie X durch 2, bis X nicht mehr gleichmäßig durch 2 teilbar ist, und überprüfen Sie dann die Kriterien 2 ^ n> x.

Java 1.7, 49 43 Bytes

Weitere 6 Bytes Staub dank @charlie.

boolean g(int p){return p--<(p&-p)*(p&-p);}

Versuch es! (ideone)

Zwei Wege, gleich lang. Wie bei den meisten Antworten hier gehen die Credits für den Ausdruck natürlich an @Dennis.

Die Wurzel der rechten Seite des Ausdrucks ziehen:

boolean f(int p){return(p-1&(1-p))>Math.sqrt(p);}

Anwenden der Zweierpotenz auf die linke Seite des Ausdrucks:

boolean g(int p){return Math.pow(p-1&(1-p),2)>p;}

Kann ein einzelnes Byte ausschalten, wenn ein positiver numerischer Wert für 'truthy' und ein negativer Wert für 'falsy' steht:

double g(int p){return Math.pow(p-1&(1-p),2)-p;}

Leider kann man dies wegen 'Narrowing Primitive Conversion' nicht einfach in Java schreiben und korrekte Ergebnisse erhalten:

((p - 1 & (1 - p))^2) > p;

Und jeder Versuch, 'p' zu verbreitern, führt zu einem Kompilierungsfehler, da bitweise Operatoren nicht unterstützt werden, z. B. für Floats oder Doubles :(

Hy , 37 Bytes

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

Probieren Sie es online!

Port of @Dennis 'Antwort.

C (GCC) , 29 30 Bytes

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

Probieren Sie es online!

Japt , 12 10 9 Bytes

É&1-U)>Uq

Probieren Sie es online!

Port of Dennis 'Jelly antworte nochmal. - 1 Danke an @Shaggy.

Cjam, 11 Bytes

Wie viele von uns ist Dennis 'exzellente Lösung ein Huckepack:

qi_(_W*&2#<

Probieren Sie es online aus

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;}

Kam erst, um die Antworten zu lesen, nachdem ich es versucht hatte.

Unter Berücksichtigung N=k*2^n+1der bedingten von k<2^n( k=1,3,5..undn=1,2,3..

Mit haben n=1wir einen kzum Testen zur Verfügung. Wenn wir uns steigern n, bekommen wir ein paar mehr k'szum Testen:

n = 1; k = 1

n = 2; k = 1 k = 3

n = 3; k = 1 k = 3 k = 5 k = 7

...

Diese Möglichkeiten Durchlaufen können wir sicher sein , N keine Prouth Zahl ist , wenn für eine gegebene ndie k=1Zahl erhalten wird , größer als N und keine andere Iteration ein Spiel war.

Also mein Code "brute-forces" seinen Weg in die Suche nach N.

Nach dem Lesen der anderen Antworten und dem Erkennen, dass Sie N-1 mit 2 faktorisieren können, num die Bedingung zu finden und sie dann zu erfüllen k<2^n, denke ich, dass mein Code mit dieser Methode kleiner und effizienter sein könnte.

Es war einen Versuch wert!

Getestet alle angegebenen Nummern und ein paar "non-Prouth" -Nummern. Die Funktion gibt 1 zurück, wenn die Zahl eine Prouth-Zahl ist, und 0, wenn dies nicht der Fall ist.

Javascript ES7, 16 Bytes

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

Port meiner Julia-Antwort, die ein Port von @ Dennis's Jelly-Antwort ist.

Danke @Charlie für 2 Bytes gespeichert!

C # (.NET Core) , 17 Byte

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

Probieren Sie es online!

Port von MegaToms C-Antwort .

Ich habe versucht, eine LINQ-basierte Lösung zu finden, aber das war zu gut.

Tinte , 60 Bytes

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

Probieren Sie es online!

Basierend auf der Maple-Antwort von @ DSkoog - es war nicht das erste seiner Art, das veröffentlicht wurde, aber es war das erste seiner Art, das ich gesehen habe.

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

x86-Maschinencode, 15 Byte

4F 89 F8 F7 D8 21 F8 0F AF C0 39 C7 19 C0 C3

Diese Bytes definieren eine Funktion, die das Eingabeargument (eine vorzeichenlose Ganzzahl) im EDIRegister gemäß der Standardaufrufkonvention von System V für x86-Systeme verwendet und EAXwie alle x86-Aufrufkonventionen das Ergebnis im Register zurückgibt .

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)

Probieren Sie es online!

Es ist eine ziemlich unkomplizierte Lösung - und konzeptionell der C-Version von MegaTom ähnlich . Tatsächlich könnten Sie dies in C so etwas wie das Folgende schreiben:

unsigned IsProthNumber(unsigned input)
{
    --input;
    unsigned temp  = (input & -input);
    temp          *= temp;
    return (input < temp) ? -1 : 0;
}

Aber der obige Maschinencode ist besser als das, was Sie von einem C-Compiler erwarten, selbst wenn er so eingestellt ist, dass er die Größe optimiert.

Der einzige "Cheat" ist, -1 als "Wahrheitswert" und 0 als "Falschwert" zurückzugeben. Dieser Trick ermöglicht die Verwendung des 2-Byte- SBBBefehls im Gegensatz zum 3-Byte- SETBBefehl.