16
\$\begingroup\$

The sequence of Harmonic numbers are the sums of the reciprocals of the first k natural numbers (not including zero):

\${\displaystyle H_{k}=1+{\frac {1}{2}}+{\frac {1}{3}}+\cdots +{\frac {1}{k}}=\sum _{i=1}^{k}{\frac {1}{i}}.}\$

Your task is to implement the sequence of numbers a(n) = the smallest k that the k'th Harmonic number is greater than n. You must output k, not the Harmonic number itself.

The first few terms zero-indexed are:

1, 2, 4, 11, 31, 83, 227, 616, 1674, 4550, 12367, 33617, ...

Your submission may fail to work for larger numbers due to language limitations as long as the algorithm works theoretically on arbitrary indices. Keep in mind that Abusing native number types to trivialize a problem is banned.

This is OEIS A002387.

This is a challenge; the shortest code wins. Standard [sequence] rules apply.

Meaningless brownie points for beating or matching my 15 bytes of Uiua :)

\$\endgroup\$
7
  • 3
    \$\begingroup\$ Is calculating \$ \lceil e^{n-\gamma}\rceil\$ acceptable? \$\endgroup\$
    – Tbw
    Commented Jun 9 at 16:48
  • 4
    \$\begingroup\$ That is a good question. As far as I can tell that formula is only conjectured to be correct, so unless you can prove it I am going to say no. \$\endgroup\$ Commented Jun 9 at 16:49
  • \$\begingroup\$ The variable names are kind-of confusing, I'm going to edit them to be more consistent \$\endgroup\$
    – xnor
    Commented Jun 9 at 19:16
  • \$\begingroup\$ From the definition and OEIS, it looks like you mean for a(0)=1, a(1)=2, a(2)=4, ..., so I edited in "zero-indexed", but it looks like some answers are assuming it's one-indexed \$\endgroup\$
    – xnor
    Commented Jun 9 at 19:32
  • 1
    \$\begingroup\$ @noodleperson if it can calculate the 2304 known terms in oeis.org/A002387/b002387.txt, then it is as capable as all the other entries here.. \$\endgroup\$
    – qwr
    Commented Jun 10 at 1:28

23 Answers 23

6
\$\begingroup\$

Python 3, 36 bytes

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

Try it online!

Outputs zero-indexed, which is how the OEIS is defined.

43 bytes

t=k=1
while[t%1*k<=1!=print(k)]:k+=1;t+=1/k

Try it online!

Prints forever

\$\endgroup\$
6
\$\begingroup\$

Octave, 34 bytes

f=@(n)find(cumsum(1./(1:4^n))>n,1)

Try it Online!

Explanation

Vectorization + cumulative sum. Can evaluate a(13) easily.

Use the 'power of two' inequality:

$$H_k = 1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\frac{1}{6}+\frac{1}{7}+\frac{1}{8}+ \cdots +\frac{1}{k}$$ is greater than $$T_k = 1+\frac{1}{2} + \left(\frac{1}{4}+\frac{1}{4}\right)+\left(\frac{1}{8}+\frac{1}{8}+\frac{1}{8}+\frac{1}{8}\right) + \cdots +\frac{1}{k}$$

So \$T_k > N\$ implies \$H_k > N\$. For the original question, the smallest \$k\$ cannot be greater than \$2^{2N}\$.

\$\endgroup\$
3
  • \$\begingroup\$ Welcome to CGCC, nice first submission, and clever way of approaching this! I see \$ T_k > N \$ implies \$ H_k > N \$ but what if \$ H_k > N > T_k \$? Or does that case just never happen in this sequence? \$\endgroup\$ Commented Jun 11 at 21:37
  • \$\begingroup\$ @noodleperson \$T_k\$ always goes up as \$k\$ increases (since one just keeping adding \$1/2\$ to it), while \$N\$ is given. One can choose a \$k\$ to satisfy \$T_k > N\$: for example, \$T_{2^{2N}} > N\$ . Let's say \$N = 3/2\$. \$2^{2(3/2)}=8\$. \$T_{8} = 1 + 1/2 +1/2+1/2 = 1+3/2 > 3/2\$. Since the input \$N\$ is an integer, a equivalent way to think about it is \$T_{2^{N}} > N/2\$. This is true because of the extra "1" at the beginning of \$T_k\$. \$\endgroup\$
    – Ka Wa Yip
    Commented Jun 12 at 0:06
  • 1
    \$\begingroup\$ Nice, that makes sense, thank you for explaining. \$\endgroup\$ Commented Jun 12 at 7:01
6
+150
\$\begingroup\$

Python 3, 34 bytes

f=lambda n,k=2:n<1or-~f(n-1/k,k+1)

A recursive function that accepts \$n\$ (0-indexed) and returns the required number of terms.

Try it online!

