21
\$\begingroup\$

Story

So I have a book that I want to separate from my table with nothing but other books. I want to know how many books do I need to achieve this with \$n\$ book lengths.

Here's a visualization that my friend at Wolfram drew for me:

a visualization from Wolfram

More information about the topic in Wolfram and Wikipedia.

Challenge

Given an integer input \$n\$, output how many books needed for the top book to be \$n\$ book length away from the table horizontally.
or
Find the smallest integer value of \$m\$ for input \$n\$ in the following inequality. $$\sum_{i=1}^{m}\frac{1}{2i} \geq n$$

Edit: for fractions use at least a IEEE single-precision floating point. sorry for editing challenge after posting

(OEIS A014537)

Test cases

 1          4
 2         31
 3        227
 5      12367
10  272400600
\$\endgroup\$
  • 1
    \$\begingroup\$ youtube.com/watch?v=pBYPXsGka74 <-- related \$\endgroup\$ – streetster Jan 27 '18 at 16:24
  • \$\begingroup\$ Does it have to be using this particular arrangement of books, which IIRC is not optimal? \$\endgroup\$ – user253751 Feb 5 '18 at 3:46

20 Answers 20

13
\$\begingroup\$

Octave, 41 40 33 bytes

1 byte saved thanks to @Dennis

@(n)find(cumsum(.5./(1:9^n))>n,1)

Try it online!

Explanation

This uses the fact that harmonic numbers can be lower-bounded by a logarithmic function.

Also, the >= comparison can be replaced by > because harmonic numbers cannot be even integers (thanks, @Dennis!).

@(n)                                   % Anonymous function of n
                     1:9^n             % Range [1 2 ... 9^n]
                .5./(     )            % Divide .5 by each entry
         cumsum(           )           % Cumulative sum
                            >n         % Is each entry greater than n?
    find(                     ,1)      % Index of first true entry
\$\endgroup\$
11
\$\begingroup\$

Python 3, 35 bytes

f=lambda n,k=2:n>0and-~f(n-1/k,k+2)

Try it online!

\$\endgroup\$
10
\$\begingroup\$

Husk, 8 bytes

V≥⁰∫m\İ0

Try it online!

Since Husk uses rational numbers when it can, this has no floating point issues

Explanation

      İ0    The infinite list of positive even numbers
    m\      Reciprocate each
   ∫        Get the cumulative sum
V           Find the index of the first element
 ≥⁰         that is greater than or equal to the input
\$\endgroup\$
  • \$\begingroup\$ 8 bytes, but in which charset? \$\endgroup\$ – john16384 Jan 27 '18 at 23:03
  • 3
    \$\begingroup\$ @john16384 Husk has it's own codepage where each symbol corresponds to a single byte. Here is the corresponding hexdump \$\endgroup\$ – H.PWiz Jan 27 '18 at 23:15
5
\$\begingroup\$

JavaScript, 30 bytes

A recursive function so it'll crap out pretty early.

f=(n,x=0)=>n>0?f(n-.5/++x,x):x

Try it online

\$\endgroup\$
4
\$\begingroup\$

Haskell, 38 bytes

k!n|n<=0=0|x<-n-1/(2*k)=1+(k+1)!x
(1!)
\$\endgroup\$
3
\$\begingroup\$

Swift, 65 bytes

func f(n:Double){var i=0.0,s=i;while s<n{i+=1;s+=0.5/i};print(i)}

Try it online!

Ungolfed

func f(n:Double) {
  var i = 0.0, s = 0.0
  while s < n {
    i += 1;
    s += 0.5 / i
  }
  print(i)
}
\$\endgroup\$
3
\$\begingroup\$

R, 39 bytes

function(n){while((F=F+.5/T)<n)T=T+1;T}

Try it online!

Brute Force!

\$\endgroup\$
3
\$\begingroup\$

Javascript (ES6), 34 bytes

