Zamiana głównych wykładników z sąsiadami

13

(Kontynuacja mojego pytania dotyczącego wymiany bitów z sąsiadami ).

Zadanie

Biorąc pod uwagę dodatnią liczbę całkowitą x = (2 a  · 3 b ) · (5 c  · 7 d ) · (11 e  · 13 f ) ·… , wydrukuj liczbę całkowitą uzyskaną przez zamianę wykładników w tym rozkładzie na każdą kolejną parę liczb pierwszych, y = (2 b  · 3 a ) · (5 d  · 7 c ) · (11 f  · 13 e ) ·…

A061898 w OEIS. To jest golf golfowy , więc wygrywa najkrótszy program (w bajtach)!

Przypadki testowe

1 -> 1
2 -> 3
3 -> 2
10 -> 21
37 -> 31
360 -> 756
12345 -> 11578
67895678 -> 125630871
code-golf primes Lynn
źródło
Czy możemy zwrócić wartość True zamiast 1 ?
Dennis
@Dennis Po namyśle zdecydowałem, że moja odpowiedź brzmi „nie”. Wynik musi przynajmniej wyglądać jak liczba.
Lynn,

Odpowiedzi:

4

Galaretka, 17 16 11 bajtów

5 bajtów dzięki Dennisowi.

ÆfÆC’^1‘ÆNP

Wypróbuj online!

Wyjaśnienie

ÆfÆC’^1‘ÆNP   Main monadic chain. Argument: n

Æf            Yield the prime factors of n.
  ÆC          For each factor, count the number of primes below it.
              This effectively yields their indices.
    ’         Decrement [each] by 1.
     ^1       Xor with 1
       ‘      Increment [each] by 1.
        ÆN    Find their corresponding primes.
          P   Yield their product.

Poprzednia 16-bajtowa wersja

ÆnÆRiЀÆf’^1‘ÆNP

Wypróbuj online!

Wyjaśnienie

ÆnÆRiЀÆf’^1‘ÆNP   Main monadic chain. Argument: n

Æn                 Yield the next prime from n.
  ÆR               Yield all primes from 2 to it.
       Æf          Yield prime factors of n
    iЀ            Yield their index in the prime list.
         ’         Decrement [each] by 1.
          ^1       Xor with 1
            ‘      Increment [each] by 1.
             ÆN    Find their corresponding primes.
               P   Yield their product.

Poprzednia 17-bajtowa wersja:

ÆnÆR©iЀÆf’^1‘ị®P

Wypróbuj online!

Wyjaśnienie

ÆnÆR©iЀÆf’^1‘ị®P   Main monadic chain. Argument: n

Æn                  Yield the next prime from n.
  ÆR                Yield all primes from 2 to it.
    ©               Store to register.
        Æf          Yield prime factors of n
     iЀ            Yield their index in the prime list.
          ’         Decrement [each] by 1.
           ^1       Xor with 1
             ‘      Increment [each] by 1.
              ị®    Find their corresponding primes in
                    the list in register.
                P   Yield their product.
Leaky Nun
źródło
3

Mathematica, 70 69 bajtów

1##&@@(Prime[BitXor[PrimePi@#+1,1]-1]^#2&)@@@FactorInteger@#/._@_->1&

Nienazwana funkcja, która przyjmuje i zwraca liczbę całkowitą. Zgłasza błąd na wejściu, 1ale nadal oblicza poprawny wynik.

Wyjaśnienie

Jak zwykle, ze względu na cały cukier składniowy, kolejność czytania jest nieco śmieszna. &Na prawo definiuje nienazwana funkcyjnych i jej argumenty są określane przez #, #2, #3, itd.

...FactorInteger@#...

Zaczynamy od faktoryzacji danych wejściowych. Daje listę par {prime, exponent}np wejście 12daje {{2, 2}, {3, 1}}. Nieco niewygodnie 1daje {{1, 1}}.

(...&)@@@...

Powoduje to zastosowanie funkcji po lewej do listy liczb całkowitych na poziomie 1, to znaczy funkcja jest wywoływana dla każdej pary, przekazując liczbę pierwszą i wykładnik jako osobne argumenty, a następnie zwraca listę wyników. (Jest to podobne do mapowania funkcji na liście, ale otrzymywanie dwóch oddzielnych argumentów jest wygodniejsze niż otrzymywanie pary.)

