Czy to liczba Proth?

37

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!

DJMcMayhem
źródło

Odpowiedzi:

41

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

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

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

Wreszcie, jeśli (2 n ) 2 = N = k2 n + 1 , 2 n 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)) 2 = 0 <1 = N .

Dlatego ((N - 1) i (1 - N)) 2 > 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.
Dennis
źródło
łał to niesamowite
don jasne
46

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

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

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

Wreszcie, jeśli (2 n ) 2 = N = k2 n + 1 , 2 n 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)) 2 = 0 <1 = N .

Dlatego ((N - 1) i (1 - N)) 2 > 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.

Dennis
źródło
23
Często korzystam z Math.SE, a moje oczy naprawdę życzą sobie pięknego LaTeXa na tej stronie zamiast wyglądać jak strona z lat 90.
qwr
Ten jest moim ulubionym.
Qix,
9

Python 2, 23 bajty

lambda n:(~-n&1-n)**2>n
feersum
źródło
9

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>#&
Michael Lee
źródło
2
Witamy w Programowaniu zagadek i Code Golf! :)
Adnan
1
Nie trzeba zaczynać g=, czysta funkcja jest w porządku!
A Simmons,
Och, słodko. Naprawiono to teraz.
Michael Lee,
Nawiasem mówiąc, twój test można znacznie uprościć Select[Range@1000,f].
numbermaniac
8

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 .

Adnan
źródło
<©Ó¬oD®s/›lub <DÓ0èoDŠ/›na 10.
Emigna
@Emigna To geniusz! Dzięki :).
Adnan,
7

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:

({}[()])(((<>()))){{}([(((({}<(({}){})>){}){})<>[({})(())])](<>)){({}())<>}{}<>{}{}<>(({})){{}{}<>(<(())>)}{}}(<{}{}>)<>{({}[()])<>(({}()[({})])){{}(<({}({}))>)}{}<>}{}<>({}<{}><>)
Kreator pszenicy
źródło
5

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 2 > 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
Luis Mendo
źródło
5

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
Leaky Nun
źródło
5

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]
X88B88
źródło
4
Witamy w Programowaniu Puzzle i Code Golf!
Dennis
Dzięki stary! Przez jakiś czas tu byłeś czającym się. Big fan btw, galaretka jest super fajna. Szkoda, że ​​nie mogę się uczyć, ale niestety, tak naprawdę nie rozumiem
X88B88,
2
Ogólna wskazówka: jeśli interesuje Cię tylko długość listy utworzonej przez zrozumienie, możesz użyć sum[1| ... ]. Tutaj możemy iść dalej i przejść test równości przed |i sprawdzić w orczy któryś z nich jest prawdziwe: f x=or[k*2^n+1==x|k<-...,n<-...,2^n>k].
nimi
Łał. Świetne wskazówki. Na pewno poprawię.
X88B88,
2
Jeśli chcesz nauczyć się galaretki, sprawdź wiki lub dołącz do pokoju galaretki .
Dennis
5

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

Deadcode
źródło
1
O wo, tylko 48 bajtów
tylko ASCII
Neil's jest bardziej podobny do mojego niż Dennisa
H.PWiz
4

Julia, 16 bajtów

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

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

Mama Fun Roll
źródło
To nie działa. W Julii &ma taki sam priorytet jak *.
Dennis
1
No tak. Naprawiono: PI powinien naprawdę przetestować mój kod.
Mama Fun Roll
2
Możesz użyć -~-xzamiast (1-x). Jest też √xzamiast x^.5, ale nie zapisuje żadnych bajtów.
Dennis
4

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

Frédéric
źródło
1
Możesz wyciągnąć P=na początku i zmienić koniec na 2^n>xi zapisać jak 5 lub 6 bajtów
user5957401
4

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*$)
Ponury
źródło
Wow, to jest bardzo fajne. Tak wiele różnych sposobów rozwiązania tego problemu!
Deadcode
1
38 bajtów: ^x(?=((xx)+?)(\1\1)*$)(?!(\1x\2*)\4*$)( Wypróbuj online )
Deadcode
2

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))
mile
źródło
Huh Nie wiedziałam o tym AND. fajne!
Conor O'Brien
2

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(2)k±1)·2)n+1+1k=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$
Neil
źródło
2

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

H.PWiz
źródło
Wow, to jest niesamowite! Bardzo ładnie wykonane. Pamiętaj, że możesz to zrobić trochę szybciej, zmieniając (\3\3)*)$na(\3\3)*$)
Deadcode
Dobra robota z tym kodem Retina. Nie wiedziałam o $=i $.=. Można to poprawić jeszcze lepiej .
Deadcode
2
@Deadcode Jeśli chcesz nitpick nagłówek i stopkę, to kilka dalszych ulepszeń .
Neil
@Neil To wygląda jak dobry golf, ale niestety wydaje się, że ma błąd. Wypróbuj pojedyncze liczby . Nie działają.
Deadcode
1
@Deadcode Przepraszamy, nie zdawałem sobie sprawy, że pojedyncze liczby są częścią „specyfikacji”.
Neil
2

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
([({}[{}(())])](<>)){({}())<>}{}{((<{}>))<>{}}{}<>{}
MegaTom
źródło
1

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.

DSkoog
źródło
1

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

MH.
źródło
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,
Niezłe! Wiedziałem, że musi istnieć sposób na pozbycie się Math.*połączeń; po prostu nie mogłem wymyślić, jak! Dzięki!
MH.
1

Hy , 37 bajtów

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

Wypróbuj online!

Port odpowiedzi @Dennis.

adl
źródło
1

Japt , 12 10 9 bajtów

É&1-U)>Uq

Wypróbuj online!

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

randomdude999
źródło
-1może być É.
Kudłaty
0

Cjam, 11 bajtów

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

qi_(_W*&2#<

Wypróbuj online

Simmons
źródło
0

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.

IanC
źródło
0

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!

Mama Fun Roll
źródło
n=x=>x-1&1-x>x**.5; n(3)daje mi 0(właściwie daje mi 0 bez względu na dane wejściowe)
eithed
Jaka przeglądarka Może tak być.
Mama Fun Roll
Chrome 52. Firefox 48 daje tę samą odpowiedź nan=x=>x-1&1-x>Math.pow(x,0.5); n(3)
eithed
Ok - to priorytet operatora. Musi tak być, (x-1&1-x)ponieważ bez niego priorytetem operatora jest:(x-1)&((1-x)>x**.5)
eithed 11.08.16
1
-1 bajt: x=>x--**.5<(x&-x)lubx=>x**.5<(--x&-x)
charlie,
0

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
Sara J.
źródło
0

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.

Cody Gray
źródło