La tâche consiste à calculer la somme des diviseurs d'un nombre étant donné sa factorisation première.

Contribution

Deux tableaux (ou quelque chose d'équivalent) de longueur n , l'un contenant le facteur premier et l'autre contenant l'exposant correspondant.

Production

La somme de tous les diviseurs (y compris le nombre lui-même).

Exemple

Le nombre 240 a 2, 3 et 5 comme facteurs premiers avec 4, 1 et 1 comme exposants respectifs. La sortie attendue serait alors de 744.

Input: [2,3,5] [4,1,1]
Output: 744

Notation

Le code le plus court en octets gagne!

Si la complexité d'exécution de votre solution est O (somme des exposants) plutôt que O (produit des exposants), votre score peut être multiplié par 0,8.

Il y avait une question similaire publiée ici, mais ce n'était pas un défi. Je pense que le problème est assez intéressant pour être joué au golf.

Le gagnant sera choisi ce week-end

Pyth, 13 octets * 0,8 = 10,4

*Fms^LhdhedCQ

Manifestation.

Cette réponse fonctionne quelque peu différemment de celles ci-dessus. Afin de calculer la somme des facteurs des puissances premières du nombre, au lieu d'utiliser une formule arithmétique, les facteurs sont explicitement construits et additionnés.

Par exemple, sur la paire [prime, exposant] [2, 4], nous mappons 2 ^ xsur 0, 1, 2, 3, 4, donnant [1, 2, 4, 8, 16], qui est ensuite additionné à 31.

Les résultats sont ensuite multipliés et imprimés.

Si l'exponentiation est correctement implémentée, ou s'il existe une mise en cache des résultats intermédiaire, ce sera le cas O(sum of exponents).

CJam, 15 octets * 0,8 = 12

q~.{_@)#(\(/}:*

Essayez-le en ligne . L'ordre d'entrée est d'abord la liste des exposants, puis la liste des nombres premiers (-3 octets grâce à @Dennis) .

Pour chaque paire d'exposants premiers, (p, e)trouver

(p^(e+1) - 1)/(p - 1)

puis trouvez le produit de tous ces éléments. Par exemple, pour 240, ce serait

(1 + 2 + 4 + 8 + 16)(1 + 3)(1 + 5) = 31 * 4 * 6 = 744

Selon la façon dont l'exponentiation est mise en œuvre, cela peut être mieux que O(sum of exponents).

APL, 18 13 octets * 0,8 = 10,4

×/(1-⊣×*)÷1-⊣

Cela crée un train de fonctions dyadiques qui prend le tableau des facteurs à gauche et les exposants à droite.

×/             ⍝ Vector product of
  (1-⊣×*)      ⍝ each factor^(exponent+1)-1
         ÷1-⊣  ⍝ divided by factor-1

Essayez-le en ligne . Notez que c'est la même approche que la réponse CJam incroyablement intelligente du Sp3000 .

5 octets enregistrés grâce à Dennis!

TI-BASIC, 17 octets * 0,8 = 13,6

Utilise également la méthode de Sp3000, bien que je l'ai trouvée indépendamment. Prend une liste de Input et une de l'écran d'accueil.

Input E
prod(AnsAns^∟E-1)/prod(Ans-1

L'utilisation de prod (deux fois est plus petite car elle nous permet d'utiliser gratuitement la parenthèse ouverte. Notez que cette réponse ne prend pas en charge les tableaux vides, car il n'y a pas de tableaux vides dans TI-BASIC.

Haskell, 38 * 0,8 = 30,4

product$zipWith(\p e->(p*p^e-1)/(p-1))

Usage:

product$zipWith(\p e->(p*p^e-1)/(p-1)) [2,3,5] [4,1,1]
744.0

La fonction anonyme prend (p,e)la somme des diviseurs pour p^evia la somme des séries géométriques. Le fait de compresser les deux listes avec cela comme la jonction et la prise du produit donne le résultat.

Je n'ai pas pu trouver quelque chose de plus court que l'expression arithmétique

(p*p^e-1)/(p-1)
sum$map(p^)[0..e]

Peut-être qu'il existe un moyen de se débarrasser de la (\p e->_).

La définition de la fonction Infix donne la même longueur (38):

p%e=(p*p^e-1)/(p-1)
product$zipWith(%)

C ++, 111 80 77 octets * 0,8 = 61,6

int g(int*p,int*e,int n){return n?g(p+1,e+1,n-1)*(pow(*p,*e-1)-1)/(*p-1):1;}

Cela calcule (p ^ (e + 1) -1) / (p-1) et multiplie récursivement tous les facteurs. Je l'ai découvert il y a un an.

Merci d'avoir aidé, totalement oublié l'utilisation booléenne de style c ++.

Matlab, 53

function t=f(x,y)
s=1:prod(x.^y);t=s*~mod(s(end),s)';

Exemple:

>> f([2 3 5], [4 1 1])
ans =
   744

Python 2156

from itertools import*
from operator import*
i=input()
print sum(reduce(mul,[a**b for a,b in zip(i[0],p)])for p in product(*map(range,[x+1 for x in i[1]])))

Contribution

[[2,3,5],[4,1,1]]

Production

744

Explication

Ce programme reçoit une liste de 2 listes: facteurs et exposants.

i=input() # Receive list of 2 lists: i[0] for factors i[1] for exponents

Ensuite, il crée une liste de toutes les combinaisons possibles de la liste des exposants.

[x+1 for x in i[1]] # [4,1,1]->[5,2,2] (to include last element)
map(range,[x+1 for x in i[1]]) # [[0, 1, 2, 3, 4], [0, 1], [0, 1]]
product(*map(range,[x+1 for x in i[1]])) # [(0, 0, 0), (0, 0, 1), ..., (4, 1, 1)]

et le zip avec les facteurs:

zip(i[0],p) for p in product(*map(range,[x+1 for x in i[1]])) # [[(2, 0), (3, 0), (5, 0)], ..., [(2, 4), (3, 1), (5, 1)]]

Calculez les facteurs de la puissance des exposants:

 [a**b for a,b in zip(i[0],p)]for p in product(*map(range,[x+1 for x in i[1]])) # [[1, 1, 1], ..., [16, 3, 5]]

et multipliez chaque liste (cela nous donne tous les diviseurs):

reduce(mul,[a**b for a,b in zip(i[0],p)])for p in product(*map(range,[x+1 for x in i[1]])) # [1, 5, 3, 15, ..., 240]

Enfin, additionnez toutes les listes et imprimez:

print sum(reduce(mul,[a**b for a,b in zip(i[0],p)])for p in product(*map(range,[x+1 for x in i[1]]))) # 744

Python 3, 134 120 117

Entrée: deux tableaux séparés par des virgules séparés par des virgules.

Exemple:

(2,3,7,11),(4,2,3,2)
21439600

from functools import*
a=eval(input())
print(reduce(int.__mul__,(sum(x**j for j in range(y+1))for x,y in zip(*a)),1))

Avec NumPy peut être réduit à 100 octets:

import numpy
a=eval(input())
print(numpy.product([sum(x**j for j in range(y+1))for x,y in zip(*a)]))

Gelée, non compétitive

Cette réponse n'est pas concurrente, car le défi est antérieur à la création de Jelly.

5 octets (sans bonus)

*PÆDS

Essayez-le en ligne!

Comment ça fonctionne

*PÆDS    Main link. Left input: p (prime factors). Right input: e (exponents).

*        Elevate the prime factors to the corresponding exponents.
 P       Take the product of all powers.
  ÆD     Find all divisors of the product.
    S    Compute the sum of the divisors.

7 octets (5,6 octets après bonus)

*‘}’:’{P

Comment ça fonctionne

×*’:’{P  Main link. Left input: p (prime factors). Right input: e (exponents).

 *       Elevate the prime factors to the corresponding exponents.
         This yields p ** e.
×        Multiply the prime factors with the corresponding powers.
         This yields p ** (e + 1).
  ’      Decrement the resulting products.
         This yields p ** (e + 1) - 1.
    ’{   Decrement the prime factors.
         This yields p - 1.
   :     Divide the left result by the right one.
         This yields (p ** (e + 1) - 1) / (p - 1).
      P  Take the product of all quotients.

Essayez-le en ligne!

APL, 12 octets * 0,8 = 9,6

×/1++/¨⎕*⍳¨⎕

Cela lit deux listes sur le clavier, les exposants en premier, à savoir:

      ×/1++/¨⎕*⍳¨⎕
⎕:
      4 1 1
⎕:
      2 3 5
744

Explication:

• ⎕: lire une liste depuis le clavier (les exposants)
• ⍳¨: pour chaque numéro de la liste, générez une liste [1..n].
• ⎕*: lire une autre liste à partir du clavier (les nombres premiers), et élever chaque nombre premier à chacun des exposants dans les listes correspondantes
• +/¨: additionner chaque liste
• 1+: ajouter un à chaque résultat, pour compenser les manquants x^0dans chacune des listes
• ×/: prendre le produit des résultats

Raquette (schéma), 65 * 0,8 = 52 octets

Même arithmétique que tout le monde

(λ(x y)(foldl(λ(m n o)(*(/(-(expt m(+ n 1))1)(- m 1))o))1 x y))

Explication:

(λ (x y)    ;defines anonymous function with two inputs
    (foldl    ;recursively applies the following function to all elements of the lists given to an argument given (foldl function argument lists lists lists...)
        (λ (m n o) (* (/ (- (expt m (+ n 1)) 1) (- m 1)) o))    ;an anonymous function representing the same arithmetic used in the CJam answer, then multiplying it with our incrementor
        1 x y))    ;the incrementor argument is 1, and the input lists are the ones provided into the original function

Python 2, 80 octets * 0,8 = 64

Cela suppose que l'entrée arrive l'une après l'autre. Suit la même formule que celle décrite dans la réponse CJam du Sp3000.

print(reduce(float.__mul__,[~-(x**-~y)/~-x for x,y in zip(input(),input())],1)) 

Si cela n'est pas autorisé, je vais l'utiliser comme une solution, qui obtient un score de 84 octets * 0,8 = 67,2. L'entrée doit être séparée par une virgule, c'est-à-dire [2,3,5],[4,1,1].

k=input()
print(reduce(float.__mul__,[~-(x**-~y)/~-x for x,y in zip(k[0],k[1])],1))

^{Psst. Hey! Ceci est une solution possible dans Symbolic, quelque chose sur laquelle je travaille:Ƥ(П([~-(x**-~y)/~-xϝx,yϊʐ(Ί,Ί)],1))}

Mathematica, 40 octets

Total[Outer@@{*}~Join~(#^0~Range~#2),3]&

Sans utiliser aucune des incrustations qui traitent des diviseurs, pour se différencier de l'autre solution mathématique dans le fil.

L'entrée est (en utilisant l'exemple) [{2, 3, 5}, {4, 1, 1}]

Perl 5, 96 octets

Évidemment, ce n'est pas gagnant, mais j'ai décidé de l'écrire pour le plaisir.

C'est un sous-programme:

{($b,$e)=@_;$s=1;map$s*=$b->[$_]**$e->[$_],0..@$b-1;$_=1x$s;for$j(1..$s){$i+=$j*/^(.{$j})*$/}$i}

Voyez-le en action ainsi:

perl -e'print sub{...}->([2,3,5],[4,1,1])'

Comment ça fonctionne:

• ($b,$e)=@_lit les tableaux de références d'entrée $b(bases) et $e(exposants).
• $s=1 initialise le produit.
• map$s*=$b->[$_]**$e->[$_],0..@$b-1multiplie $spar les puissances successives d'exposant de base. Maintenant$s c'est le nombre composite.
• $_=1x$sdéfinit $_égal à une chaîne de uns, $slongue. $iest initialisé à 0.
• for$j(1..$s){$i+=$j*/^(.{$j})*$/}essaie, pour chaque nombre $jentre 1 et $s, de se $_séparer en $jrépétant les caractères autant de fois que nécessaire . Si c'est le cas, alors $jdivise $s, et /^(.{$j})*$/est 1 (sinon c'est 0), et $iest augmenté de $j. Ainsi, nous ajoutons au $inombre de partitions dans une partition de taille égale de $_. Comme le souligne Omar E. Pol , $ic'est le nombre que nous recherchons.
• $ià la fin revient $i.

J, 14 octets * 0,8 = 11,2

[:*/(^>:)%&<:[

Usage

   f =: [:*/(^>:)%&<:[
   2 3 5 f 4 1 1
744