N-movers: Do ilu nieskończonej planszy mogę dotrzeć?

48

Pojedyncze ruchy

Plansza jest nieskończoną 2-wymiarową kwadratową siatką, niczym nieograniczona szachownica. Kawałek o wartości N (ruchomy N ) może przesunąć się na dowolny kwadrat, który jest dokładnie o pierwiastku kwadratowym N z jego obecnego kwadratu (odległość euklidesowa mierzona od środka do środka).

Na przykład:

  • 1-poruszający się gracz może przejść do dowolnego kwadratu sąsiadującego poziomo lub pionowo
  • 2-poruszający się może przesunąć się na dowolny kwadrat, który sąsiaduje po przekątnej
  • 5-poruszający się porusza się jak rycerz szachowy

Pamiętaj, że nie wszystkie ruchy N mogą się poruszać. 3-poruszający się nigdy nie może opuścić swojego aktualnego kwadratu, ponieważ żaden z kwadratów na planszy nie jest w odległości dokładnie 3 pierwiastków od bieżącego kwadratu.

Wiele ruchów

Jeśli pozwolą ci się poruszać wielokrotnie, niektóre pionki mogą dosięgnąć dowolnego kwadratu na planszy. Na przykład zarówno 1-mover, jak i 5-mover mogą to zrobić. 2-poruszający się może poruszać się tylko po przekątnej i może dotrzeć tylko do połowy kwadratów. Element, który nie może się poruszyć, podobnie jak 3-poruszający się, nie może dosięgnąć żadnego z kwadratów (kwadrat początkowy nie jest liczony jako „osiągnięty”, jeśli nie nastąpi ruch) .

1 wnioskodawca 2 ruchome 3-ruchowy 4-ruchowy 5 wnioskodawców 8 wnioskodawców 9-wnioskodawca 10 wnioskodawców 20 wnioskodawców 25 wnioskodawców 40-wnioskodawca 64-wnioskodawca 65-wnioskodawca 68-wnioskodawca

Obrazy pokazują, do których kwadratów można dotrzeć. Więcej informacji na temat aktywowania. Kliknij, aby powiększyć obraz.

  • Kwadraty osiągalne w 1 lub więcej ruchach są zaznaczone na czarno
  • Kwadraty osiągalne w dokładnie 1 ruchu są oznaczone czerwonymi pionkami
    (poza 3-ruchomym, który nie może się poruszać)

Jaką część planszy może osiągnąć dany N-mover?

Wejście

  • Dodatnia liczba całkowita N

Wynik

  • Część planszy, którą może osiągnąć N-mover
  • Jest to liczba od 0 do 1 (obie włącznie)
  • W przypadku tego wyzwania dozwolona jest produkcja jako ułamek w najniższych kategoriach, takich jak 1/4

Więc dla wejścia 10, zarówno 1/2i 0.5są dopuszczalne wyjścia. Dane wyjściowe jako oddzielny licznik i mianownik są również dopuszczalne, ponieważ obejmują języki, które nie obsługują liczb zmiennoprzecinkowych ani ułamkowych. Na przykład 1 2lub [1, 2].

W przypadku liczb całkowitych (0 i 1) akceptowalne są dowolne z poniższych formatów:

  • 0: 0, 0.0, 0/1, 0 1,[0, 1]
  • do 1: 1, 1.0, 1/1, 1 1,[1, 1]

Punktacja

To jest kod golfowy. Wynik to długość kodu w bajtach. W każdym języku wygrywa najkrótszy kod.

Przypadki testowe

W formacie input : output as fraction : output as decimal

  1 : 1     : 1
  2 : 1/2   : 0.5
  3 : 0     : 0
  4 : 1/4   : 0.25
  5 : 1     : 1
  6 : 0     : 0
  7 : 0     : 0
  8 : 1/8   : 0.125
  9 : 1/9   : 0.1111111111111111111111111111
 10 : 1/2   : 0.5
 13 : 1     : 1
 16 : 1/16  : 0.0625
 18 : 1/18  : 0.05555555555555555555555555556
 20 : 1/4   : 0.25
 25 : 1     : 1
 26 : 1/2   : 0.5
 64 : 1/64  : 0.015625
 65 : 1     : 1
 72 : 1/72  : 0.01388888888888888888888888889
 73 : 1     : 1
 74 : 1/2   : 0.5
 80 : 1/16  : 0.0625
 81 : 1/81  : 0.01234567901234567901234567901
 82 : 1/2   : 0.5
