How far should I sum?

Question

How far should I sum?

The harmonic series is the "infinite sum" of all the fractions of the form \$\frac1n\$ for \$n\$ positive integer. I.e. the harmonic series is

$$\frac11 + \frac12 + \frac13 + \frac14 + \cdots$$

It is well-known that this sum diverges, which means that if you define

$$ H_n = \frac11 + \frac12 + \cdots + \frac1n$$

Then the value of \$H_n\$ goes to infinity. This can also be stated in a different way: for any positive value \$x\$ you pick, there is some value \$N\$ such that, to the right of \$N\$, the \$H\$ values are bigger than \$x\$:

$$\forall\ x\ \exists\ N: n > N \implies H_n > x $$

Your task

Write a program/function that takes as input a positive number x (not necessarily an integer) and outputs the first integer n for which

$$H_n \geq x$$

In theory your program must work for arbitrary x, even if in practice you are limited by the memory and/or precision of your programming language/computer.

Test cases

1.5 -> 2
2 -> 4
3 -> 11
3.1415 -> 13
4 -> 31
5 -> 83
7.5 -> 1015
10 -> 12367

This is code-golf so shortest solution wins! Standard loopholes are forbidden by default. Happy golfing.

Answer 1

APL (Dyalog), 13 bytes

-1 bytes thanks to ngn

{⊃⍸⍵≤+\÷⍳⌈*⍵}

Try it online!

A dfn solution that takes a right argument.

Explanation:

{           }   ⍝ dfn
 ⊃              ⍝ Take the first of
  ⍸             ⍝ The indexes of the truthy values of
   ⍵≤           ⍝ The right argument is smaller than or equal to
     \+         ⍝ The cumulative sum
       ÷        ⍝ The reciprocal of each of
        ⍳       ⍝ The range 1 to
         ⌈      ⍝ The ceiling of
          *⍵    ⍝ e to the power of the right argument

Answer 2

Python 3, 35 bytes

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

Try it online!

Answer 3

JavaScript (ES6),  32  29 bytes

Saved 3 bytes thanks to @Shaggy

f=(n,k=0)=>n>0?f(n-1/++k,k):k

Try it online!

---

Non-recursive version, 35 bytes

n=>eval("for(k=0;(n-=1/++k)>0;);k")

Try it online!

---

Approximation (25 bytes, not fully working)

This gives the correct result for all but the first test case.

n=>Math.exp(n-.5772)+.5|0

Try it online!

Answer 4

Perl 6, 27 bytes

{+([\+](1 X/1..*)...*>=$_)}

Try it online!

Explanation:

{                         } # Anonymous code block taking one argument
 +(                      )  # Return the length of
   [\+](        )             # The cumulative sum
        1 X/                    # Of the reciprocal of all of
            1..*                  # 1 to infinity
                 ...          # Take from this until
                    *>=$_     # It is larger than or equal to the input

Answer 5

05AB1E, 8 bytes

∞.ΔLzOI@

Try it online!

∞.Δ        # first integer y such that:
   L       #  range [1..y]
    z      #  invert each [1, 1/2, .., 1/y]
     O     #  sum
      I@   #  >= input

Answer 6

Octave / MATLAB, 31 bytes

