Denominador de séries harmônicas

16

Anteriormente, fizemos o pseudo - fatorial de um número, que é o LCM dos números de 1até n.

Seria útil adicionar frações.

No entanto, descobrimos que o denominador de 1/1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6é em 20vez do pseudo-fatorial de 6, que é 60.

Sua tarefa é encontrar o denominador de 1/1 + 1/2 + ... + 1/num número inteiro positivo dado n.

Casos de teste

 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

Referências

Entre os melhores

Mostrar snippet de código

code-golf sequence Freira Furada
fonte
Qual o tamanho de uma entrada que ela tem para trabalhar?
Brad Gilbert b2gills
@ BradGilbertb2gills Tão grande quanto possível.
Leaky Nun

Respostas:

8

M , 9 6 bytes

Obrigado a FryAmTheEggman por salvar 3 bytes! Código:

RİSg¹İ

M tem uma enorme vantagem aqui, porque trabalha com frações e não com flutuadores. Explicação:

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)

Usa o codificação Jelly . Experimente online! .

Além disso, há um solução de 4 bytes , que gera um zero inicial às vezes (por exemplo 280 -> 0280). Não tenho certeza se isso é permitido ou não:

RİSV

Experimente online!.

Adnan
fonte
1
1. A explicação do código de 6 bytes não está correta. g¹calcula o divisor comum mais grato da fração e n . O uso g1provavelmente seria mais claro. 2. Vlança a fração em uma corda e a elimina niladicamente. <num>/é (não cumulativo) reduzido por um operador niládico. Isso não faz sentido, mas como existe apenas um número (o argumento implícito 0 ), ele simplesmente não faz nada. O próximo link, o denominador, é niládico; portanto, o valor de retorno anterior é impresso implicitamente e substituído por esse nilad.
Dennis
@Dennis Thanks! Corrigida a explicação.
Adnan
@ Adnan Existe alguma documentação para M?
Esolanging Fruit
@ Challenger5 Não que eu saiba. Na verdade, é uma variante do Jelly, mas com frações de precisão arbitrárias. A documentação Jelly pode ser usado, mas ser Awate que um monte de recursos implementados no Jelly não são implementadas em M.
Adnan
5

Julia, 22 bytes

Uma função anônima.

n->1.//(1:n)|>sum|>den
Lynn
fonte
Mesmo comprimento:n->sum(inv,1//1:n).den
Alex A.
4

Mathematica, 27 bytes

Uma função anônima.

Denominator@*HarmonicNumber

Por exemplo:

 In[1] := (Denominator@*HarmonicNumber)[10]
 Out[1] = 2520
Lynn
fonte
Você poderia encontrar uma solução de 26-byte, se você cavar o bate-papo :)
Leaky Nun
Oh! Eu deveria deixar Martin postar essa, se ele quiser. Este é adoravelmente literal, então eu vou mantê-lo.
Lynn
Você exemplificaria como o código é usado?
21416
3

Python 2, 69 67 bytes

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

Teste no Ideone .

Como funciona

Seja H (n) a soma das inversas multiplicativas dos primeiros n números inteiros positivos. Em todos os momentos, temos que a / b = 1 + H (k - 1) . Na verdade, um , b , e k são inicializados para um , e 1/1 = 1 = 1 + H (0) .

Repetimos o trecho de código

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

(como uma string) n (entrada) vezes e executa o resultado. Em cada etapa, nós atualizamos a , b , e k usando a identidade a / b + 1 / k = ak / bk + b / bk = (ak + b) / bk .

Depois que todas as cópias foram executadas, a / b = 1 + H (n) , que tem o mesmo denominador que H (n) .

A forma totalmente reduzida de a / b é (a ÷ gcd (a, b)) / (b ÷ gcd (a, b)) . Em vez de calcular o maior divisor comum, inicializamos r como 1 e continuamos incrementando r até que ra seja um múltiplo de b .