144 : 1/144 : 0.006944444444444444444444444444
145 : 1     : 1
146 : 1/2   : 0.5
148 : 1/4   : 0.25
153 : 1/9   : 0.1111111111111111111111111111
160 : 1/32  : 0.03125
161 : 0     : 0
162 : 1/162 : 0.006172839506172839506172839506
163 : 0     : 0
164 : 1/4   : 0.25
241 : 1     : 1
242 : 1/242 : 0.004132231404958677685950413223
244 : 1/4   : 0.25
245 : 1/49  : 0.02040816326530612244897959184
260 : 1/4   : 0.25
261 : 1/9   : 0.1111111111111111111111111111
288 : 1/288 : 0.003472222222222222222222222222
290 : 1/2   : 0.5
292 : 1/4   : 0.25
293 : 1     : 1
324 : 1/324 : 0.003086419753086419753086419753
325 : 1     : 1
326 : 0     : 0
360 : 1/72  : 0.01388888888888888888888888889
361 : 1/361 : 0.002770083102493074792243767313
362 : 1/2   : 0.5
369 : 1/9   : 0.1111111111111111111111111111
370 : 1/2   : 0.5
449 : 1     : 1
450 : 1/18  : 0.05555555555555555555555555556
488 : 1/8   : 0.125
489 : 0     : 0
490 : 1/98  : 0.01020408163265306122448979592
520 : 1/8   : 0.125
521 : 1     : 1
522 : 1/18  : 0.05555555555555555555555555556
544 : 1/32  : 0.03125
548 : 1/4   : 0.25
549 : 1/9   : 0.1111111111111111111111111111
584 : 1/8   : 0.125
585 : 1/9   : 0.1111111111111111111111111111
586 : 1/2   : 0.5
592 : 1/16  : 0.0625
593 : 1     : 1
596 : 1/4   : 0.25
605 : 1/121 : 0.008264462809917355371900826446
610 : 1/2   : 0.5
611 : 0     : 0
612 : 1/36  : 0.02777777777777777777777777778
613 : 1     : 1
624 : 0     : 0
625 : 1     : 1
trichopaks
źródło
10
Zadałem to pytanie na Math.SE: math.stackexchange.com/questions/3108324/…
infmagic2047
Ciekawa hipoteza!
trichoplax
1
„Kawałek, który nie może się poruszyć, jak 3-poruszający się, nie może dosięgnąć żadnego kwadratu”. Co ciekawe, nawet jeśli policzysz kwadrat początkowy, ponieważ plansza jest nieskończona, nadal zbiega się w proporcji do 0.
Beefster
@ Beefster dobry punkt. Poszedłem tą drogą, aby ułatwić znalezienie limitu bez konieczności przejścia do nieskończoności ...
trichoplax
2
Pytanie matematyczne @ infmagic2047 dotyczące podejścia opartego na faktoringu podstawowym ma teraz odpowiedź z kompletnym dowodem .
Ørjan Johansen

Odpowiedzi:

19

JavaScript (Node.js) , 144 138 125 74 73 70 bajtów

f=(x,n=2,c=0)=>x%n?x-!c?f(x,n+1)/(n%4>2?n/=~c&1:n%4)**c:1:f(x/n,n,c+1)

Wypróbuj online!

-4 bajty dzięki @Arnauld!

Oryginalne podejście, 125 bajtów

a=>(F=(x,n=2)=>n*n>x?[x,0]:x%n?F(x,n+1):[n,...F(x/n,n)])(a).map(y=>r-y?(z*=[,1,.5,p%2?0:1/r][r%4]**p,r=y,p=1):p++,z=r=p=1)&&z

Wypróbuj online!

Zainspirowany filmem Pi ukrywającym się w najlepszych regularnościach przez 3Blue1Brown.

Dla każdego czynnika pierwszego w faktoryzacji liczby obliczyć :pnf(pn)

  • Jeśli jest nieparzyste, a - . Ponieważ nie ma dokąd pójść.np3 (mod 4)f(pn)=0
  • Jeśli jest parzyste, a - .np3 (mod 4)f(pn)=1pn
  • Jeśli - .p=2f(2n)=12n
  • Jeśli - .p1 (mod 4)f(pn)=1

Pomnóż wszystkie te wartości funkcji, oto jesteśmy.

