Hilbert Primes Golf

Question

Hilbert numbers are defined as positive integers of the form 4n + 1 for n >= 0. The first few Hilbert numbers are:

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

The Hilbert number sequence is given by OEIS sequence A016813.

A related number sequence, the Hilbert primes, are defined as the Hilbert numbers H > 1 that are not divisible by any Hilbert number k such that 1 < k < H. The first few Hilbert primes are:

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

Naturally, OEIS has this sequence too.

Given a integer n such that 0 <= n <= 2^16 as input, output the nth Hilbert prime.

This is code-golf, so standard rules apply, and the shortest code in bytes wins.

Leaderboard

The Stack Snippet at the bottom of this post generates the leaderboard from the answers a) as a list of shortest solution per language and b) as an overall leaderboard.

To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:

## Language Name, N bytes

where N is the size of your submission. If you improve your score, you can keep old scores in the headline, by striking them through. For instance:

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

If there you want to include multiple numbers in your header (e.g. because your score is the sum of two files or you want to list interpreter flag penalties separately), make sure that the actual score is the last number in the header:

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

You can also make the language name a link which will then show up in the snippet:

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

<style>body { text-align: left !important} #answer-list { padding: 10px; width: 290px; float: left; } #language-list { padding: 10px; width: 290px; float: left; } table thead { font-weight: bold; } table td { padding: 5px; }</style><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="language-list"> <h2>Shortest Solution 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> <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> <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><script>var QUESTION_ID = 65895; var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe"; var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk"; var OVERRIDE_USER = 45941; var answers = [], answers_hash, answer_ids, answer_page = 1, more_answers = true, comment_page; function answersUrl(index) { return "https://api.stackexchange.com/2.2/questions/" + QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER; } function commentUrl(index, answers) { return "https://api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER; } function getAnswers() { jQuery.ajax({ url: answersUrl(answer_page++), method: "get", dataType: "jsonp", crossDomain: true, success: function (data) { answers.push.apply(answers, data.items); answers_hash = []; answer_ids = []; data.items.forEach(function(a) { a.comments = []; var id = +a.share_link.match(/\d+/); answer_ids.push(id); answers_hash[id] = a; }); if (!data.has_more) more_answers = false; comment_page = 1; getComments(); } }); } function getComments() { jQuery.ajax({ url: commentUrl(comment_page++, answer_ids), method: "get", dataType: "jsonp", crossDomain: true, success: function (data) { data.items.forEach(function(c) { if (c.owner.user_id === OVERRIDE_USER) answers_hash[c.post_id].comments.push(c); }); if (data.has_more) getComments(); else if (more_answers) getAnswers(); else process(); } }); } getAnswers(); var SCORE_REG = /<h\d>\s*([^\n,<]*(?:<(?:[^\n>]*>[^\n<]*<\/[^\n>]*>)[^\n,<]*)*),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/; var OVERRIDE_REG = /^Override\s*header:\s*/i; function getAuthorName(a) { return a.owner.display_name; } function process() { var valid = []; answers.forEach(function(a) { var body = a.body; a.comments.forEach(function(c) { if(OVERRIDE_REG.test(c.body)) body = '<h1>' + c.body.replace(OVERRIDE_REG, '') + '</h1>'; }); var match = body.match(SCORE_REG); if (match) valid.push({ user: getAuthorName(a), size: +match[2], language: match[1], link: a.share_link, }); else console.log(body); }); valid.sort(function (a, b) { var aB = a.size, bB = b.size; return aB - bB }); var languages = {}; var place = 1; var lastSize = null; var lastPlace = 1; valid.forEach(function (a) { if (a.size != lastSize) lastPlace = place; lastSize = a.size; ++place; var answer = jQuery("#answer-template").html(); answer = answer.replace("{{PLACE}}", lastPlace + ".") .replace("{{NAME}}", a.user) .replace("{{LANGUAGE}}", a.language) .replace("{{SIZE}}", a.size) .replace("{{LINK}}", a.link); answer = jQuery(answer); jQuery("#answers").append(answer); var lang = a.language; lang = jQuery('<a>'+lang+'</a>').text(); languages[lang] = languages[lang] || {lang: a.language, lang_raw: lang.toLowerCase(), user: a.user, size: a.size, link: a.link}; }); var langs = []; for (var lang in languages) if (languages.hasOwnProperty(lang)) langs.push(languages[lang]); langs.sort(function (a, b) { if (a.lang_raw > b.lang_raw) return 1; if (a.lang_raw < b.lang_raw) return -1; return 0; }); for (var i = 0; i < langs.length; ++i) { var language = jQuery("#language-template").html(); var lang = langs[i]; language = language.replace("{{LANGUAGE}}", lang.lang) .replace("{{NAME}}", lang.user) .replace("{{SIZE}}", lang.size) .replace("{{LINK}}", lang.link); language = jQuery(language); jQuery("#languages").append(language); } }</script>

