18
\$\begingroup\$

The generalised harmonic number of order \$m\$ of \$n\$ is

$$H_{n,m} = \sum_{k=1}^n \frac 1 {k^m}$$

For example, the harmonic numbers are \$H_{n,1}\$, and \$H_{\infty,2} = \frac {\pi^2} 6\$. These are related to the Riemann zeta function as

$$\zeta(m) = \lim_{n \to \infty} H_{n,m}$$

Given two positive integers \$n > 0\$, \$m > 0\$, output the exact rational number \$H_{n,m}\$. The fraction should be reduced to its simplest term (i.e. if it is \$\frac a b\$, \$\gcd(a, b) = 1\$). You may output as a numerator/denominator pair, a rational number or any clear value that distinguishes itself as a rational number. You may not output as a floating point number.

This is , so the shortest code in bytes wins

Test cases

n, m -> Hₙ,ₘ
3, 7 -> 282251/279936
6, 4 -> 14011361/12960000
5, 5 -> 806108207/777600000
4, 8 -> 431733409/429981696
3, 1 -> 11/6
8, 3 -> 78708473/65856000
7, 2 -> 266681/176400
6, 7 -> 940908897061/933120000000
2, 8 -> 257/256
5, 7 -> 2822716691183/2799360000000
\$\endgroup\$
2

20 Answers 20

9
\$\begingroup\$

M, 4 bytes

Rİ*S

Try it online!

Obligatory trivial answer ;-;

Rİ*S  Main Link; takes n on the left and m on the right
R     Range: [1, 2, 3, ..., n]
 İ    Inverse/Reciprocal: [1, 1/2, 1/3, ..., 1/n]
  *   Exponent: [1, 1/2^m, 1/3^m, ..., 1/n^m]
   S  Sum
\$\endgroup\$
2
  • 3
    \$\begingroup\$ What kind of language is M? The README just has an.... M. \$\endgroup\$ – Jonah May 18 at 2:55
  • 3
    \$\begingroup\$ @Jonah it's Jelly but using Python's sympy for infinite precision math. Or rather, an extremely outdated revision of Jelly lol \$\endgroup\$ – hyper-neutrino May 18 at 3:09
5
\$\begingroup\$

Raku, 29 bytes

{sum((1/1..$^n)X**-$^m).nude}

Try it online!

This function takes two arguments, $^m and $^n. 1/1 .. $^n is a sequence of rational numbers from 1 to the second argument. X** -$^m produces the exponentiated cross product of that list with the negative of the first argument. sum sums those rational numbers, and .nude produces a two-element list of the numerator and denominator of the sum.

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

JavaScript (ES7), 68 bytes

A 1-byte shorter, slightly less readable version with a single recursive call. This is otherwise identical to the commented version below.

m=>g=(n,N=0,D=1)=>D?g(n-!!n,n?p=N*n**m+D:D,n?q=D*n**m:N%D):[p/N,q/N]

Try it online!


JavaScript (ES7), 69 bytes

Expects (m)(n). Returns [numerator, denominator].

m=>g=(n,N=0,D=1)=>n?g(n-1,p=N*n**m+D,q=D*n**m):D?g(0,D,N%D):[p/N,q/N]

Try it online!

How?

The recursive function \$g\$ first computes the unreduced numerator and denominator \$(N,D)\$ of \$H_{n,m}\$ and saves a copy of the final result into \$(p,q)\$:

n ? g(n - 1, p = N * n**m + D, q = D * n**m) : ...

When \$n=0\$, it enters its 2nd phase where the GCD of \$(p,q)\$ is computed in \$N\$:

... : D ? g(0, D, N % D) : ...

When \$D=0\$, it eventually returns:

... : [p / N, q / N]
\$\endgroup\$
5
\$\begingroup\$

Wolfram Language (Mathematica), 14 bytes

HarmonicNumber

Try it online!

Naturally.


Alternatively, 16 bytes without the built-in:

Tr[Range@#^-#2]&

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ I get the feeling there have been Wolfram answers where the built-in is longer than the non-built-in answer. \$\endgroup\$ – chunes May 18 at 2:14
  • 1
    \$\begingroup\$ @chunes One example given in the Mathematica golfing tips thread is EuclideanDistance: it's always shorter to write (Norm[#-#2]&). \$\endgroup\$ – att May 18 at 2:22
5
\$\begingroup\$

J, 13 bytes

1#.(%@^~1+i.)

Try it online!

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

Jelly, 13 12 bytes

*€:@S,:gɗɗP$

Try it online!

A byte less than *€µP:¹S,P:g/$, but the abuse of ɗ leads me to believe this can be shorter yet.

*€              Raise each 1 .. n to the power of m.
         ɗP$    For that list and the product of its elements:
  :@            divide each by the product
    S           and sum;
        ɗ       for that sum:
     ,          pair it with the product,
      :         and divide both by
       g        the GCD of the sum and product.
\$\endgroup\$
3
  • 1
    \$\begingroup\$ I feel like there's some ð chaining able to be done here, but I can't figure anything out :/ \$\endgroup\$ – caird coinheringaahing May 18 at 1:39
  • \$\begingroup\$ @cairdcoinheringaahing Outputting reversed pairs, this is the same length, so maybe you're on to something \$\endgroup\$ – Unrelated String May 18 at 2:20
  • 1
    \$\begingroup\$ I've not manged to find a save here but I do have *€µṭP:\§µ:g/ and half a dozen variants (all outputting [denominator, numerator]) if it helps anyone. \$\endgroup\$ – Jonathan Allan May 18 at 13:10
4
\$\begingroup\$

Java, 155 138 bytes

int g(int a,int b){return b<1?a:g(b,a%b);}
m->n->{int p=1,d=0,t;for(;n>0;d=d*t+p,p*=t)t=(int)Math.pow(n--,m);return d/g(d,p)+"/"+p/g(d,p);}

Try it online!

$$Denominator_{n, m} = \prod_{k=1}^n k^m$$

$$Numerator_{n,m} = \sum_{k=1}^n \frac {Denominator_{n,m}} {k^m} = Numerator_{n-1,m} \times k^m + Denominator_{n-1,m}$$

Java + Commons Lang 2, 127 bytes

m->n->{org.apache.commons.lang.math.Fraction x=null;for(x=x.ZERO;n>0;)x=x.add(x.getFraction(1,(int)Math.pow(n--,m)));return x;}
\$\endgroup\$
3
\$\begingroup\$

Factor + math.unicode, 35 24 bytes

[ [1,b] 0 rot - v^n Σ ]

Try it online!

-11 thanks to @Bubbler!

Explanation:

It's a quotation (anonymous function) that takes two integers from the data stack as input and leaves a fully-reduced mixed fraction (it's simply the way that Factor is) on the data stack as output.

  • [1,b] Make a range from 1 to n.
  • 0 rot Push 0 and bring m to the top of the stack.
  • - Subtract m from 0.
  • v^n Raise every element in the range to the -m power.
  • Σ Sum.
\$\endgroup\$
2
  • 2
    \$\begingroup\$ 24 bytes \$\endgroup\$ – Bubbler May 18 at 2:32
  • \$\begingroup\$ @Bubbler Wow, very nice! \$\endgroup\$ – chunes May 18 at 2:38
3
\$\begingroup\$

J, 11 bytes

1#.#\@$^-@]

Try it online!

TFW J beats Jelly...

Used as n f m, where n and m are given as extended-precision integers.

How it works

1#.#\@$^-@]    NB. dyadic train; left = n, right = m
   #\@$        NB. 1..n in a dyadic context:
     @$        NB.   reshape m into dimension n, and then
   #\          NB.   get the lengths of prefixes
       ^       NB. each raised to the power of
        -@]    NB. -m
1#.            NB. sum of them
\$\endgroup\$
3
\$\begingroup\$

Vyxal, 14 bytes

ɾ$eDΠ$/∑$Π":ġ/

Try it Online!

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

Nim, 81 bytes

import math,rationals
func H(n,m:int):any=
 var r=0//1;for i in 1..n:r+=1//i^m
 r

Try it online!

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

Haskell, 28 bytes

n#m=sum$map((1%).(^m))[1..n]
\$\endgroup\$
5
  • 1
    \$\begingroup\$ I think this requires an import to Data.Ratio to get %: Try it online \$\endgroup\$ – xnor May 18 at 1:53
  • 1
    \$\begingroup\$ Though you can also force a rational output with normal arithmetic by specifying the type explicitly: Try it online \$\endgroup\$ – xnor May 18 at 2:07
  • \$\begingroup\$ I admit it does. Does that cost any extra bytes, and if so, how many? \$\endgroup\$ – NoLongerBreathedIn May 18 at 3:49
  • 1
    \$\begingroup\$ With the import, you just include it as part of the code like this. \$\endgroup\$ – xnor May 18 at 7:53
  • 1
    \$\begingroup\$ A few tips. 1) You can import GHC.Real instead of Data.Ratio for -2 bytes. 2) Using a list comprehension, you can shorten your code a bit: n#m=sum[1%k^m|k<-[1..n]]. 3) Instead of importing Data.Ratio or ` GHC.Real, you can actually use the Prelude` function toRational: n#m=sum[1/toRational k^m|k<-[1..n]], for a total of 35 bytes. \$\endgroup\$ – Delfad0r May 18 at 8:33
2
\$\begingroup\$

Stax, 6 bytes

ê☺σ;vù

Run and debug it

just another trivial answer.

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

Ruby, 27 bytes

->n,m{(1..n).sum{|x|x**-m}}

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ You can update your answer to ruby 2.7+ to make use of numbered arguments and save 2 bytes ->n,m{(1..n).sum{_1**-m}} \$\endgroup\$ – EliteDaMyth May 18 at 9:36
  • \$\begingroup\$ It would not work on TIO, so I prefer to keep it this way. \$\endgroup\$ – G B May 18 at 11:36
2
\$\begingroup\$

Python 3.8, 91 bytes

import math
f=lambda n,m,N=0,D=1:n and f(n-1,m,N*n**m+D,D*n**m)or(N/(G:=math.gcd(N,D)),D/G)