Thanks to @Giuseppe (based on @John's answer) for making a correction and saving 1 byte at the same time.

@(n)sum(cumsum(1./(1:3^n))<n)+1

Try it online!

Explanation

The code uses the fact that 1+1/2+···+1/m is lower-bounded by log(m). Therefore, given n the solution to the challenge is less than exp(n), or less than 3^n (to save bytes).

So the code computes the cumulative sum of the vector [1, 1/2, 1/3, ..., 1/(3^n)], and the solution is 1 plus the number of entries that are less than n.

Answer 7

R, 39 33 bytes

x=scan();sum(cumsum(1/1:x^x)<x)+1

Try it online!

For a more limited x:

29 bytes

sum(cumsum(1/1:9^8)<scan())+1

Try it online!

Answer 8

C (gcc), 45 bytes

Some inspiration taken from @Noodle9; go upvote their answer!

i;g(x,s)float x,s;{for(s=i=0;s<x;s+=1./++i);}

• i;g(x,s)float x,s;: Old-style function definition. Abuses the fact that old-style function definition don't require all the arguments to be passed (so old-style variadic functions would work) to declare an extra local variable. Having the i as a global variable causes the exploit below to work.

• for(s=i=0;s<x;s+=1./++i);: same old stuff as before, harmonic function, yada yada. Note that s=i=0 is allowed; the i=0 is an integer that is converted to a float and assigned to s.

• The i variable is stored in the %eax (return) register, so nothing is required to initialize it. (thanks @Cody Gray!)

Try it online!

C (gcc), 72 bytes

Recursive solution.

i;float h(n){return n?h(n-1)+1./n:0;}g(float x){for(i=0;h(i++)<x;);--i;}

Explanation:

• i;: counter for finding the first integer n where h(n) >= x.

• float h(n): recursive function taking an int parameter and returning the term of the Harmonic series for n.

• return n?h(n-1)+1./n:0; - recursive function calculating the Harmonic series and stopping at 0.

• g(float x): function finding the first i where h(i) >= x.

• for(i=0;: start loop and initialize i to 0 (functions must be reusable).

• h(i++)<x: loop while h(i) < x.

• --i; returns i-1 by exploiting GCC's behavior when compiling without optimization; intermediate results are all stored in the eax/rax register.

Try it online!

C (gcc), 83 bytes

Non-recursive solution.

i;float h(n){float r=0;for(;n;)r+=1./n--;r=r++;}g(float x){for(i=0;h(i++)<x;);--i;}

Explaining the part that's different from the previous solution:

• float r=0;: this is our result. Initialize it to 0.

• for(;n;): Loop until n is 0.

• r+=1./n--;: Add the next iteration of the Harmonic series. Also decrement n so we don't have to do that in the last part of the for loop.

• r=r++; is like return n; but shorter. It's similar to the fake return in the previous solution but does it with the floating-point return register instead of the integer return register. We have to have the ++ just so GCC doesn't optimize it out as redundant (and yes, some optimizations are enabled without a flag).

Try it online!

Answer 9

C (gcc), ^{52 51} 49 bytes

Saved a bytes thanks to @ceilingcat!!!
Saved 2 bytes thanks to @S.S.Anne!!!

i;f(n,s)float n,s;{for(s=i=0;s<n;s+=1./++i);n=i;}

Try it online!

Answer 10

Python 3, ⁴⁹ 40 bytes

Saved 9 bytes thanks to @JoKing!!!

lambda n,s=0,i=1:s<n and-~f(n,s+1/i,i+1)

Try it online!

Answer 11

Ruby, 31 30 bytes

->x{b=0;x-=1r/b+=1while x>0;b}

Try it online!

Answer 12

Jelly, 9 bytes

1İ€S<¬ʋ1#

A monadic Link accepting a number which yields a list containing one integer; as a full program it prints that integer.

Try it online!

How?

1İ€S<¬ʋ1# - Link: number, x
1         - set left to one
       1# - count up (from n=left) finding the first (1) n such that:
      ʋ   -   last four links as a dyad - f(n, x)
 ݀       -     inverse each (of [1..n])
   S      -     sum
    <     -     less than (x)?
     ¬    -     logical NOT

---

‘!İ€Ä<⁸S‘

Is another 9 but it's much less efficient as \$x\$ gets bigger since it builds a list of the first \$(x+1)!\$ harmonic numbers.

Answer 13

K (Kona), 21 20 bytes

{1+*&~x>+\1.%1+!3^x}

Try it online!

Inspired by Jo King's APL solution

Switched from oK to Kona, as it has power

Answer 14

Haskell, 34 bytes

(#1)
x#n|x>0=(x-1/n)#(n+1)|1>0=n-1

Try it online!

Answer 15

Java 8, 71 43 bytes

x->{int n=0;for(;(x-=1d/++n)>0;);return n;}

-28 bytes by porting @Arnauld's non-recursive JavaScript answer.

Try it online.

Explanation:

x->{                // Method with double as both parameter and integer as return-type
  int n=0;          //  Result-integer `n`, starting at 0
  for(;(x-=1d/++n)  //  Decrease `x` by 1/(n+1), by first increasing `n` by 1 with `++n`
       >0;);        //  And continue doing this until `x` is 0
  return n;}        //  Then return `n` as result

Answer 16

Pyth, 11 10 9 bytes

fgZ=-Qc1T

Try it online!

Explaination:

            # Implicit Q=eval(input())
f           # The first element T of [1,2,3,...] where
 gZ         # 0 >=
   =-Qc1T   # Q = Q - (1/T)
            # Implicit print

-1 -2 bytes thanks to @issacg

Answer 17

GolfScript, 21 20 [bytes]

New Solution TIO
Old Solution TIO

The new solution takes our input and recursively subtracts the inverses from it until we get the solution. Very messy stack management, could probably be done cleaner.

New Solution (20)

0{).-1?@\-.@\0>}do\;

New Solution Explanation

0{).-1?@\-.@\0>}do\; #Take in a number c as input, and output the lowest n s.t. Hn<x
0                    # The stack is now [c n=0]. We're just using n here for clarity.
 {             }do   # Until we pop a TRUE, loop the following
 {)            }do   # Increment n by 1
 {  .           }do   # Then duplicate it 
 {  -1?        }do   # Raise the dupe to the power of 1 (inverse)
 {     @\      }do   # Move our c to the second element of the stack, between n and 1/n 
 {       -     }do   # Subtract. Stack is now [n c-(1/n)]
 {        .    }do   # Duplicate c-(1/n)
 {         @\  }do   # Move n back to the second element of the stack
 {           0>}do   # Check if our c-(1/n) is less than zero. If so, leave the loop.
 {             }do   # If not, repeat, but with c-(1/n) as our new c.
                  \; # Remove c once it's below 0, leaving our tally. This gets outputted.        

