Soma parcial exata da série harmônica

15

Desafio

Dado um número inteiro positivo N, produza a soma dos primeiros Nrecíprocos como uma fração exata, que é representada como um par de números inteiros em uma ordem consistente, representando numerador e denominador.

Regras

  • A saída deve ser exata.

  • A saída deve ser como um par de números inteiros em uma ordem consistente, representando numerador e denominador.

  • É proibido o uso de tipos numéricos não inteiros (integrados ou biblioteca).

    • Esclarecimento / exceção: tipos numéricos não inteiros são válidos se, e somente se, todos os valores usados, computados e retornados forem números inteiros (por exemplo, seu idioma usa números racionais por padrão, mas você só usa aritmética inteira em sua resposta)
  • A saída deve ser o mais reduzida possível. ( 3/2está tudo bem, 6/4não está)

  • As brechas padrão são proibidas.

  • Os envios devem funcionar para entradas de no mínimo 20, ou essa meta , o que for maior.

Casos de teste

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

Geração de casos de teste (Python 3)

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

Semelhante a este desafio e este desafio .

Os numeradores são OEIS A001008 e os denominadores são OEIS A002805 .

pizzapants184
fonte
Publicação de
relacionado
Leaky Nun
É gcduma "função interna" se o seu idioma fornecer?
Chas Brown
@ChasBrown gcde outras funções internas estão bem. Tipos racionais / fracionários não são permitidos.
Pizzapants184
1
@JoKing Tudo bem se os números forem do tipo racional, contanto que apenas números inteiros sejam usados. Vou atualizar a pergunta.
pizzapants184

Respostas:

8

Python 2 , 80 79 bytes

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

Experimente online!

Imprime o numerador e o denominador.

Yay! Suporte MathJax !!!! Observa-se:

i=1n1i=i=1nn!n!i=i=1nn!in!

Então, pensando em recursão, para positivo, no umerador:nN

i=1n+1(n+1)!i=(n+1)i=1nn!i+(n+1)!n+1=(n+1)i=1nn!i+n!

e não se pode deixar de pensar no Denominador recursivamente também; assim o .n!exec

Devemos pagar o Piper de frações reduzidas com um cálculo de GCD no whileloop; e então terminamos.

Chas Brown
fonte
7

Gelatina , 10 bytes

!:RS,!:g/$

Experimente online!

Como funciona

!: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.
Dennis
fonte
5

J , 16 bytes

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

Experimente online!

Executar exemplos

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

Como funciona

!(,%+.)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 bytes, usando o tipo de fração

1#.1%1+i.

Experimente online!

J fornece frações para a divisão int-int, se não divisível.

Bubbler
fonte
Contaria 2 x:1#.1%1+i.como uma resposta válida ou é um uso inválido de um tipo racional?
cole
5

05AB1E , 10 bytes

!DIL÷O)D¿÷

Experimente online!

