30
\$\begingroup\$

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 so shortest solution wins! Standard loopholes are forbidden by default. Happy golfing.

\$\endgroup\$
  • 2
    \$\begingroup\$ Related OEIS sequence. \$\endgroup\$ – Arnauld Feb 9 at 23:32
  • \$\begingroup\$ @Arnauld included for completeness? Or do you think it might help someone in any way? \$\endgroup\$ – RGS Feb 9 at 23:43
  • 9
    \$\begingroup\$ Your recent challenges have been great! Keep up the good work! \$\endgroup\$ – S.S. Anne Feb 10 at 0:48
  • \$\begingroup\$ @S.S.Anne thanks :D I'll try to come up with more decent challenges. \$\endgroup\$ – RGS Feb 10 at 7:27
  • \$\begingroup\$ You ask: "how far should I go". I suggest anywhere between 6 to 8 metres. :P \$\endgroup\$ – Lyxal Feb 10 at 10:26

29 Answers 29

7
\$\begingroup\$

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
|improve this answer|||||
\$\endgroup\$
  • 1
    \$\begingroup\$ 1⍳⍨ -> ⊃⍸­­ \$\endgroup\$ – ngn Feb 10 at 0:43
  • \$\begingroup\$ What does dfn stand for? Also, be sure to upvote the challenge if you liked solving it :) \$\endgroup\$ – RGS Feb 10 at 7:19
  • 2
    \$\begingroup\$ @RGS dfn stands for Direct Function \$\endgroup\$ – Jo King Feb 10 at 7:50
  • 2
    \$\begingroup\$ Sorry, but the first thing I saw in your answer was this face: {⊃≥⍵≤⊃} \$\endgroup\$ – Taazar Feb 10 at 16:48
7
\$\begingroup\$

Python 3, 35 bytes

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

Try it online!

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Thanks for the submission. When X <= 0 the LHS evaluates to false. How does the lambda return n at that point? Also be sure to upvote if you liked golfing this challenge. \$\endgroup\$ – RGS Feb 10 at 7:29
  • \$\begingroup\$ I don’t understand why the complement operator makes the and return the number instead of False. What happens there? \$\endgroup\$ – Émile Jetzer Feb 10 at 13:41
  • 3
    \$\begingroup\$ @ÉmileJetzer The -~ is basically a shorter variation of +1. Since it's a recursive function that eventually results in False, the -~/+1 will interpret this as 0 in Python and adds the 1 (False+1 = 1 in Python). Here a step-by-step explanation of what happens for f(2). \$\endgroup\$ – Kevin Cruijssen Feb 10 at 16:49
  • 1
    \$\begingroup\$ @KevinCruijssen that makes a whole lot'a sense! Thanks for explaining it and going through the effort of explaining it step by step. \$\endgroup\$ – RGS Feb 10 at 22:04
  • \$\begingroup\$ @KevinCruijssen Thanks for detailed breakdown! The idea of incrementing the recursive output starting from a base case of 0, as a replacement for outputting the final value n, is a pattern that I find to come up a lot. For example, when finding the n'th number meeting a condition p, as in my tip here, we can use f=lambda n,i=1:n and-~f(n-p(i),i+1), which looks very similar to this answer. \$\endgroup\$ – xnor Feb 11 at 3:10
6
\$\begingroup\$

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
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ I should learn some Perl! +1 Thanks for including an explanation of the code. \$\endgroup\$ – RGS Feb 9 at 23:00
  • 2
    \$\begingroup\$ @RGS Note that these days Perl 6 is called Raku (TIO still uses Perl 6 hence most submissions use it). It was designed originally as a non-backwards compatible successor to Perl 5, but now both still live on with different names — Perl 5 is just Perl, and Perl 6 is Raku. I'm biased since I do a lot of (non golfing) work in it, but it's really one of the more beautiful and fun languages to write general code in, which sounds weird given the (unfair) image that Perl 5 had. \$\endgroup\$ – user0721090601 Feb 12 at 4:06
  • \$\begingroup\$ @user0721090601 thank you for your testimonial. Tbh, I heard some "mean" things about Perl but I never programmed in it! Neither Perl <= 5, nor Perl 6 :) \$\endgroup\$ – RGS Feb 12 at 7:12
  • 2
    \$\begingroup\$ @RGS Perl — moreso than other languages as it regularly beats all but the golfing languages on here — can be extremely code-golfy and line-noisy. Sadly too many people used to write their $day-job code like that which gave it the bad rap, particularly when others had to read such golfy/noisy code. \$\endgroup\$ – user0721090601 Feb 12 at 23:13