Old Solution (21)

:c;0.{\).-1?@+.c<}do;

Old Solution Explanation

:c;0.{\).-1?@+.c<}do; # Take in a number c and find the lowest n s.t. Hn>c
:c;                   # Set c to our goal number, then pop it from our stack.
   0.                 # Make our stack [0 0]. Let will be our n, right will be our running sum.
     {           }do  # At the end of each loop, if the top of the stack isn't 0, repeat.
     {\)         }do  # Move the n to the top of the stack and increment it by 1.
     {  .-1?     }do  # Duplicate it, then inverse it.
     {      @    }do  # Bring our running total to the top (now third in the stack behind 1/n and n)
     {       +   }do  # Add the top two elements (running total + 1/n)
     {        .  }do  # Duplicate the running total
     {         c<}do  # If it's less than c, print 1 (repeat do), else 0 (stop do)
                    ; # Pop our running total, leaving behind just our n.

Shouldn't be too hard to shave a char off somewhere.

Got one.

Answer 18

Burlesque, 27 bytes

rds1@1moiT{1j?/g1++cm0>=}fi

Try it online!

For some reason save/load seems to be working a bit funny with this one on TIO. To test the code, use the following:

Burlesque, 28 bytes

rd@1moiT{1j?/++cm0>=}x/4iafi

Try it online!

rd    # Read input as double
[s1]  # Save slot 1
@1    # 1.0
mo    # Infinite multiples of {1.0, 2.0, 3.0...}
iT    # All tails of {{}, {1.0}, {1.0,2.0}, {1.0,2.0,3.0},...}}
{
 1j?/ # Reciprocal
 ++   # Sum
 [g1] # Get slot 1 (not working)
 cm   # UFO operator (-1 on <, 0 on ==, 1 on >)
 -1.> # 0 or 1
}
x/   # Reorder stack
3ia  # Insert input at position 3 of array (before compare)  
fi   # Find first index

Answer 19

Japt, 12 11 bytes

@TwUµ1/X}f1

Try it

Answer 20

Red, 53 bytes

f: func[n][i: 0 until[0 >= n: n -(1.0 /(i: i + 1))]i]

Try it online!

Simple iterative solution.

Red, 78 bytes

f: func[n /a i][either a[either n > 0[f/a n -(1.0 / i)i + 1][i - 1]][f/a n 1]]