n=>eval("for(i=0;n>0;n-=.5/i)++i")

Ungolfed

n => {
    for(i = 0; n > 0; ++i)
        n -= .5 / i
    return i;
}

Test Cases

f=n=>eval("for(i=0;n>0;n-=.5/i)++i")
<button onclick="console.log(f(1))">Run for n = 1</button>
<button onclick="console.log(f(2))">Run for n = 2</button>
<button onclick="console.log(f(3))">Run for n = 3</button>
<button onclick="console.log(f(5))">Run for n = 5</button>
<button onclick="console.log(f(10))">Run for n = 10</button>

\$\endgroup\$
  • \$\begingroup\$ Came up with a similar solution using recursion for 30 bytes. Dunno whether to post it or not, after seeing yours. \$\endgroup\$ – Shaggy Jan 27 '18 at 14:14
  • 1
    \$\begingroup\$ I may be missing something, but why do you need to wrap it in an eval statement? \$\endgroup\$ – caird coinheringaahing Jan 27 '18 at 22:03
  • 1
    \$\begingroup\$ @cairdcoinherigaahing, without the eval the i variable would need to be returned at the end, at the cost of a few more bytes. \$\endgroup\$ – Shaggy Jan 27 '18 at 22:12
2
\$\begingroup\$

Jelly, 8 bytes

RİSH:ð1#

This is very slow.

Try it online!

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

Haskell, 71 49 48 bytes

f x=length.fst.span(<x).scanl(+)0$(0.5/)<$>[1..]

@BMO saved me a whopping 22 bytes!

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

Julia 0.6, 30 27 bytes

<(n,i=1)=n>0?n-.5/i<i+1:i-1

Try it online!

Only works up to n = 6, because Julia has no tail call optimization.

-3 bytes thanks to Dennis.

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

TI-BASIC, 27 bytes

Prompts user for input and displays output on termination. Note: ⁻¹ is the -1 (inverse) token.

Input N
1
Repeat 2N≤Σ(I⁻¹,I,1,Ans
Ans+1
End
Ans
\$\endgroup\$
  • 2
    \$\begingroup\$ If you're going to save Ans in N immediately, then Input N or Prompt N is an input method that saves you one byte over Ans→N. And M can be replaced by Ans, so that 1→M becomes 1 and M+1→M becomes Ans+1. (But I am skeptical about an output in Ans that does not get displayed - see this - so maybe ending with :Ans is appropriate: then the value will be shown in place of "Done".) \$\endgroup\$ – Misha Lavrov Jan 31 '18 at 4:32
  • \$\begingroup\$ Thank you! I knew Ans→N felt funny. Nice optimizations. Also took your advice on output just to be safe. Still comes out with a net -3 bytes :D \$\endgroup\$ – kamoroso94 Jan 31 '18 at 5:22
1
\$\begingroup\$

05AB1E, 11 bytes

XµN·zODI›}N

Try it online!

Explanation

Xµ       }    # loop until counter is 1
  N·z         # push 1/(2*N)
     O        # sum the stack
      DI›     # break if the sum is greater than the input
          N   # push N
\$\endgroup\$
1
\$\begingroup\$

Pyth, 10 bytes

f!>Qsmc1yh

Try it online!

Extremely slow.

Pyth, 10 bytes

fgscL1STyQ

Try it online!

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

Japt, 12 bytes

The same length as, but slightly more efficient than, the recursive option.

@T¨(Uµ½÷X}a1

Try it


Explanation

@T¨(Uµ½÷X}a1
                 :Implicit input of integer U
@        }a1     :Return the first number X >=1 that returns truthy when passed through the following function
 T               :Zero
  ¨              :Greater than or equal to
    Uµ           :Decrement U by...
      ½÷X        :0.5 divided by X
\$\endgroup\$
1
\$\begingroup\$

J, 22 bytes

-6 bytes thanks to frownyfrog