...PrimePi@#...

Obliczamy liczbę liczb pierwszych do (włącznie) danych wejściowych (pierwszych) za pomocą wbudowanego PrimePi. To daje nam indeks liczby pierwszej.

...BitXor[...+1,1]-1...

Wynik jest zwiększany, XOR'owany 1i ponownie zmniejszany. To zamienia 1 <-> 2, 3 <-> 4, 5 <-> 6, ..., tzn. Wszystkie indeksy 1. Zauważ, że dane wejściowe 1przyniosą zysk, 0na PrimePiktóry jest następnie mapowany -1w tym procesie. Zajmiemy się tym później.

 ...Prime[...]^#2...

Otrzymujemy teraz n- tą liczbę pierwszą (gdzie n jest wynikiem poprzedniego obliczenia), która jest poprawnie zamienioną liczbą pierwszą i podnosimy ją do potęgi oryginalnej liczby pierwszej w rozkładzie na czynniki wejściowe. W tym momencie Prime[-1]wyrzuci błąd, ale zwróci się bez oceny. Moc w tym przypadku jest 1taka, że ​​cały dotychczasowy proces daje {Prime[-1]}wkład 1i listę poprawnych mocy pierwotnych dla wszystkich innych czynników.

 1##&@@...

Następnie pomnożymy wszystkie główne moce. 1##&to standardowa sztuczka golfowa dla tej Timesfunkcji. Zobacz tę końcówkę (sekcja „sekwencje argumentów”) dla, jak to działa.

Wreszcie musimy zadbać o wkład, 1w wyniku którego wszystkie powyższe wyniki zaowocowały Prime[-1]. Możemy to łatwo naprawić za pomocą prostej reguły wymiany. Pamiętaj, że f@xto jest skrót od f[x]. Chcemy tylko dopasować dowolne wyrażenie tej formy (ponieważ wszystkie inne wyniki będą liczbami całkowitymi, tj. Wyrażeniami atomowymi) i zastąpimy je 1:

.../._@_->1

Tutaj /.jest skrótem ReplaceAll, _@_jest wzorem dla f[x]dowolnej postaci (tj. Dowolnego wyrażenia złożonego z jednym dzieckiem) i ->1mówi „zamień na 1”.

Martin Ender
źródło
3

Python 2, 149 139 bajtów

10 bajtów dzięki Dennisowi.

n=input()
p=f=1;w=[2]
while w[-1]<=n:f*=p;p+=1;w+=[p]*(-~f%p<1)
r=p=1;w=w[1:]
while n>1:
    p+=1
    while n%p<1:n/=p;r*=w[w.index(p)^1]
print r
Leaky Nun
źródło
input()działa w Python 2?
NoOneIsHere
@NoOneIsHere Tak, jest to odpowiednik eval(input())w Pythonie 3.
Mego
2

MATL , 17 bajtów

EZqGYfy&mt2\Eq+)p

Wypróbuj online!

Wyjaśnienie

To nie korzysta bezpośrednio z wykładników. Zamiast tego zamienia każdy (prawdopodobnie powtarzany) czynnik pierwszy na pierwszą lub poprzednią liczbę pierwszą.

EZq    % Implicit input. Multiply by 2
Zq     % Array with sequence of primes up to that (this is more than enough)
GYf    % Prime factors of input, with possible repetitions
y      % Duplicate array with sequence of primes
&m     % Indices of prime factors in the sequence of primes
t2\    % Duplicate, modulo 2. Gives 0 for even indices, 1 for odd
Eq     % Multiply by 2, add 1. Transforms 0 / 1 into -1 / 1 
+      % Add. This modifies the indices to perform the swapping
)      % Apply the new indices into the sequence of primes
p      % Product. Implicit display
Luis Mendo
źródło
2

Julia, 64 bajty

~=primes
!n=prod(t->(~3n)[endof(~t[1])+1$1-1]^t[2],factor(2n))/3

Wypróbuj online! Ostatni przypadek testowy wymaga zbyt dużo pamięci dla TIO, ale zweryfikowałem to lokalnie.