Aktualizacja

Dzięki wysiłkom autorów Math.SE algorytm jest teraz poparty dowodem

Shieru Asakoto
źródło
Czy wideo zawiera dowód? Próbowałem udowodnić ten wynik od kilku godzin, ale nie mogłem tego rozgryźć.
infmagic2047
1
@ infmagic2047 Nie bardzo, ale daje metodę zliczania punktów w okręgu . Jest to przydatne, gdy sprowadza się do tego, jak może iść n-mover. n
Shieru Asakoto
3
@ infmagic2047 Myślę, że banalne jest udowodnienie przypadków ale sprawy dotyczące pozostałych są dość trudne do udowodnienia formalnie ...q=pPp{2,3} (mod 4)pep
Shieru Asakoto
1
Pytanie matematyczne @ infmagic2047 dotyczące tego podejścia ma teraz odpowiedź z kompletnym dowodem .
Ørjan Johansen
11

Mathematica, 80 bajtów

d[n_]:=If[#=={},0,1/Det@LatticeReduce@#]&@Select[Tuples[Range[-n,n],2],#.#==n&];

Ten kod opiera się głównie na twierdzeniu matematycznym. Podstawową ideą jest to, że kod pyta o gęstość sieci, biorąc pod uwagę pewien zestaw generacyjny.

Mówiąc dokładniej, otrzymaliśmy zbiór wektorów - mianowicie tych, których długość do kwadratu wynosi N - i poprosiliśmy o obliczenie gęstości zbioru możliwych sum tych wektorów w porównaniu do wszystkich wektorów całkowitych. Matematyka w grze polega na tym, że zawsze możemy znaleźć dwa wektory (i ich przeciwieństwa), które „generują” (tj. Których sumy są) taki sam zestaw jak oryginalna kolekcja. LatticeReduce robi dokładnie to.

Jeśli masz tylko dwa wektory, możesz sobie wyobrazić, że narysujesz identyczny równoległobok wyśrodkowany w każdym osiągalnym punkcie, ale którego długości krawędzi są podanymi wektorami, tak że płaszczyzna jest całkowicie ułożona sąsiadująco przez te równoległoboki. (Wyobraź sobie na przykład sieć kształtów „diamentowych” dla n = 2). Obszar każdego równoległoboku jest wyznacznikiem dwóch wektorów generujących. Pożądana proporcja płaszczyzny jest odwrotnością tego obszaru, ponieważ każdy równoległobok ma tylko jeden osiągalny punkt.

Kod jest dość prostą implementacją: generuj wektory, użyj LatticeReduce, weź wyznacznik, a następnie weź odwrotność. (Prawdopodobnie można lepiej grać w golfa)

Milo Brandt
źródło
76 bajtów:d@n_:=Boole[#!={}]/Det@LatticeReduce@#&@Select[Range[-n,n]~Tuples~2,#.#==n&]
u54112
11

Czysty , 189 185 172 171 bajtów

import StdEnv
$n#r=[~n..n]
#p=[[x,y]\\x<-r,y<-r|x^2+y^2==n]
=sum[1.0\\_<-iter n(\q=removeDup[k\\[a,b]<-[[0,0]:p],[u,v]<-q,k<-[[a+u,b+v]]|all(\e=n>=e&&e>0)k])p]/toReal(n^2)

Wypróbuj online!

Znajduje każdą pozycję nmożliwą do osiągnięcia w kwadracie o boku wzdłuż narożnika na początku w pierwszym kwadrancie, a następnie dzieli przez, n^2aby uzyskać dostęp do części wszystkich komórek.

Działa to, ponieważ:

  • Całą osiągalną płaszczyznę można uznać za zachodzące na siebie kopie tego nkwadratu o boku długości, z których każdy jest osaczony w osiągalnym punkcie od początku, jakby był początkiem.
  • Wszystkie ruchy są podzielone na cztery grupy ze znakami ++ +- -+ --, co pozwala na przedłużenie nakładających się kafelków przez pozostałe trzy kwadranty poprzez odbicie lustrzane i obrót.
Obrzydliwe
źródło
Przepraszam - patrzyłem na przypadki testowe, które zaczynają się od N = 10 do N = 13, podczas gdy twoje przypadki testowe również obejmują N = 11 i N = 12. Rzeczywiście masz rację dla N = 13. +1 ode mnie :)
trichoplax
1
@trichoplax Zmieniłem testy, aby odpowiadały na pytanie, aby ponownie uniknąć tego samego zamieszania
Οurous
Następnie przetestowałem do N = 145 i wszystkie są poprawne. Nie mogłem jednak przetestować 146 na TIO z powodu 60-sekundowego limitu czasu. Spodziewam się bardzo długich czasów w odpowiedziach tutaj ...
trichoplax
1
Ponieważ zdałem sobie z tego sprawę: powodem, dla którego kwadratowe rogi są osiągalne, jeśli istnieje co najmniej jeden ruch (a, b), jest złożone równanie (a + bi) (a-bi) = a ^ 2 + b ^ 2, które w postaci wektorowej staje się (N, 0) = a (a, b) + b (b, -a).
Ørjan Johansen
5

Retina 0.8.2 , 126 82 bajtów

.+
$*
+`^(1(1111)+)(?<!^\3+(11+))(\1)*$
1$#4$*
^(?!((^1|11\2)+)\1?$)1+
0
11+
1/$.&

Wypróbuj online! Link zawiera przypadki testowe. Wyjaśnienie:

.+
$*

Konwertuj na unary.

+`^(1(1111)+)(?<!^\3+(11+))(\1)*$
1$#4$*

Wielokrotnie dziel przez główne czynniki formy 4k+1.

^(?!((^1|11\2)+)\1?$)1+
0

Jeśli wynikiem nie jest ani kwadrat, ani dwa razy kwadrat, wynik wynosi zero.

11+
1/$.&

Oblicz odwrotność jako ułamek dziesiętny.

Neil
źródło
5

Regex (ECMAScript, wzajemność), 256 163 157 94 83 82 bajtów

-93 bajtów dzięki Neilowi
-6 bajtów dzięki Neilowi
-63 bajtów dzięki podziałowi bez przechwytywania dzielnika
-11 bajtów dzięki jednoczesnemu opcjonalnemu dzieleniu przez stałą Grimy i pierwiastkowi kwadratowemu
-1 bajtu poprzez przesunięcie warunku dopasowania końcowego i przechwytywanie wartości zwrotnej w pętli jako druga alternatywa, dzięki Grimy

Wykorzystuje to tę samą matematykę, co odpowiedź JavaScript Shieru Asakoto .

Dane wejściowe są jednoargumentowe. Ponieważ czysty wyrażenie regularne może zwracać jako dane wyjściowe tylko podłańcuch z wejścia (tj. Liczbę naturalną mniejszą lub równą wartości wejściowej) lub „brak dopasowania”, to wyrażenie regularne zwraca odwrotność proporcji płyty, którą przesuwa N może osiągnąć. Ponieważ odwrotnością 0 jest nieskończoność, w takim przypadku zwraca „brak dopasowania”.

OSTRZEŻENIE SPOILERA : W przypadku pierwiastka kwadratowego, wyrażenie regularne używa wariantu uogólnionego algorytmu mnożenia, co nie jest oczywiste i może być satysfakcjonującą łamigłówką do samodzielnego opracowania. Aby uzyskać więcej informacji, zobacz wyjaśnienie tej formy algorytmu w Znajdź liczbę Rocco .

pp1 (mod 4)mm3 (mod 4)mm/2mm

mm/2p3 (mod 4)

^(?=((?=(x+)(?!(\2+)(\2\3)+$)((\2{4})+$))\5|((xx?)(\8*))(?=(\7*)\9+$)\7*$\10)+$)\1

Wypróbuj online!
Wypróbuj online! (tylko przypadki testowe)

^
(?=
    (                          # Capture return value, which will just be the value
                               # matched by the last iteration of this loop.
    # Divide tail by every one of its prime factors that's ≡1 mod 4, as many times as
    # possible.
        (?=
            (x+)               # \2 = quotient
            (?!(\2+)(\2\3)+$)  # Assert divisor is prime
            ((\2{4})+$)        # Assert divisor ≡1 mod 4; \5 = tool to make tail = \2
        )\5                    # tail = \2
    |
    # When the above alternative has been done as many times as possible:
    # Test if tail or tail/2 is a perfect square. If this test fails, the regex engine
    # will backtrack into the division loop above, and run the same perfect square
    # test on every previous number (effectively "multiplying" it by each previous P
    # in reverse, one at a time). This will not cause a failure of the test to change
    # into a success, however, because the odd power of a prime ≡3 mod 4 will see be
    # present in the number at every step. Allowing this backtracking to happen is a
    # golf optimization, and it does make the regex slower.
    # Failure of this perfect square test results in returning "no match" and indicates
    # a return value of zero.
        (                      # \7 = \8 * sqrt(tail / \8)
            (xx?)              # \8 = control whether to take sqrt(tail)
                               #                         or 2*sqrt(tail/2)
            (\8*)              # \9 = \7 - \8
        )
        (?=
            (\7*)\9+$          # Iff \8 * (\7 / \8)^2 == our number, then the first match
                               # here must result in \10==0
        )
        \7*$\10                # Test for divisibility by \7 and for \10==0
                               # simultaneously
    )+
    $                          # Require that the last iteration of the above loop was
                               # the perfect square test. Since the first alternative,
                               # the division, always leaves >=1 in tail, this guarantees
                               # that the last step is a successful perfect square test,
                               # or else the result will be "no match".
)
\1                             # Return value (which is a reciprocal)

Regex (ECMAScript + (? *), Wyjście wzajemne), 207 138 132 bajtów

Przestarzały przez podział bez przechwytywania dzielnika (tj. Jest teraz identyczny z powyższym).

Regex (ECMAScript 2018, wyjście wzajemne), 212 140 134 bajtów

Przestarzały przez podział bez przechwytywania dzielnika (tj. Jest teraz identyczny z powyższym).

Regex (ECMAScript, wyjście ułamkowe), 80 bajtów

W tej wersji licznik jest zwracany w \10(zero, jeśli nie jest ustawiony / NPCG), a mianownik w \7.

W przeciwieństwie do wersji z wyjściem wzajemnym:

  • Wejście zerowe nie jest poprawnie traktowane (zwraca „brak dopasowania” tak jak w tej wersji, ale w przeciwieństwie do niego nie odpowiada wartości wyjściowej zero).
  • Jeśli idealny test kwadratowy nie powiedzie się, nie powraca do pętli podziału, więc ta wersja jest bardziej wydajna w czasie wykonywania.

Dużym minusem takiej specyfikacji wyjściowej jest to, że nie jest ona zawarta w samym programie.

((?=(x+)(?!(\2+)(\2\3)+$)((\2{4})+$))\5)*((((x)x?)(\9*))(?=(\8*)\11+$)\8*$\12|x)

Wypróbuj online!
Wypróbuj online! (tylko przypadki testowe)

# No need to anchor, since we return a match for all inputs in the domain.
# Divide tail by every one of its prime factors that's ≡1 mod 4
(
    (?=
        (x+)               # \2 = quotient
        (?!(\2+)(\2\3)+$)  # Assert divisor is prime
        ((\2{4})+$)        # Assert divisor ≡1 mod 4; \5 = tool to make tail = \2
    )\5                    # tail = \2
)*
# Test if tail or tail/2 is a perfect square. If this test succeeds, return tail as
# the denominator and 1 as the numerator.
(                          # \7 = denominator output
    (                      # \8 = \9 * sqrt(tail / \9)
        ((x)x?)            # \9 = control whether to take sqrt(tail) or 2*sqrt(tail/2);
                           # \10 = numerator output (NPCG to represent zero)
        (\9*)              # \11 = \8 - \9
    )
    (?=
        (\8*)\11+$         # Iff \9 * (\8 / \9)^2 == our number, then the first match
                           # here must result in \12==0
    )
    \8*$\12                # Test for divisibility by \8 and for \12==0
                           # simultaneously
|
# Failure of the perfect square test results in returning 0/1 as the answer, so here
# we return a denominator of 1.
    x
)
Deadcode
źródło
1
Przepraszam, oczywiście nie wypróbowałem tego na wystarczającej liczbie przypadków testowych.
Neil
1
@trichoplax Czy można uznać, że odpowiedzią jest stosunek długości dwóch określonych grup przechwytywania? (W rzeczywistości odpowiedź byłaby krótsza, ponieważ sprawienie, by cały mecz był rezultatem, sprawia kłopot).
Neil
1
Po komentarzu @ Neila dokonałem edycji, aby zezwolić na wyjście jako osobny licznik i mianownik, ponieważ wydaje się to najmniejszą zmianą, która pozwala na czystą regex. Daj mi znać, jeśli nadal będzie to problem
trichoplax
1
-11 bajtów za pomocą, (((xx?)(\9*))(?=(\8*)\10+$)\8*$\11)aby sprawdzić, czy N lub N / 2 jest kwadratem.
Grimmy,
1
Wskaźniki @Deadcode do odnośników zwrotnych nie powinny mieć kosztu bajtu, ponieważ są one domyślnie dozwolone .
Grimmy
4

Galaretka ,  25  24 bajtów

ÆFµ%4,2CḄ:3+2Ịị,*/ʋ÷*/)P

