Divisor sum from prime-power factorisation

Question

The task is to compute the divisor sum of a number given its prime factorisation.

Input

Two arrays (or something equivalent) of length n, one containing the prime factor and the other containing the corresponding exponent.

Output

The sum of all divisors (including the number itself).

Example

The number 240 has 2, 3, and 5 as prime factors with 4, 1, and 1 as the respective exponents. The expected output would then be 744.

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

Scoring

Shortest code in bytes wins!

If your solution's run time complexity is O(sum of exponents) rather than O(product of exponents), your score may be multiplied by 0.8.

---

There was a similar question posted here, but it wasn't a challenge. I think the problem is interesting enought to be golfed.

The winner will be choosen this weekend

• Sp3000: Does the prime factor array always have to be first and the exponent array second or can we assume that the arrays are inputted the other way around?
• Moartem: You may assume any input format similiar to the proposed one
• flawr: Cannot find it right now, but I think this or something similar is on projecteuler.net

Answer 1

CJam, 15 bytes * 0.8 = 12

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

Try it online. The input order is exponent list first, then list of primes (-3 bytes thanks to @Dennis).

For each prime-exponent pair (p, e) find

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

then find the product of all of these. E.g. for 240 this would be

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

Depending on how exponentiation is implemented, this can be better than O(sum of exponents).

Answer 2

APL, (削除) 18 (削除ここまで) 13 bytes * 0.8 = 10.4

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

This creates a dyadic function train that takes the array of factors on the left and the exponents on the right.

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

Try it online. Note that this is the same approach as Sp3000's awesomely clever CJam answer.

Saved 5 bytes thanks to Dennis!

Answer 3

Pyth, 13 bytes * 0.8 = 10.4

*Fms^LhdhedCQ

Demonstration.

This answer works somewhat differently from those above. In order to calculate the sum of the factors of the prime powers of the number, instead of using an arithmetic formula, the factors are explictly constructed and summed.

For instance, on the [prime, exponent] pair [2, 4], we map 2 ^ x over 0, 1, 2, 3, 4, giving [1, 2, 4, 8, 16], which is then summed to 31.

The results are then multiplied together and printed.

If exponentiation is implemented properly, or if there is intermediate result caching, this will be O(sum of exponents).

• Dennis: Independently of the implementation, I don't think it's possible to calculate the first n power of a in O(n) time, unless you assume that multiplication is O(1).
• izzyg: @Dennis Well, the higher order terms dominate, so it would probably have the rutime of the highest order multiplication, which is O(n) if we can assume the base is a constant.

Answer 4

TI-BASIC, 17 bytes * 0.8 = 13.6

Also uses Sp3000's method, though I found it independently. Takes one list from Input and one from the homescreen.

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

Using prod( twice is smaller because it lets us use the open parenthesis for free. Note that this answer does not support empty arrays, because there are no empty arrays in TI-BASIC.

Answer 5

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

The anonymous function takes (p,e) to the divisor-sum for p^e via geometric series sum. Zipping together the two lists with this as the joining and taking the product gives the result.

I wasn't able to find anything shorter that the arithmetic expression

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

Maybe there's a way to get rid of the (\p e->_).

Infix function definition gives the same length (38):

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

Answer 6

C++, (削除) 111 (削除ここまで) (削除) 80 (削除ここまで) 77 bytes * 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;}

This computes (p^(e+1)-1)/(p-1) and recursively multiplies all factors. Found that out myself a year ago.

Thank you for helping, totally forgot about c++ style boolean usage.

• Toby Speight: n==0 simplifies to !n - or you could reverse the outcomes and just use n

Answer 7

Matlab, 53

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

Example:

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

• Moartem: Looks like you may add the 0.8 bonus
• Luis Mendo: @Moartem Thanks! But I'm not sure about that. I compute the number s and then test all possible divisors from 1 to s. So it's (at least) O(s), which is probably between O(sum of exponents) and O(product of exponents)
• Moartem: Yes, that´s right, it´s even bigger than O(product of exponents)

Answer 8

Python 2,156

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]])))

Input

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

Output

744

Explanation

This program receive list of 2 lists: factors and exponents.

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

