21
\$\begingroup\$

Given a number n > 77, write a program or function that finds a set of distinct positive integers such that the sum of the set equals n, and the sum of the reciprocals of the set equals 1.

Example for 80:

80 = 2 + 4 + 10 + 15 + 21 + 28    ⟶     1/2 + 1/4 + 1/10 + 1/15 + 1/21 + 1/28 = 1

Your program or function must (theoretically) work for any n < 232, and is not excused for floating point rounding errors. Note that solutions exist for all n > 77.


Shortest code in bytes wins.

There is a bonus incentive: I will award a bounty to the smallest solution that works for any n and runs log(n). For small n it must be fast (determined at my discretion). Yes, this is possible.

\$\endgroup\$
12
  • 3
    \$\begingroup\$ Is such decomposition always guaranteed to exist? Any number-theoretic theorem that assures that? \$\endgroup\$
    – Luis Mendo
    Jan 10 '16 at 16:47
  • \$\begingroup\$ It seems that there is for all n>77. (I did not check every detail.) That should have been in the description of your challenge... \$\endgroup\$
    – flawr
    Jan 10 '16 at 19:11
  • 1
    \$\begingroup\$ @flawr, I presume that he didn't include that reference because it gives away the O(log n) algorithm. \$\endgroup\$ Jan 10 '16 at 19:13
  • 1
    \$\begingroup\$ Still he should have mentioned that this set exists for the given n. (And I found that paper on the first page when googling the title.) \$\endgroup\$
    – flawr
    Jan 10 '16 at 19:15
  • 1
    \$\begingroup\$ @flawr, it took me about 10 minutes to find it. I got to it via a page on Egyptian fractions, and you ninja'd me by 10 seconds. \$\endgroup\$ Jan 10 '16 at 19:32
3
\$\begingroup\$

Mathematica, 54 bytes