Łącze monadyczne wykorzystujące trasę czynnika pierwotnego.

Wypróbuj online!

W jaki sposób?

ÆFµ%4,2CḄ:3+2Ịị,*/ʋ÷*/)P - Link: integer, n               e.g. 11250
ÆF                       - prime factor, exponent pairs        [[2,1], [3,2], [5,4]]
  µ                   )  - for each pair [F,E]:
    4,2                  -   literal list [4,2]
   %                     -   modulo (vectorises)                [2,1]  [3,0]  [1,0]
       C                 -   complement (1-x)                  [-1,0] [-2,1]  [0,1]
        Ḅ                -   from base 2                         -2     -3      1      
         :3              -   integer divide by three             -1     -1      0
           +2            -   add two (call this v)                1      1      3
                  ʋ      -   last four links as a dyad, f(v, [F,E])
             Ị           -     insignificant? (abs(x)<=1 ? 1 : 0)   1      1      0
                */       -     reduce by exponentiation (i.e. F^E)  2      9     625
               ,         -     pair v with that                   [1,2]  [1,9]  [3,625]
              ị          -     left (Ị) index into right (that)     1      1     625
                    */   -   reduce by exponentiation (i.e. F^E)    2      9     625
                   ÷     -   divide                                1/2    1/9  625/625
                       P - product                                 1/18 = 0.05555555555555555

