Tantangan

Dengan bilangan bulat positif N, hasilkan jumlah dari Nresiprokal pertama sebagai fraksi yang tepat, yang direpresentasikan sebagai sepasang bilangan bulat dalam urutan yang konsisten yang menunjukkan pembilang dan penyebut.

Aturan

• Keluaran harus tepat.

• Output harus berupa sepasang bilangan bulat dalam urutan yang konsisten yang mewakili pembilang dan penyebut.

• Dilarang menggunakan tipe angka non-integer (built-in atau perpustakaan).

  • Klarifikasi / pengecualian: tipe numerik non-integer baik-baik saja jika dan hanya jika semua nilai yang digunakan, dihitung, dan dikembalikan adalah bilangan bulat (yaitu bahasa Anda menggunakan bilangan rasional secara default, tetapi Anda hanya menggunakan aritmatika bilangan bulat dalam jawaban Anda)

• Keluaran harus dikurangi sebanyak mungkin. ( 3/2tidak apa-apa, 6/4tidak)

• Celah standar dilarang.

• Kiriman harus bekerja untuk input setidaknya hingga 20, atau meta ini , mana yang lebih tinggi.

Uji Kasus

1: 1/1
2: 3/2 (1/1 + 1/2)
3: 11/6 (1/1 + 1/2 + 1/3)
4: 25/12 etc.
5: 137/60
6: 49/20
20: 55835135/15519504
56: 252476961434436524654789/54749786241679275146400
226: 31741146384418617995319820836410246588253008380307063166243468230254437801429301078323028997161/5290225078451893176693594241665890914638817631063334447389979640757204083936351078274058192000

Generasi Uji-Kasus (Python 3)

import fractions
def f(x):
    return sum(fractions.Fraction(1,i) for i in range(1,x+1))

Mirip dengan tantangan ini dan tantangan ini .

Numerator adalah OEIS A001008 , dan penyebutnya OEIS A002805 .

Python 2 , 80 79 byte

D=1;N=n=0;exec"n+=1;y=N=N*n+D;x=D=D*n;"*input()
while y:x,y=y,x%y
print N/x,D/x

Cobalah online!

Mencetak pembilang dan penyebut.

Yay! Dukungan MathJax !!!! Satu mengamati:

$$\sum_{i=1}^{n} \frac{1}{i} = \sum_{i=1}^{n} \frac{n!}{n!i} = \frac{\sum_{i=1}^{n} \frac{n!}{i}}{n!}$$

Kemudian, berpikir tentang rekursi, untuk positif, dalam umerator:$n$N

$$\sum_{i=1}^{n+1} \frac{(n+1)!}{i} = (n+1) \sum_{i=1}^{n} \frac{n!}{i} + \frac{(n+1)!}{n+1} = (n+1) \sum_{i=1}^{n} \frac{n!}{i} + n!$$

dan tidak ada yang bisa memikirkan Denominator secara rekursif juga; dengan demikian$n!$exec .

Kita harus membayar Reduksi Pecahan Fraksi dengan perhitungan GCD di whileloop; dan kemudian kita selesai.

Jelly , 10 byte

!:RS,!:g/$

Cobalah online!

Bagaimana itu bekerja

!:RS,!:g/$  Main link. Argument: n

!           Compute n!.
  R         Range; yield [1, ..., n].
 :          Divide n! by each k in [1, ..., n].
   S        Take the sum. Let's call it s.
     !      Compute n! again.
    ,       Pair; yield [s, n!].
      :g/$  Divide [s, n!] by their GCD.

J , 16 byte

!(,%+.)1#.!%1+i.

Cobalah online!

Jalankan contoh

f =: !(,%+.)1#.!%1+i.
f 6x
   20 49
f 20x
   15519504 55835135
f 56x
   54749786241679275146400 252476961434436524654789

Bagaimana itu bekerja