Then its create list of all possible combinations of the exponent list.

[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)]

and zip it with the factors:

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)]]

Calculate the factors to the power of exponents:

 [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]]

and multiply each list (this gives us all the divisors):

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]

Finally, sum all the lists and print:

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

• Moartem: Could you briefly explain what your code does (as I´m not familiar with python), so I can judge the complexity of your code?
• Moartem: Thats a clever approach, but the complexity is the product of the exponents
• TheCrypt: @Moartem Yeah, I didn't spend much time on reducing the complexity

Answer 9

Python 3, (削除) 134 (削除ここまで) (削除) 120 (削除ここまで) 117

Input: two comma-separated arrays separated by comma.

Example:

(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))

With NumPy can be reduced to 100 bytes:

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

• Kade: For the first example, just so you know, instead of importing operator for using mul once, you can use float.__mul__ to save a bunch of bytes.

Answer 10

APL, 12 bytes * 0.8 = 9.6

×ばつ/1++/ ̈⎕*⍳ ̈⎕

This reads two lists from the keyboard, exponents first, i.e.:

 ×ばつ/1++/ ̈⎕*⍳ ̈⎕
⎕:
 4 1 1
⎕:
 2 3 5
744

Explanation:

• ⎕: read a list from the keyboard (the exponents)
• ⍳ ̈: for each number in the list, generate a list [1..n].
• ⎕*: read another list from the keyboard (the primes), and raise each prime to each of the exponents in the corresponding lists
• +/ ̈: sum each list
• 1+: add one to each result, to compensate for the missing x^0 in each of the lists
• ×ばつ/: take the product of the results

Answer 11

Racket (Scheme), 65 * 0.8 = 52 bytes

Same arithmetic as everyone else

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

Explanation:

(λ (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

Answer 12

Jelly, 4 bytes

*PÆs

Try it online!

How it works

*PÆs - Main link. Takes bases B on the left and exponents E on the right
* - Raise each base to each exponent
 P - Take the product
 Æs - Take the divisor sum

Answer 13

Jelly

(削除) This answer is non-competing, since the challenge predates the creation of Jelly. (削除ここまで)

5 bytes (no bonus)

*PÆDS

Try it online!

How it works

*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 bytes (5.6 bytes after bonus)

*‘}’:’{P

How it works

×ばつ*’:’{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.

Try it online!

Answer 14

Python 2, 80 Bytes * 0.8 = 64

This assumes the input comes in one after another. Follows the same formula as outlined in Sp3000's CJam answer.

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

If this isn't allowed, then I'll use this as a solution, which gets a score of 84 bytes * 0.8 = 67.2. Input should be separated by a comma, i.e. [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! This is a possible solution in Symbolic, something I'm working on: Ƥ(П([~-(x**-~y)/~-xϝx,yϊʐ(Ί,Ί)],1))}

Answer 15

Mathematica, 40 bytes

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

Without using any of the inbuilts that deal with divisors, to differentiate from the other mathematica solution in the thread.

Input is (using example) [{2, 3, 5}, {4, 1, 1}]

Answer 16

Perl 5, 96 bytes

Obviously this is nonwinning, but I decided to write it for fun.

It's a subroutine:

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

See it in action thus:

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

How it works:

• ($b,$e)=@_ reads the input arrayrefs $b (bases) and $e (exponents).
• $s=1 initializes the product.
• map$s*=$b->[$_]**$e->[$_],0..@$b-1 multiplies $s by successive base-exponent powers. Now $s is the composite number.
• $_=1x$s sets $_ equal to a string of ones, $s long. $i is initialized at 0.
• for$j(1..$s){$i+=$j*/^(.{$j})*$/} tries, for every number $j between 1 and $s, to break $_ up as $j characters repeated any number of times. If it can, then $j divides $s, and /^(.{$j})*$/ is 1 (otherwise it's 0), and $i is augmented by $j. Thus, we add to $i the number of partitions in a equal-sized partition of $_. As Omar E. Pol points out, $i is the number we're seeking.
• $i at the end returns $i.

Answer 17

J, 14 bytes * 0.8 = 11.2

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

Usage

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