Poprzednie 25 to:

ŒRp`²S⁼ɗƇ⁸+€`Ẏ;Ɗ%³QƊÐLL÷²

Pełny program brutal forcer ; być może dłuższy kod niż trasa pierwszego czynnika (mógłbym spróbować później).

Wypróbuj online!

Rozpoczyna się od utworzenia pojedynczych ruchów jak współrzędne następnie wielokrotnie ruchy ze wszystkich miejscach nagromadzenia osiągnięte wyniki, przy modulo nkażdej współrzędnej (ograniczyć do nprzez nćwiartkę) i utrzymywania tych, które są różne, aż do osiągnięcia punktu stałego; następnie dzieli liczbę przezn^2

Jonathan Allan
źródło
4

05AB1E , 27 26 25 bajtów

ÓεNØ©<iozë®4%D≠iyÈ®ymz*]P

Port @ShieruAsakoto JavaScript odpowiedź „s , więc upewnij się upvote go tak dobrze!

Wypróbuj online lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie:

Ó                   # Get all prime exponent's of the (implicit) input's prime factorization
                    #  i.e. 6 → [1,1]      (6 → 2**1 * 3**1)
                    #  i.e. 18 → [1,2]     (18 → 2**1 * 3**2)
                    #  i.e. 20 → [2,0,1]   (20 → 2**2 * 3**0 * 5**1)
                    #  i.e. 25 → [0,0,2]   (25 → 2**0 * 3**0 * 5**2)
 ε                  # Map each value `n` to:
  NØ                #  Get the prime `p` at the map-index
                    #   i.e. map-index=0,1,2,3,4,5 → 2,3,5,7,11,13
    ©               #  Store it in the register (without popping)
     <i             #  If `p` is exactly 2:
       oz           #   Calculate 1/(2**`n`)
                    #    i.e. `n`=0,1,2 → 1,0.5,0.25
      ë             #  Else:
       ®4%          #   Calculate `p` modulo-4
                    #    i.e. `p`=3,5,7,11,13 → 3,1,3,3,1
          D         #   Duplicate the result (the 1 if the following check is falsey)
           i       #   If `p` modulo-4 is NOT 1 (in which case it is 3):
             yÈ     #    Check if `n` is even (1 if truthy; 0 if falsey)
                    #     i.e. `n`=0,1,2,3,4 → 1,0,1,0,1
             ®ymz   #    Calculate 1/(`p`**`n`)
                    #     i.e. `p`=3 & `n`=2 → 0.1111111111111111 (1/9)
                    #     i.e. `p`=7 & `n`=1 → 0.14285714285714285 (1/7)
              *     #    Multiply both with each other
                    #     i.e. 1 * 0.1111111111111111 → 0.1111111111111111
                    #     i.e. 0 * 0.14285714285714285 → 0
 ]                  # Close both if-statements and the map
                    #  i.e. [1,1] → [0.5,0.0]
                    #  i.e. [1,2] → [0.5,0.1111111111111111]
                    #  i.e. [2,0,1] → [0.25,1.0,1]
                    #  i.e. [0,0,2] → [1.0,1.0,1]
  P                 # Take the product of all mapped values
                    #  i.e. [0.5,0.0] → 0.0
                    #  i.e. [0.5,0.1111111111111111] → 0.05555555555555555
                    #  i.e. [0.25,1.0,1] → 0.25
                    #  i.e. [1.0,1.0,1] → 1.0
                    # (and output implicitly as result)
