Hilbert Primes Golf

18

Os números de Hilbert são definidos como números inteiros positivos do formulário 4n + 1para n >= 0. Os primeiros números de Hilbert são:

1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57, 61, 65, 69, 73, 77, 81, 85, 89, 93, 97

A sequência numérica de Hilbert é dada pela sequência OEIS A016813 .

Uma sequência numérica relacionada, os números primos de Hilbert, são definidos como os números de Hilbert H > 1que não são divisíveis por nenhum número de Hilbert kcomo esse 1 < k < H. Os primeiros primos de Hilbert são:

5, 9, 13, 17, 21, 29, 33, 37, 41, 49, 53, 57, 61, 69, 73, 77, 89, 93, 97, 101, 109, 113, 121, 129, 133, 137, 141, 149, 157, 161, 173, 177, 181, 193, 197

Naturalmente, o OEIS também tem essa sequência .

Dado um número inteiro ncomo, por 0 <= n <= 2^16exemplo, output, o nth Hilbert prime.

Isso é código-golfe , então as regras padrão se aplicam e o código mais curto em bytes vence.

Entre os melhores

O snippet de pilha na parte inferior desta postagem gera o cabeçalho das respostas a) como uma lista da solução mais curta por idioma eb) como um cabeçalho geral.

Para garantir que sua resposta seja exibida, inicie-a com um título, usando o seguinte modelo de remarcação:

## Language Name, N bytes

onde Nestá o tamanho do seu envio. Se você melhorar sua pontuação, poderá manter as pontuações antigas no título, identificando-as. Por exemplo:

## Ruby, <s>104</s> <s>101</s> 96 bytes

Se você quiser incluir vários números no cabeçalho (por exemplo, porque sua pontuação é a soma de dois arquivos ou você deseja listar as penalidades do sinalizador de intérpretes separadamente), verifique se a pontuação real é o último número no cabeçalho:

## Perl, 43 + 2 (-p flag) = 45 bytes

Você também pode transformar o nome do idioma em um link que será exibido no snippet:

## [><>](http://esolangs.org/wiki/Fish), 121 bytes

Mostrar snippet de código

code-golf math number sequence number-theory Mego
fonte
Eu acho que você quer dizer "não divisível por" em vez de "relativamente primo com". 21 e 9 compartilham um fator comum de 3.
xnor

Respostas:

3

Pitão, 21 bytes

Lh*4bye.fqZf!%yZyT1hQ

Experimente on-line: Demonstration or Test Suite

Explicação:

Lh*4bye.fqZf!%yZyT1Q    implicit: Q = input number
L                       define a function y(b), which returns
 h*4b                      4*b + 1
                        this converts a index to its Hilbert number
       .f          hQ   find the first (Q+1) numbers Z >= 1, which satisfy:
           f      1        find the first number T >= 1, which satisfies:
            !%yZyT            y(Z) mod y(T) == 0
         qZ                test if the result is equal to Z 

                        this gives a list of indices of the first Q Hilbert Primes
      e                 take the last index
     y                  apply y and print
Jakube
fonte
11

Haskell, 46 bytes

(foldr(\a b->a:[x|x<-b,mod x a>0])[][5,9..]!!)

Uma função anônima.

O núcleo é foldr(\a b->a:[x|x<-b,mod x a>0])[][5,9..], que itera através da progressão aritmética 5,9,13,..., removendo múltiplos de cada um da lista à sua direita. Isso produz a lista infinita de números primos de Hilbert. Então, !!pega o nth elemento.

Eu tentei fazer (\a b->a:[x|x<-b,mod x a>0])pointfree, mas não encontrei uma maneira mais curta.

xnor
fonte
3
Transformar a foldrcompreensão em outra lista economiza dois bytes:([x|x<-[5,9..],all((>0).mod x)[5,9..x-1]]!!)
nimi
@nimi Solução agradável. Você deve postar isso, é um método diferente. Infelizmente, é mais curto porque é mais direto para a definição e a repetição da lista é menos bonita.
Xnor
4

CJam, 36 33 32 23 bytes

5ri{_L+:L;{4+_Lf%0&}g}*

Experimente online

A versão mais recente é realmente muito mais @ MartinBüttner do que a minha. A idéia principal em sua solução sugerida é usar dois loops aninhados para encontrar o n-ésimo valor que atenda à condição. Eu pensei que estava sendo inteligente usando apenas um único loop na minha solução original, mas acontece que a lógica adicionada custou mais do que eu economizei ao não usar um segundo loop.

Explicação

