Étant donné un entier positif n , calculer la valeur de la fonction Mertens M ( n ) où

et μ ( k ) est la fonction de Möbius où μ ( k ) = 1 si k a un nombre pair de facteurs premiers distincts, -1 si k a un nombre impair de facteurs premiers distincts, et 0 si les facteurs premiers ne sont pas distincts.

• Il s'agit de code-golf, alors créez le code le plus court pour une fonction ou un programme qui calcule la fonction Mertens pour un entier d'entrée n > 0.
• Il s'agit de la séquence OEIS A002321 .

Cas de test

n M(n)
1 1
2 0
3 -1
4 -1
5 -2
6 -1
7 -2
8 -2
9 -2
10 -1
117 -5
5525 5
7044 -25
8888 4
10000 -23

Gelée , 6 octets

:Ḋ߀SC

Essayez-le en ligne! ou vérifiez les cas de test plus petits . (Prend un certain temps)

Contexte

Cela utilise la propriété

de A002321 , ce qui conduit à la formule récursive suivante.

Comment ça fonctionne

:Ḋ߀SC  Main link. Argument: n

 Ḋ      Dequeue; yield [2, ..., n].
:       Perform the integer division of n by each k in [2, ..., n].
  ߀    Recursively call the main link on each result.
    S   Sum; add the results from the recursive calls.
     C  Complement; map the sum r to 1 - r.

Mathematica, 22 20 octets

Merci à @miles pour avoir économisé 2 octets.

Tr@*MoebiusMu@*Range

Explication

Range

Générez une liste de 1 à l'entrée.

MoebiusMu

Trouver MoebiusMuchaque numéro

Tr

Additionnez le résultat.

Python 2, 45 37 octets

f=lambda n,k=2:n<k or f(n,k+1)-f(n/k)

Testez-le sur Ideone .

Contexte

Cela utilise la propriété

de A002321 , ce qui conduit à la formule récursive suivante.

Comment ça fonctionne

Nous utilisons la récursivité non seulement pour calculer M pour les quotients, mais aussi pour calculer la somme de ces images. Cela économise 8 octets sur l'implémentation simple et suivante.

M=lambda n:1-sum(M(n/k)for k in range(2,n+1))

Lorsque f est appelé avec un seul argument n , l'argument optionnel k prend par défaut la valeur 2 .

Si n = 1 , on n<kobtient vrai et f renvoie cette valeur. Ceci est notre cas de base.

Si n> 1 , n<krenvoie initialement False et le code suivant orest exécuté. f(n/k)calcule récursivement un terme de la somme, qui est soustrait de la valeur de retour de f(n,k+1). Ce dernier incrémente k et appelle récursivement f , itérant ainsi sur les valeurs possibles de k . Une fois n <k + 1 ou n = 1 , f(n,k+1)retournera 1 , mettant fin à la récursivité.

05AB1E , 16 15 octets

