Funkcja Möbius

Funkcja Möbiusa jest ważną funkcją teorii liczb.

Twoje zgłoszenie powinno zaakceptować dodatnią liczbę całkowitą ni zwrócić wartość funkcji Möbius ocenianej na n.

Definicja

Funkcja Möbiusa μ (n) jest zdefiniowana następująco:

       |  1 if n is squarefree and has an even number of distinct prime factors
μ(n) = | -1 if n is squarefree and has an odd number of distinct prime factors
       |  0 otherwise

nnazywa się bezkwadratowy, jeśli wykładniki pierwotnej faktoryzacji n są dokładnie mniejsze niż dwa. (Alternatywnie: Brak liczby pierwszej do potęgi dwóch podziałów n).

Przypadki testowe

Tutaj możesz zobaczyć pierwsze 50 wartości μ:

^{_{Obraz domeny publicznej z Wikipedii}}

Funkcja Möbius ma numer kolejny A008683 w OEIS.

Oto pierwsze 77 wartości:

1, -1, -1, 0, -1, 1, -1, 0, 0, 1, -1, 0, -1, 1, 1, 0, -1, 0, -1, 0, 1, 1, -1, 0, 0, 1, 0, 0, -1, -1, -1, 0, 1, 1, 1, 0, -1, 1, 1, 0, -1, -1, -1, 0, 0, 1, -1, 0, 0, 0, 1, 0, -1, 0, 1, 0, 1, 1, -1, 0, -1, 1, 0, 0, 1, -1, -1, 0, 1, -1, -1, 0, -1, 1, 0, 0, 1

Większe wartości można również łatwo sprawdzić na Wolframalpha.com lub w pliku b OEIS , jak sugeruje @ MartinBüttner.

Python 2, 48 bajtów

m=lambda n,d=1:d%n and-m(d,n%d<1)+m(n,d+1)or 1/n

Wcześniejsza 51-bajtowa wersja:

m=lambda n:1/n-sum(m(k)for k in range(1,n)if n%k<1)

Möbius - odwraca sekwencję 1,0,0,0,0....

Funkcja Möbiusa ma tę właściwość, że dla każdego n>1, funkcje Mobius z n„s suma dzielników do 0. Tak więc, dla n>1, μ(n)oblicza się poprzez zanegowanie sumę μ(k)dla wszystkich właściwych dzielników ko n. Dane n=1wyjściowe to 1.

Kod obsługuje przypadku podstawowym dodając podłogi przez podział 1/n, który daje 1na n==1i 0w inny sposób.

Podziękowania dla Dennisa za oszczędność 3 bajtów dzięki lepszej rekurencyjnej obsłudze zainspirowanej podobną strukturą w tym wyzwaniu .

Galaretka , 7 bajtów

Kod:

ÆF>1’PS

Wyjaśnienie:

ÆF       # This computes the prime factorization as well as the exponent
  >1     # Compares each element if it's greater than 1, resulting in 1's and 0's
    ’    # Decrement on each element
     P   # Compute the product
      S  # Compute the sum of the list

Na przykład liczba 10 :

ÆF       # [[2, 1], [5, 1]]
  >1     # [[1, 0], [1, 0]]
    ’    # [[0, -1], [0, -1]]
     P   # [0, 1]
      S  # 1

I wyniki w 1 .

Wypróbuj online .

Mathematica, 9 bajtów

MoebiusMu

Oczywiście Mathematica ma wbudowaną funkcję. (I tak zapewne zostanie pobity przez Jelly.)

CJam, 18 15 bajtów

WrimFz~\1&+f/:*

Fakt, że CJam zwraca 1 we wbudowanych faktoryzacjach dla, n = 1sprawia, że ​​jest to nieco trudne.

Wypróbuj online | Zestaw testowy

Dzięki @PeterTaylor za fajną 1&+sztuczkę do obsługi 1 sprawy.