Usa o mesmo método que todas as outras entradas. A saída está no formulário [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. 
Mr. Xcoder
fonte
3

JavaScript (ES6), 60 bytes

Retorna [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]

Experimente online!

Quão?

O método é semelhante à resposta Python do @ ChasBrown .

umabuma=0 0b=1

umauman+bbbnnn-1

até n=0 0.

Nós economizamos (uma,b) para dentro (p,q) e depois calcular umagcd(uma,b) com:

umabbumamodb

até b=0 0.

Finalmente retornamos o numerador reduzido p/uma e denominador reduzido q/uma.

Arnauld
fonte
3

Perl 6 , 57 53 bytes

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

Experimente online!

Um bloco de código anônimo que pega um número inteiro e retorna uma tupla de denominator, numerator.

Se nos fosse permitido usar tipos fracionários, seria o 32 byter muito mais simples:

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

Experimente online!

Brincadeira
fonte
2

C ++ 17 (gcc) , 108 bytes

Use apenas aritmética inteira:

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

Experimente online!


C ++ 17 (gcc) , 108 bytes

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

Experimente online!

O mesmo que abaixo, mas use C ++ 17's std::gcd.


C ++ (gcc) , 109 bytes

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

Experimente online!

Como o C ++ não possui suporte nativo ao bigint, isso definitivamente excederá n>20.

Exigir:

  • importdeclaração obsoleta do gcc .
  • GCC's std::__gcd.
  • -O0(Acho que sim) caso contrário, o compilador será otimizado d/=a.
  • Pelo menos 64 bits long.

Explicação:

  • Deixei d=n!,uma=Hn.
  • Rodada a*dpara número inteiro mais próximo, lançando a*d+.5para long, e atribuir a n. Agora n/dé a saída.
  • Simplifique a fração com std::__gcd.
user202729
fonte
Você não pode usar em auto a=0.vez de double a=0(1 char a menos)?
Dan M.
Sim ele pode. E mais um byte do loop: 106 bytes
movatica
2

MATL, 13 bytes

:tptb/sht&Zd/

Experimente no MATL Online

O mesmo método usado na resposta do @Dennis 'Jelly .

: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.     

(Saída implícita, imprime o denominador primeiro e depois o numerador.)

Imprecisões de ponto flutuante significam que isso não funciona para n = 20, porque os valores intermediários são muito grandes. Parece que a saída do caso de teste foi um erro de digitação, isso retorna a mesma resposta que as outras respostas para n = 20.

Aqui está uma versão de preservação de tipo inteiro (25 bytes) que tentei enquanto isso, antes de descobrir isso:

25 bytes, entrada até 43

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

Experimente online!

Faz a conversão dos números uint64antes de operá-los, faz a aritmética explicitamente em um loop (sem usar prodou sum). Mais importante, divide os numeradores e denominadores parciais pelo seu CDG a cada passo ao longo do caminho, no final de cada iteração. Isso aumenta a faixa de entrada para permitir naté 43. Parte do código é baseada na resposta Python do @Chas Brown.

Método alternativo (original) usando LCM em vez de fatorial:

16 15 bytes

:t&Zmtb/sht&Zd/

Experimente no MATL Online

sundar - Restabelecer Monica
fonte
1

Excel VBA, 141 bytes

Leva entradas [A1]e saídas para o console.

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)

Sem Golfe e Comentado

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
Taylor Scott
fonte
1

dc , 87 bytes

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

Experimente online!

Isso deixa o numerador e o denominador no topo da pilha nessa ordem, conforme permitido por esse padrão de saída. Como dcnão possui um gcdbuilt-in, isso utiliza o algoritmo euclidiano para calcular o gcd.

R. Kap
fonte
1

Stax , 11 bytes

ó╢Δ'åç4}ú┌7

Execute e depure

Explicação:

Queremos calcular:

Eu=1n1Eu

Agora precisamos de um denominador b e uma lista de numeradores umaEu:

Eu=1numaEub=Eu=1numaEub

Podemos fazer b=n!, então nós temos:

umaEun!=1Eu|×n!umaEu=n!Eu

Então nós temos:

Eu=1n1n=Eu=1nn!Eun!
|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
wastl
fonte
1

APL (NARS), 56 caracteres, 112 bytes

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

teste:

  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 

Em poucas palavras, reduza "a função soma em 2 números de fração" (um número de fração é uma lista de 2 números inteiros) no conjunto:

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

isso abaixo parece errado:

 f 56
74359641471727289 16124934538402170

mas se eu alterar o tipo de entrada do que:

  f 56x
252476961434436524654789 54749786241679275146400 
  f 226x
31741146384418617995319820836410246588253008380307063166243468230254437801429301078323028997161 529022507845189
  3176693594241665890914638817631063334447389979640757204083936351078274058192000
RosLuP
fonte
1

APL (Dyalog Unicode) , 15 12 bytes

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

Experimente online!

Função tácita, usando um único argumento . Salva um byte removendo o se for permitido imprimir o denominador primeiro.

Obrigado @dzaima por 3 bytes.

Quão:

⌽!(,÷∨)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.
J. Sallé
fonte