12
\$\begingroup\$

Given a positive integer n > 1 determine how many numbers can be made by adding integers greater than 1 whose product is n. For example if n = 24 we can express n as a product in the following ways

24 = 24             -> 24            = 24
24 = 12 * 2         -> 12 + 2        = 14
24 = 6 * 2 * 2      -> 6 + 2 + 2     = 10
24 = 6 * 4          -> 6 + 4         = 10
24 = 3 * 2 * 2 * 2  -> 3 + 2 + 2 + 2 = 9
24 = 3 * 4 * 2      -> 3 + 4 + 2     = 9
24 = 3 * 8          -> 3 + 8         = 11

We can get the following numbers this way:

24, 14, 11, 10, 9

That is a total of 5 numbers, so our result is 5.

Task

Write a program or function that takes n as input and returns the number of results that can be obtained this way.

This is a question so answers will be scored in bytes, with fewer bytes being better.

OEIS sequence

OEIS A069016

\$\endgroup\$
9
  • 1
    \$\begingroup\$ Suggested test case 240 \$\endgroup\$ Aug 6 '17 at 18:52
  • \$\begingroup\$ Since 36 has caused a lot of debate, I suggest it as a test case. \$\endgroup\$
    – user41805
    Aug 6 '17 at 19:00
  • 3
    \$\begingroup\$ @WheatWizard 12 * 3 \$\endgroup\$ Aug 6 '17 at 19:05
  • 1
    \$\begingroup\$ I have 2,2,3,3 -> 10, 2,6,3 -> 11, 2,2,9 -> 13, 12,3 -> 15, 2,18 -> 20, 36 -> 36 \$\endgroup\$ Aug 6 '17 at 19:07
  • 2
    \$\begingroup\$ 36 should be 7 because (2*3)+(2*3)=12 should be in the list too. \$\endgroup\$ Aug 6 '17 at 19:15
6
\$\begingroup\$

Brachylog, 8 bytes

{~×≜+}ᶜ¹

Try it online!

Explanation

{    }ᶜ¹  Count unique results of this predicate:
 ~×       Create list of numbers whose product is the input.
   ≜      Label the list, forcing it to take a concrete value.
    +     Take its sum.

I'm not entirely sure why only produces lists with elements above 1, but it seems to do so, which works great in this challenge.

\$\endgroup\$
1
  • \$\begingroup\$ It only produces lists with elements above 1 because otherwise there are infinitely many lists, which is often bad in challenges like these. \$\endgroup\$
    – Fatalize
    Mar 5 '18 at 7:20
4
\$\begingroup\$

Gaia, 9 14 13 bytes

Bug fixed at the cost of 5 bytes thanks to Jonathan Allan, then 1 byte golfed.

ḍfḍ¦e¦Π¦¦Σ¦ul

Try it online! or try as a test suite

Explanation

ḍ              Prime factors
 f             Permutations
  ḍ¦           Get the partitions of each permutation
    e¦         Dump each list of partitions (1-level flatten the list)
      Π¦¦      Product of each partition
         Σ¦    Sum each group of products
           u   Deduplicate
            l  Length
\$\endgroup\$
8
  • \$\begingroup\$ Can you provide a TIO link containing the corresponding outputs the numbers 1 through 36 inclusive? \$\endgroup\$
    – user41805
    Aug 6 '17 at 18:51
  • \$\begingroup\$ This is exactly like the Jelly answer... \$\endgroup\$ Aug 6 '17 at 18:53
  • 1
    \$\begingroup\$ The OP says the output for 36 should be 5, not 6 \$\endgroup\$
    – user41805
    Aug 6 '17 at 18:56
  • 1
    \$\begingroup\$ According to OEIS, 36 gives 7 instead of 5, but yours gives 6 \$\endgroup\$
    – user41805
    Aug 6 '17 at 19:26
  • 1
    \$\begingroup\$ Apparently Gaia leaves out [6 6] \$\endgroup\$
    – user41805
    Aug 6 '17 at 19:27
2
\$\begingroup\$