I.~0+/\@,1%2*1+[:i.9&^

Try it online!

original answer

Luis's answer in J:

1+]i.~[:<.[:+/\1%2*1+[:i.9&^

Ungolfed

1 + ] i.~ [: <. [: +/\ 1 % 2 * 1 + [: i. 9&^

Mostly curious to see if it can be drastically improved (cough paging miles)

Explanation

1 +      NB. 1 plus... 
] i.~    NB. find the index of the arg in...
[: <.    NB. the floor of...
[: +/\   NB. the sumscan of...
1 %      NB. the reciprical of...
2 *      NB. two times...
1 +      NB. 1 plus...
[: i.    NB.  the integers up to 
9&^      NB. 9 raised to the power of the arg

Try it online!

\$\endgroup\$
  • \$\begingroup\$ 1+]i.~[:<. -> 1+]I.~ -> I.~0, \$\endgroup\$ – FrownyFrog Jan 29 '18 at 5:06
  • \$\begingroup\$ ofc! thank you frownyfrog \$\endgroup\$ – Jonah Jan 29 '18 at 5:15
  • \$\begingroup\$ And then I.~0+/\@, \$\endgroup\$ – FrownyFrog Jan 29 '18 at 7:43
  • \$\begingroup\$ If you edit, you’ll beat Julia :) \$\endgroup\$ – FrownyFrog Jan 31 '18 at 20:29
  • \$\begingroup\$ @FrownyFrog, done. if you have some time, i would love to see you solve this one: codegolf.stackexchange.com/questions/154345/bracket-expansion. all the solutions i can think of are too verbose to post in good conscience... \$\endgroup\$ – Jonah Jan 31 '18 at 22:09
0
\$\begingroup\$

PHP, 35 bytes

while($argv[1]>$s+=.5/++$i);echo$i;

Run it using the CLI:

$ php -d error_reporting=0 -r 'while($argv[1]>$s+=.5/++$i);echo$i;' 5
\$\endgroup\$
0
\$\begingroup\$

Wolfram Language (Mathematica), 40 bytes

⌈x/.NSolve[HarmonicNumber@x==2#,x]⌉&

Try it online!

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

Java 8, 49 bytes

n->{float r=0,s=0;for(;s<n;)s+=.5f/++r;return r;}

Explanation:

Try it online. (Times out for test cases above n=7.)

n->{             // Method with integer parameter and float return-type
  float r=0,     //  Result-float, starting at 0
        s=0;     //  Sum-float, starting at 0
  for(;s<n;)     //  Loop as long as the sum is smaller than the input
    s+=.5f/++r;  //   Increase the sum by `0.5/(r+1)`,
                 //   by first increasing `r` by 1 with `r++`
  return r;}     //  Return the result-float
\$\endgroup\$
0
\$\begingroup\$

tinylisp, 98 bytes

(load library
(d _(q((k # N D)(i(l N(* D # 2))(_(inc k)#(+(* N k)D)(* D k))(dec k
(q((#)(_ 1 # 0 1

The last line is an unnamed lambda function that takes the number of book-lengths and returns the number of books needed. Try it online!

Explanation

The only numeric data type tinylisp has is integers, so we calculate the harmonic series as a fraction by keeping track of the numerator and denominator. At each step, N is the numerator, D is the denominator, and k is the sum index. We want the new partial sum to be N/D + 1/k, or (N*k + D)/(D*k). Thus, we recurse with a new numerator of N*K + D, a new denominator of D*k, and a new index of k+1.

The recursion should halt once the partial sum is greater than or equal to #, the desired number of book-lengths. At this point, we've gone one book too far, so we return k-1. The condition is 1/2 * N/D < #; multiplying out the denominator, we get N < D*#*2, which is the golfiest way to write it.

The recursive helper function _ does all these calculations; the main function is merely a one-argument wrapper that calls _ with the correct starting values for k, N, and D.

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