Kevin Cruijssen
źródło
4

APL (Dyalog Extended) , 21 bajtów

Ten program używa trasy czynnika podstawowego. Jestem wdzięczny Adamowi, dzaimie, H.PWizowi, J.Sallé i ngn. APL Orchard to świetne miejsce do nauki APL i zawsze są chętni do pomocy

(×/÷,34|*∘≢⌸)⍭*14|⍭

Wypróbuj online!

Ungolfing

Część 2 tego kodu jest taka sama jak w poniższej wersji Dyalog Unicode, dlatego w tym wyjaśnieniu skupię się na ⍭*1≠4|⍭

⍭*14|⍭

        Gives us a list of the prime factors of our input.
           Example for 45: 3 3 5
  14|   Checks if each prime is of the form 4k+1.
⍭*       Takes each prime to the power of 1 or 0,
           turning all the 4k+1 primes into 1s.
           Example for 45: 3 3 1

APL (Dyalog Unicode) , 41 40 36 35 bajtów SBCS

Ten program używa trasy czynnika podstawowego. Nauczyłem się kilku trików podczas pisania tego i jestem głęboko wdzięczny Adamowi, dzaimie, H.PWizowi, J.Sallé i ngn. APL Orchard to świetne miejsce do nauki APL i zawsze są chętni do pomocy (lub ten post nigdy by nie powstał :)