!(,%+.)1#.!%1+i.    NB. Tacit verb
            1+i.    NB. 1 to n inclusive
          !%        NB. Divide factorial by 1 to n
       1#.          NB. Sum i.e. numerator (not reduced)
!                   NB. Factorial i.e. denominator (not reduced)
 (,%+.)             NB. Divide both by GCD

---

J , 9 byte, menggunakan tipe pecahan

1#.1%1+i.

Cobalah online!

J memberikan pecahan untuk pembagian int-int jika tidak dapat dibagi.

05AB1E , 10 byte

!DIL÷O)D¿÷

Cobalah online!

Menggunakan metode yang sama dengan semua entri lainnya. Output dalam bentuk [denominator, numerator].

!DIL÷O)D¿÷   Full program. Let's call the input I.
!D           Push the factorial twice to the stack. STACK: [I!, I!]
  IL         Range from 1 to I. STACK: [I!, I!, [1 ... I]]
    ÷        Vectorized integer division. STACK: [I!, [I! / 1, I! / 2, ..., I! / I]]
     O       Sum. STACK: [I!, I! / 1 + I! / 2 + ... + I! / I]
      )      Wrap stack. STACK: [[I!, I! / 1 + I! / 2 + ... + I! / I]]
       D     Duplicate. STACK: [[I!, I! / 1 + ... + I! / I], [I!, I! / 1 +... + I! / I]]
        ¿    GCD. STACK: [[I!, I! / 1 + ... + I! / I], gcd(I!, I! / 1 +... + I! / I)]
         ÷   Vectorized integer division. 

Bahasa Wolfram (Mathematica) , 30 byte

#/GCD@@#&@{Tr[#!/Range@#],#!}&

Cobalah online!

---

14 byte jika tipe fraksional bawaan diizinkan

HarmonicNumber

Cobalah online!

JavaScript (ES6), 60 byte

Pengembalian [numerator, denominator].

f=(n,a=0,b=1)=>n?f(n-1,p=a*n+b,q=b*n):b?f(0,b,a%b):[p/a,q/a]

Cobalah online!

Bagaimana?

Metode ini mirip dengan jawaban Python @ ChasBrown .

Kami pertama-tama menghitung pembilang yang tidak direduksi $a$ dan penyebut yang tidak direduksi $b$ dengan memulai dengan $a=0$ dan $b=1$ dan secara rekursif melakukan:

$$a\gets an+b\\ b\gets bn\\ n\gets n-1$$

sampai $n=0$.

Kami menabung $(a,b)$ ke $(p,q)$ dan kemudian menghitung $a\gets \gcd(a,b)$ dengan:

$$a\gets b\\ b\gets a \bmod b$$

sampai $b=0$.

Kami akhirnya mengembalikan pembilang yang dikurangi $p/a$ dan mengurangi penyebut $q/a$.

Perl 6 , 57 53 byte

