Wcześniej robiliśmy pseudofactorial z liczby, która jest LCM liczb od 1do n.

Przydałoby się dodać razem ułamki.

Okazuje się jednak, że mianownik 1/1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6jest 20zamiast pseudo czynnikowego 6, który jest 60.

Twoim zadaniem jest znalezienie mianownika 1/1 + 1/2 + ... + 1/npodanej dodatniej liczby całkowitej n.

Przypadki testowe

 n result
 1 1
 2 2
 3 6
 4 12
 5 60
 6 20
 7 140
 8 280
 9 2520
10 2520
11 27720
12 27720
13 360360
14 360360
15 360360
16 720720
17 12252240
18 4084080
19 77597520
20 15519504
21 5173168
22 5173168
23 118982864
24 356948592
25 8923714800
26 8923714800
27 80313433200
28 80313433200
29 2329089562800
30 2329089562800

• Lista dla nod 1do200 .
• Lista dla nod 1do1000 .
• Lista dla nod 1do10000 .

Bibliografia

• Obowiązkowy OEIS A002805 (dzięki @FryAmTheEggman )

Tabela liderów

var QUESTION_ID=82815,OVERRIDE_USER=48934;function answersUrl(e){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"http://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;

body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>

M , 9 6 bajtów

Dzięki FryAmTheEggman za oszczędność 3 bajtów! Kod:

RİSg¹İ

M ma tutaj ogromną przewagę, ponieważ działa raczej z ułamkami niż pływakami. Wyjaśnienie:

R       # Get the list [1 ... n].
 İ      # Inverse each, resulting into [1/1, 1/2, 1/3, ..., 1/n].
  S     # Sum it up. (86021/27720 for n=12)
   g¹   # Compute the greatest common denominator with n. (1/27720 for n=12)
     İ  # Calculate the inverse again. (27720 for n=12)

Wykorzystuje kodowanie Jelly . Wypróbuj online! .

Istnieje również rozwiązanie 4-bajtowe , które czasami wyświetla wiodące zero (np 280 -> 0280.). Nie jestem pewien, czy jest to dozwolone, czy nie:

RİSV

Wypróbuj online! .

Julia, 22 bajty

Anonimowa funkcja.

n->1.//(1:n)|>sum|>den

Mathematica, 27 bajtów

Anonimowa funkcja.

Denominator@*HarmonicNumber

Na przykład:

 In[1] := (Denominator@*HarmonicNumber)[10]
 Out[1] = 2520

Python 2, 69 67 bajtów

a=b=k=r=1
exec'a=a*k+b;b*=k;k+=1;'*input()
while r*a%b:r+=1
print r

Przetestuj na Ideone .

Jak to działa

Niech H (n) będzie sumą odwrotności multiplikatywnej pierwszych n dodatnich liczb całkowitych. Przez cały czas mamy a / b = 1 + H (k - 1) . W rzeczywistości wszystkie a , b i k są inicjowane na 1 , a 1/1 = 1 = 1 + H (0) .

Powtarzamy fragment kodu

a=a*k+b;b*=k;k+=1;

(jako ciąg) n (dane wejściowe) razy i wykonaj wynik. Na każdym etapie aktualizujemy a , b i k przy użyciu tożsamości a / b + 1 / k = ak / bk + b / bk = (ak + b) / bk .

Po wykonaniu wszystkich kopii a / b = 1 + H (n) , który ma ten sam mianownik co H (n) .

Całkowicie zredukowana postać a / b to (a ÷ gcd (a, b)) / (b ÷ gcd (a, b)) . Zamiast obliczać największy wspólny dzielnik, inicjalizujemy r jako 1 i zwiększamy r, aż ra będzie wielokrotnością b .

Oczywiście sprawia to, że ra jest najmniejszą wspólną wielokrotnością a i b . Ponieważ gcd (a, b) · lcm (a, b) = ab , mamy to, że b ÷ gcd (a, b) = lcm (a, b) ÷ a = ra ÷ a = r , co daje r pożądaną moc wyjściową.

Haskell, 52

Import Data.Ratio
f n=denominator$sum[1%k|k<-[1..n]]

Jeśli plik jest załadowany do GHCI, f może być użyte jako funkcja.

Galaretka, 9 bajtów

!©÷RSg®®÷

Wypróbuj tutaj.

             Argument: n
! ÷R         Compute [n!÷1, n!÷2, … n!÷n].
 ©             (And store n! in the register.)
    S        Find the sum of this list.
     g®      GCD with n!.
       ®÷    Divide n! by this GCD.

MATL , 14 13 bajtów

:p:G:!/s1\&X<

Wypróbuj online!

Wyjaśnienie

W przypadku wejścia N dane wyjściowe są ograniczone przez N ! (silnia N ). Kod oblicza n / k dla n = 1, ..., N ! i dla k = 1, ..., N . Następnie sumuje się nad k , co daje liczbę harmoniczną pomnożoną przez każdy n . Pożądanym wynikiem jest indeks n pierwszej z tych wartości, która jest liczbą całkowitą.

Ruby, 57 47 bajtów

->n{(1..n).reduce{|a,i|a+1.to_r/i}.denominator}

Dzięki Kevinowi Lau za skrócenie tego o dziesięć bajtów.

Mathematica, 26 bajtów

Denominator@Tr[1/Range@#]&

Funkcja bez nazwy, która przyjmuje ndane wejściowe i zwraca mianownik. Wykorzystuje standardową sztuczkę polegającą na nadużywaniu Tr(śledzenie), aby zsumować listę wzajemności.

JavaScript (ES6), 88 bajtów

m=>{for(d=1,i=0;i<m;d*=++i);for(n=i=0;i<m;n+=d/++i);for(g=d;g;[g,n]=[n%g,g]);return d/n}

Działa tylko do m = 20 z powodu ograniczeń precyzji liczbowej JavaScript.

05AB1E , 8 bajtów

Kod:

!йL/O¿/

Wyjaśnienie:

!         # Take the factorial of the input.
 Ð        # Triplicate this.
  ¹L      # Get the list [1 ... input].
    /O    # Divide and sum up.
      ¿   # Get the GCD of the sum and the factorial.
       /  # Divide the factorial by this.

Mogą wystąpić pewne problemy z dokładnością dla n> 19 z powodu podziału Pythona ... Używa kodowania CP-1252 .

Wypróbuj online! .

Pari / GP , 30 bajtów

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

Wypróbuj online!

J, 20 bajtów

(!%!+.[:+/!%1+i.)@x:

W oparciu o podejście zastosowane w rozwiązaniu @ Lynn .

Jeśli precyzja nie jest konieczna dla dużych wartości n lub jeśli możemy założyć, że n zostanie przekazana jako rozszerzona liczba całkowita, z przyrostkiem x, można zastosować krótsze rozwiązanie dla 15 bajtów .

!%!+.[:+/!%1+i.

Stosowanie

   f =: (!%!+.[:+/!%1+i.)@x:
   f 30
2329089562800
   (,:f"0) >: i. 15
1 2 3  4  5  6   7   8    9   10    11    12     13     14     15
1 2 6 12 60 20 140 280 2520 2520 27720 27720 360360 360360 360360

Wyjaśnienie

(!%!+.[:+/!%1+i.)@x:  Input: n
                  x:  Convert n into an extended integer
              i.      Creates the range [0, 1, ..., n-1]
            1+        Add one to each, range is now [1, 2, ..., n]
          !           Get factorial of n
           %          Divide n! by each value in the range [1, 2, ..., n]
      [:+/            Sum those values
   !                  Get n!
    +.                Get gcd between n! and the sum
 !                    Get n!
  %                   Divide n! by the gcd and return

Perl 6 ,  36  32 bajtów

{([+] 1.FatRat X/1..$_).denominator}
{([+] 1.FatRat X/1..$_).nude[1]}

Wyjaśnienie:

{
  (
    [+]        # reduce with &infix:<+>

      # the following produces a Seq of Rational numbers
      # 1/1, 1/2, 1/3 ... 1/n

      1.FatRat # FatRat.new: 1,1
      X/       # crossed using &infix:</>
      1 .. $_  # Range from 1 to the input inclusive

  ) # resulting in a FatRat

  .nude # (nu)merator (de)nominator
  .[1]  # grab the denominator
}

Test:

my &hd = {([+] 1.FatRat X/1..$_).nude[1]}

say (1..10)».&hd; # (1 2 6 12 60 20 140 280 2520 2520)

say hd 100; # 2788815009188499086581352357412492142272
say chars hd 1000; # 433
say chars hd 10000; # 4345

Hoon , 95 bajtów

|=
@
=+
n=(gulf 1 +<)
=+
f=(roll n mul)
(div f d:(egcd f (roll (turn n |=(@ (div f +<))) add)))

Utwórz listę [1...n], złóż ją ++mulza pomocą silni, stwórz listę [n!/1, n!/2, ... n!/n]i zsumuj, znajdź GCD zn! i listę i podziel silnię przez tę liczbę.

Prawdopodobnie istnieje o wiele łatwiejszy sposób obliczenia mianownika, ale nie mogę tego rozgryźć: /

Python 3, 153 150 146 142 bajtów

Jestem pewien, że można pograć w golfa dalej. Ale jestem tu nowy

f=lambda x:0**x or x*f(x-1)
z=int(input());i=f(z)
r=sum(i/y for y in range(1,z+1))  
p=lambda a,b:a if b<1else not a%b+b or p(b,a%b)
print(i/p(r,i))

Aksjomat, 34 bajty

f(x)==denominator(sum(1/n,n=1..x))

test

(24) -> [[i,f(i)] for i in 1..30]
   (24)
   [[1,1], [2,2], [3,6], [4,12], [5,60], [6,20], [7,140], [8,280], [9,2520],
    [10,2520], [11,27720], [12,27720], [13,360360], [14,360360], [15,360360],
    [16,720720], [17,12252240], [18,4084080], [19,77597520], [20,15519504],
    [21,5173168], [22,5173168], [23,118982864], [24,356948592],
    [25,8923714800], [26,8923714800], [27,80313433200], [28,80313433200],
    [29,2329089562800], [30,2329089562800]]
                                       Type: List List Expression Integer

PHP, 81 bajtów

for($p=1;$z++<$argn;$n=$n*$z+$p/$z)$p*=$z;for($t=1+$n;$p%--$t||$n%$t;);echo$p/$t;

Wypróbuj online!