Wyjaśnienie

W                 Push -1
 ri               Push input as int
   mF             Factorise input into [base exponent] pairs
     z~           Zip and unwrap pairs, leaving stack like [-1 bases exponents]
       \1&        Setwise intersect bases with 1, giving [1] for 1 and [] otherwise
          +       Append to exponent array
           f/     Divide the previously pushed -1 by each element in the array 
                  This gives -1 for 1s and 0 otherwise, since / is int division
             :*   Take product

Ponieważ n > 1zmodyfikowana tablica jest tylko tablicą wykładniczą. Jeśli nie nzawiera kwadratów, tablica zawiera wszystkie 1 s, które stają się wszystkimi -1 po podzieleniu. W przeciwnym razie, jeśli n ma dzielnik kwadratowy, to po dzieleniu pojawi się 0, co da iloczyn 0.

Dla n = 1zmodyfikowanej tablicy to [1] + [1], co się [-1 -1]po podziale, otrzymując produkt 1.

Alternatywa 16:

rimF{1#2+3%(}%:*

Używa #(znajdź) w każdej [base exponent]tablicy, aby wyszukać 1, a następnie mapy -1 -> 0, 0 -> 1, 1 -> -1.

Rubinowy, 65 + 7 = 72 62 + 7 = 69 bajtów

->x{((d=x.prime_division).all?{|_,n|n<2}?1:0)*(d.size%2*-2+1)}

+7 bajtów dla -rprimeflagi.

Robimy to w bardzo naiwny sposób:

->x{
 (
  (d=x.prime_division)  # ex. input 20 results in [[2,2],[5,1]] here
  .all?{|_,n|n<2}?      # are all factors' exponents under 2?
  1:0                   # if so, result in a 1; otherwise, a 0
 )
 *                      # multiply that 1 or 0 by...
  (d.size%2*-2+1)       # magic
}

Część „magiczna” powoduje 1, jeśli liczba jest parzysta, a -1 w przeciwnym razie. Oto jak:

Expression       Even  Odd
--------------------------
d.size%2         0     1
d.size%2*-2      0     -2
d.size%2*-2+1    1     -1

Pyth, 9 bajtów

^_{IPQlPQ

Wyjaśnienie:

^_{IPQlPQ    Implicit: Q=input
    PQ       Prime factorization of Q
  {I         Is invariant under uniquify.
  {IPQ       1 if Q is squarefree; 0 otherwise.
 _{IPQ       -1 if Q is squarefree; 0 otherwise.
^     lPQ    Exponentiation to length of PQ.

Wypróbuj tutaj .

Labirynt , 87 bajtów

1
:
}
?   @ "}){/{=:
""({! "      ;
} )   :}}:={%"
* _}}){     ;
{      #}):{{
")`%#/{+

Wypróbuj online!

Krótkie wyjaśnienie

Oto port używanego algorytmu w Pythonie:

divisor = 1
mobius = 1
n = int(input())

while n != 1:
  divisor += 1
  count = 0

  while n % divisor == 0:
    n //= divisor
    count += 1

  mobius *= (count + 3)//(count + 1)%3*-1 + 1

print(mobius)

Długie wyjaśnienie

Zwykły podkład w Labiryncie:

• Labirynt jest oparty na stosie i dwuwymiarowy, a jego wykonanie rozpoczyna się od pierwszego rozpoznanego znaku. Istnieją dwa stosy, główny stos i stos pomocniczy, ale większość operatorów działa tylko na stosie głównym.
• Na każdej gałęzi labiryntu sprawdzana jest górna część stosu, aby ustalić, gdzie dalej iść. Negatyw to skręt w lewo, zero to kierunek na wprost, a dodatni to skręt w prawo.

Wykonanie tego programu rozpoczyna się w lewym górnym rogu 1.

Outer preparation
=================

1        Pop 0 (stack is bottomless and filled with 0s) and push 0*10+1 = 1
:}       Duplicate and shift to auxiliary stack
?        Read int from input
         Stack is now [div=1 n | mob=1]

Top of stack positive but can't turn right. Turn left into outer loop.

Begin outer loop
================
Inner preparation
-----------------

(        Decrement top of stack

If top was 1 (and is now zero), move forward and do...
------------------------------------------------------

{!       Print mob
@        Terminate

If top of stack was greater than 1, turn right and do...
--------------------------------------------------------

)        Increment n back to its previous value
_}       Push 0 and shift to aux
         This will count the number of times n can be divided by div
}){      Increment div
         Stack is now [div n | count mob]

Inner loop
----------

:}}      Dup n, shift both n's to aux
:=       Dup div and swap top of main with top of aux
{%       Shift div down and take mod
         Stack is now [div n%div | n count mob]

If n%div == 0, move forward and do...
-----------------------------------

;        Pop n%div
:={/     Turn n into n/div
{)}      Increment count
         (continue inner loop)

If n%div != 0, turn right (breaking out of inner loop) and do...
================================================================

;        Pop n%div
{{       Pull n and count from aux
:)}      Dup and increment count, giving (count+1), and shift to aux
#+       Add length of stack to count, giving (count+3)
{/       Calculate (count+3)/(count+1)
#%       Mod by length of stack, giving (count+3)/(count+1)%3
`        Multiply by -1
)        Increment, giving (count+3)/(count+1)%3*-1 + 1
         This is 1 if count was 0, -1 if count was 1 and 0 if count > 1
{*}      Multiply mob by this number
         (continue outer loop)

CJam, 20 bajtów

rimf1-___&=\,2%!2*(*

Uruchom tutaj w stosunku do szeregu danych wejściowych.

Wygląda na golfa.

R 39 16 bajtów

numbers::moebius

Wymaga zainstalowanego pakietu numerów w systemie ...

Edycja: znacznie prostsze, jeśli odpowiednio przeczytam specyfikacje [dzięki @AlexA.]

Pyth , 16 bajtów

?nl{PQlPQZ^_1lPQ

Wypróbuj online!

Moja pierwsza rzeczywista odpowiedź na pytanie Pyth. Sugestie docenione! :)

Wyjaśnienie

Moje rozwiązanie wykorzystuje fakt, że liczba nie jest kwadratowa, jeśli jej czynniki pierwsze nie zawierają liczby więcej niż jeden raz. Jeśli dane wejściowe nie zawierają kwadratów, funkcja Möbius przyjmuje wartość -1 ^ (liczba czynników pierwotnych).

?n        if not equal
  l{PQ      length of the list of the distinct input-Primefactors
  lPQ       length of the list of primefactors including duplicates    
    Z         Input is not squarefree, so output Zero
  ^_1lPQ  if input is squarefree, output -1^(number of prime-factors)

MATL , 15 17 bajtów

tq?YftdAwn-1w^*

Używa bieżącej wersji (10.1.0) języka / kompilatora.

Wypróbuj online!

Wyjaśnienie

t         % implicit input. Duplicate that
q         % decrement by 1. Gives truthy (nonzero) if input exceeds 1
?         % if input exceeds 1, compute function. Otherwise leave 1 on the stack
  Yf      % vector of prime factors. Results are sorted and possibly repeated
  td      % duplicate and compute differences
  A       % true if all differences are nonzero
  w       % swap
  n       % number of elements in vector of prime factors, "x"
  -1w^    % -1^x: gives -1 if x odd, 1 if x even 
  *       % multiply by previously obtained true/false value, so non-square-free gives 0
          % implicitly end "if"
          % implicitly display stack contents

05AB1E , 8 bajtów, niekonkurujące

Cholera, jeszcze raz błąd, który powoduje, że moje zgłoszenie nie jest konkurencyjne. Kod:

.p0K1›<P

Wyjaśnienie:

.p        # Get the prime factorization exponents
  0K      # Remove all zeroes from the list
    1›    # Compare each element if greater than 1
      <   # Decrement on each element
       P  # Take the product

Wykorzystuje kodowanie CP-1252

Pyth, 11

*{IPQ^_1lPQ

Zestaw testowy

To zwielokrotnia wartość boolowską, jeśli czynniki pierwsze nie są kwadratowe, -1do potęgi liczby czynników pierwszych, które ma liczba.

Ijest sprawdzeniem niezmienniczości poprzedzającego operatora, którym jest tutaj {operator unikalny.

Japt, 21 bajtów

V=Uk)¬¥Vâ ¬?Vl v ªJ:0

Przetestuj online!

Julia, 66 bajtów

n->(f=factor(n);any([values(f)...].>1)?0:length(keys(f))%2>0?-1:1)

Jest to funkcja lambda, która przyjmuje liczbę całkowitą i zwraca liczbę całkowitą. Aby go wywołać, przypisz go do zmiennej.

Nie golfowany:

function µ(n::Int)
    # Get the prime factorization of n as a Dict with keys as primes
    # and values as exponents
    f = factor(n)

    # Return 0 for non-squarefree, otherwise check the length of the list
    # of primes
    any([values(f)...] .> 1) ? 0 : length(keys(f)) % 2 > 0 ? -1 : 1
end

PARI / GP, 7 bajtów

moebius

Niestety möbiusnie jest dostępny. :)

Poważnie, 19 18 bajtów

,w;`iX1=`Mπ)l1&τD*

Wypróbuj online!

Wyjaśnienie:

,w;`iXDY`Mπ)l1&τD*
,w;                push two copies of the full prime factorization of the input
                      (a list of [base, exponent] pairs)
   `    `M         map the following function:
    iX1=             flatten list, discard, equal to 1
                        (push 1 if exponent == 1 else 0)
          π)       product of list, push to bottom of stack
            1&     push 1 if the # of prime factors is even else 0
              τD   double and decrement (transform [0,1] to [-1,1])
                *  multiply

C # (.NET Core) , 86 73 72 65 bajtów

a=>{int b=1,i=1;for(;++i<=a;)b=a%i<1?(a/=i)%i<1?0:-b:b;return b;}

Wypróbuj online!

-13 bajtów: usprawnione pętle, dodana zmienna zwrotna (dzięki Kevin Cruijssen )
-1 bajt: zmieniono ustawienie b na zero na trójkę z if (dzięki Kevin Cruijssen )
-7 bajtów: zmieniono instrukcję if w pętli na trójkę (dzięki Peter Taylor i Kevin Cruijssen )

Nie golfowany:

a => {
    int b = 1, i = 1;           // initialize b and i to 1

    for(; ++i <= a;)            // loop from 2 (first prime) to a
        b = a % i < 1 ?                     // ternary: if a is divisible by i
            ((a /= i) % i < 1 ? 0 : -b) :   // if true: set b to 0 if a is divisible by i squared, otherwise flip sign of b
            b;                              // if false: don't change b

    return b;                   // return b (positive for even numbers of primes, negative for odd, zero for squares)
}

GNU sed, 89 bajtów

#!/bin/sed -rf
s/.*/factor &/e
s/.*://
/\b([0-9]+) \1\b/!{
s/[0-9]+//g
s/$/1/
s/  //g
y/ /-/
}
s/ .*/0/

J, 18 bajtów

[:*/3<:@|2+2<._&q:

Microsoft Office Excel, wersja brytyjska, 196 bajtów

=IF(ROW()>=COLUMN(),IF(AND(ROW()=1,COLUMN()=1),1,IF(COLUMN()=1,
-SUM(INDIRECT(ADDRESS(ROW(),2)&":"&ADDRESS(ROW(),ROW()))),
IF(MOD(ROW(),COLUMN())=0,INDIRECT(ADDRESS(FLOOR(ROW()/COLUMN(),1),
1)),""))),"")

Formuła komórki Excel, którą należy wprowadzić w komórkach A1 do AX50.

Julia, 35 bajtów

\(n,k=1)=k%n>0?n\-~k-k\0^(n%k):1÷n

Na podstawie odpowiedzi Python @ xnor . Wypróbuj online!

Poważnie, 11 bajtów

Sugestie dotyczące gry w golfa mile widziane. Wypróbuj online!

;y;l0~ⁿ)π=*

Ungolfing

     Implicit input n.
;    Duplicate n.
y    Push a list of the distinct prime factors of n. Call it dpf.
;    Duplicate dpf.
l    Push len(dpf).
0~   Push -1.
ⁿ    Push (-1)**len(dpf).
)    Rotate (-1)**len(dpf) to BOS. Stack: dpf, n, (-1)**len(dpf)
π    Push product(dpf).
=    Check if product(dpf) == n.
      This is only true if n is squarefree.
*    Multiply (n is squarefree) by (-1)**len(dpf).
     Implicit return.

Java 8, 72 68 65 bajtów

n->{int r=1,i=1;for(;++i<=n;)r=n%i<1?(n/=i)%i<1?0:-r:r;return r;}

-4 bajty dzięki @PeterTaylor .

Port odpowiedzi .NET C # @ Meerkata, na którą najpierw grałem trochę dalej, więc pamiętajcie o jego głosowaniu!

Wypróbuj online.

Wyjaśnienie:

n->{                 // Method with integer as both parameter and return-type
  int r=1,           //  Result-integer, starting at 1
  i=1;for(;++i<=n;)  //  Loop `i` in the range [1, n]:
    r=n%i<1?         //   If `n` is divisible by `i`:
       (n/=i)        //    Divide `n` by `i` first
        %i<1?        //    And if `n` is still divisible by `i`:
         0           //     Change `r` to 0
        :            //    Else:
         -r          //     Swap the sign of `r` (positive to negative or vice-versa)
      :              //    Else:
       r;            //     Leave `r` unchanged
  return r;}         //  Return `r` as result

JavaScript (ES6), 48 bajtów

f=(n,i=1)=>n-1?n%++i?f(n,i):(n/=i)%i?-f(n,i):0:1

Po pierwsze - to mój pierwszy kod do golfa, więc do pewnego stopnia mogę źle zrozumieć zasady. W tym zgłoszeniu ;można pominąć ostatni znak i nadal będzie on działał, ale nie jestem nawet pewien, czy kod byłby zgodny ze specyfikacją ES6. W każdym razie krótkie wyjaśnienie.

Najpierw wyjaśnię trochę ten pomysł; bierzemy ni próbujemy podzielić to przez liczbę całkowitą i. Jeśli jest podzielna, robimy to i sprawdzamy, czy jest podzielna i. W takim przypadku musimy wrócić 0. W przeciwnym razie możemy spróbować innego i. Fajne jest to, że możemy zacząć od i=2dodania i za 1każdym razem zwiększać , aby podzielić wszystkie czynniki pierwsze.

Kod działa więc tak:

f=(n,i=1)=>                                           We will increase i by one at the start of
                                                         the function body, so default is 1
           n-1?                                       Check if n==1.
               n%++i?                                 If i isn't, increase i by 1, check if n
                                                         is divisible by i
                     f(n,i):                          if it isn't, we check the next i
                            (n/=i)%i?                 if it is, divide n by i, and check for
                                                         divisibility by i again
                                     -f(n,i):         if it not, then we flip the value to
                                                         account for the 1 and -1 depending on the
                                                         amount of factors
                                             0:       if it's divisible by i twice, done.
                                               1      if we're at 1, divided out all factors,
                                                         then we return 1. The line with
                                                         -f(n,i) will then take care of the sign

To jest moje poddanie.