{+($!=[*] 1..$_)/($!=($/=sum $! X/1..$_)gcd$!),$//$!}

Cobalah online!

Blok kode anonim yang mengambil integer dan mengembalikan tuple denominator, numerator.

Jika kita diizinkan untuk menggunakan tipe fraksional, itu akan menjadi byter yang jauh lebih sederhana:

{sum(map 1/*.FatRat,1..$_).nude}

Cobalah online!

Oktaf , 29 byte

@(n)sym(sprintf('+1/%i',1:n))

Cobalah online!

C ++ 17 (gcc) , 108 byte

Hanya gunakan bilangan bulat aritmatika:

#import<random>
int f(int x,long&n,long&d){n=0;d=1;int
a;while(n=n*x+d,d*=x,a=std::gcd(n,d),n/=a,d/=a,--x);}

Cobalah online!

---

C ++ 17 (gcc) , 108 byte

#import<random>
int f(long&n){double a=0;long
d=1;while(d*=n,a+=1./n,--n);n=a*d+.5;n/=a=std::gcd(n,d);d/=a;}

Cobalah online!

Sama seperti di bawah ini, tetapi gunakan C ++ 17's std::gcd.

---

C ++ (gcc) , 109 byte

#import<regex>
int f(long&n){double a=0;long
d=1;while(d*=n,a+=1./n,--n);n=a*d+.5;n/=a=std::__gcd(n,d);d/=a;}

Cobalah online!

Karena C ++ tidak memiliki dukungan bigint asli, ini pasti akan meluap n>20.

Memerlukan:

• importPernyataan usang gcc .
• gcc std::__gcd.
• -O0(Saya kira begitu) kalau tidak kompiler akan mengoptimalkan keluar d/=a.
• Setidaknya 64-bit long.

Penjelasan:

• Membiarkan $d=n!, a=H_n$.
• Membulatkan a*dke bilangan bulat terdekat dengan melemparkan a*d+.5ke long, dan menetapkan ke n. Sekarang n/dadalah output.
• Sederhanakan fraksi dengan std::__gcd.

Pari / GP , 34 byte

n->l=[sum(i=1,n,n!/i),n!];l/gcd(l)

Cobalah online!

---

17 byte jika tipe fraksional bawaan diizinkan

n->sum(i=1,n,1/i)

Cobalah online!

MATL, 13 byte

:tptb/sht&Zd/

Cobalah di MATL Online

Metode yang sama seperti yang digunakan dalam jawaban Jelly @Dennis .

:t    % Range from 1 to n, duplicate. 
pt    % Take the product of that (= factorial), duplicate that too.     
b/    % Bring the range to top of stack, divide factorial by each element    
sh    % Sum those. Concatenate factorial and this into a single array.     
t&Zd/ % Compute GCD of those and divide the concatenated array elements by the GCD.     

(Output tersirat, mencetak denominator pertama dan kemudian pembilang.)

Ketidakakuratan titik mengambang berarti ini tidak bekerja untuk n = 20, karena nilai menengah terlalu besar.Sepertinya hasil test case adalah salah ketik, ini mengembalikan jawaban yang sama dengan jawaban lain untuk n = 20.

Berikut ini adalah versi pelestarian tipe integer (25 byte) yang saya coba saat itu, sebelum menemukan ini:

25 byte, masukan hingga 43

O1i:3Y%"t@*b@*b+wht&Zd/Z}

Cobalah online!

Melemparkan angka ke uint64sebelum mengoperasikannya, melakukan aritmatika secara eksplisit dalam satu lingkaran (tanpa menggunakan prodatau sum). Lebih penting lagi, membagi pembilang parsial dan penyebut dengan GCD mereka setiap langkah di sepanjang jalan, pada akhir setiap iterasi. Ini meningkatkan rentang input nhingga 43. Sebagian kode didasarkan pada jawaban Python @Chas Brown.

Metode alternatif (asli) menggunakan LCM daripada faktorial:

16 15 byte

:t&Zmtb/sht&Zd/

Cobalah di MATL Online

Excel VBA, 141 byte

Membawa input dari [A1]dan keluaran ke konsol.

s="=If(Row()>A$1,":[B:B]=s+"1,Row())":l=[LCM(B:B)]:[C:C]=s &"0,"&l &"/B1)":g=[GCD(LCM(B:B),SUM(C:C))]:?Format([Sum(C:C)]/g,0)"/"Format(l/g,0)

Tidak Disatukan dan Dikomentari

Sub HarmonicSum(n)
    [A1] = n                            ''  Pipe input
    s = "=IF(ROW()>A$1,"                ''  Hold the start of formulas
    [B1:B40] = s + "1,ROW())"           ''  Get series of numbers 1 to N, trailing 1s
    l = [LCM(B1:B40)]                   ''  Get LCM
    [C1:C40] = s & "0," & l & "/B1)"    ''  Get LCM/M for M in 1 to N
    g = [GCD(LCM(B1:B40),SUM(C1:C40))]  ''  Get GCD
                                        ''  Format and print output
    Debug.Print Format([Sum(C1:C40)] / g, 0); "\"; Format(l / g, 0)
End Sub

dc , 87 byte

?sn1dsNsD[lndlDdlNln*+sN*sD1-dsn1<M]sMln1<MlDsAlNsB[lAlB%sTlBsAlTsBlB0<G]dsGxlDlA/lNlA/

Cobalah online!

Daun ini pembilang dan penyebut di atas tumpukan agar, sebagaimana diizinkan oleh ini keluaran default. Karena dctidak memiliki gcdbuilt-in, ini menggunakan algoritma Euclidean untuk menghitung gcd.

Stax , 11 byte

ó╢Δ'åç4}ú┌7

Jalankan dan debug itu

Penjelasan:

Kami ingin menghitung:

$$\sum_{i=1}^n{\frac 1 i}$$

Kita sekarang membutuhkan penyebut $b$ dan daftar pembilang $a_i$:

$$\sum_{i=1}^n{\frac{a_i}b}=\frac{\sum_{i=1}^n{a_i}}{b}$$

Kita dapat membuat $b=n!$, maka kita memiliki:

$$\begin{align} \frac{a_i}{n!}&=\frac 1 i&|\times n! \\ a_i&=\frac{n!}i \end{align}$$

Jadi kita punya:

$$\sum_{i=1}^n{\frac 1 n}=\frac{\sum_{i=1}^n{\frac{n!}i}}{n!}$$

|Fx{[/m|+L:_m Full program
|F            Factorial
  x           Push input again
   {  m       Map over range [1, n]
    [           Copy the factorial
     /          Divide factorial by current value
       |+     Sum
         L    Listify stack, top gets first element
          :_  Divide both values by gcd
            m Print each followed by newline

APL (NARS), 56 karakter, 112 byte

{⍵=1:⊂1 1⋄{(r s)←⍺⋄(i j)←⍵⋄m÷∨/m←((r×j)+s×i),s×j}/1,¨⍳⍵}

uji:

  f←{⍵=1:⊂1 1⋄{(r s)←⍺⋄(i j)←⍵⋄m÷∨/m←((r×j)+s×i),s×j}/1,¨⍳⍵}
  f 1
1 1 
  f 2
3 2 
  f 3
11 6 
  f 20
55835135 15519504 

Dalam beberapa kata kurangi "fungsi penjumlahan pada 2 bilangan pecahan" (satu bilangan pecahan adalah daftar 2 bilangan bulat) di set:

1 2, 1 3,..., 1 n

ini di bawah ini tampaknya salah:

 f 56
74359641471727289 16124934538402170

tetapi jika saya mengubah jenis input dari:

  f 56x
252476961434436524654789 54749786241679275146400 
  f 226x
31741146384418617995319820836410246588253008380307063166243468230254437801429301078323028997161 529022507845189
  3176693594241665890914638817631063334447389979640757204083936351078274058192000

APL (Dyalog Unicode) , 15 12 byte

⌽!(,÷∨)1⊥!÷⍳

Cobalah online!

Fungsi Tacit, mengambil satu argumen ⍵. Menghemat satu byte dengan menghapus ⌽jika kita diizinkan untuk mencetak penyebut terlebih dahulu.

Terima kasih @dimaima selama 3 byte.

Bagaimana:

⌽!(,÷∨)1⊥!÷⍳ ⍝ Tacit function, argument will be called ⍵.
           ⍳ ⍝ Range 1..⍵ 
          ÷  ⍝ Dividing
         !   ⍝ the factorial of ⍵
       1⊥    ⍝ Base-1 decode, aka sum;
 !(   )      ⍝ Using that sum and the factorial of ⍵ as arguments, fork:
     ∨       ⍝ (GCD
    ÷        ⍝ dividing
   ,         ⍝ the vector with both arguments)
⌽            ⍝ reversed.