5       Push first Hilbert prime.
ri      Get input n and convert to integer.
{       Loop n times.
  _       Push a copy of current Hilbert prime.
  L       Push list of Hilbert primes found so far (L defaults to empty list).
  +       Prepend current Hilbert prime to list.
  :L      Store new list of Hilbert primes in variable L.
  ;       Pop list off stack.
  {       Start while loop for finding next Hilbert prime.
    4+      Add 4 to get next Hilbert number.
    _       Copy candidate Hilbert number.
    L       Push list of Hilbert primes found so far.
    f%      Element wise modulo of Hilbert number with smaller Hilbert primes.
    0&      Check for 0 in list of modulo values.
  }g      End while loop.
}*      End loop n times.
Reto Koradi
fonte
2

Número 0.14 , 46 37 32 bytes

Eu não percebi que o gosub era totalmente desnecessário ...> _>

n$z(xxi4*5+d(4-$d%)1=,z+$ziz-)N.

Experimente aqui e verifique todos os casos de teste aqui .

Explicação

n$z                                 Take number from input and store it in the register
   (                                Open while loop
    xx                              Dump the stack
      i4*5+                         Loop counter times 4 plus 5 (Hilbert number)
           d                        Duplicate
            (                       Open while loop
             4-                     Subtract 4
               $d                   Duplicate stack
                 %                  Modulo
                  )                 Exit while loop when top of stack is 0
                   1=,              0 if 1, 1 otherwise
                      z             Push register value
                       +            Add
                        $z          Pop and store in register
                          iz-       Subtract z from loop counter
                             )      Exit while loop when top of stack is 0
                              N.    Output as number and stop.

O registro é usado para armazenar o índice de destino. O loop while externo calcula cada número de Hilbert e faz alguma contabilidade. O loop while interno verifica cada número de Hilbert quanto à primalidade. Se um número Hilbert não for um primo Hilbert, o alvo será incrementado para que o loop while externo tenha que repetir (pelo menos) mais uma vez, ignorando efetivamente os compósitos Hilbert.

El'endia Starman
fonte
2

Mathematica, 65 bytes

Select[4Range[4^9]+1,Divisors[#][[2;;-2]]~Mod~4~FreeQ~1&][[#+1]]&

Gera a lista inteira e seleciona o elemento dela.

LegionMammal978
fonte
1

Ruby, 60 bytes

h=->i{n=[];x=5;n.any?{|r|x%r<1}?x+=4: n<<x until e=n[i-1];e}

Apenas verifica os fatores primos de Hilbert.

MegaTom
fonte
0

JavaScript (ES6), 73 bytes

n=>{for(i=0,t=2;i<=n;)i+=!/^(.(....)+)\1+$/.test(Array(t+=4));return t-1}

Basta verificar os números de Hilbert, um por um, até chegar ao enésimo número Hilbert. A divisibilidade pelo número de Hilbert é tratada pelo regex.

n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳
fonte
0

Matlab, 74 83 bytes

function t=H(n)
x=5;t=x;while nnz(x)<n
t=t+4;x=[x t(1:+all(mod(t,x)))];end

Obrigado a Tom Carpenter por remover 9 bytes!

Exemplo de uso:

>> H(20)
ans =
   101
Luis Mendo
fonte
@TomCarpenter Thanks! Agora, esta resposta é mais o seu que o meu :-)
Luis Mendo
Seja bem-vindo :). Ainda é sua lógica, apenas apliquei alguns truques que aprendi ao longo do caminho.
Tom Carpenter
0

Julia, 73 bytes

n->(a=[x=5];while length(a)<n;x+=4;all(k->mod(x,k)>0,a)&&push!(a,x)end;x)

Obrigado Alex A. por salvar 11 bytes! Isso usa o mesmo algoritmo que as respostas Matlab e Ruby. Como as matrizes Julia são de um índice, isso começa com f(1) == 5.

Minha primeira tentativa, usando o pacote Lazy, é de 106 bytes . Se você planeja executar isso no REPL, adicione ponto e vírgula às extremidades das linhas para suprimir a saída infinita. E ligue Pkg.Add("Lazy")se você ainda não o tiver instalado.

using Lazy
r=range
h=r(1,Inf,4)
p=@>>r() filter(n->n!=1&&all(map(x->mod(h[n],h[x])<1,2:n-1)))
f=n->h[p[n]]
Andrew diz Restabelecer Monica
fonte
1
73 bytes:n->(a=[x=5];while length(a)<n x+=4;all(k->mod(x,k)>0,a)&&push!(a,x)end;x)
Alex A.
1
Você pode economizar um pouco mais usando em endofvez de lengthe em x%kvez de mod(x,k).
Alex A.