How?

Count the number of non-unit terms (\$\frac{1}{2}, \frac{1}{3}, ...\$) we need to subtract to reach a number below one and add one.

One may think that this could overshoot for some \$n\$, but that would only happen if some harmonic number other than \$0\$ or \$1\$ were an integer, which is not the case due to Bertrand's postulate - see "proof 2" here.

Uses the fact that in Python True quacks like 1.

f=lambda  ,   :                     # f is a function that accepts
         n                          # n
           k=2                      # and, optionally, k defaulting to 2:
               n<1                  #   is n less than one?
                  or                #   if not...
                      f(     ,   )  #     call f with
                        n-1/k       #       n reduced by the current term (1/k)
                              k+1   #       and k incremented -> C
                     ~              #     bitwise NOT         -> -1 - C
                    -               #     negate              -> -(-1 - C) = C + 1
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Huh, that just works, nice find. Here's a bounty. \$\endgroup\$
    – xnor
    Commented Jun 12 at 17:08
  • \$\begingroup\$ Thanks @xnor! I was on the fence for a little bit between posting and gifting, but the reasoning seemed worthy enough. \$\endgroup\$ Commented Jun 12 at 17:23
5
\$\begingroup\$

JavaScript (ES6), 29 bytes

Returns the \$n\$-th term, 1-indexed.

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

Try it online!

\$\endgroup\$
5
\$\begingroup\$

R, 36 bytes

\(n){k=0;while(F<=n)F=F+1/(k=k+1);k}

Try it online!

Minus 2 bytes thanks to @pajonk's suggestion in comment.

\$\endgroup\$
3
  • \$\begingroup\$ -2 bytes using F for h. \$\endgroup\$
    – pajonk
    Commented Jun 11 at 14:39
  • \$\begingroup\$ Why does the TIO link not have the \(n){...} syntax? Is the version of R not high enough to support it? EDIT - maybe go over to ATO, that seems to work :) \$\endgroup\$ Commented Jun 11 at 17:07
  • 1
    \$\begingroup\$ @JonathanAllan You are right, TIO doesn't support the not so new syntax (R 4.1.0, 2021-05-18), it throws an error. \$\endgroup\$ Commented Jun 11 at 17:59
4
\$\begingroup\$

Vyxal 3, 8 bytes

λɾė∑⁰>}“

Try it Online!

λɾė∑⁰>}“­⁡​‎‎⁡⁠⁢⁤‏‏​⁡⁠⁡‌⁢​‎⁠‎⁡⁠⁤‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁣‏‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁢‏‏​⁡⁠⁡‌⁢⁡​‎⁠‎⁡⁠⁢⁢‏‏​⁡⁠⁡‌⁢⁢​‎‎⁡⁠⁢⁡‏‏​⁡⁠⁡‌­
       “  # ‎⁡Find first positive integer such that
   ∑      # ‎⁢the sum of 
  ė       # ‎⁣the reciprocals of
 ɾ        # ‎⁤the numbers from 1 to the integer
     >    # ‎⁢⁡is greater than
    ⁰     # ‎⁢⁢the input
💎

Created with the help of Luminespire.

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

Haskell, 31 bytes

(0!)
k!n|n<1=k|k<-1+k=k!(n-1/k)

Ungolfed:

f n = (0!n)
(k!n)
 | n<1       = k
 | otherwise = let k' = 1+k in k' ! (n-1/k')

A port of @Arnauld's answer.

Attempt This Online!

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

Arturo, 41 bytes

g:$[n k][(n<1)?->k->g n-1//<=k+1]$=>[g&1]

Try it!

A port of Arnauld's JavaScript answer. Arturo doesn't have default arguments, so two functions are necessary where the second calls the first with a fixed k.

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

Jelly, 7 bytes

İ€S>ð1#

A monadic Link that accepts a non-negative integer and yields a singleton list containing a positive integer. Or a full program that prints the result.

Try it online!

How?

İ€S>ð1# - Link: non-negative integer, N
      # - starting with k=N increment k finding the...
     1  - ...first 1 k for which:
    ð   -   the dyadic chain - f(k, N):
İ€      -     inverse each of {[1..k]}
  S     -     sum
   >    -     is greater than {N}?
\$\endgroup\$
4
\$\begingroup\$

Google Sheets, 57 bytes

Expects \$n\$ in A1 (\$0\$-indexed)

=LET(R,LAMBDA(R,s,i,IF(s>A1,i-1,R(R,s+1/i,i+1))),R(R,,1))

Reaches calc limit starting from \$n=10\$ (\$a(n) = 12367\$).

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

cQuents, 13 12 bytes

$0:#$<bN
;/$

Try it online!

-1 because I remembered I had added a unary / for reciprocal

Explanation

First line:

$0        set starting index to 0
  :       mode: sequence - given input n, return the nth term
          each term equals
   #                       the first value of N such that:
    $     the current index
     <                      <
      b                       the second line (   )
       N                                        N

Second line:

;         mode: series - given input n, return the sum of the first n terms
          each term equals
 /                         1 /
  $                            current index
\$\endgroup\$
3
\$\begingroup\$

PowerShell Core, 37 bytes

for(){if(($s+=1/++$d)-gt$c){$d
$c++}}

Try it online!

Outputs the sequence indefinitely

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

Wolfram Language (Mathematica), 43 bytes

Ceiling@*InverseFunction[HarmonicNumber]@*N

Try it online! (for some reason TIO returns 1 instead of 2 for the input 1; it works correctly on my computer)

The inevitable built-in. Mathematica can calculate HarmonicNumber\$(x)\$ for any real number \$x>-1\$, and thus it can calculate the exact InverseFunction of that function. N makes it treat the input as a real number rather than an integer, and Ceiling rounds up to the nearest integer.

Yet again I wish I understood how to install and use Sledgehammer....

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

05AB1E, 7 bytes

∞.ΔLzO‹

Given a 0-based \$n\$, outputs the \$n^{th}\$ value.

Try it online or verify the infinite list.

Explanation:

∞        # Push an infinite positive list: [1,2,3,...]
 .Δ      # Pop and find the first value which is truthy for:
   L     #  Pop and push a list in the range [1,value]
    z    #  Convert each inner value v to its reciprocal 1/v
     O   #  Sum this list of reciprocals
      ‹  #  Check if the (implicit) input-integer is smaller than this
         # (after which the found result is output implicitly)
\$\endgroup\$
4
  • 1
    \$\begingroup\$ Handy that 05AB1E passes the implicit input through functions, the Jelly solution has to explicitly call it as a dyad which I guess it realizes the right side has to be the input \$\endgroup\$ Commented Jun 10 at 11:12
  • \$\begingroup\$ @noodleperson 05AB1E doesn't have any functions, but I assume you mean in vectorized contexts like maps/filters/etc. (in this case the find_first )? 05AB1E is a stack-based language, so when a builtin needs two arguments and only a single one is given (as is the case with in this program above), it'll use the (implicit) input. :) On the other hand, Jelly usually has implicit left/right arguments within its dyads or multiple implicit uses within its monads, for which 05AB1E should use Duplicates and swaps when you want to use an argument more than once. \$\endgroup\$ Commented Jun 10 at 11:18
  • 1
    \$\begingroup\$ I was just comparing your solution to the Vyxal equivalent at the bottom of the page which is 8 bytes because it has to refer to the input explicitly since it doesn’t get passed through the finding-lambda. Vyxal would usually use implicit input there but in this case the “implicit input” is a copy of the lambda’s input number. I know how stack langs work! \$\endgroup\$ Commented Jun 10 at 11:23
  • 1
    \$\begingroup\$ Ah ok, I don't know too much about Vyxal to comment on that. I would have expected Vyxal to work with implicit inputs within vectorized contexts as well, but maybe lambdas are an exception to that. 🤔 In 05AB1E, the implicit input can be used any time a builtin needs an argument and there is none. (And I never claimed you didn't knew how stack-based languages work. I simply added the explanation in case you didn't know 05AB1E in general or that it was a stack-based language, and for anyone else who might read these comments to explain the differences between 05AB1E and Jelly for this example.) \$\endgroup\$ Commented Jun 10 at 11:36
3
\$\begingroup\$

Desmos, 43 bytes

f(n)=g(n,1)
g(n,k)=\{n<0:0,g(n-1/k,k+1)+1\}

Port of xnor's Python answer.

Try It On Desmos!

Try It On Desmos! - Prettified

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

Charcoal, 18 bytes

NθW¬‹θ⁰«→≧⁻∕¹ⅈθ»Iⅈ

Try it online! Based on @Arnauld's answer but I chose to make mine 0-indexed. Explanation:

Nθ

Input n.

W¬‹θ⁰«

Until n is negative...

→≧⁻∕¹ⅈθ

... subtract the next unit fraction from n.

»Iⅈ

Output k.

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

Python, 41 bytes

f=lambda n,k=0:n<1and k or f(n-1/-~k,-~k)

A port of @Arnauld's answer.

Attempt This Online!

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

MATL, 11 bytes

`1@:/sG>~}@

Inputs n, outputs a(n).

Try it online!

How it works

`       % Do...while
  1     %   Push 1
  @     %   Push iteration index k, starting at 1
  :     %   Range: gives [1 2 ... k]
  /     %   Inverse, element-wise
  s     %   Sum: gives H_k
  G     %   Push n
  >     %   Greater than?
  ~     %   Negate. This is the loop condition
}       % Finally (execute on loop exit)
  @     %   Push k of the last iteration
        % End (implicit)
        % Display stack (implicit)