Jelly,  11 15  14 bytes

+4 bytes fixing up a bug (maybe a better way?)
-1 byte by abusing symmetry

ÆfŒ!ŒṖ€ẎP€S€QL

A monadic link taking and returning positive integers

Try it online! or see a test suite

How?

Updating...

ÆfŒ!ŒṖ€ẎP€S€QL - Link: number, n      e.g. 30
Æf             - prime factors of n        [2,3,5]
  Œ!           - all permutations          [[2,3,5],[2,5,3],[3,2,5],[3,5,2],[5,2,3],[5,3,2]]
    ŒṖ€        - all partitions for €ach   [[[[2],[3],[5]],[[2],[3,5]],[[2,3],[5]],[[2,3,5]]],[[[2],[5],[3]],[[2],[5,3]],[[2,5],[3]],[[2,5,3]]],[[[3],[2],[5]],[[3],[2,5]],[[3,2],[5]],[[3,2,5]]],[[[3],[5],[2]],[[3],[5,2]],[[3,5],[2]],[[3,5,2]]],[[[5],[2],[3]],[[5],[2,3]],[[5,2],[3]],[[5,2,3]]],[[[5],[3],[2]],[[5],[3,2]],[[5,3],[2]],[[5,3,2]]]]
       Ẏ       - tighten                   [[[2],[3],[5]],[[2],[3,5]],[[2,3],[5]],[[2,3,5]],[[2],[5],[3]],[[2],[5,3]],[[2,5],[3]],[[2,5,3]],[[3],[2],[5]],[[3],[2,5]],[[3,2],[5]],[[3,2,5]],[[3],[5],[2]],[[3],[5,2]],[[3,5],[2]],[[3,5,2]],[[5],[2],[3]],[[5],[2,3]],[[5,2],[3]],[[5,2,3]],[[5],[3],[2]],[[5],[3,2]],[[5,3],[2]],[[5,3,2]]]
        P€     - product for €ach          [[30],[6,5],[10,3],[2,3,5],[30],[10,3],[6,5],[2,5,3],[30],[6,5],[15,2],[3,2,5],[30],[15,2],[6,5],[3,5,2],[30],[10,3],[15,2],[5,2,3],[30],[15,2],[10,3],[5,3,2]]
               -   ...this abuses the symmetry saving a byte over P€€
          S€   - sum €ach                  [30,11,13,10,30,13,11,10,30,11,17,10,30,17,11,10,30,13,17,10,30,17,13,10][10,17,11,30,10,17,13,30,10,13,11,30,10,13,17,30,10,11,13,30,10,11,17,30]
            Q  - de-duplicate              [30,11,13,10,17]
             L - length                    5
\$\endgroup\$
0
1
\$\begingroup\$

Python 2, 206 bytes

k=lambda n,i=2:n/i*[k]and[k(n,i+1),[i]+k(n/i)][n%i<1]
def l(t):
 r=[sum(t)]
 for i,a in enumerate(t):
    for j in range(i+1,len(t)):r+=l(t[:i]+[a*t[j]]+t[i+1:j]+t[j+1:])
 return r
u=lambda n:len(set(l(k(n))))

Try it online!

Explanation

    # Finds the prime factors
k=lambda n,i=2:n/i*[k]and[k(n,i+1),[i]+k(n/i)][n%i<1]
    # Function for finding all possible numbers with some repetition
def l(t):
    # Add the current sum
 r=[sum(t)]
    # For each number in the current factors
 for i,a in enumerate(t):
    # For all numbers further back in the current factors, find all possible numbers when we multiply together two of the factors
    for j in range(i+1,len(t)):r+=l(t[:i]+[a*t[j]]+t[i+1:j]+t[j+1:])
 return r
    # Length of set for distinct elements
u=lambda n:len(set(l(k(n))))
\$\endgroup\$
1
  • 1
    \$\begingroup\$ 194 bytes \$\endgroup\$
    – ovs
    Aug 6 '17 at 21:19
1
\$\begingroup\$

Mathematica, 110 bytes

