ZA Liczba Proth , nazwany François Proth, to numer, który można wyrazić jako

N = k * 2^n + 1

Gdzie kjest nieparzysta dodatnia liczba całkowita in jest liczbą całkowitą dodatnią taką, że 2^n > k. Użyjmy bardziej konkretnego przykładu. Weź 3. 3 to liczba Proth, ponieważ można ją zapisać jako

(1 * 2^1) + 1

i 2^1 > 1 jest zadowolony. 5 Jest także liczbą Proth, ponieważ można ją zapisać jako

(1 * 2^2) + 1

i 2^2 > 1jest zadowolony. Jednak 7 nie jest liczbą Proth, ponieważ jest to jedyny sposób na zapisanie jej w formularzuN = k * 2^n + 1 jest

(3 * 2^1) + 1

i 2^1 > 3nie jest zadowolony.

Twoje wyzwanie jest dość proste: musisz napisać program lub funkcję, która przy dodatniej liczbie całkowitej określa, czy jest to liczba Proth, czy nie. Możesz przyjmować dane wejściowe w dowolnym rozsądnym formacie i powinieneś wypisać prawdziwą wartość, jeśli jest to liczba Protha i wartość fałsz, jeśli nie jest. Jeśli język ma żadnego „Proth-szereg funkcji wykrywania”, to może z nich korzystać.

Przetestuj IO

Oto pierwsze 46 liczb Proth do 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

Każde inne prawidłowe wejście powinno dawać wartość fałszowania.

Jak zwykle jest to gra w golfa, więc obowiązują standardowe luki i wygrywa najkrótsza odpowiedź w bajtach!

Ciekawostka z teorii liczb:

Największą znaną liczbą pierwszą, która nie jest Mersenne Prime, jest 19249 * 2^13018586 + 1tak naprawdę liczba Proth!

Galaretka , 5 bajtów

’&C²>

Wypróbuj online! lub zweryfikuj wszystkie przypadki testowe .

tło

Niech j będzie ściśle dodatnią liczbą całkowitą. j + 1 przełącza wszystkie końcowe bity j i sąsiedni niezbity bit. Na przykład 10011 ₂ + 1 = 10100 ₂ .

Ponieważ ~ j = - (j + 1) = -j - 1 , -j = ~ j + 1 , więc -n stosuje powyższe do bitowego NOT z j (który przełącza wszystkie bity), w ten sposób przełączając wszystkie bity przed ostatnim 1 .

Biorąc j & -j - bitowe AND i j oraz -j - wszystkie bity przed i po ostatnim zestawie bitów są zerowane (ponieważ są nierówne w j i -j ), co daje najwyższą potęgę 2, która dzieli równomiernie j .

Dla wejścia N chcemy zastosować powyższe do N - 1, aby znaleźć 2 ⁿ , najwyższą moc 2 dzielącą N - 1 . Jeśli m = N - 1 , -m = - (N - 1) = 1 - N , więc (N - 1) i (1 - N) daje 2 ⁿ .

Wszystko, co pozostało do przetestowania, to czy 2 ⁿ > k . Jeśli k> 0 , jest to prawdą wtedy i tylko wtedy, gdy (2 ⁿ ) ² > k2 ⁿ , co samo jest prawdą wtedy i tylko wtedy, gdy (2 ⁿ ) ² ≥ k2 ⁿ + 1 = N .

Wreszcie, jeśli (2 ⁿ ) ² = N = k2 ⁿ + 1 , 2 ⁿ musi być nieparzyste ( 1 ), aby parzystości obu stron mogły się zgadzać, co oznacza, że k = 0, a N = 1 . W tym przypadku (N - 1) i (1 - N) = 0 i 0 = 0 oraz ((N - 1) i (1 - N)) ² = 0 <1 = N .

Dlatego ((N - 1) i (1 - N)) ² > N jest prawdą wtedy i tylko wtedy, gdy N jest liczbą Proth.

Jak to działa

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

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

To jest port mojej odpowiedzi na żelki . Przetestuj na Ideone .

Jak to działa

Niech j będzie ściśle dodatnią liczbą całkowitą. j + 1 przełącza wszystkie końcowe bity j i sąsiedni niezbity bit. Na przykład 10011 ₂ + 1 = 10100 ₂ .

Ponieważ ~ j = - (j + 1) = -j - 1 , -j = ~ j + 1 , więc -n stosuje powyższe do bitowego NOT z j (który przełącza wszystkie bity), w ten sposób przełączając wszystkie bity przed ostatnim 1 .

Biorąc j & -j - bitowe AND i j oraz -j - wszystkie bity przed i po ostatnim zestawie bitów są zerowane (ponieważ są nierówne w j i -j ), co daje najwyższą potęgę 2, która dzieli równomiernie j .