Jak to działa

Aby uniknąć wejścia specjalnego 1 - nie jest zdefiniowany iloczyn pustego słownika - mnożymy wejście n przez 2 i dzielimy wynik końcowy przez jego parę 3 .

factor(2n)daje wszystkim dodatnim wykładnikom czynników pierwszych 2n jako słownik. Podczas iteracji w słowniku otrzymamy pary klucz-wartość / liczba pierwsza-wykładnik. Funkcja prodweźmie te pary, zastosuje t->...wobec nich funkcję anonimową i zwróci iloczyn wyników.

Dla każdej pary T = (s, e) , endof(~t[1])lub endof(primes(t[1]))dwie strony k liczba bodźców, które są mniejsze lub równe p , co oznacza, że p jest k p pierwsza.

+1$1-1zwiększy k , XOR k + 1 o 1 i zmniejszy wynik. Jeśli k jest nieparzyste, k + 1 jest parzyste, więc XOR zwiększa się, a końcowy wynik to k + 1 . Jeśli k jest parzyste, k + 1 jest nieparzyste, więc XOR zmniejsza się, a końcowy wynik to k - 1 .

Na koniec obliczamy wszystkie liczby pierwsze mniejsze lub równe 3n z (~3n)lub primes(3n)(najwyższy współczynnik liczby podstawowej 2n jest mniejszy lub równy n, jeśli n> 2 , i zawsze jest liczba pierwsza między n a 2n ), wybierz tę o indeksie k + 1 lub k - 1 i podnieś ją do e- mej mocy za pomocą ^t[2].

Dennis
źródło
2

Python 2, 112 109 108 95 94 bajtów

f=lambda n,k=4,m=6,p=[3,2]:1/n or n%p[1]and f(n,k+1,m*k,m*m%k*[k]+p)or p[len(p)*2%4]*f(n/p[1])

Przetestuj na Ideone .

Jak to działa

Gdy wywoływane jest f , najpierw oblicza 1 / n . Jeśli wynik jest niezerowy, n oznacza 1, a f zwraca 1 .