Edycja: -1 bajt od ngn. -2 bajty z Adám i -2 więcej z ngn. -1 bajt od ngn.

{(×/÷,34|*∘≢⌸)p*14|p←¯2÷/∪∧\⍵∨⍳⍵}

Wypróbuj online!

Ungolfing

To jest program składający się z dwóch części:

p*14|p←¯2÷/∪∧\⍵∨⍳⍵  Part 1

      p             We can define variables mid-dfn (a function in {} brackets).
               ⍵∨⍳⍵  We take the GCD of our input 
                       with every member of range(1, input).
            ∪∧\      This returns all the unique LCMs of every prefix
                       of our list of GCDs.
                       Example for 31500: 1 2 6 12 60 420 1260 6300 31500
        ¯2÷/         We divide pairwise (and in reverse)
                       by using a filter window of negative two 2).
                       Example for 31500: 2 3 2 5 7 3 5 5
  14|p              Check if the primes are 1 modulo 4 or not
p*                   And take each prime to the power of the result (1 or 0),
                       turning the 4k+3 primes into 1s
                       and leaving any 2s and 4k+3 primes.
                       Example for 31500: 2 3 2 1 7 3 1 1

(×/÷,34|*∘≢⌸)  Part 2

(            )  We apply all this to the filtered array of primes.
         *∘≢⌸   This takes all of our primes to their exponents
                  (the number of times those primes appear in the factorization).
                  Example for 31500: 4 9 1 7
     34|       Then we take each prime modulo 4 and check if not equal to 3.
                  We will only get a falsey if any 4k+3 primes, as an even number of
                  4k+3 primes multiplied together will result in some 4m+1.
                  Example for 31500: 1 1 1 0
   ÷,           We append the results of the above condition check
                  to the reciprocals of the primes in p.
                  Example for 31500: (1/2) (1/3) (1/2) 1 (1/7) (1/3) 1 1 1 1 1 0
 ×/             We multiply it all together, resulting in a positive fraction or 0
                  depending on our condition check.
                  Example for 31500: 0
                We return the results of all our checks implicitly.
Sherlock9
źródło