Dla wejścia N chcemy zastosować powyższe do N - 1, aby znaleźć 2 ⁿ , najwyższą moc 2 dzielącą N - 1 . Jeśli m = N - 1 , -m = - (N - 1) = 1 - N , więc (N - 1) i (1 - N) daje 2 ⁿ .

Wszystko, co pozostało do przetestowania, to czy 2 ⁿ > k . Jeśli k> 0 , to prawdą tylko wtedy, gdy (2 ⁿ ) ² > k2 ⁿ , które samo jest prawdą tylko wtedy, gdy (2 ⁿ ) ² ≥ k2 ⁿ + 1 = N .

Wreszcie, jeśli (2 ⁿ ) ² = N = k2 ⁿ + 1 , 2 ⁿ musi być nieparzyste ( 1 ), aby parzystości obu stron mogły się zgadzać, co oznacza, że k = 0 i N = 1 . W tym przypadku (N - 1) i (1 - N) = 0 i 0 = 0 a ((N - 1) i (1 - n)) ² = 0 <1 = N .

Dlatego ((N - 1) i (1 - N)) ² > N jest prawdą wtedy i tylko wtedy, gdy N jest liczbą Proth.

Ignorując niedokładności zmiennoprzecinkowe, jest to równoważne kodowi N-1&1-N>N**.5w implementacji.

Python 2, 23 bajty

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

Mathematica, 50 48 45 40 38 35 31 29 bajtów

Mathematica ogólnie jest do bani, jeśli chodzi o golfa kodowego, ale czasami jest wbudowany, który sprawia, że ​​wszystko wygląda naprawdę ładnie.

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

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}

Edycja: Właściwie, jeśli ukradnę bitowy pomysł Dennisa , mogę sprowadzić go do 23 22 20 bajtów.

Mathematica, 23 22 20 bajtów (dzięki A Simmons )

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

05AB1E , 14 10 bajtów

Dzięki Emigna za uratowanie 4 bajtów!

Kod:

<©Ó¬oD®s/›

Wykorzystuje kodowanie CP-1252 . Wypróbuj online!.

Wyjaśnienie:

Dla wyjaśnienia użyjmy liczby 241 . Najpierw zmniejszamy liczbę o jeden za pomocą <. To daje wynik 240 . Teraz obliczamy czynniki pierwsze (z duplikatami) za pomocą Ò. Głównymi czynnikami są:

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

Podzieliliśmy je na dwie części. Za pomocą 2Q·0Kotrzymujemy listę dwóch:

[2, 2, 2, 2]

Za pomocą ®2Kotrzymujemy listę pozostałych liczb:

[3, 5]

Na koniec weź produkt obu. [2, 2, 2, 2]wyniki w 16 . Iloczyn [3, 5]wyników do 15 .

Ten przypadek testowy jest prawdziwy, ponieważ 16 > 15 .

Brain-Flak , 460 350 270 266 264 188 176 bajtów

Wypróbuj online!

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

Wyjaśnienie

Program przechodzi przez potęgi dwa i cztery, dopóki nie znajdzie potęgi o wartości większej niż N-1. Kiedy go znajdzie, sprawdza dzielność N-1 przez potęgę dwóch za pomocą modulo i generuje wynik

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

Ten program nie jest czysty. Jeśli dodasz dodatkowe 4 bajty, możesz wyczyścić stos:

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

MATL , 9 bajtów

qtYF1)EW<

Prawdziwe wyjście to 1. Falsy jest 0lub puste wyjście. (Jedynymi danymi wejściowymi, które generują puste dane wyjściowe, są 1i 2; reszta produkuje jeden 0lub 1).

Wypróbuj online!

Wyjaśnienie

Niech x oznacza dane wejściowe. Niech y będzie największą potęgą 2 dzielącą x -1, a z = ( x -1) / y . Zauważ, że z jest automatycznie nieparzyste. Zatem x jest liczbą Proth wtedy i tylko wtedy, gdy y > z , lub równoważnie, jeśli 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

Brachylog , 28 bajtów

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

Wypróbuj online!

Zweryfikuj wszystkie przypadki testowe jednocześnie. (Lekko zmieniony.)

Wyjaśnienie

Brachylog, będący pochodną Prologu, bardzo dobrze udowadnia.

Tutaj udowadniamy następujące rzeczy:

>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 bajtów

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

Edycja: Dzięki nim, teraz 46 bajtów

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

ECMAScript Regex, 48 43 41 bajtów

