Ist es eine Proth Nummer?

37

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!

DJMcMayhem
quelle

Antworten:

41

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 2 + 1 = 10100 2 .

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 n 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 n .

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

Schließlich, wenn (2 N ) 2 = N = k2 n + 1 , 2 n 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)) 2 = 0 <1 = N .

Daher ist ((N - 1) & (1 - N)) 2 > 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.
Dennis
quelle
woah. das ist unglaublich
don bright
46

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 2 + 1 = 10100 2 .

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 n 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 n .

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

Schließlich, wenn (2 N ) 2 = N = k2 n + 1 , 2 n 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)) 2 = 0 <1 = N .

Daher ist ((N - 1) & (1 - N)) 2 > 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.

Dennis
quelle
23
Ich bin häufig in Math.SE und meine Augen wünschen sich wirklich schönes LaTeX auf dieser Site, anstatt wie eine Site aus den 90ern
auszusehen
Das ist mein Favorit.
Qix
9

Python 2, 23 Bytes

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

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>#&
Michael Lee
quelle
2
Willkommen bei Programming Puzzles und Code Golf! :)
Adnan
1
Es ist nicht nötig g=, eine reine Funktion ist in Ordnung!
Ein Simmons
Oh wie süß. Behebt es jetzt.
Michael Lee
Übrigens kann Ihr Test erheblich vereinfacht werden Select[Range@1000,f].
numbermaniac
8

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 .

Adnan
quelle
<©Ó¬oD®s/›oder <DÓ0èoDŠ/›für 10.
Emigna
@Emigna Das ist Genie! Vielen Dank :).
Adnan
7

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:

({}[()])(((<>()))){{}([(((({}<(({}){})>){}){})<>[({})(())])](<>)){({}())<>}{}<>{}{}<>(({})){{}{}<>(<(())>)}{}}(<{}{}>)<>{({}[()])<>(({}()[({})])){{}(<({}({}))>)}{}<>}{}<>({}<{}><>)
Weizen-Assistent
quelle
5

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 2 > 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
Luis Mendo
quelle
5

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
Undichte Nonne
quelle
5

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]
X88B88
quelle
4
Willkommen bei Programming Puzzles & Code Golf!
Dennis
Danke, Mann! Seit einer Weile ein Lauerer hier. Großer Fan übrigens, Gelee ist super cool. Ich wünschte, ich könnte lernen, aber leider verstehe ich nicht wirklich
X88B88
2
Ein allgemeiner Tipp: Wenn Sie nur an der Länge einer durch ein Verständnis erstellten Liste interessiert sind, können Sie verwenden sum[1| ... ]. Hier können wir noch weiter gehen und die Gleichheit Tests vor der Bewegung |und überprüfen Sie mit , orwenn einer von ihnen ist wahr: f x=or[k*2^n+1==x|k<-...,n<-...,2^n>k].
nimi
Wow. Tolle Tipps. Ich werde auf jeden Fall überarbeiten.
X88B88
2
Wenn du Jelly lernen möchtest, schau im Wiki nach oder betrete den Jelly-Raum .
Dennis
5

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

Deadcode
quelle
1
O_o wow, nur 48 Bytes
ASCII
Neil's ist meiner ähnlicher als Dennis '
H.PWiz
4

Julia, 16 Bytes

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

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

Mama Fun Roll
quelle
Das geht nicht Hat bei Julia &den gleichen Vorrang wie *.
Dennis
1
Oh, richtig. Behoben: PI sollte meinen Code wirklich testen.
Mama Fun Roll
2
Sie können -~-xanstelle von verwenden (1-x). Es gibt auch √xstattdessen x^.5, aber es werden keine Bytes gespeichert.
Dennis
4

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

Frédéric
quelle
1
Sie können das P=am Anfang ziehen und das Ende ändern 2^n>xund wie 5 oder 6 Bytes
speichern
4

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*$)
Grimmig
quelle
Wow, das ist sehr cool. So viele verschiedene Möglichkeiten, um dieses Problem zu lösen!
Deadcode
1
38 Bytes: ^x(?=((xx)+?)(\1\1)*$)(?!(\1x\2*)\4*$)( Online
testen
2

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))
Meilen
quelle
Huh. Ich wusste es nicht AND. cool!
Conor O'Brien
2

Retina 0.8.2 , 47 Bytes

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

k·2n+1(2k±1)·2n+1+1k=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$
Neil
quelle
2

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

H.PWiz
quelle
Wow, das ist großartig! Sehr schön gemacht. Beachten Sie, dass Sie es ein bisschen schneller machen können, indem Sie (\3\3)*)$auf(\3\3)*$)
Deadcode
Gute Arbeit mit diesem Retina-Code. Ich wusste nicht über $=und $.=. Es kann noch besser verbessert werden .
Deadcode
2
@Deadcode Wenn Sie die Kopf- und Fußzeile nicht auswählen, gibt es einige weitere Verbesserungen .
Neil
@Neil Das sieht nach gutem Golf aus, scheint aber leider einen Bug zu haben. Versuchen Sie es mit einzelnen Zahlen . Sie arbeiten nicht.
Deadcode
1
@Deadcode Tut mir leid, ich hatte nicht bemerkt, dass einzelne Zahlen Teil der "Spezifikation" waren.
Neil
2

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

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.

DSkoog
quelle
1

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

MH.
quelle
1
f = 47:boolean f(int p){return Math.sqrt(p--)<(p&-p);}
Charlie
1
g = 43:boolean g(int p){return p--<(p&-p)*(p&-p);}
Charlie
Schön! Ich wusste, dass es einen Weg geben musste, die Math.*Anrufe loszuwerden . konnte nur nicht herausfinden, wie! Vielen Dank!
MH.
1

Hy , 37 Bytes

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

Probieren Sie es online!

Port of @Dennis 'Antwort.

adl
quelle
1

Japt , 12 10 9 Bytes

É&1-U)>Uq

Probieren Sie es online!

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

randomdude999
quelle
-1kann sein É.
Shaggy
0

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.

IanC
quelle
0

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!

Mama Fun Roll
quelle
n=x=>x-1&1-x>x**.5; n(3)gibt mir 0(eigentlich gibt es mir 0 unabhängig von der Eingabe)
11.
Welcher Browser? Es kann genau das sein.
Mama Fun Roll
Chrome 52 Firefox 48 gibt die gleiche Antwort fürn=x=>x-1&1-x>Math.pow(x,0.5); n(3)
eithed
Ok - es ist der Operator Vorrang. Es muss so sein, (x-1&1-x)wie ohne es der Operator-Vorrang tatsächlich ist:(x-1)&((1-x)>x**.5)
mitte
1
-1 Byte: x=>x--**.5<(x&-x)oderx=>x**.5<(--x&-x)
Charlie
0

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
Sara J
quelle
0

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.

Cody Gray
quelle