Try it online!

Inputs \$n\$ and \$m\$ and returns the numerator and denominator of \$H_{n,m}\$ as a tuple.

Uses the formula from Arnauld's JavaScript answer.

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

APL(Dyalog Unicode), 31 27 bytes SBCS

{(⊢÷∨/){⍵,⍨+/⍵÷x}∧/x←⍵*⍨⍳⍺}

Try it on APLgolf!

(⊢÷∨/){⍵,⍨+/⍵÷x}∧/x←⍵*⍨⍳⍺ is equivelent to x←(⍳⍺)*⍵⋄(⊢÷∨/){⍵,⍨+/⍵÷x}∧/x. APL translated to Python:

from math import *

def H(n, m):
    x = [i**m for i in range(1,n+1)] # x←(⍳⍺)*⍵
    tmp = lcm(*x) # ∧/x
    tmp = (sum(tmp//i for i in x), tmp) # {⍵,⍨+/⍵÷x}
    tmp = [e//gcd(*tmp) for e in tmp] # (⊢÷∨/)
    return tmp

First I make a list from 1 to n -- ⍳⍺. Then I raise every element of the list to the power of m to calculate the value of all the denominators, and assign it to the variable x -- x ← (⍳⍺)*⍵.

I then calculate the denominator after all the fractions are added together by taking the least common multiple of all the elements of x (all the denominators) -- ∧/x.

Next I create a two element tuple, the second element of which is the denominator -- {⍵,⍨...}. The first element is the numerator, calculated as the sum of the denominator divided by each of the original denominators -- +/⍵÷x.

Lastly, I simplify the fraction by dividing it by it's gcd -- (⊢÷∨/).

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

Excel, 70 bytes

=LET(k,SEQUENCE(A1)^B1,d,PRODUCT(k),n,SUM(d/k),g,GCD(n,d),n/g&"/"&d/g)

Link to Spreadsheet

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

Charcoal, 40 bytes

≔X…·¹NNθ≔Πθη≔Σ÷ηθζ⊞υζ⊞υηWζ«≔﹪ηιζ≔ιη»I÷υη

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

≔X…·¹NNθ

Generate the first n powers of m.

≔Πθη≔Σ÷ηθζ

Calculate the product, then divide that by each power and take the sum.

⊞υζ⊞υη

Save the values for later.

Wζ«≔﹪ηιζ≔ιη»

Find the GCD.

I÷υη

Divide the saved values by the GCD.

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

Core Maude, 111 bytes

fmod H is pr RAT . op __ : Nat Nat -> Rat . vars N M : Nat . eq 0 M = 0 . eq(s N)M = 1 / s N ^ M +(N M) . endfm

Example Session

             \||||||||||||||||||/
           --- Welcome to Maude ---
             /||||||||||||||||||\
         Maude 3.1 built: Oct 12 2020 20:12:31
         Copyright 1997-2020 SRI International
           Tue May 18 23:37:06 2021
Maude> fmod H is pr RAT . op __ : Nat Nat -> Rat . vars N M : Nat . eq 0 M = 0 . eq(s N)M = 1 / s N ^ M +(N M) . endfm
Maude> red 3 7 .
reduce in H : 3 7 .
rewrites: 17 in 0ms cpu (0ms real) (17206 rewrites/second)
result PosRat: 282251/279936
Maude> red 6 4 .
reduce in H : 6 4 .
rewrites: 40 in 0ms cpu (0ms real) (~ rewrites/second)
result PosRat: 14011361/12960000
Maude> red 3 1 .
reduce in H : 3 1 .
rewrites: 17 in 0ms cpu (0ms real) (~ rewrites/second)
result PosRat: 11/6
Maude> red 2 8 .
reduce in H : 2 8 .
rewrites: 10 in 0ms cpu (0ms real) (~ rewrites/second)
result PosRat: 257/256
Maude> red 5 7 .
reduce in H : 5 7 .
rewrites: 32 in 0ms cpu (0ms real) (~ rewrites/second)
result PosRat: 2822716691183/2799360000000

Ungolfed

fmod GENERALIZED-HARMONIC-NUMBERS is
    protecting RAT .
    op H : Nat Nat -> Rat .
    vars N M : Nat .
    eq H(0, M) = 0 .
    eq H(s N, M) = 1 / (s N ^ M) + H(N, M) .
endfm

H(N, M) is the naive recursive definition of \$H_{n, m}\$. Maude's built-in rational number module automatically reduces fractions to lowest common denominator.

There's not much golfing we can do because only a handful of characters can separate identifiers ((, ), [, ], {, }, ,, and space). I've renamed the function operator H to __ (juxtaposition of two values) in the golfed version to save a few bytes.

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

MATLAB/Octave, 25 bytes

@(n,m)sum(1./sym(1:n).^m)

Try it online!
Anonymous function. Returns accurate value of symbolic type, which can represent real numbers (so rational numbers including).
Unfortunatelly, to my suprise, MATLAB doesn't implement that function, only non-generalized harmonic numbers (so only for m=1).

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