LÒvX(ygmyyÙïQ*O

Explication

L        # range [1 .. n]
Ò        # list of prime factors for each in list
v        # for each prime factor list
 X(ygm   # (-1)^len(factors)
 yyÙïQ*  # multiplied by factors == (unique factors)
 O       # sum

Essayez-le en ligne!

Brachylog , 22 20 octets

yb:1a+
$p#dl:_1r^|,0

Essayez-le en ligne!

Explication

yb                 The list [1, 2, …, Input]
  :1a              Apply predicate 1 (second line) to each element
     +             Sum the resulting list


    $p#d               All elements of the list of prime factors of the Input are distinct
        l:_1r^         Output = (-1)^(<length of the list of prime factors>)
|                  Or
    ,0                 Output = 0

Gelée , 9 octets

RÆFỊNP€FS

Essayez-le en ligne! ou vérifiez tous les cas de test .

Comment ça fonctionne

RÆFỊNP€FS  Main link. Argument: n

R          Range; yield [1, ..., n].
 ÆF        Factor; decompose each integer in that range into prime-exponent pairs.
   Ị       Insignificant; yield 1 for argument 1, 0 for all others.
    N      Negative; map n to -n.
           This maps primes to 0, exponent 1 to -1, and all other exponents to 0.
     P€    Reduce the columns of the resulting 2D arrays by multiplication.
           The product of the prime values will always be 0; the product of the
           exponent values is 0 if any exponent is greater than, 1 if there is an
           even number of them, -1 is there is an odd number of them.
       FS  Flatten and sum, computing the sum of µ(k) for k in [1, ..., n].

Haskell, 29 27 octets

f n=1-sum(f.div n<$>[2..n])

Gelée , 7 octets

Ị*%ðþÆḊ

Pas très efficace; les déterminants sont difficiles.

Essayez-le en ligne! ou vérifiez les cas de test plus petits . (Prend un certain temps)

Contexte

Cela utilise une formule de A002321 :

M (n) est le déterminant de la matrice booléenne A _{n × n} , où a _{i, j} vaut 1 si j = 1 ou i | j et 0 sinon.

Comment ça fonctionne

Ị*%ðþÆḊ  Main link. Argument: n

   ð     Combine the preceding atoms into a chain (unknown arity).
         Begin a new, dyadic chain with arguments a and b.
Ị        Insignificant; return 1 iff a = 1.
  %      Compute a % b.
 *       Compute (a == 1) ** (a % b).
         This yields 1 if a = 1, or if a ≠ 1 and a % b = 0; otherwise, it yields 0.
    þ    Table; construct the matrix A by calling the defined chain for every pair
         of integers in [1, ..., n].
     ÆḊ  Compute the determinant of the resulting matrix.

PHP, 113 octets

for(;$i=$argv[1]--;){for($n=$j=1;$j++<$i;)if(!($i%$j)){$i/=$j;$n++;if(!($i%$j))continue 2;}$a+=$n%2?1:-1;}echo$a;

Pour autant que je sache, php n'a rien à voir avec la fonctionnalité des nombres premiers, c'est donc une sorte de douleur. Il est probablement possible de faire mieux.

utiliser comme:

 php -r "for(;$i=$argv[1]--;){for($n=$j=1;$j++<$i;)if(!($i%$j)){$i/=$j;$n++;if(!($i%$j))continue 2;}$a+=$n%2?1:-1;}echo$a;" 10000

Raquette 103 octets

(λ(N)(for/sum((n(range 1 N)))(define c(length(factorize n)))(cond[(= 0 c)0][(even? c)1][(odd? c)-1])))

Non golfé:

(define f
  (λ(N)
    (for/sum ((n (range 1 N)))
      (define c (length (factorize n)))
      (cond
        [(= 0 c) 0]
        [(even? c) 1]
        [(odd? c) -1]))))

CJam (20 octets)

qiM{_,:)(@@f/{j-}/}j

Démo en ligne

Utilise la formule d'OEIS

sum(k = 1..n, a([n/k])) = 1. - David W. Wilson, 27 février 2012

et l'opérateur de mémorisation de CJam j.

Dissection

qi       e# Read stdin as an integer
M{       e# Memoise with no base cases
         e#   Memoised function: stack contains n
  _,:)(  e#   Basic manipulations to give n [2 .. n] 1
  @@f/   e#   More basic manipulations to give 1 [n/2 ... n/n]
  {j-}/  e#   For each element of the array, make a memoised recursive call and subtract
}j

JavaScript (ES6), 50 octets

n=>[1,...Array(n-1)].reduce((r,_,i)=>r-f(n/++i|0))

Port de @ Dennis's Python answer.

Julia, 26 25 octets

!n=1-sum(map(!,n÷(2:n)))

Essayez-le en ligne!

Contexte

Cela utilise la propriété

de A002321 , ce qui conduit à la formule récursive suivante.

Comment ça fonctionne

Nous redéfinissons l'opérateur unaire ! pour nos besoins.

n÷(2:n)calcule tous les quotients requis, notre redéfini ! est mappé sur eux, et enfin la somme de tous les appels récursifs est soustraite de 1 .

Malheureusement,

!n=1-sum(!,n÷(2:n))

ne fonctionne pas car la somme dyadique s'étouffera sur une collection vide.

!n=n<2||1-sum(!,n÷(2:n))

corrige cela, mais il n'enregistre aucun octet et renvoie True pour l'entrée 1 .

C, 51 50 47 octets

f(n,t,u){for(t=u=1;n/++u;t-=f(n/u));return t;}

Edit: Merci à @Dennis pour -3 octets!

Scala, 53 octets

def?(n:Int,k:Int=2):Int=if(n<k)1 else?(n,k+1)- ?(n/k)

Un port de la réponse de Dennis en pythin.

J'ai appelé la méthode ?, qui est un jeton qui ne colle pas aux lettres.

Pyth, 12 octets

Définit une fonction yqui prend le n.

L-1syM/LbtSb

Suite de tests ici. (Notez que la fin yici est d'appeler réellement la fonction déclarée.)

En fait, 18 17 16 octets

Suggestions de golf bienvenues. Essayez-le en ligne!

R`;y;l0~ⁿ)π=*`MΣ

Ungolfing

         Implicit input n.
R        Push the range [1..n].
`...`M   Map the following function over the range. Variable k.
  ;        Duplicate k.
  y        Push the distinct prime factors of k. Call it dpf.
  ;        Duplicate dpf.
  l        Push len(dpf).
  0~       Push -1.
  ⁿ        Push (-1)**len(dpf).
  )        Move (-1)**len(dpf) to BOS. Stack: dpf, k, (-1)**len(dpf)
  π        Push product(dpf).
  =        Check if this product is equal to k.
            If so, then k is squarefree.
  *        Multiply (k is squarefree) * (-1)**(length).
            If k is NOT squarefree, then 0.
            Else if length is odd, then -1.
            Else if length is even, then 1.
           This function is equivalent to the Möbius function.
Σ        Sum the results of the map.
         Implicit return.

PARI / GP, 24 octets

n->sum(x=1,n,moebius(x))

J, 19 octets

1#.1*/@:-@~:@q:@+i.

Calcule la fonction Mertens en nutilisant la somme de la fonction Möbius sur la plage [1, n].

Usage

   f =: 1#.1*/@:-@~:@q:@+i.
   (,.f"0) 1 2 3 4 5 6 7 8 9 10 117 5525 7044 8888 10000
    1   1
    2   0
    3  _1
    4  _1
    5  _2
    6  _1
    7  _2
    8  _2
    9  _2
   10  _1
  117  _5
 5525   5
 7044 _25
 8888   4
10000 _23

Explication

1#.1*/@:-@~:@q:@+i.  Input: integer n
                 i.  Range [0, 1, ..., n-1]
   1            +    Add 1 to each
             q:@     Get the prime factors of each
          ~:@        Sieve mask of each, 1s at the first occurrence
                     of a value and 0 elsewhere
        -@           Negate
    */@:             Reduce each using multiplication to get the product
1#.                  Convert that to decimal from a list of base-1 digits
                     Equivalent to getting the sum