6
\$\begingroup\$

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!

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ I have to get used to those solutions with evaluating loop code... why isn't the solution the actual loop? +1 for teaching me smth \$\endgroup\$ – RGS Feb 9 at 22:58
  • \$\begingroup\$ @RGW Without eval(), it would be n=>{for(k=0;(n-=1/++k)>0;);return k}, which is 1 byte longer. \$\endgroup\$ – Arnauld Feb 9 at 23:01
  • \$\begingroup\$ ah wow, of course. Thanks for elaborating \$\endgroup\$ – RGS Feb 9 at 23:04
  • 1
    \$\begingroup\$ @RGS As a side note, the version with eval() is much, much slower than without eval() because the code never gets a chance to be processed by the JIT compiler. \$\endgroup\$ – Arnauld Feb 9 at 23:11
  • 1
    \$\begingroup\$ n=>Math.exp(n-.5772)+.4|0 will work with all the test cases at least. I wonder how much further it will push out? \$\endgroup\$ – Guillermo Phillips Feb 10 at 19:15
5
\$\begingroup\$

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
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Thanks for your submission +1 Do you think you could include an explanation of the code? \$\endgroup\$ – RGS Feb 9 at 23:00
  • 2
    \$\begingroup\$ @RGS there you go, done \$\endgroup\$ – Grimmy Feb 9 at 23:51
  • \$\begingroup\$ another 8 bytes: ∞z.¥ÅΔI@, or ∞z.¥I@ÅΔ \$\endgroup\$ – Command Master Mar 30 at 12:10
  • \$\begingroup\$ this is 7 bytes: ∞z.¥‹ÅΔ or ∞z.¥ÅΔ‹ but sadly it doesn't work when the sum is exact \$\endgroup\$ – Command Master Mar 30 at 12:17
5
\$\begingroup\$

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!

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ 36 bytes -- you need the +T at the end to prevent small x from returning TRUE. \$\endgroup\$ – Giuseppe Feb 10 at 15:56
  • \$\begingroup\$ @Giuseppe I changed the core functionality in this edit. Any feedback? \$\endgroup\$ – John Feb 10 at 16:03
  • \$\begingroup\$ I'd probably just use scan() in place of x but your edit now fails the requirement to work in theory for arbitrary x. \$\endgroup\$ – Giuseppe Feb 10 at 16:32
  • 3
    \$\begingroup\$ @Giuseppe good point. I made it arbitrary, but it won't work for all test cases due to memory limits \$\endgroup\$ – John Feb 10 at 16:48
  • \$\begingroup\$ good R submission, +1. Unfortunately, the shorter solution doesn't meet the requirements, as Giuseppe pointed out :/ \$\endgroup\$ – RGS Feb 10 at 17:30
5
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$
  • 2
    \$\begingroup\$ +1 Clever solution, to use the lower bound so that you don't have to recurse or anything like that \$\endgroup\$ – RGS Feb 10 at 13:14
  • \$\begingroup\$ @Giuseppe Thank you! Edited \$\endgroup\$ – Luis Mendo Feb 10 at 22:35
4
\$\begingroup\$

Python 3, 49 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!

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Cool submission +1 it is just a shame that the recursion depth doesn't allow us to check for larger test cases. Also be sure to upvote the challenge if you liked golfing it :) \$\endgroup\$ – RGS Feb 10 at 7:22
4
\$\begingroup\$

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!

|improve this answer|||||
\$\endgroup\$
4
\$\begingroup\$

Ruby, 31 30 bytes

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

Try it online!

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Clean solution, +1. Can you save 1 byte if you write b=.0? \$\endgroup\$ – RGS Feb 10 at 8:50
  • 1
    \$\begingroup\$ Not really, but I can achieve something similar with rational numbers (1r). \$\endgroup\$ – G B Feb 10 at 8:59
4
\$\begingroup\$

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!

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Thanks for your submission. +1 I see you are fond of exploiting that GCC bug you mention. Be sure to upvote my challenge if you liked solving it :) \$\endgroup\$ – RGS Feb 10 at 0:02
  • 1
    \$\begingroup\$ @RGS Definitely, there you go. return is a big space-killer so removing it is high on my list. I'm only sad I couldn't do it with h. \$\endgroup\$ – S.S. Anne Feb 10 at 0:04
  • 1
    \$\begingroup\$ For the first solution, you don't need x=i; at all on GCC with -O0. It works because the loop counter (i) is already getting put in the eax register by the code-gen, which is where x86 expects the return value to be. Look at the disassembly. That saves you 4 more bytes. And seriously risks nasal demons. In fact, my nose is starting to itch... \$\endgroup\$ – Cody Gray Feb 11 at 1:05
  • \$\begingroup\$ @Cody This is code golf. Get over it. \$\endgroup\$ – S.S. Anne Feb 11 at 1:07