Select[IntegerPartitions@#,Unequal@@#&&Tr[1/#]==1&,1]&

About as inefficient as it gets, but it does solve n = 78 in about 9 seconds.

The result is returned as a list wrapped in a singleton list, e.g.:

{{45, 12, 9, 5, 4, 3}}
\$\endgroup\$
4
  • \$\begingroup\$ I wonder if it works for very large n. \$\endgroup\$ Jan 10 '16 at 13:54
  • \$\begingroup\$ @njpipeorgan Given enough memory and time, yes. \$\endgroup\$ Jan 10 '16 at 14:03
  • \$\begingroup\$ I found an estimation of the length of IntegerPartition[n], which is at the order of exp(sqrt(n)), ~10^10^4.5 for n=2^30. I really don't believe that mathematica (or even any architecture) is able to hold the array. \$\endgroup\$ Jan 10 '16 at 14:20
  • \$\begingroup\$ @njpipeorgan The challenge explicitly states that the algorithm must work up to 2^32 theoretically, not practically (as is usually assumed for code golf, unless the challenge explicitly requires that the program actually finishes for all inputs in a reasonable amount of time and memory). \$\endgroup\$ Jan 10 '16 at 14:35
5
+50
\$\begingroup\$

Python 3, 7306 1995 Bytes

This solution runs in log(n) complexity (as far as I can tell).

def i(s,t):
 for n in s[::-1]:t=t.replace(*n)
 return [[]]*78+[list(bytearray.fromhex(a))for a in t.split(",")]
def f(n):
 g,h=lambda c,n:c+[[[2],[3,7,78,91]][n[len(c)]%2]+[i*2for i in c[-1]]],lambda n:[]if n<78 else h((n-[2,179][n%2])//2)+[n]
 v=h(n);c=[i([['g',',03040'],['h',',,0306080'],['i',',020'],['j','b0c1'],['k','21'],['l','60'],['m','30'],['n','141'],['o','k24'],['p',',g'],['q','618'],['r','0c0'],['s','1e'],['t',',0ml'],['u','283c'],['v','e0f1'],['w','2a38'],['x','80'],['y','a0'],['z','01'],['A','50'],['B','24'],['C','i40'],['D','plb1'],['E','gl'],['F','48'],['G','bre1'],['H','28'],['I','6k'],['J','416s'],['K',',040Al'],['L','90'],['M','2a'],['N','54'],['O','k6o'],['P','3c'],['Q','il'],['R','18'],['S','px'],['T','im'],['U','70'],['V','b1'],['W','23'],['X','pj'],['Y','hj'],['Z','0n']],'020lxycHTaRHCyf1517CyfneC91k51cCLdneQU912MCyf0dBiALyf2dClfPEyfneT9s2dELdneEjIgmLydHg5rd14BKLardsE3n8sQ9rd1517Q9rdneplmdRBgUmcRMC5sPEyf102bgA6sPE91z2miAj41IQmc0dRBQUen7spl31z82bT9RFT3wE7neMgmyf0dRBgUmaHMELc1b36EUdBMQLyfs2d,C710M2bgLardRHT3BFQ9rf0dPQ7rdBMQm9Rs2d,0mAl9100d142bE710M2bQmc0fRPtxarfn8sEc1k4sBTfnePExcwtxarf1k8BExcuT3kkT91663C51964,0mAl71k4BMELe12NTcRwQjOT820ltmarf1z8mExeRNCqBFtmyjIHKLa100ds2bQU91bM36garf1k4sBTcRBFgxarfwE91keB2dtUxcn8sME9nbs36gm9rduC5R78,0mAUyf0d14BME91kbB36QLc12AB2dgyjqkHEUeMNT9157eQU9RMFT8s78C8neuixLc1zk4AtUxc1z8Mmt8re0fn8sWhLyc1bH36pl8neu,Kxycsw,iAxc1420l,K8ren8NS9n81bs36hc0vz8WmYzqkmhyv2WBHhyVOHXkJoSjIwSjIuSvz4WASVZIAXZ6skmSj6oFXzOmplvcsW46D61csk46plv8WBFDqoF,tarvk8WBH,tyjkqoHhGqkN,tmvZ8sWmhVZqskmpc0vZ8WAXZqkAplbnImASbn6skwSbn6skuSVOwSVOupGONSbn6soFpyVkJk5aSj6sk78YJkuDkIP5aYOuhvzk4WBAhVzk416oA,tyjkJ265a,,0mxyjk41q53sYzIHmPXkqowXkqouhyVqoHFYz6omFhb0e1zqkmNSyVIP78YJ20klpyVOHwYk620olpc0vz8WBmFXzqomFpG61ckH38PhyjIP78Yz620kmlDkImLDzINUhGIuNDzIA78hb0e1ZIANYkqk366chG6oFNXkJkP5ahVZ6somFSb0e1620kNlhVk41qomADzIFLXkqso78pGqoFNXzkImP5a,tyjk620oHlhG620kNlXzqskm78,tjZqskHmPYqouFD6sku78YzqkNU,tjZqsomF')[v[0]]]
 for o in range(len(v)-1):c=g(c,v)
 return c[-1]

You can test that f(2**32 - 1) runs almost instantly

I used this paper on a method for computing it. With this method there is a massive chunk of data for the pre-determined values for n from 78 to 334 without the even numbers after 168. I wanted to turn this data into something small and I didn't know any good compression algorithms so I made my own.

The way I compressed it was by having a list of string replace rules. I created a method which found the string replace rule which would cut down the most content over all taking into account defining the rule. I then recursively applied this until I could create no more rules (I used characters g-z and A-Z). The string I made to replace with was a comma separated list of the hex values for each of the numbers. In retrospect, converting them to their hex values may not have been the wisest choice, it would probably be shorter to leave them in decimal, since having hex would only save for the 3 digit numbers but would add a 0 for single digit numbers.

The line where I set c you can see the list of replace rules and the text which it runs it on. The rules need to be applied in reverse as well because some rules include characters created from other rules.

There are also numerous places in this code where I could probably cut down on syntax, such as turning the list of lists into a single list and then using a different method to access the rules to replace the text with

\$\endgroup\$
2
  • 1
    \$\begingroup\$ n=218 outputs [2] is that expected?? \$\endgroup\$ Jun 23 '17 at 7:16
  • 1
    \$\begingroup\$ No, I'll see why that's happening a bit later. My apologies. Might be an error in the data I compressed initially. \$\endgroup\$ Jun 23 '17 at 7:20
1
\$\begingroup\$

Haskell, 93 bytes

import Data.List
import Data.Ratio
p n=[x|x<-subsequences[2..n],sum x==n,1==sum(map(1%)x)]!!0

Horribly slow1 but it runs in constant memory. Trivial solution: check all subsequences of [2..n] for sum and sum of reciprocals.

Returning all solutions instead of one is 3 bytes shorter: just remove the !!0 (beware: the running time will always be off the charts).


1 The running time depends on how early the result appears in the list of subsequences. Haskell's laziness stops the search if the first match is found. When compiled, p 89 (result: [3,4,6,9,18,21,28]) runs on my (4 year old) laptop in 35s. Other values, even smaller ones, can take hours.

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

Julia, 77 bytes

n->collect(filter(i->i==∪(i)&&sum(j->Rational(1,j),i)==1,partitions(n)))[1]

This is an inefficient lambda function that accepts an integer and returns an integer array. To call it, assign it to a variable.

We get the partitions of the integer using partitions. We then filter the set of partitions to only those with unique elements whose reciprocals sum to 1. To ensure no roundoff error occurs, we use Julia's Rational type to construct the reciprocals. filter returns an iterator, so we have to collect it into an array. This gives us an array of arrays (with only a single element), so we can get the first using [1].

Now, when I say inefficient, I mean it. Running this for n = 80 takes 39.113 seconds on my computer and allocates 13.759 GB of memory.

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

Jelly, 19 bytes

œcL’$P€S=P
ŒṗQƑƇÇƇḢ

Try it online!

Very inefficient. This times out for all valid inputs, but takes less than a minute for all \$n < 62\$

If we were able to ignore failures due to floating point issues, then this could be reduced to 12 bytes:

ŒṗQƑƇİS=1ƲƇḢ

Try it online!

Instead, to avoid division, we use the fact that a set of numbers \$a_1, a_2, ..., a_n\$ such that \$\sum^n_{i=1}a_i = n\$ for an input \$n\$ has their reciprocals sum equal to \$1\$ iff:

$$ (a_2\cdots a_n)+(a_1\cdot a_3\cdots a_n)+\cdots = \prod^n_{i=1}a_i \tag{1} $$

i.e. the sum of the products of each sublist of length \$n-1\$ equals the product of the set.

How they work

œcL’$P€S=P - Helper link. Takes a list l on the left
    $      - Group the previous two links together:
  L        -   Take the length of l
   ’       -   Decrement
œc         - Combinations of length n
             This returns all versions of l with a single element removed
     P€    - Take the product of each
       S   - Take the sum
         P - Product of l
        =  - Are the two equal?
             This checks whether or not (1) is true for a given partition

ŒṗQƑƇÇƇḢ - Main link. Takes n on the left
Œṗ       - Yield all partitions of n
  QƑƇ    - Remove those which contain duplicated elements
     ÇƇ  - Keep those for which the helper link is true
       Ḣ - Return the first such list

The second one uses the basic

$$\sum^n_{i=1}\frac1a_i = 1$$

formula, which utterly fails for pretty much every input due to floating point issues. I think that, if it were up to date with Jelly, this code would work in M, due to it's symbolic math functions. Unfortunately, however, M hasn't been updated in ~5 years, so it doesn't appear to have to have the integer partitions builtin.

ŒṗQƑƇİS=1ƲƇḢ - Main link. Takes n on the left
Œṗ           - All partitions of n
  QƑƇ        - Remove those which contain duplicated elements
         ƲƇ  - Keep those for which the following is true:
     İ       -   Yield 1/a for each element
      S      -   Take the sum
       =1    -   Is equal to 1?
           Ḣ - Return the first list found
\$\endgroup\$
0
\$\begingroup\$

Husk, 14 bytes

ḟ§&o=1ṁ\o=¹ΣṖḣ

Try it online!

Husk's usage of fractions is really beneficial for this challenge.

Just like all the answers except Cameron's, is very slow for larger test cases.

\$\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.