Exact generalised harmonic numbers

Question

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 code-golf, 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

\$\begingroup\$ Brownie points for beating/matching my 4 byte M answer \$\endgroup\$
– caird coinheringaahin g ♦
May 18, 2021 at 0:40 — caird coinheringaahin g, May 18, 2021 at 0:40
\$\begingroup\$ Related. Related \$\endgroup\$
– caird coinheringaahin g ♦
May 18, 2021 at 0:41 — caird coinheringaahin g, May 18, 2021 at 0:41

hyper-neutrino · Accepted Answer · 2021-05-18 00:46:05Z

9

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

answered May 18, 2021 at 0:46

hyper-neutrino♦

40.8k5 gold badges65 silver badges219 bronze badges

3

\$\begingroup\$ What kind of language is M? The README just has an.... M. \$\endgroup\$
– Jonah
May 18, 2021 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, 2021 at 3:09

Add a comment |

att · Accepted Answer · 2021-05-18 02:13:22Z

6

Wolfram Language (Mathematica), 14 bytes

HarmonicNumber

Try it online!

Naturally.

Alternatively, 16 bytes without the built-in:

Tr[Range@#^-#2]&

Try it online!

answered May 18, 2021 at 2:13

att

18.7k2 gold badges13 silver badges54 bronze badges

\$\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, 2021 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, 2021 at 2:22

Add a comment |

Sean · Accepted Answer · 2021-05-18 01:17:58Z

5

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.

answered May 18, 2021 at 1:17

Sean

7,3769 silver badges15 bronze badges

Add a comment |

Arnauld · Accepted Answer · 2021-05-18 01:55:19Z

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 2^nd 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]

Jonah · Accepted Answer · 2021-05-18 02:43:57Z

5

J, 13 bytes

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

Try it online!

answered May 18, 2021 at 2:43

Jonah

31.5k4 gold badges35 silver badges88 bronze badges

Add a comment |

Unrelated String · Accepted Answer · 2021-05-18 01:41:05Z

4

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.

edited May 18, 2021 at 1:41

answered May 18, 2021 at 1:18

Unrelated String

18.9k3 gold badges27 silver badges51 bronze badges

1

\$\begingroup\$ I feel like there's some ð chaining able to be done here, but I can't figure anything out :/ \$\endgroup\$
– caird coinheringaahin g ♦
May 18, 2021 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, 2021 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, 2021 at 13:10

Add a comment |

caird coinheringaahin g · Accepted Answer · 2021-05-19 00:12:53Z

4

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;}

edited May 19, 2021 at 0:12

caird coinheringaahin g♦

48.5k10 gold badges115 silver badges342 bronze badges

answered May 18, 2021 at 1:23

Unmitigated

2,7291 gold badge4 silver badges14 bronze badges

Add a comment |

chunes · Accepted Answer · 2021-05-18 02:38:06Z

3

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.

edited May 18, 2021 at 2:38

answered May 18, 2021 at 2:00

chunes

18.3k3 gold badges18 silver badges45 bronze badges

2

\$\begingroup\$ 24 bytes \$\endgroup\$
– Bubbler
May 18, 2021 at 2:32
\$\begingroup\$ @Bubbler Wow, very nice! \$\endgroup\$
– chunes
May 18, 2021 at 2:38

Add a comment |

Bubbler · Accepted Answer · 2021-05-18 03:23:33Z

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

Wasif · Accepted Answer · 2021-05-18 07:38:32Z

3

Vyxal, 14 bytes

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

Try it Online!

edited May 18, 2021 at 7:38

answered May 18, 2021 at 6:53

Wasif

12.2k1 gold badge16 silver badges46 bronze badges

Add a comment |

xigoi · Accepted Answer · 2021-05-18 09:00:13Z

3

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!

answered May 18, 2021 at 9:00

xigoi

6,6631 gold badge9 silver badges21 bronze badges

Add a comment |

NoLongerBreathedIn · Accepted Answer · 2021-05-18 01:23:57Z

2

Haskell, 28 bytes

n#m=sum$map((1%).(^m))[1..n]

answered May 18, 2021 at 1:23

NoLongerBreathedIn

1,6977 silver badges11 bronze badges

1

\$\begingroup\$ I think this requires an import to Data.Ratio to get %: Try it online \$\endgroup\$
– xnor
May 18, 2021 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, 2021 at 2:07
\$\begingroup\$ I admit it does. Does that cost any extra bytes, and if so, how many? \$\endgroup\$
– NoLongerBreathedIn
May 18, 2021 at 3:49
1

\$\begingroup\$ With the import, you just include it as part of the code like this. \$\endgroup\$
– xnor
May 18, 2021 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, 2021 at 8:33

Add a comment |