3
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ +1 for some jelly. For some reason the code feels long D: is it just me being a jerk? \$\endgroup\$ – RGS Feb 9 at 23:19
3
\$\begingroup\$

Haskell, 34 bytes

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

Try it online!

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ +1 really cool solution with the infix operator. The cpp flag is just for the purposes of writing `f=` in the header? \$\endgroup\$ – RGS Feb 10 at 13:12
3
\$\begingroup\$

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

|improve this answer|||||
\$\endgroup\$
  • 2
    \$\begingroup\$ +1 for the answer in a language I have never seen! \$\endgroup\$ – RGS Feb 10 at 13:11
3
\$\begingroup\$

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
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Seeing such short solutions in "normal" programming languages fills me with joy \$\endgroup\$ – RGS Feb 10 at 13:17
3
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ +1 for this GS submission! if you liked the challenge, consider upvoting it :) \$\endgroup\$ – RGS Feb 10 at 17:24
3
\$\begingroup\$

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

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ cool submission! can you explain it, please? +1 :) \$\endgroup\$ – RGS Feb 10 at 17:29
  • \$\begingroup\$ @RGS I'm not great at writing explainations but here goes nothing. \$\endgroup\$ – famous1622 Feb 10 at 17:36
  • \$\begingroup\$ If you remove the first Q, it'll be filled in implicitly. Also, g is the greater than or equal to function. \$\endgroup\$ – isaacg Feb 10 at 18:52
  • \$\begingroup\$ @isaacg g gets me wrong output for 1.5 for some reason, but the Q being implicitly filled is interesting, thanks! \$\endgroup\$ – famous1622 Feb 10 at 19:03
  • \$\begingroup\$ @famous1622 g works fine for me, once I move the Z to the front: Try it online! \$\endgroup\$ – isaacg Feb 10 at 19:05
2
\$\begingroup\$

Japt, 12 11 bytes

@TwUµ1/X}f1

Try it

|improve this answer|||||
\$\endgroup\$
  • 1
    \$\begingroup\$ Thanks for the solution! Is there any way you could include an explanation? Also, are you using such a specific version for some reason? \$\endgroup\$ – RGS Feb 9 at 23:44
2
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ It makes me sad that you have to use all those spaces around the operators :( \$\endgroup\$ – RGS Feb 10 at 9:31
  • 1
    \$\begingroup\$ @RGS Yes, it's true. This is a deliberate design decision taken by the creator of Rebol (the precursor of Red) \$\endgroup\$ – Galen Ivanov Feb 10 at 9:35
2
\$\begingroup\$

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
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ +1 thanks for your suggestion. I made an edit suggestion to your answer and it gave me the impression that you may have used a templating tool to create the skeleton for your answer. Does what I am saying make any sense? \$\endgroup\$ – RGS Feb 9 at 23:42
  • 1
    \$\begingroup\$ Sure, not sure it makes much difference though. No templating tool. Just me being lazy in typing. \$\endgroup\$ – DeathIncarnate Feb 9 at 23:52
2
\$\begingroup\$

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!

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ hey, you can save 1 byte. +1 for your J submission. Upvote the challenge if you liked it :) \$\endgroup\$ – RGS Feb 10 at 17:28
2
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ bc and dc solutions don't require functions AFAIK. You can put it in the header and footer. You could at least change the variable names. \$\endgroup\$ – S.S. Anne Feb 11 at 2:44
  • \$\begingroup\$ @S.S.Anne How about Posting a code snippet instead of a complete answer and it's referenced question. \$\endgroup\$ – David G. Feb 11 at 2:55
  • \$\begingroup\$ Interesting solution in a language that hasn't been used in this thread :) +1 \$\endgroup\$ – RGS Feb 11 at 7:03
2
\$\begingroup\$

Wolfram Language (Mathematica), 29 bytes

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