Claramente, isso faz do ra o múltiplo menos comum de a e b . Como gcd (a, b) lcm (a, b) = ab , temos que b ÷ gcd (a, b) = lcm (a, b) ÷ a = ra ÷ a = r , tornando r a saída desejada.

Dennis
fonte
3

Haskell, 52

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

Se o arquivo for carregado no GHCI, f pode ser usado como uma função.

Vaelus
fonte
1
Presumivelmente, você quer dizer importletras minúsculas? Ele salva um byte para usar um em mapvez de uma compreensão:sum$map(1%)[1..n]
xnor
2

Geléia, 9 bytes

!©÷RSg®®÷

Experimente aqui.

             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.
Lynn
fonte
Acredito que é possível obter o mesmo número de conta sem esse registro.
Leaky Nun
2

MATL , 14 13 bytes

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

Experimente online!

Explicação

Para a entrada N , a saída é delimitada por N ! (fatorial de N ). O código calcula n / k para n = 1, ..., N ! e para k = 1, ..., N . Em seguida, soma sobre k , que fornece o número harmônico multiplicado por cada n . O resultado desejado é o índice n do primeiro desses valores que é um número inteiro.

Luis Mendo
fonte
2

Ruby, 57 47 bytes

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

Agradecemos a Kevin Lau por ter diminuído isso em dez bytes.

Peter Kagey
fonte
Atribua uma variável para 1.to_rque você não precise fazer injeção e conversão de string. Além disso, como o padrão de Ruby reduceé usar o primeiro elemento como inicial e 1/1=1você não precisa definir especificamente 0como o valor inicial.
Value Ink
2

Mathematica, 26 bytes

Denominator@Tr[1/Range@#]&

Uma função sem nome, tendo ncomo entrada e retornando o denominador. Usa o truque padrão de abusar Tr(rastrear) para somar a lista de recíprocos.

Martin Ender
fonte
1

JavaScript (ES6), 88 bytes

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}

Funciona apenas até m = 20 devido aos limites da precisão numérica do JavaScript.

Neil
fonte
1

05AB1E , 8 bytes

Código:

!йL/O¿/

Explicação:

!         # 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.

Pode haver alguns problemas de precisão para n> 19 devido à divisão do Python ... Usa o CP-1252 codificação .

Experimente online! .

Adnan
fonte
0

J, 20 bytes

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

Com base na abordagem usada pela solução da @ Lynn .

Se a precisão não for necessária para valores grandes de n ou se pudermos assumir que n será passado como um número inteiro estendido, com o sufixo de x, uma solução mais curta poderá ser usada por 15 bytes .

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

Uso

   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

Explicação

(!%!+.[:+/!%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
milhas
fonte
0

Perl 6 ,  36  32 bytes

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

Explicação:

{
  (
    [+]        # 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
}

Teste:

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
Brad Gilbert b2gills
fonte
0

Hoon , 95 bytes

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

Crie uma lista [1...n], dobre-a com ++mulo fatorial, crie uma lista[n!/1, n!/2, ... n!/n] e some-a, encontre o MDC de n!e a lista e divida o fatorial por esse número.

Provavelmente existe uma maneira muito mais fácil de calcular o denominador, mas não consigo descobrir: /

RenderSettings
fonte
Oh Hoon, por que seu tokenizer precisa de tantos espaços em branco redundantes?
Leaky Nun
Todas as minhas entradas Hoon olhar feio por causa das novas linhas :( código normal Hoon usa dois espaços entre fichas, mas uma nova linha é mais curto
RenderSettings
0

Python 3, 153 150 146 142 bytes

Tenho certeza que isso pode ser jogado mais. Mas eu sou novo aqui

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))
George
fonte
Bem-vindo ao PPCG!
Leaky Nun
0

Axioma, 34 bytes

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

teste 

(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
RosLuP
fonte
0

PHP, 81 bytes

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

Experimente online!

Jörg Hülsermann
fonte