ZA Liczba Proth , nazwany François Proth, to numer, który można wyrazić jako
N = k * 2^n + 1
Gdzie k
jest 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 > 1
jest 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 > 3
nie 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 + 1
tak naprawdę liczba Proth!
źródło
Python, 22 bajty
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**.5
w implementacji.źródło
Python 2, 23 bajty
źródło
Mathematica,
5048454038353129 bajtówMathematica ogólnie jest do bani, jeśli chodzi o golfa kodowego, ale czasami jest wbudowany, który sprawia, że wszystko wygląda naprawdę ładnie.
Test:
Edycja: Właściwie, jeśli ukradnę bitowy pomysł Dennisa , mogę sprowadzić go do
232220 bajtów.Mathematica,
232220 bajtów (dzięki A Simmons )źródło
g=
, czysta funkcja jest w porządku!Select[Range@1000,f]
.05AB1E ,
1410 bajtówDzięki Emigna za uratowanie 4 bajtów!
Kod:
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ą:Podzieliliśmy je na dwie części. Za pomocą
2Q·0K
otrzymujemy listę dwóch:Za pomocą
®2K
otrzymujemy listę pozostałych liczb: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 .
źródło
<©Ó¬oD®s/›
lub<DÓ0èoDŠ/›
na 10.Brain-Flak ,
460350270266264188176 bajtówWypró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
Ten program nie jest czysty. Jeśli dodasz dodatkowe 4 bajty, możesz wyczyścić stos:
źródło
MATL , 9 bajtów
Prawdziwe wyjście to
1
. Falsy jest0
lub puste wyjście. (Jedynymi danymi wejściowymi, które generują puste dane wyjściowe, są1
i2
; reszta produkuje jeden0
lub1
).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.
źródło
Brachylog , 28 bajtów
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:
źródło
Haskell,
5546 bajtówEdycja: Dzięki nim, teraz 46 bajtów
źródło
sum[1| ... ]
. Tutaj możemy iść dalej i przejść test równości przed|
i sprawdzić wor
czy któryś z nich jest prawdziwe:f x=or[k*2^n+1==x|k<-...,n<-...,2^n>k]
.ECMAScript Regex,
484341 bajtówWyrazy 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ęcejniż 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.
Wypróbuj online!
źródło
Julia, 16 bajtów
Podziękowania dla @Dennis za odpowiedź i kilka wskazówek golfowych!
źródło
&
ma taki sam priorytet jak*
.-~-x
zamiast(1-x)
. Jest też√x
zamiastx^.5
, ale nie zapisuje żadnych bajtów.R,
5250 bajtówProgram zaczyna się od podzielenia
N-1
(zwanego tutajP
ix
)2
tak długo, jak to możliwe, aby znaleźć2^n
część równania, pozostawiająck=(N-1)/2^n
, a następnie oblicza, czyk
jest to gorsze czy nie2^n
, przy użyciu faktu, że2^n>x/2^n <=> (2^n)²>x <=> 2^2n>x
źródło
P=
na początku i zmienić koniec na2^n>x
i zapisać jak 5 lub 6 bajtówRegex (ECMAScript),
4038 bajtów-2 bajty dzięki Deadcode
Wypróbuj online!
Skomentowana wersja:
źródło
^x(?=((xx)+?)(\1\1)*$)(?!(\1x\2*)\4*$)
( Wypróbuj online )J, 10 bajtów
Na podstawie bitowego rozwiązania @Dennis .
Pobiera dane wejściowe
n
i zwraca 1, jeśli jest to liczba Proth, inaczej 0.Stosowanie
Wyjaśnienie
źródło
AND
. fajne!Siatkówka 0.8.2 , 47 bajtów
Konwertuj na unary.
Konwertuj na binarny.
Kilkakrotnie uruchom formułę generacji Proth w odwrotnej kolejności.
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:
źródło
ECMAScript Regex, 42 bajty
Wypróbuj online! (Korzystanie z siatkówki)
Zasadniczo odejmuję 1, dzielę przez największą możliwą liczbę nieparzystą
k
, a następnie sprawdzam, czy przynajmniejk+1
został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
źródło
(\3\3)*)$
na(\3\3)*$)
$=
i$.=
. Można to poprawić jeszcze lepiej .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:
źródło
Klon, 100 bajtów (łącznie ze spacjami)
Ładnie rozmieszczone dla czytelności:
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.
źródło
Java 1.7,
4943 bajtówKolejne 6 bajtów pyłu dzięki @charlie.
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:
Zastosowanie potęgi dwóch do lewej strony wyrażenia:
Może zgolić jeden bajt, jeśli dodatnia wartość liczbowa może reprezentować „prawda”, a ujemna „fałsz”:
Niestety z powodu „zawężenia pierwotnej konwersji” nie można po prostu napisać tego w Javie i uzyskać poprawne wyniki:
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 :(źródło
boolean f(int p){return Math.sqrt(p--)<(p&-p);}
boolean g(int p){return p--<(p&-p)*(p&-p);}
Math.*
połączeń; po prostu nie mogłem wymyślić, jak! Dzięki!Hy , 37 bajtów
Wypróbuj online!
Port odpowiedzi @Dennis.
źródło
C (gcc) , 29
30bajtówWypróbuj online!
źródło
Japt ,
12109 bajtówWypróbuj online!
Port galaretki Port Dennisa ponownie. - 1 dzięki @Shaggy.
źródło
-1
może byćÉ
.Cjam, 11 bajtów
Jak wielu z nas, wykorzystując doskonałe rozwiązanie Dennisa:
Wypróbuj online
źródło
C (137 bajtów)
Dopiero po przeczytaniu przyszedłem przeczytać odpowiedzi.
Biorąc pod uwagę
N=k*2^n+1
warunekk<2^n
(k=1,3,5..
in=1,2,3..
Dzięki
n=1
mamy jedenk
do przetestowania. W miarę wzrostun
liczby kolejnychk's
testó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 danego
n
k=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źć,
n
a 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.
źródło
JavaScript ES7, 16 bajtów
Port mojej odpowiedzi Julii, która jest portem galaretki @ Dennisa.
Dzięki @Charlie za 2 bajty zapisane!
źródło
n=x=>x-1&1-x>x**.5; n(3)
daje mi0
(właściwie daje mi 0 bez względu na dane wejściowe)n=x=>x-1&1-x>Math.pow(x,0.5); n(3)
(x-1&1-x)
ponieważ bez niego priorytetem operatora jest:(x-1)&((1-x)>x**.5)
x=>x--**.5<(x&-x)
lubx=>x**.5<(--x&-x)
C # (.NET Core) , 17 bajtów
Wypróbuj online!
Odpowiedź C portu MegaTom .
Próbowałem rozwiązania opartego na LINQ, ale było to zbyt dobre.
źródło
atrament , 60 bajtów
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
źródło
Kod maszynowy x86, 15 bajtów
Te bajty definiują funkcję, która przyjmuje argument wejściowy (liczbę całkowitą bez znaku) do
EDI
rejestru, zgodnie ze standardową konwencją wywoływania Systemu V dla systemów x86, i zwraca wynik wEAX
rejestrze, jak wszystkie konwencje wywoływania x86.W mnemonikach asemblera:
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:
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
SBB
w przeciwieństwie do instrukcji 3-bajtowejSETB
.źródło