Try it online!

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Really simple solution in mathematics :D +1 \$\endgroup\$ – RGS Feb 11 at 7:04
  • \$\begingroup\$ While it's not as short (40 bytes), it's amusing to note that Mathematica basically has a builtin for this problem: Ceiling@*InverseFunction[HarmonicNumber] \$\endgroup\$ – Greg Martin Feb 11 at 16:30
  • 1
    \$\begingroup\$ @GregMartin I think everybody knows that by now ;-) Unfortunately, once again the name is pretty big... \$\endgroup\$ – J42161217 Feb 11 at 16:34
  • \$\begingroup\$ 30 bytes \$\endgroup\$ – Roman Feb 22 at 20:31
  • 1
    \$\begingroup\$ @Roman that was long ago hahah. I posted a different approach which is even shorter! \$\endgroup\$ – J42161217 Feb 22 at 22:15
2
\$\begingroup\$

W d, 11 9 bytes

╪ª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?
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ What happened when you tried to compress the program? \$\endgroup\$ – Lyxal Feb 11 at 11:01
  • \$\begingroup\$ I feel that the short code length is worth all the downvotes... (If you can't see the answer, someone downvoted my answer.) \$\endgroup\$ – user85052 Feb 11 at 12:06
  • \$\begingroup\$ I would say bug fixes to the language don't make the answers in said languages non competing. +1 for your W submission! \$\endgroup\$ – RGS Feb 11 at 14:20
  • \$\begingroup\$ Answers in newer languages are never non-competing nowdays. \$\endgroup\$ – pppery Mar 29 at 21:29
1
\$\begingroup\$

Charcoal, 19 bytes

⊞υ¹W‹ΣυIθ⊞υ∕¹⊕LυILυ

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

⊞υ¹

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

W‹ΣυIθ

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

⊞υ∕¹⊕Lυ

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

ILυ

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.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Thanks for the submission. I don't want to be rude, but at the end of the day, me not knowing charcoal means I can't say your verbose version of the code matches what you wrote here. Why do you always link the verbose version? :) \$\endgroup\$ – RGS Feb 9 at 23:56
  • \$\begingroup\$ Ah, is it what the flags in the TIO link are for? They print the golfed code? \$\endgroup\$ – RGS Feb 9 at 23:57
  • 1
    \$\begingroup\$ @RGS Yes, the -v flag translates the verbose code to succinct code and the -l flag prints that code and its byte length, before the succinct code then gets run as if it was the original code. (So occasionally I trip over bugs in the succinct code translator...) \$\endgroup\$ – Neil Feb 10 at 10:28
  • \$\begingroup\$ you trip on your own bugs? Did you create charcoal? Or you do just in charcoal's bugs? \$\endgroup\$ – RGS Feb 10 at 13:15
  • 1
    \$\begingroup\$ @RGS My only contribution to Charcoal was to fix a bug caused by a Python 3 update. \$\endgroup\$ – Neil Feb 10 at 14:00
1
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$
  • 1
    \$\begingroup\$ Thanks for you keg submission (+1). Were you the one creating keg? Also be sure to upvote the challenge if you liked it. It keeps me going. \$\endgroup\$ – RGS Feb 10 at 7:25
  • \$\begingroup\$ @RGS yep, guilty as charged :P. Hard to upvote something I've already up voted! \$\endgroup\$ – Lyxal Feb 10 at 7:27
  • 1
    \$\begingroup\$ +2 for you then :D did you create keg so that you can golf here? \$\endgroup\$ – RGS Feb 10 at 7:30
  • 1
    \$\begingroup\$ @RGS indeed I did. Y'all can see right through me! :P ;) \$\endgroup\$ – Lyxal Feb 10 at 7:32
1
\$\begingroup\$

Scratch 3.0, 15 blocks / 127 bytes

Scratch blocks

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!

|improve this answer|||||
\$\endgroup\$
  • 1
    \$\begingroup\$ I find your scratch submissions amusing +1 I think you want a >= and not a > for the repeat test. \$\endgroup\$ – RGS Feb 10 at 7:27
  • \$\begingroup\$ @RGS, >=? We don't do that round these parts! Really though... Scratch doesn't have a >= operator, so I'll have to make it different :P \$\endgroup\$ – Lyxal Feb 10 at 7:31
1
\$\begingroup\$

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?
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Isn't this very similar to your first W submission? \$\endgroup\$ – RGS Feb 22 at 11:28
0
\$\begingroup\$

Perl 5 -p, 22 bytes

$i+=1/++$\while$_>$i}{

Try it online!

|improve this answer|||||
\$\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.