11
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – Sp3000 Jul 22 '15 at 18:20
  • \$\begingroup\$ You may assume any input format similiar to the proposed one \$\endgroup\$ – Moartem Jul 23 '15 at 6:39
  • \$\begingroup\$ Cannot find it right now, but I think this or something similar is on projecteuler.net \$\endgroup\$ – flawr Jun 6 '16 at 12:49

16 Answers 16

3
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ 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). \$\endgroup\$ – Dennis Jul 23 '15 at 21:28
  • \$\begingroup\$ @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. \$\endgroup\$ – isaacg Jul 23 '15 at 21:59
9
\$\begingroup\$

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

\$\endgroup\$
6
\$\begingroup\$

APL, 18 13 bytes * 0.8 = 10.4

×/(1-⊣×*)÷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
  (1-⊣×*)      ⍝ 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!

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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(%)
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ n==0 simplifies to !n - or you could reverse the outcomes and just use n \$\endgroup\$ – Toby Speight Jul 23 '15 at 8:59
2
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Looks like you may add the 0.8 bonus \$\endgroup\$ – Moartem Jul 25 '15 at 9:43
  • \$\begingroup\$ @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) \$\endgroup\$ – Luis Mendo Jul 25 '15 at 10:16
  • \$\begingroup\$ Yes, that´s right, it´s even bigger than O(product of exponents) \$\endgroup\$ – Moartem Jul 27 '15 at 6:39
1
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Could you briefly explain what your code does (as I´m not familiar with python), so I can judge the complexity of your code? \$\endgroup\$ – Moartem Jul 24 '15 at 7:37
  • \$\begingroup\$ Thats a clever approach, but the complexity is the product of the exponents \$\endgroup\$ – Moartem Jul 25 '15 at 9:41
  • \$\begingroup\$ @Moartem Yeah, I didn't spend much time on reducing the complexity \$\endgroup\$ – TheCrypt Jul 25 '15 at 17:46
1
\$\begingroup\$

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)]))
\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Kade Jul 24 '15 at 13:24
1
\$\begingroup\$

Jelly, non-competing

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!

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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.
\$\endgroup\$
0
\$\begingroup\$

J, 14 bytes * 0.8 = 11.2

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

Usage

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.