Cut the gold chain

Question

A traveler needs to stay for n days in a hotel outside town. He is out of cash and his credit card is expired. But he has a gold chain with n links.

The rule in this hotel is that residents should pay their rent every morning. The traveler comes to an agreement with the manager to pay one link of the golden chain for each day. But the manager also demands that the traveler should make the least possible damage to the chain while paying every day. In other words, he has to come up with a solution to cut as few links as possible.

Cutting a link creates three subchains: one containing only the cut link, and one on each side. For example, cutting the third link of a chain of length 8 creates subchains of length [2, 1, 5]. The manager is happy to make change, so the traveller can pay the first day with the chain of length 1, then the second day with the chain of length 2, getting the first chain back.

Your code should input the length n, and output a list of links to cut of minimum length.

Rules:

• n is an integer > 0.
• You can use either 0-based or 1-based indexing for the links.
• For some numbers, the solution is not unique. For example, if n = 15 both [3, 8] and [4, 8] are valid outputs.
• You can either return the list, or print it with any reasonable separator.
• This is code-golf, so the shortest code in bytes wins.

Test cases:

Input          Output (1-indexed)
1              []
3              [1]
7              [3]
15             [3, 8]
149            [6, 17, 38, 79]

Detailed example

For n = 15, cutting the links 3 and 8 results in subchains of length [2, 1, 4, 1, 7]. This is a valid solution because:

 1 = 1
 2 = 2
 3 = 1+2
 4 = 4
 5 = 1+4
 6 = 2+4
 7 = 7
 8 = 1+7
 9 = 2+7
10 = 1+2+7
11 = 4+7
12 = 1+4+7
13 = 2+4+7
14 = 1+2+4+7
15 = 1+1+2+4+7

No solution with only one cut exists, so this is an optimal solution.

Addendum

Note that this problem is related to integer partitioning. We're looking for a partition P of n such that all integers from 1 to n have at least one patition that is a subset of P.

Here's a YouTube video about one possible algorithm for this problem.

Answer 1

05AB1E, 23 11 8 bytes

ΔÍN-;иg=

Try it online!

Uses 0-based indexing.

Explanation:

             # start from the implicit input
Δ            # loop forever
 Í           # subtract 2
  N-         # subtract the current iteration number
    ;        # divide by 2
     и       # create a list of length x
      g      # get the length of the list
       =     # print

иg looks like a noop, but it actually does two useful things: it truncates to an integer (; returns a float), and it crashes the interpreter if x is negative (this is the only exit condition).

---

The 23 byte solution used a very different approach, so here it is for posterity: ÅœʒR2äθP}ʒæOê¥P}θ2äθη€O (TIO, explanation).

Answer 2

Python 2, 75 bytes

f=lambda n,i=0:n>=i<<i and f(n,i+1)or[min(n,2**j*i-i+j)for j in range(1,i)]

Try it online!

---

Explanation:

Builds a sequence of 'binary' chunks, with a base number matching the number of cuts.

Eg:

63 can be done in 3 cuts, which means a partition in base-4 (as we have 3 single rings):

Cuts: 5, 14, 31, which gives chains of 4 1 8 1 16 1 32 (sorted: 1 1 1 4 8 16 32).

All numbers can be made:

1       1
2       1 1
3       1 1 1
4       4
...
42      1 1 8 32
...
62      1 1 4 8 16 32
63      1 1 1 4 8 16 32

Other examples:

18: 4,11        ->  3 1 6 1 7
27: 5,14,27     ->  4 1 8 1 13 1
36: 5,14,31     ->  4 1 8 1 16 1 5
86: 6,17,38,79  ->  5 1 10 1 20 1 40 1 7

Answer 3

R, 77 69 bytes

-8 bytes thanks to Aaron Hayman

pmin(n<-scan(),0:(k=sum((a=2:n)*2^a<=n))+cumsum((k+2)*2^(0:k))+1)[-n]

Try it online!