Razetime · Accepted Answer · 2021-05-18 04:45:41Z

2

Stax, 6 bytes

ê☺σ;vù

Run and debug it

just another trivial answer.

answered May 18, 2021 at 4:45

Razetime

26.6k3 gold badges26 silver badges71 bronze badges

Add a comment |

G B · Accepted Answer · 2021-05-18 06:34:48Z

2

Ruby, 27 bytes

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

Try it online!

answered May 18, 2021 at 6:34

G B

19.9k1 gold badge19 silver badges50 bronze badges

\$\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\$
– user100752
May 18, 2021 at 9:36
\$\begingroup\$ It would not work on TIO, so I prefer to keep it this way. \$\endgroup\$
– G B
May 18, 2021 at 11:36

Add a comment |

Noodle9 · Accepted Answer · 2021-05-18 12:17:31Z

2

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.

edited May 18, 2021 at 12:17

answered May 18, 2021 at 12:07

Noodle9

19.5k3 gold badges19 silver badges45 bronze badges

Add a comment |

Ruan · Accepted Answer · 2021-05-25 10:19:49Z

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 -- (⊢÷∨/).

Welcome to Code Golf, and nice first answer! Be sure to check out our Tips for golfing in APL page for ways you can golf your program, and check out the APL Orchard, a chat room for APL — caird coinheringaahin g, May 21, 2021 at 14:23

Axuary · Accepted Answer · 2021-05-18 11:15:19Z

1

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

answered May 18, 2021 at 11:15

Axuary

3,3664 silver badges11 bronze badges

Add a comment |

Neil · Accepted Answer · 2021-05-18 11:25:09Z

Charcoal, 40 bytes

≔Ｘ…·¹ＮＮθ≔Πθη≔Σ÷ηθζ⊞υζ⊞υηＷζ«≔﹪ηιζ≔ιη»Ｉ÷υη

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

≔Ｘ…·¹ＮＮθ

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.

Ｗζ«≔﹪ηιζ≔ιη»

Find the GCD.

Ｉ÷υη

Divide the saved values by the GCD.

Chris Bouchard · Accepted Answer · 2021-05-19 03:48:51Z

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.

elementiro · Accepted Answer · 2021-05-20 20:54:29Z

1

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}$ ).

answered May 20, 2021 at 20:54

elementiro

8781 gold badge4 silver badges10 bronze badges

Add a comment |

Stack Exchange Network

Exact generalised harmonic numbers

Test cases

20 Answers 20

M, 4 bytes

Wolfram Language (Mathematica), 14 bytes

Raku, 29 bytes

JavaScript (ES7), 68 bytes

JavaScript (ES7), 69 bytes

How?

J, 13 bytes

Jelly, 13 12 bytes

Java, 155 138 bytes

Java + Commons Lang 2, 127 bytes

Factor + `math.unicode`, 35 24 bytes

Explanation:

J, 11 bytes

How it works

Vyxal, 14 bytes

Nim, 81 bytes

Haskell, 28 bytes

Stax, 6 bytes

Ruby, 27 bytes

Python 3.8, 91 bytes

APL(Dyalog Unicode), 31 27 bytes ^SBCS

Excel, 70 bytes

Charcoal, 40 bytes

Core Maude, 111 bytes

Example Session

Ungolfed

MATLAB/Octave, 25 bytes

Your Answer

Not the answer you're looking for? Browse other questions tagged
code-golf
math
rational-numbers
or ask your own question.

Linked

Hot Network Questions

Exact generalised harmonic numbers

Test cases

20 Answers 20

M, 4 bytes

Wolfram Language (Mathematica), 14 bytes

Raku, 29 bytes

JavaScript (ES7), 68 bytes

JavaScript (ES7), 69 bytes

How?

J, 13 bytes

Jelly, 13 12 bytes

Java, 155 138 bytes

Java + Commons Lang 2, 127 bytes

Factor + math.unicode, 35 24 bytes

Explanation:

J, 11 bytes

How it works

Vyxal, 14 bytes

Nim, 81 bytes

Haskell, 28 bytes

Stax, 6 bytes

Ruby, 27 bytes

Python 3.8, 91 bytes

APL(Dyalog Unicode), 31 27 bytes SBCS

Excel, 70 bytes

Charcoal, 40 bytes

Core Maude, 111 bytes

Example Session

Ungolfed

MATLAB/Octave, 25 bytes

Your Answer

Sign up or log in

Post as a guest

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

Linked

Related

Hot Network Questions

Factor + `math.unicode`, 35 24 bytes

APL(Dyalog Unicode), 31 27 bytes ^SBCS

Not the answer you're looking for? Browse other questions tagged
code-golf
math
rational-numbers
or ask your own question.