Гильберт Примес Гольф

18

Числа Гильберта определяются как положительные целые числа в форме 4n + 1для n >= 0. Первые несколько чисел Гильберта:

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

Последовательность чисел Гильберта задается последовательностью OEIS A016813 .

Связанная числовая последовательность, простые числа Гильберта, определяются как числа Гильберта H > 1, которые не делятся на любое число Гильберта, kтакое что 1 < k < H. Первые несколько простых чисел Гильберта:

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

Естественно, у OEIS есть и эта последовательность .

Учитывая целое число nтакое, что в 0 <= n <= 2^16качестве входных данных выведите nth простое число Гильберта.

Это код-гольф , поэтому применяются стандартные правила, и выигрывает самый короткий код в байтах.

Leaderboard

Фрагмент стека в нижней части этого поста создает таблицу лидеров из ответов а) в виде списка кратчайшего решения для каждого языка и б) в качестве общей таблицы лидеров.

Чтобы убедиться, что ваш ответ обнаружен, начните его с заголовка, используя следующий шаблон уценки:

## Language Name, N bytes

где Nразмер вашего представления. Если вы улучшите свой счет, вы можете сохранить старые результаты в заголовке, вычеркнув их. Например:

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

Если вы хотите включить в заголовок несколько чисел (например, потому что ваш результат равен сумме двух файлов или вы хотите перечислить штрафы за флаг интерпретатора отдельно), убедитесь, что фактический результат является последним числом в заголовке:

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

Вы также можете сделать имя языка ссылкой, которая будет отображаться во фрагменте кода:

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

Показать фрагмент кода

code-golf math number sequence number-theory Mego
источник
Я думаю, что вы имеете в виду «не делится на» вместо «относительно простой с». 21 и 9 имеют общий множитель 3.
xnor

Ответы:

3

Pyth, 21 байт

Lh*4bye.fqZf!%yZyT1hQ

Попробуйте онлайн: демонстрация или тестовый набор

Объяснение:

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
источник
11

Haskell, 46 байтов

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

Анонимная функция.

Ядро foldr(\a b->a:[x|x<-b,mod x a>0])[][5,9..], которое перебирает арифметическую прогрессию 5,9,13,..., удаляя кратные каждого из списка справа от него. Это приводит к бесконечному списку простых чисел Гильберта. Затем !!принимает nэлемент.

Я пытался сделать (\a b->a:[x|x<-b,mod x a>0])бессмысленно, но не нашел более короткого пути.

XNOR
источник
3
Превращение foldrв другой список понимания спасает два байса:([x|x<-[5,9..],all((>0).mod x)[5,9..x-1]]!!)
nimi
@nimi Хорошее решение. Вы должны опубликовать это, это другой метод. Мне жаль, что оно короче, потому что оно более прямое к определению, а повторение списка менее привлекательно.
xnor
4

CJam, 36 33 32 23 байта

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

Попробуйте онлайн

Последняя версия на самом деле намного больше @ MartinBüttner, чем моя. Основная идея в предложенном им решении состоит в том, чтобы использовать два вложенных цикла для нахождения n-го значения, которое удовлетворяет условию. Я думал, что был умен, используя только один цикл в моем исходном решении, но оказалось, что добавленная логика стоит больше, чем я сэкономил, не используя второй цикл.

объяснение

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.
Рето Коради
источник
2

Минколанг 0,14 , 46 37 32 байта

Я не осознавал, что госуб совершенно не нужен ...> _>

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

Попробуйте здесь и проверьте все тесты здесь .

объяснение

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.

Регистр используется для хранения целевого индекса. Внешний цикл while вычисляет каждое число Гильберта и ведет некоторую бухгалтерию. Внутренний цикл while проверяет каждое число Гильберта на простоту. Если число Гильберта не является простым числом Гильберта, то цель увеличивается, так что внешний цикл while должен повторяться (как минимум) еще один раз, эффективно пропуская композиты Гильберта.

El'ndia Starman
источник
2

Mathematica, 65 байт

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

Создает весь список и выбирает из него элемент.

LegionMammal978
источник
1

Рубин, 60 байт

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

Только проверяет главные факторы Гильберта.

MegaTom
источник
0

JavaScript (ES6), 73 байта

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

Просто проверяйте числа Гильберта одно за другим, пока мы не достигнем n-го простого Гильберта. Делимость на число Гильберта обрабатывается регулярным выражением.

n̴̖̋h̷͉a̷̭̿h̸̡̅ẗ̵̨d̷̰ĥ̷̳
источник
0

Matlab, 74 83 байта

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

Спасибо Тому Карпентеру за удаление 9 байт!

Пример использования:

>> H(20)
ans =
   101
Луис Мендо
источник
@ TomCarpenter Спасибо! Теперь этот ответ больше ваш, чем мой :-)
Луис Мендо
Пожалуйста :). Это по-прежнему ваша логика, просто применил несколько трюков, которые я выучил на этом пути.
Том Карпентер
0

Юлия, 73 байта

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

Спасибо Алексею Александровичу за сохранение 11 байт! При этом используется тот же алгоритм, что и в ответах Matlab и Ruby. Поскольку массивы Julia индексируются однозначно, это начинается сf(1) == 5 .

Моя первая попытка с использованием пакета Lazy - это 106 байт . Если вы планируете выполнить это в REPL, обязательно добавьте точки с запятой в конце строк, чтобы подавить бесконечный вывод. И позвоните, Pkg.Add("Lazy")если он еще не установлен.

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]]
Эндрю говорит восстановить Монику
источник
1
73 байта:n->(a=[x=5];while length(a)<n x+=4;all(k->mod(x,k)>0,a)&&push!(a,x)end;x)
Алекс А.
1
Вы можете сохранить еще немного, используя endofвместо lengthи x%kвместо mod(x,k).
Алекс А.