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\$ Commented Aug 6, 2017 at 18:52
  • \$\begingroup\$ Since 36 has caused a lot of debate, I suggest it as a test case. \$\endgroup\$ Commented Aug 6, 2017 at 19:00
  • 3
    \$\begingroup\$ @WheatWizard 12 * 3 \$\endgroup\$ Commented Aug 6, 2017 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\$ Commented Aug 6, 2017 at 19:07
  • 2
    \$\begingroup\$ 36 should be 7 because (2*3)+(2*3)=12 should be in the list too. \$\endgroup\$ Commented Aug 6, 2017 at 19:15

7 Answers 7

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\$ Commented Mar 5, 2018 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\$ Commented Aug 6, 2017 at 18:51
  • \$\begingroup\$ This is exactly like the Jelly answer... \$\endgroup\$ Commented Aug 6, 2017 at 18:53
  • 1
    \$\begingroup\$ The OP says the output for 36 should be 5, not 6 \$\endgroup\$ Commented Aug 6, 2017 at 18:56
  • 1
    \$\begingroup\$ According to OEIS, 36 gives 7 instead of 5, but yours gives 6 \$\endgroup\$ Commented Aug 6, 2017 at 19:26
  • 1
    \$\begingroup\$ Apparently Gaia leaves out [6 6] \$\endgroup\$ Commented Aug 6, 2017 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\$ Commented Aug 6, 2017 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\$ Commented Aug 7, 2017 at 1:05
  • 1
    \$\begingroup\$ -1 byte from @notjagan improvement \$\endgroup\$ Commented Aug 7, 2017 at 6:03
  • \$\begingroup\$ Thanks to @notjagan, but the initial code was so wrong... \$\endgroup\$ Commented Aug 9, 2017 at 15:42
  • \$\begingroup\$ Thanks to @HalvardHummel, but same remark as above. \$\endgroup\$ Commented Aug 9, 2017 at 15:42

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.