Jeśli n> 1 , dzieje się tak.

  • Jeśli n nie jest podzielne przez p [1] (początkowo 2 ), n%p[1]daje prawdziwą wartość i

    f(n,k+1,m*k,m*m%k*[k]+p)

    zostaje wezwany.

    Ta gałąź generuje liczbę pierwszą, dopóki przedostatnia nie podzieli n . W tym celu wykorzystuje następujący wniosek twierdzenia Wilsona .

    następstwo twierdzenia Wilsona

    Przez cały czas m jest równe silni k-1 (początkowo 6 = 3! I 4. W każdej iteracji wynik m*m%k*[k]jest dodawany do listy liczb pierwszych p . Zgodnie z tym wynikiem m*m%kjest 1, jeśli k jest liczbą pierwszą i 0, jeśli nie, to wstawia k do p wtedy i tylko wtedy, gdy k jest liczbą pierwszą.

  • Jeżeli n jest podzielne przez p [1] , to n%p[1]daje 0 i

    p[len(p)*2%4]*f(n/p[1])

    zostaje stracony.

    Jeśli p zawiera parzystą liczbę liczb pierwszych, len(p)*2%4zwróci 0, a pierwsza liczba mnoga przyjmuje wartość p [0] . Jeśli p zawiera nieparzystą liczbę liczb pierwszych, len(p)*2%4zwróci 2, a pierwsza liczba mnoga przyjmuje wartość p [2] .

    W obu przypadkach jest to liczba pierwsza, której wykładniki muszą zostać zamienione na jeden z p [1] , więc dzielimy n przez p [1] (zmniejszając wykładnik o 1 ) i mnożymy wynik f(n/p[1])przez odpowiednią liczbę pierwszą (zwiększając wykładnik o 1 ).

    Zauważ, że f(n/p[1])resetuje k , m oraz p do ich wartości domyślnych. f(n/p[1],k,m,p)poprawiłoby wydajność kosztem sześciu dodatkowych bajtów.

Dennis
źródło
1

Pyth, 25 bajtów

JfP_TSfP_ThQ*F+1m@Jx1xJdP

Zestaw testowy.

Wyjaśnienie

JfP_TSfP_ThQ*F+1m@Jx1xJdP

           Q    get input
          h     add one
      fP_T      find the first prime after it
     S          range from 1 to that prime
 fP_T           filter for the primes
J               assign to J

                        P  prime factorize input
                m      d   for each factor
                     xJ    find its index in J
                   x1      xor with 1
                 @J        find the corresponding entry in J
            *F+1           product of the whole list
Leaky Nun
źródło
1

Julia, 155 131 127 bajtów

n->(x=[sort([merge([p=>0for p=primes(n+1)],factor(n))...]);1=>0];prod([x[i-1][1]^x[i][2]*x[i][1]^x[i-1][2]for i=2:2:endof(x)]))

Jest to anonimowa funkcja, która przyjmuje liczbę całkowitą i zwraca liczbę całkowitą. Aby go wywołać, przypisz go do zmiennej. Wymaga wersji Julii <0,5, ponieważ podstawowa funkcjonalność została usunięta z bazy w wersji 0.5.

Nie golfowany:

function f(n::Int)
    # Create an array of pairs by merging the Dict created from factoring n
    # with all primes less than n+1 with a 0 exponent. Append an extra pair
    # to account for 1 and situations where x would otherwise have odd length.
    x = [sort([(merge([p=>0 for p in primes(n+1)], factor(n))...]); 1=>0]

    # Compute a^d * c^b, where a and c are primes with b and d as their
    # respective exponents.
    prod([x[i-1][1]^x[i][2] * x[i][1]^x[i-1][2] for i = 2:2:endof(x)])
end

Wypróbuj online! (Obejmuje wszystkie przypadki testowe)

Alex A.
źródło
1

Właściwie 15 bajtów

w`i;r♂Pí1^Pn`Mπ

Wypróbuj online!

Wyjaśnienie:

w`i;r♂Pí1^Pn`Mπ
w                prime factorization
 `          `M   map (for (p,e) in factorization):
  i;               flatten, make a copy of p
    r♂P            [prime[i] for i in range(p)]
       í           index (essentially the 0-based prime index of p)
        1^         XOR with 1
          P        prime[n]
           n       repeat e times
              π  product
Mego
źródło
1

05AB1E, 22 bajty

Ó¾‚˜2ô€R˜DgL<Ø)øvy`smP

Wyjaśniono

Ó¾‚˜                    # list of primeexponents with a 0 appended: n=10 -> [1,0,1,0] 
    2ô                  # split into pairs: [[1,0],[1,0]]
      €R˜               # reverse each pair and flatten: [0,1,0,1]
         DgL<Ø          # get list of primes corresponding to the exponents: [2,3,5,7]
              )ø        # zip lists: [[0,2],[1,3],[0,5],[1,7]]
                vy`sm   # raise each prime to its new exponent: [1,3,1,7]
                     P  # product: 21

Wypróbuj online

Emigna
źródło
0

J, 21 bajtów

([:,_2|.\,&0)&.(_&q:)

Pobiera główne wykładniki n jako główne potęgi z zerami. Następnie podziel je na nie nakładające się podlisty o rozmiarze 2, wypełniając dodatkowe zero. Następnie odwróć każdą podlistę i spłaszcz ją na liście. Na koniec przekonwertuj z głównych wykładników na liczbę.

Stosowanie

   f =: ([:,_2|.\,&0)&.(_&q:)
   (,.f"0) 1 2 3 10 37 360 12345
    1     1
    2     3
    3     2
   10    21
   37    31
  360   756
12345 11578
   f 67895678x
125630871

Wyjaśnienie

([:,_2|.\,&0)&.(_&q:)  Input: n
                _&q:   Obtain the list of prime exponents
(           )&.        Apply to the list of prime exponenets
         ,&0           Append a zero to the end of the list
    _2  \              Split the list into nonoverlapping sublists of size 2
      |.               Reverse each sublist
 [:,                   Flatten the list of sublists into a list
             &.(    )  Apply the inverse of (Obtain the list of prime exponents)
                       to convert back to a number and return it
mile
źródło