Wyrazy regularne Neila i H.PWiza (oba także smak ECMAScript) są same w sobie piękne. Jest inny sposób, aby to zrobić, zbiegiem okoliczności, który był o 1 bajt większy niż Neila, a teraz z sugerowanym przez H.PWiza golfem (dzięki!), Jest o 1 bajt więcej niż H.PWiz.

Ostrzeżenie: Pomimo niewielkiego rozmiaru tego wyrażenia regularnego zawiera on duży spoiler . Zdecydowanie zalecam nauczenie się rozwiązywania pojedynczych problemów matematycznych w wyrażeniu regularnym ECMAScript przez samodzielne ustalenie początkowych danych matematycznych. To była dla mnie fascynująca podróż i nie chcę zepsuć jej nikomu, kto mógłby potencjalnie chcieć spróbować samemu, szczególnie tym, którzy interesują się teorią liczb.Zobacz ten wcześniejszy post znajduje się lista zalecanych problemów oznaczonych spoilerem do rozwiązania jeden po drugim.

Więc nie czytaj dalej, jeśli nie chcesz, aby zepsuła Ci się jakaś zaawansowana magia wyrażeń regularnych . Jeśli chcesz spróbować samodzielnie odkryć tę magię, zdecydowanie polecam zacząć od rozwiązania niektórych problemów z wyrażeniem regularnym ECMAScript, jak opisano w linku powyżej.

Tak więc regex działa po prostu: Zaczyna się odejmując jeden. Następnie znajduje największy czynnik nieparzysty, k . Następnie dzielimy przez k (za pomocą algorytmu podziału wyjaśnionego w skrócie w akapicie mojego znacznika wyrażenia regularnego o wyrażeniu regularnym ). Podstępnie twierdzimy, że wynikowy iloraz jest większy niż k . Jeśli podział się zgadza, mamy numer Proth; jeśli nie, my nie.

Byłem w stanie usunąć 2 bajty z tego wyrażenia regularnego (43 → 41), używając sztuczki znalezionej przez Grimy'ego, która może dodatkowo skrócić podział w przypadku, gdy iloraz jest gwarantowany, że jest większy lub równy dzielnikowi.

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

Wypróbuj 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 bajtów

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

Podziękowania dla @Dennis za odpowiedź i kilka wskazówek golfowych!

R, 52 50 bajtów

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

Program zaczyna się od podzielenia N-1(zwanego tutaj Pi x) 2tak długo, jak to możliwe, aby znaleźć 2^nczęść równania, pozostawiając k=(N-1)/2^n, a następnie oblicza, czy kjest to gorsze czy nie 2^n, przy użyciu faktu, że2^n>x/2^n <=> (2^n)²>x <=> 2^2n>x

Regex (ECMAScript), 40 38 bajtów

-2 bajty dzięki Deadcode

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

Wypróbuj online!

Skomentowana wersja:

# 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 bajtów

%:<<:AND-.

Na podstawie bitowego rozwiązania @Dennis .

Pobiera dane wejściowe ni zwraca 1, jeśli jest to liczba Proth, inaczej 0.

Stosowanie

   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

Wyjaśnienie

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

Siatkówka 0.8.2 , 47 bajtów

\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$ . Można to łatwo wykonać przez przekształcenie reprezentacji binarnej.

\d+
$*

Konwertuj na unary.

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

Konwertuj na binarny.

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

Kilkakrotnie uruchom formułę generacji Proth w odwrotnej kolejności.

^10*1$

Dopasuj podstawowy przypadek formuły generowania Proth.

Edycja: Myślę, że w rzeczywistości możliwe jest dopasowanie liczby Proth bezpośrednio do liczby jednorzędowej za pomocą jednego wyrażenia regularnego. Obecnie zajmuje mi to 47 bajtów, 7 bajtów więcej niż mój obecny kod Retina do sprawdzania, czy liczba jednostkowa jest liczbą Proth:

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

ECMAScript Regex, 42 bajty

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

Wypróbuj online! (Korzystanie z siatkówki)

Zasadniczo odejmuję 1, dzielę przez największą możliwą liczbę nieparzystą k, a następnie sprawdzam, czy przynajmniej k+1zostało.

Okazuje się, że mój regex jest bardzo podobny do tego, który podaje Neil na końcu swojej odpowiedzi . Używam x(xx)*zamiast (x*)\2x. I używam krótszej metody do sprawdzeniak < 2^n

Brain-Flak , 128 bajtów

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

Wypróbuj online!

Użyłem zupełnie innego algorytmu niż starsze rozwiązanie Brain-Flak .

Zasadniczo dzielę przez 2 (zaokrąglając w górę), aż trafię na parzystą liczbę. Następnie po prostu porównuję wynik ostatniego podziału z dwoma do potęgi liczby podziałów.

Wyjaśnienie:

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