Let \$k\$ be the number of cuts needed; \$k\$ is the smallest integer such that \$(k+1)\cdot2^k\geq n\$. Indeed, a possible solution is then to have subchains of lengths \$1,1,\ldots,1\$ (\$k\$ times) and \$(k+1), 2(k+1), 4(k+1), 8(k+1), \ldots, (k+1)\cdot 2^{k-1}\$. It is easy to check that this is sufficient and optimal.

(The last subchain might need to be made shorter if we exceed the total length of the chain.)

Ungolfed (based on previous, similar version):

n = scan()                            # read input
if(n - 1){                            # If n==1, return NULL
  k = match(F, (a = 2:n) * 2 ^ a > n) # compute k
  b = (k + 1) * 2 ^ (1:k - 1)         # lengths of subchains
  c = 1:k + cumsum(b)                 # positions of cuts
  pmin(c, n )                         # if last value is >n, coerce it to n
}

(Proof that the value of \$k\$ is as I state: suppose we have \$k\$ cuts. We then have \$k\$ unit subchains, so we need the first subchain to be of length \$k+1\$. We can now handle all lengths up to \$2k+1\$, so we need the next one to be of length \$2k+2\$, then \$4k+4\$... Thus the maximum we can get out of \$k\$ cuts is obtained by summing all those lengths, which gives \$(k+1)\cdot 2^k-1\$.)

If \$a(k)\$ is the smallest integer \$n\$ requiring \$k\$ cuts, then \$a(k)\$ is OEIS A134401.

Answer 4

Jelly, 12 bytes

’_‘ɼ:2»-µƬṖḊ

Try it online!

Translation of Grimy's 05AB1E answer so be sure to upvote that one too! Slightly disappointed this comes in a byte longer, but does at least have something a bit like an emoticon as the first three bytes!

Answer 5

JavaScript (ES6), 66 bytes

This is a port of TFeld's answer.

n=>(g=a=>n<++i<<i?a.map(j=>(j+=(i<<j)-i)>n?n:j):g([...a,i]))(i=[])

Try it online!

Answer 6

C++, 109,107 bytes

-2 bytes thanks to Kevin

#include<iostream>
main(){int n,k=0;for(std::cin>>n;++k<<k<n;);for(n-=k;n>0;k*=2,n-=k+1)std::cout<<n<<',';}

The algorithm is similar to the Robin Ryder's answer. The code is written in a compilable, whole form. Try it!

Details:

std::cin>>n;               // get the value of n as input
while(++k<<k<n);           // determine k
for(n-=k;n>0;k*=2,n-=k+1)  // we don't need n, so the lengths...
    std::cout<<n<<' ';     // of links are subtracted repeatedly

This has a C variation with the same byte length (doesn't seem to need a separate answer):

#include<stdio.h>
main(){int n,k=0;for(scanf("%d",&n);++k<<k<n;);for(n-=k;n>0;k*=2,n-=k+1)printf("%d,",n);}

Answer 7

Retina 0.8.2, 61 bytes

.+
11,$&$*
+`\b(1+),(\1(1*)1?\3)$
1$2¶1$1,$3
1+,
1
1A`
1+
$.&

Try it online! 1-indexed port of @Grimy's answer. Explanation:

.+
11,$&$*

Start with N=2 and the input converted to unary.

+`\b(1+),(\1(1*)1?\3)$

Repeatedly try to subtract N from the input and then divide by 2.

1$2¶1$1,$3

If successful, remember 1 more than the input on the previous line, increment N on the current line, and update the input to the new value.

1+,
1

Remove N and increment the last value so that it's also 1-indexed.

1A`

Remove the incremented original input.

1+
$.&

Convert the results to decimal.

Answer 8

Ruby, 62 bytes

->n{(1...c=(0..n).find{|r|n<r<<r}).map{|b|[n,b-c+(c<<b)].min}}

Try it online!

Mostly stolen from TFeld's Python answer.