Nie, nie mam na myśli ϕ = 1.618...
i π = 3.14159...
. Mam na myśli funkcje .
- φ (x) jest liczbą całkowitą mniejszą lub równą,
x
która jest względnie podstawowax
. - π (x) to liczba liczb pierwszych mniejsza lub równa
x
. - Powiedzmy, że „not pi” to wtedy π̅ (x) i zdefiniujmy, że jest to liczba kompozytów mniejsza lub równa
x
.
Zadanie
Biorąc pod uwagę ściśle dodatnią liczbę całkowitą x
, oblicz φ (π̅ (x)) . Punktacja jest w bajtach.
Przykłady
Każdy wiersz składa się z danych wejściowych (od 1 do 100 włącznie) i odpowiednich danych wyjściowych oddzielonych spacją.
1 0
2 0
3 0
4 1
5 1
6 1
7 1
8 2
9 2
10 4
11 4
12 2
13 2
14 6
15 4
16 6
17 6
18 4
19 4
20 10
21 4
22 12
23 12
24 6
25 8
26 8
27 16
28 6
29 6
30 18
31 18
32 8
33 12
34 10
35 22
36 8
37 8
38 20
39 12
40 18
41 18
42 12
43 12
44 28
45 8
46 30
47 30
48 16
49 20
50 16
51 24
52 12
53 12
54 36
55 18
56 24
57 16
58 40
59 40
60 12
61 12
62 42
63 20
64 24
65 22
66 46
67 46
68 16
69 42
70 20
71 20
72 32
73 32
74 24
75 52
76 18
77 40
78 24
79 24
80 36
81 28
82 58
83 58
84 16
85 60
86 30
87 36
88 32
89 32
90 48
91 20
92 66
93 32
94 44
95 24
96 70
97 70
98 24
99 72
100 36
Użyj tego łącza, aby obliczyć oczekiwany wynik dla dowolnego wejścia. Również lista wejść i wyjść dla x <= 1000
znajduje się tutaj na pastebin . (Wygenerowano za pomocą tego programu Minkolang .)
Liderów
Oto fragment kodu, który pozwala wygenerować zarówno zwykłą tabelę wyników, jak i przegląd zwycięzców według języka.
Aby upewnić się, że Twoja odpowiedź się pojawi, zacznij od nagłówka, korzystając z następującego szablonu Markdown:
## Language Name, N bytes
gdzie N
jest rozmiar twojego zgłoszenia. Jeśli poprawić swój wynik, to może zachować stare porachunki w nagłówku, uderzając je przez. Na przykład:
## Ruby, <s>104</s> <s>101</s> 96 bytes
Jeśli chcesz umieścić w nagłówku wiele liczb (np. Ponieważ twój wynik jest sumą dwóch plików lub chcesz osobno wymienić kary za flagi tłumacza), upewnij się, że rzeczywisty wynik jest ostatnią liczbą w nagłówku:
## Perl, 43 + 2 (-p flag) = 45 bytes
Możesz także ustawić nazwę języka jako link, który pojawi się we fragmencie tabeli wyników:
## [><>](http://esolangs.org/wiki/Fish), 121 bytes
źródło
Odpowiedzi:
GS2 ,
1210 bajtówKod źródłowy używa kodowania CP437 . Wypróbuj online!
Testowe uruchomienie
Jak to działa
źródło
Regex (.NET),
122113 bajtówZakładając, że dane wejściowe i wyjściowe są jednoargumentowe, a dane wyjściowe są pobierane z głównego dopasowania wyrażenia regularnego.
Podział wyrażenia regularnego:
^(?=((?=.*$(?<=^(\3+(.+.))(.*?(?>(.\4)?)))).)+(.*))
oblicza π̅ (x) i przechwytuje resztę ciągu w grupie przechwytywania 6 w celu potwierdzenia w drugiej części..*$
ustawia wskaźnik na końcu ciągu, dzięki czemu mamy liczbę całkowitąx
w jednym kierunku.(?<=^(\3+(.+.))(.*?(?>(.\4)?)))
dopasowuje od prawej do lewej i sprawdza liczbę złożoną, zapętlając od x do 0.(.*?(?>(.\4)?))
jest „zmienną”, która zaczyna się od 0 w pierwszej iteracji i kontynuuje od liczby w poprzedniej iteracji i zapętla do x. Ponieważ najmniejsza liczba złożona to 4,(.\4)?
nigdy nie jest niezgodna, jeśli dostępna jest grupa przechwytywania 4.^(\3+(.+.))
sprawdza, co pozostało z „zmiennej” powyżej (tj.x - "variable"
), czy jest to liczba złożona.((?=.*(?=\6$)(?<=(?!(.+.)\8*(?=\6$)(?<=^\8+))(.+?(?>\9?)))).)+
oblicza φ (π̅ (x)), ograniczając operacje od lewej do prawej za pomocą(?=\6$)
..*(?=\6$)
ustawia wskaźnik w pozycji π̅ (x). Oznaczmy y = π̅ (x).(?<=(?!(.+.)\8*(?=\6$)(?<=^\8+))(.+?(?>\9?)))
dopasowuje od prawej do lewej i sprawdza względną liczbę pierwszą, zapętlając od (y - 1) do 0(.+?(?>\9?))
jest „zmienną”, która zaczyna się od 1 w pierwszej iteracji i kontynuuje od liczby w poprzedniej iteracji i zapętla do y(?!(.+.)\8*(?=\6$)(?<=^\8+))
dopasowuje od lewej do prawej 1 i sprawdza, czy „zmienna” iy są liczbą pierwszą względną.(.+.)\8*(?=\6$)
wybiera dzielnik „zmiennej”, który jest większy niż 1, a efektem ubocznym jest to, że po lewej stronie mamy liczbę całkowitą y.(?<=^\8+)
sprawdza, czy dzielnik „zmiennej” jest również dzielnikiem y.1 W .NET spojrzenie w przyszłość ustawia kierunek na LTR zamiast podążania za bieżącym kierunkiem; look-behind ustawia kierunek na RTL zamiast odwracania kierunku.
Przetestuj wyrażenie regularne w RegexStorm .
Wersja 2 usuwa grupy nie przechwytujące i używa grup atomowych zamiast składni warunkowej.
źródło
J,
1514 bajtówTo jest milczący, monadyczny czasownik. Spróbuj go online z J.js .
Jak to działa
źródło
Poważnie , 27 bajtów
Tak, pokonałem CJam! Wypróbuj online
Objaśnienie (
a
odnosi się do początku stosu,b
odnosi się do drugiego z góry):Uwaga: od opublikowania tej odpowiedzi dodałem funkcje pi i phi do serio. Oto niekonkurencyjna odpowiedź z tymi funkcjami:
Objaśnienie (niektóre polecenia są przesunięte, aby nie nakładały się na inne):
źródło
Julia,
5250 bajtówSpowoduje to utworzenie nienazwanej funkcji, która przyjmuje wartość całkowitą i zwraca liczbę całkowitą. Aby to nazwać, nadaj mu nazwę, np
f=x->...
.Nie golfowany:
źródło
sum
zamiast,count
aby zapisać kilka znaków. Jest to jednak trochę frustrujące - inny sposób liczenia liczb pierwszychsum(isprime,1:x)
jest taki sam jakendof(primes(x))
.sum
kończy się niepowodzeniem za puste kolekcje, acount
zwraca 0. W ten sposóbsum
nie da pożądanego wynikux<4
.Mathematica, 24 bajty
źródło
PhiNotPi@#&
: 11 bajtów: PPyth, 14 bajtów
Demonstracja , weryfikator
Kompozyty obliczamy za pomocą prostego filtra, bierzemy jego długość i zapisujemy w
J
. Następnie bierzemy gcdJ
z każdą liczbą doJ
i liczymy, ile wyników jest równych 1.źródło
Minkolang 0.11 , 12 bajtów (NIE jest konkurencyjny)
Ta odpowiedź NIE jest konkurencyjna. Zaimplementowałem pi i phi jako wbudowane przed opublikowaniem pytania, co daje mi niesprawiedliwą przewagę. Publikuję to tylko dla tych, którzy są zainteresowani językiem.
Wypróbuj tutaj.
Wyjaśnienie
źródło
CJam, 28 bajtów
Wypróbuj to skrzypce w interpretatorze CJam lub sprawdź wszystkie przypadki testowe naraz .
Jak to działa
źródło
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
. Czy to prawda?Python, 137
139źródło
range(n) if
i])) if
Siatkówka , 48 bajtów
Wypróbuj online!
Wyjaśnienie
Konwertuj dane wejściowe na jednoargumentowe.
Policz liczby złożone nie większe niż dane wejściowe, licząc, jak często możemy dopasować ciąg znaków, który składa się z co najmniej dwóch powtórzeń współczynnika co najmniej 2.
Konwertuj ponownie na unary.
Oblicz φ, licząc od tego, ile pozycji nie jest w stanie znaleźć współczynnika (co najmniej 2) sufiksu z tej pozycji, który jest również współczynnikiem prefiksu (jeśli znajdziemy taki czynnik, to
i <= n
dzieli to czynnik zn
nie jest zatem chroniony prawem autorskim). Na.
końcu gwarantuje, że nie liczymy zera (dla którego nie możemy znaleźć współczynnika co najmniej 2).źródło
Regex (.NET),
8886 bajtówWypróbuj online! (Jako program Retina.)
Używa tego samego wejścia / wyjścia co odpowiedź n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨d̷̰̀ĥ̷̳ , tj. Jednoargumentowego wejścia i dopasowuje podciąg długości wyniku.
Możliwe może być dalsze skrócenie tego procesu poprzez zastąpienie jednej lub obu grup bilansujących referencjami do przodu.
Alternatywa przy tej samej liczbie bajtów:
Istnieją również alternatywy dla pierwszej połowy, np. Użycie negatywnego spojrzenia w przód zamiast pozytywnego dla liczb kompozytowych lub użycie warunkowego również tam.
Wyjaśnienie
Zakładam, że masz podstawową wiedzę na temat równoważenia grup , ale w skrócie, grupy przechwytywania w .NET są stosami (więc za każdym razem, gdy użyjesz grupy przechwytywania, nowe przechwytywanie jest umieszczane na górze) i
(?<-x>...)
wyskakuje przechwytywanie ze stosux
. To bardzo pomocne w liczeniu rzeczy.źródło
PARI / GP, 27 bajtów
źródło
Galaretka , niekonkurująca
7 bajtów Ta odpowiedź jest niekonkurencyjna, ponieważ używa języka, który stanowi datę późniejszą wyzwania.
Jak to działa
źródło
Oktawa,
5251Edycja: zapisano 1 bajt dzięki Thomasowi Kwa
Wyjaśnienie:
źródło
PARI / GP, 35 bajtów
źródło
SageMath 26 bajtów
Działa dobrze nawet dla
n=0
in=1
dzięki implementacji Sage.źródło
Galaretka , 6 bajtów
Wypróbuj online!
Jest to współpraca między Cairnem coinheringahhing a Mr. Xcoderem na czacie
Wyjaśnienie
źródło
Gaia , 5 bajtów
Wypróbuj online!
źródło
Ohm v2 , 7 bajtów
Wypróbuj online!
źródło
MATL , 9 bajtów (niekonkurujące)
Ta odpowiedź nie jest konkurencyjna, ponieważ język jest późniejszy niż wyzwanie.
Używa wersji (10.1.0) języka / kompilatora.
Wypróbuj online!
Wyjaśnienie
źródło
GAP, 33 bajtów
Number(l,p)
liczy, ile elementówl
spełniap
. Aby zrekompensować fakt, że 1 nie jest ani liczbą pierwszą, ani złożoną, muszę odjąć od n jeden więcej niż liczbę liczb pierwszych do n. Zamiast robić-1
dla dwóch bajtów, zaczynam listę od -2 zamiast 1 lub 2, dodając w ten sposób jeszcze jedną liczbę, która jest uważana za pierwszą przezIsPrime
tylko jeden dodatkowy bajt.źródło
Python 3.5 - 130 bajtów
Jeśli niedopuszczalne jest przekazanie funkcji jako p (n, 0,0), to +3 bajty.
Wykorzystuje to fakt, że używam twierdzenia Wilsona, aby sprawdzić, czy liczba jest złożona i muszę zadzwonić do modułu matematycznego dla funkcji silni. Python 3.5 dodał funkcję gcd do modułu matematycznego.
Pierwsza pętla kodu będzie zwiększać k o jeden, jeśli liczba jest złożona, i zwiększać o 0 w przeciwnym razie. (Chociaż twierdzenie Wilsona dotyczy tylko liczb całkowitych większych niż 1, traktuje 1 jako liczbę pierwszą, więc pozwala nam to wykorzystać).
Druga pętla będzie następnie zapętlać w zakresie liczby kompozytów i zwiększać g tylko wtedy, gdy wartości nie pi i l są pierwszorzędne.
g jest wówczas liczbą wartości mniejszych lub równych liczbie liczb zespolonych mniejszych lub równych n.
źródło
Python 3 + sympy ,
5958 bajtów* -1 bajt, zastępując
compositepi(k)
wk+~primepi(k)
.Wypróbuj online!
źródło
05AB1E ,
118 bajtówWypróbuj online!
To może być niekonkurencyjne - nie mogę się dowiedzieć, kiedy powstało 05AB1E.
Jak to działa
źródło
Pyt , 6 bajtów
Wyjaśnienie:
Wypróbuj online!
źródło
APL NARS, 38 bajtów, 19 znaków
13π to funkcja totient, a 2π to podstawowa funkcja count <= jej argument. Test
źródło
Dodaj ++ , 21 bajtów
Wypróbuj online!
Jak to działa
R
þP
þ
P
bL
1_
dR
Þ%
bL
G
!!
Tak, naprawdę chciałem wypróbować nowy LaTex
źródło