Klon, 100 bajtów (łącznie ze spacjami)

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:

Ładnie rozmieszczone dla czytelności:

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:

Ten sam pomysł, jak kilka innych; podziel X przez 2, aż X nie będzie już równomiernie podzielny przez 2, a następnie sprawdź kryteria 2 ^ n> x.

Java 1.7, 49 43 bajtów

Kolejne 6 bajtów pyłu dzięki @charlie.

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

Spróbuj! (ideone)

Dwa sposoby, jednakowo długie. Podobnie jak w przypadku większości odpowiedzi tutaj, napisy znajdują się oczywiście na @Dennis.

Korzenie prawej strony wyrażenia:

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

Zastosowanie potęgi dwóch do lewej strony wyrażenia:

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

Może zgolić jeden bajt, jeśli dodatnia wartość liczbowa może reprezentować „prawda”, a ujemna „fałsz”:

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

Niestety z powodu „zawężenia pierwotnej konwersji” nie można po prostu napisać tego w Javie i uzyskać poprawne wyniki:

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

I każda próba rozszerzenia „p” doprowadzi do błędu kompilacji, ponieważ operatory bitowe nie są obsługiwane na np. Zmiennoprzecinkowe lub podwajające :(

Hy , 37 bajtów

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

Wypróbuj online!

Port odpowiedzi @Dennis.

C (gcc) , 29 30 bajtów

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

Wypróbuj online!

Japt , 12 10 9 bajtów

É&1-U)>Uq

Wypróbuj online!

Port galaretki Port Dennisa ponownie. - 1 dzięki @Shaggy.

Cjam, 11 bajtów

Jak wielu z nas, wykorzystując doskonałe rozwiązanie Dennisa:

qi_(_W*&2#<

Wypróbuj online

C (137 bajtów)

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

Dopiero po przeczytaniu przyszedłem przeczytać odpowiedzi.

Biorąc pod uwagę N=k*2^n+1warunek k<2^n( k=1,3,5..in=1,2,3..

Dzięki n=1mamy jeden kdo przetestowania. W miarę wzrostu nliczby kolejnych k'stestów do przetestowania:

n = 1; k = 1

n = 2; k = 1 k = 3

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

...

Iteracja tych możliwości możemy być pewni, N nie jest liczbą Prouth jeśli dla danegonk=1 liczba jest większa niż uzyskane N i żadna inna iteracja był mecz.

Więc mój kod zasadniczo „brutalnie zmusza” do znalezienia N.

Po przeczytaniu innych odpowiedzi i zdaniu sobie sprawy, możesz dodać N-1 do 2, aby znaleźć, na następnie uzależnićk<2^n , myślę, że mój kod może być mniejszy i bardziej wydajny przy użyciu tej metody.

Warto było spróbować!

Przetestowano wszystkie podane liczby i kilka liczb „innych niż Prouth”. Funkcja zwraca 1, jeśli liczba jest liczbą Prouth i 0, jeśli nie jest.

JavaScript ES7, 16 bajtów

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

Port mojej odpowiedzi Julii, która jest portem galaretki @ Dennisa.

Dzięki @Charlie za 2 bajty zapisane!

C # (.NET Core) , 17 bajtów

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

Wypróbuj online!

Odpowiedź C portu MegaTom .

Próbowałem rozwiązania opartego na LINQ, ale było to zbyt dobre.

atrament , 60 bajtów

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

Wypróbuj online!

Na podstawie odpowiedzi Klon @ DSkoog - nie był to pierwszy tego rodzaju publikowany, ale był to pierwszy tego rodzaju, jaki widziałem.

Bez golfa

= 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

Kod maszynowy x86, 15 bajtów

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

Te bajty definiują funkcję, która przyjmuje argument wejściowy (liczbę całkowitą bez znaku) do EDIrejestru, zgodnie ze standardową konwencją wywoływania Systemu V dla systemów x86, i zwraca wynik w EAXrejestrze, jak wszystkie konwencje wywoływania x86.

W mnemonikach asemblera:

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)

Wypróbuj online!

Jest to dość proste rozwiązanie - i koncepcyjnie podobne do wersji C MegaTom . W rzeczywistości możesz napisać to w C jako coś takiego:

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

ale powyższy kod maszynowy jest lepiej golfowany niż to, co otrzymasz z kompilatora C, nawet jeśli jest ustawiony na optymalizację pod kątem wielkości.

Jedynym „oszustwem” jest tutaj zwrócenie -1 jako wartości „prawdy”, a 0 jako wartości „fałszu”. Ta sztuczka pozwala na użycie instrukcji 2-bajtowej SBBw przeciwieństwie do instrukcji 3-bajtowej SETB.