Try it online!

I know this is way longer than other recursive solutions, but I wanted to post it because of the fact that Red functions have fixed arity. In order to simulate default values for the additional parameters, we need to use a refinement - here it's /a- whenever we need the value of the i parameter.

Answer 21

J, 29 28 bytes

-1 byte thanks to RGS

Shameless translation of Jo King's APL answer.

3 :'>:1 i.~y&<:+/\%}.i.<.^y'

Probably a lot of room for improvement, but I couldn't find a shorter tacit way.

Try it online!

Answer 22

bc, 52 bytes

define f(x){
scale=999
for(s=i=0;s<x;s=s+1/i)i=i+1
}

Try it online!

If you need more precision, change the 999 to 9E3 or 9E9. Expect memory usage to skyrocket and performance to plummet.

I'm testing a variant that prints as it passes integers. It matches OEIS A004080 so far (23 -> 5471312310). With scale=9, it is correct to 11 -> 33617 but is off by 4 for 12. With scale=99, it is so far accurate to 25 -> 40427833596. Since scale=99 can't be extended without adding another byte, I'm not going to claim it.

Answer 23

Wolfram Language (Mathematica), 29 bytes

(i=0;#//.x_/;x>0:>x-1/++i;i)&

Try it online!

Answer 24

W d, 11 9 bytes

The latest commit is a bugfix - I assume that doesn't make this non-competing?

╪ª4PĽ┌∙×

Uncompressed:

i1ak/+rb<!W

Explanation

i         W % Find the first number from 1 to positive infinity
            % That satisfies this condition
  ak        % Generate a range from 1 to the number
 1  /       % Find the reciprocal of every item (automatically vectorises)
     +r     % Reduce by addition
       b<!  % Is this number greater than or equal to the input?

Answer 25

Charcoal, 19 bytes

⊞υ¹Ｗ‹ΣυＩθ⊞υ∕¹⊕ＬυＩＬυ

Try it online! Link is to verbose version of code. Explanation:

⊞υ¹

Start off with n=1, pushing 1/1 to the predefined list.

Ｗ‹ΣυＩθ

Repeat while the list sums to less than the target...

⊞υ∕¹⊕Ｌυ

... push the next Egyptian fraction to the list.

ＩＬυ

Output the length of the list, i.e. n.

It might be possible to reduce the floating-point inaccuracy slightly by adding a Reverse after the Sum.

Answer 26

Keg, -hr, 12 bytes

0&0{¿⑻>|:⑨⑱⑼

Uses the most recent Keg interpreter, so no TIO thus far.

Explained

0&

We store 0 in the register as this will be the means of storing the total sum of the series.

0

We then push 0 onto the stack, as this will be what keeps track of the term number (n)

{¿⑻>|

The condition of the while loop is that it will repeat while the input (which is automatically filled if no input is given -- the reason why this doesn't have a TIO link) is greater than the value in the register.

⑨

We then increment the top of the stack to get to the next term. This is done before the reciprocal is taken so that we avoid an "off-by-one" error.

:⑱⑼

We then take the reciprocal of the top of the stack and add it to the register (⑱ = 1/x and ⑼ = register += t.o.s). -hr will automatically print the top of the stack at end of execution as an integer.

Here is a Try it online version that uses a variable to keep track of the input. This is mainly just so that y'all can see that the algorithm works, as the variables can be replaced with the above 12 byter.

Answer 27

Scratch 3.0, 15 blocks / 127 bytes

when gf clicked
ask()and wait
set[n v]to(0
set[t v]to(0
repeat until<(t)>(answer
change[n v]by(1
change[t v]by((1)/(n
end
say(n

Just a port of my Keg answer, so Try it online Scratch!

Answer 28

W d, 8 bytes

Let's see if I can come tied with 05AB1E ...

♠wⁿ=^φ→§

Uncompressed:

kJrJb<!iX

Explanation

       iX % Foreach in [1 .. +inf],
          % find first number that satisfies:
k         % Range of 1 .. number
 Jr       % Reciprocal each
   J      % Summation of entire list
    b<!   % Is that >= the input?