Answer 1

Haskell, 46 bytes

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

An anonymous function.

The core is foldr(\a b->a:[x|x<-b,mod x a>0])[][5,9..], which iterates through the arithmetic progression 5,9,13,..., removing multiples of each one from the list to its right. This produces the infinite list of Hilbert primes. Then, !! takes the nth element.

I has tried making (\a b->a:[x|x<-b,mod x a>0]) pointfree but didn't find a shorter way.

Answer 2

Pyth, 21 bytes

Lh*4bye.fqZf!%yZyT1hQ

Try it online: Demonstration or Test Suite

Explanation:

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

Answer 3

CJam, 36 33 32 23 bytes

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

Try it online

The latest version is actually much more @MartinBüttner's than mine. The key idea in his suggested solution is to use two nested loops to find the n-th value that meets the condition. I thought I was being clever by using only a single loop in my original solution, but it turns out that the added logic cost more than I saved by not using a second loop.

Explanation

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.

Answer 4

Husk, 8 bytes

!ü¦¡+4 5

Try it online! Uses 1-based indexing.

Explanation

!ü¦¡+4 5   Implicit input n.
   ¡       Iterate
    +4     addition of 4
       5   starting from 5: [5,9,13,17,..]
 ü         Uniquify by
  ¦        divisibility.
!          Get nth element.

Most of the work is done by ü¦. The function ü, when given a binary function f and a list, greedily constructs a subsequence where f x y is falsy for every (not necessarily adjacent) pair of elements x, y. In this case it picks a number if it's not divisible by any earlier pick. Then we just index into the resulting infinite list.

Answer 5

Minkolang 0.14, 46 37 32 bytes

I didn't realize that the gosub was totally unnecessary... >_>

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

Try it here and check all test cases here.

Explanation

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.

The register is used to store the target index. The outer while loop calculates each Hilbert number and does some bookkeeping. The inner while loop checks each Hilbert number for primality. If a Hilbert number is not a Hilbert prime, then the target is incremented so that the outer while loop has to repeat (at least) one more time, effectively skipping Hilbert composites.

Answer 6

Mathematica, 65 bytes

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

Generates the entire list and selects the element from it.

Answer 7

Raku, 35 bytes

grep {$_%%none 5,9...^$_},(5,9...*)

Try it online!

This is an expression for the lazy, infinite list of Hilbert primes.

• 5, 9 ... * is the infinite list of Hilbert numbers. (Raku infers that it's an arithmetic sequence from the first two elements.)
• grep { $_ %% none 5, 9 ...^ $_ } filters that list to those which are divisible (%%) by none of the Hilbert numbers up to, but not including (...^), the number being tested.

Answer 8

Ruby, 60 bytes

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

Only checks Hilbert prime factors.

Answer 9

JavaScript (ES6), 73 bytes

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

Just check Hilbert numbers one by one until we reach the nth Hilbert prime. Divisibility by Hilbert number is handled by regex.

Answer 10

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

Thanks to Tom Carpenter for removing 9 bytes!

Example use:

>> H(20)
ans =
   101

Answer 11

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)