\$\endgroup\$
2
\$\begingroup\$

Brachylog, 11 bytes

≤.⟦₁/₁ᵐ+>?∧

Try it online!

Takes n as input.

Explanation

≤.            n ≤ k, k is the output
 .⟦₁          Take the range [1, …, k]
    /₁ᵐ       Map inverse: [1, …, 1/k]
       +>?    The sum of inverses must be greater than n
          ∧  (Implicitely find a value of k that fits these constraints)
\$\endgroup\$
2
\$\begingroup\$

Ruby, 28 27 bytes

->n{(1..).find{0>n-=1r/_1}}

Attempt This Online!

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

PHP, 51 bytes

function f($n,$k=0){return$n<1?$k:f($n-1/++$k,$k);}

Try it online!

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

Vyxal, 6 bytes

↵ʀĖ¦⌈ḟ

Try it Online!

You know me, gotta be posting the most stupid and inefficent answers. Goes slow for inputs that make \$10^x\$ very large. 1-indexed.

Uses some lucky math coincidences to get 6 bytes instead of 7 doing it the normal way.

Explained

↵ʀĖ¦⌈ḟ­⁡​‎‎⁡⁠⁡‏⁠‎⁡⁠⁢‏‏​⁡⁠⁡‌⁢​‎‏​⁢⁠⁡‌⁣​‎‎⁡⁠⁣‏‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁤‏‏​⁡⁠⁡‌⁢⁡​‎‎⁡⁠⁢⁡‏‏​⁡⁠⁡‌⁢⁢​‎‎⁡⁠⁢⁢‏‏​⁡⁠⁡‌­
↵ʀ      # ‎⁡Push the range [0, 10 ** n]. As noted on the OEIS,
        # ‎⁡For n >= 1, log(n + 1/2) + gamma < H(n) < log(n + 1/2) + gamma + 1/(24n^2), where gamma is Euler's constant
        # ‎⁡(source: https://oeis.org/A002387 under the comments section)
        # ‎⁡Luckily, for n >= 1, 10 ** n > that. Therefore, it's guaranteed
        # ‎⁡that the answer is contained within the range.
# ‎⁢This is also why the program takes a while for larger inputs.
  Ė     # ‎⁣Reciprocals of each number in that range
   ¦    # ‎⁤Cumulative sums of those reciprocals
    ⌈   # ‎⁢⁡And take the floor of each cumulative sum.
     ḟ  # ‎⁢⁢Find the first index of the input in that list.
        # ‎⁢⁢This is why the output is 1-indexed.
        # ‎⁢⁢It's essentially finding the point where the harmonic number is first > n - 1
💎

Created with the help of Luminespire.

\$\endgroup\$
2
  • \$\begingroup\$ Nice! ↵ʀ can also be Þ: though that doesn't seem to be any faster. \$\endgroup\$ Commented Jun 15 at 1:42
  • \$\begingroup\$ Þ: isn't as funny as using a brute force range :p. I think it's the same speed because it's all lazily evaluated until the find index command, which is what takes the most time. \$\endgroup\$
    – lyxal
    Commented Jun 15 at 1:44
1
\$\begingroup\$

Uiua, 15 bytes

⍢(⊙+:÷,1+1)⋅≥.0

Try it online!

Nobody tried to beat my Uiua score in the three weeks since I posted this challenge, so I decided to just leave it here for reference.

This leaves k at the top of the stack, with the actual harmonic number below it and the input below that.

Here's the code commented with a translation to traditional imperative code:

⍢(⊙+:÷,1+1)⋅≥.0­⁡​‎⁠⁠⁠⁠⁠⁠⁠‎⁡⁠⁤⁢‏⁠‎⁡⁠⁤⁣‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁡‏⁠‎⁡⁠⁢‏⁠⁠⁠‎⁡⁠⁣⁣‏⁠‎⁡⁠⁣⁤‏⁠‎⁡⁠⁤⁡‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁣⁡‏⁠‎⁡⁠⁣⁢‏‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁢⁢‏⁠‎⁡⁠⁢⁣‏⁠‎⁡⁠⁢⁤‏‏​⁡⁠⁡‌⁢⁡​‎‎⁡⁠⁣‏⁠‎⁡⁠⁤‏⁠‎⁡⁠⁢⁡‏‏​⁡⁠⁡‌­
             .0  # ‎⁡k = 0, H = 0, n = input
⍢(        )⋅≥    # ‎⁢while H >= n:
        +1       # ‎⁣  k += 1
  ⊙+:÷,1         # ‎⁢⁡  H += 1/k

💎

Code explanation created with the help of Luminespire.

Uiua is a tacit language, so that translation isn't one-to-one, but it's close enough.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.