If[#==1,1,Length@Union[Tr/@Select[Array[f~Tuples~{#}&,Length[f=Rest@Divisors[s=#]]]~Flatten~1,Times@@#==s&]]]&
\$\endgroup\$
1
\$\begingroup\$

JavaScript (ES6) 107 bytes

f=(n,o,s=0,i=2,q=n/i)=>(o||(o={},o[n]=t=1),i<n?(q>(q|0)|o[e=s+i+q]||(o[e]=t+=1),f(q,o,s+i),f(n,o,s,i+1)):t)

Ungolfed:

f=(n,                                 //input
   o,                                 //object to hold sums
   s=0,                               //sum accumulator
   i=2,                               //start with 2
   q=n/i                              //quotient
  )=>(
  o||(o={},o[n]=t=1),                 //if first call to function, initialize o[n]
                                      //t holds the number of unique sums
  i<n?(                               //we divide n by all numbers between 2 and n-1
    q>(q|0)|o[e=s+i+q]||(o[e]=t+=1),  //if q is integer and o[s+i+q] is uninitialized,
                                      //... make o[s+i+q] truthy and increment t
    f(q,o,s+i),                       //recurse using q and s+i
    f(n,o,s,i+1)                      //recurse using n with the next i
  ):t                                 //return t
)

Test cases:

f=(n,o,s=0,i=2,q=n/i)=>(o||(o={},o[n]=t=1),i<n?(q>(q|0)|o[e=s+i+q]||(o[e]=t+=1),f(q,o,s+i),f(n,o,s,i+1)):t)

s= [];

for(i = 1; i <= 103 ; i++) {
  s.push(f(i));
}

console.log(s.join`, `)

To verify that the function calculates the correct sums, we can output the keys of the object instead of t:

f=(n,o,s=0,i=2,q=n/i)=>(o||(o={},o[n]=t=1),i<n?(q>(q|0)|o[e=s+i+q]||(o[e]=t+=1),f(q,o,s+i),f(n,o,s,i+1)):Object.keys(o))

console.log(f(24));  //9, 10, 11, 14, 24

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

Python 3, 251 bytes

lambda n:1 if n==1else len(set(sum(z)for z in t(f(n))))
f=lambda n:[]if n==1else[[i]+f(n//i)for i in range(2,n+1)if n%i==0][0]
t=lambda l:[l] if len(l)==1else[[l[0]]+r for r in t(l[1:])]+[r[:i]+[l[0]*e]+r[i+1:]for r in t(l[1:])for i,e in enumerate(r)]

Try it online!

The design is basic:

  1. factorize n into its prime factors (a prime factor may appear several times : 16 -> [2,2,2,2]). That's the function f.

  2. compute the partitions of the list of prime factors, and multiply the factors in each partition. The partitions are found as in https://stackoverflow.com/a/30134039, and the products are computed on the fly. That's the function t.

  3. The final function gets the products of each partition of n and sums them, the get the number of different values.

The result for 2310=2*3*5*7*11 is 49.

EDIT : Maybe needs fix, but I don't have time to look at it now (I'm in a hurry). Hint: is the result correct for 2310=2*3*5*7*11 ? I dont' think so.

EDIT2 : Huge fix. See above. Previous (buggy) version was: Try it online!

f computes the factors (, with a (0, n) instead of (1, n) as first element.

The lambda splits each factor in "sub-factors" and sums the those "sub-factors".

\$\endgroup\$
4
  • 1
    \$\begingroup\$ -19 bytes. \$\endgroup\$
    – notjagan
    Aug 7 '17 at 1:05
  • 1
    \$\begingroup\$ -1 byte from @notjagan improvement \$\endgroup\$ Aug 7 '17 at 6:03
  • \$\begingroup\$ Thanks to @notjagan, but the initial code was so wrong... \$\endgroup\$
    – jferard
    Aug 9 '17 at 15:42
  • \$\begingroup\$ Thanks to @HalvardHummel, but same remark as above. \$\endgroup\$
    – jferard
    Aug 9 '17 at 15:42

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.