Thanks Alex A. for saving 11 bytes! This uses the same algorithm as the Matlab and Ruby answers. Since Julia arrays are one-indexed, this starts with f(1) == 5.

My first attempt, using the Lazy package, is 106 bytes. If you plan to run this in the REPL, make sure to add semicolons to the ends of the lines to suppress the infinite output. And call Pkg.Add("Lazy") if you don't already have it installed.

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

Answer 12

Jelly, 17 15 bytes

ŻḤḤ‘ḍḍiɗċ1=2µ#Ṫ

Try it online!

Uses 1-indexing (e.g. 1 -> 5, 2 -> 9, etc.), allowed by default on sequence challenges.

How it works

ŻḤḤ‘ḍḍiɗċ1=2µ#Ṫ - Main link. Takes n via STDIN
            µ#  - Execute the following on integers k = 1, 2, 3, ... until n integers return True:
Ż               -   Yield [0, 1, 2, ..., k]
 Ḥ              -   Unhalve; [0, 2, 4, ..., 2k]
  Ḥ             -   Unhalve; [0, 4, 8, ..., 4k]
   ‘            -   Increment; [1, 5, 9, ..., 4k+1]
       ɗ        -   Group the previous three links into a dyad.
                    Use l = [1, 5, ..., 4k+1] on the left and k on the right:
    ḍ           -     Each element in l is divisible by k?
      i         -     Index of k in l or 0?
     ḍ          -     1 or 0 is divisible by the index?
                    This yields a list with 2 1s for Hilbert primes
        ċ1      -   Count 1s
          =2    -   Equals 2?
              Ṫ - Take the last one i.e. the nth Hilbert prime

Answer 13

Perl 5 -p, 56 bytes

$k=$.+=4;1while($k-=4)>1&&$.%$k;($k>1||--$_)&&redo;$_=$.

Try it online!

Answer 14

JavaScript, 59 58 54 bytes

0-indexed and based on the (possibly erroneous?) observation that, just as all composite numbers are divisible by at least one prime, all Hilbert composites are also divisible by at least one Hilbert prime.

Here's a limited proof of that using the first 20000 Hilbert numbers.

We handle the edge case of 1 being neither prime nor composite below by hardcoding 5 as our stating point.

a=[x=5];f=n=>a[a.every(y=>x%y,x+=4)?a.push(x):n]||f(n)

Try it online!

Explanation

We initialise an array a=[5], which will hold the Hilbert primes, and an integer x=5, which we'll use as a temporary variable for the Hilbert numbers, outside the main function. Usually this wouldn't be possible because our rules require that everything be reusable by successive function calls, but here on each successive call of the function a[n] will either exist and be immediately returned or we'll resume building the array of primes from where we left off on the last call and continue until it does exist.

f, then, is our recursive function taking input via parameter n. On each iteration we increment x by 4 and then check that, for each existing prime y in a, x%y>0.

If it is then we push the new value of x to a, which returns the updated length of a. We use that to index into a but, as JavaScript uses 0-based indexing, a[a.length] will always return undefined, which is falsey, so we fall through the logical OR to execute a recursive call to f(n) and continue to do so until we encounter a Hilbert composite (i.e., for at least one y in a, x%y===0).

When we do encounter a composite we instead index n into a and, if it exists, return that value, or continue recursing until the next composite if it doesn't.

Answer 15

Python, 80 bytes

f=lambda I,i=0,H=[2]:(i>I)*H[0]or f(I,i+all((p:=4*len(H)+1)%h for h in H),[p]+H)

Attempt This Online!

0-indexed (but it would be trivial to change to be 1-indexed). Stores the previous Hilbert numbers in H, and stores how many Hilbert primes have been found so far in i.