Partial Sums of Harmonic Series
Given an positive integer $n$, return the least positive integer $k$ such that the $k$th partial sum of the harmonic series is greater than or equal to $n$. For example, if $n = 2$, then $k = 4$, because $1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} = \frac{25}{12} > 2$.
More Input/Output Examples
Input -> Output
1 -> 1
3 -> 11
4 -> 31
This is code-golf, so shortest code wins.
Japt, 11 10 bytes >0©Òß …
3y ago
[Python 3], 35 bytes …
4y ago
AppleScript, 178 bytes ``` …
4y ago
[Raku], 27 bytes {+ …
4y ago
[Scala], 55 bytes ( …
4y ago
Stax, 9 bytes Ç≈f♠É↔X+ö …
4y ago
[JavaScript (Node.js)], 47 byt …
4y ago
[Jelly], 8 bytes İ€S<¬ʋ …
3y ago
Vyxal, 7 bytes ``` ɾĖ∑?≥) …
24d ago
[J], 23 bytes >:@]^:(>1 …
3y ago
JavaScript, 29 bytes …
3y ago
Goruby, 38 bytes ``` ->n{dw{ …
2y ago
12 answers
You are accessing this answer with a direct link, so it's being shown above all other answers regardless of its score. You can return to the normal view.
Raku, 27 bytes
{+([\+](1 X/1..*)...*>=$_)}
{ } # Anonymous code block
[\+]( ) # Get the partial sum of
1 X/ # 1 over each of
1..* # All positive integers
...*>=$_ # Take from the list until it is bigger than the input
+( ) # And return the length of the list
This will start to suffer precision issues, but you can add .FatRat to work correctly (but much slower)
Python 3, 35 bytes
f=lambda x,i=1:x>0and-~f(x-1/i,i+1)
Subtracts each 1/i in turn from the initial value until the result is no longer positive.
0 comment threads
AppleScript, 178 bytes
set n to text returned of (display dialog "" default answer "") as number
set k to 0
set h to 0
repeat
set k to k + 1
set h to h + (1 / k)
if h >= n then exit repeat
end repeat
k
It's really a shame that AppleScript doesn't support explicit stdin.
Scala, 55 bytes
(Stream from 1 map 1.0./scanLeft.0)(_+_)indexWhere _.<=
Written in a more sane manner:
n => Stream.from(1).map(1.0/_).scanLeft(0.0)(_+_).indexWhere(_ >= n)
Explanation:
(
Stream from 1 //Make an infinite list of integers, starting at 1
map 1.0./ //Find the reciprocal of each (divide 1.0)
scanLeft .0)(_+_) //Sum each partial sequence
indexWhere //Find the index where
_.<= //n (underscore) is less than or equal to a partial sum
0 comment threads
JavaScript (Node.js), 47 bytes
f=(a,b=0,c=a=>a&&1/a+c(a-1))=>c(b)<a?f(a,b+1):b
For large numbers, a rounding error will occur and yield incorrect result. The solution below works for any integer (no rounding errors):
93 bytes
f=(a,i=0n,p=a=>g(a)/c(a),g=(a,b=a)=>a&&c(b)/a+g(~-a,b),c=a=>a?a*c(~-a):1n)=>p(i)<a?f(a,-~i):i
0 comment threads
Jelly, 8 bytes
İ€S<¬ʋ1#
How it works
İ€S<¬ʋ1# - Main link. Takes n on the left
ʋ - Group the previous 4 links into a dyad f(k, n):
€ - Over each integer 1 to k:
İ - Get its reciprocal
S - Sum
< - Less than n?
¬ - Logical not
1# - Find the first integer k ≥ n such that f(k, n) is true
0 comment threads
Vyxal, 7 bytes
ɾĖ∑?≥)ṅ
Try it Online! Vyxal has arbitrary-precision rationals, so this will never run into precision errors.
ṅ # Find the first integer
-----) # where
∑ # sum of
Ė # reciprocals of
ɾ # range from 1 to n inclusive
≥ # is at least
? # the input
0 comment threads
J, 23 bytes
>:@]^:(>1#.1%1+i.)^:_&1
>:@]^:(...)^:_&1 Increments from 1 while
>1#.1%1+i. the harmonic sum up to that is less than the input
0 comment threads
0 comment threads