21
\$\begingroup\$

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

\$\endgroup\$
1
  • \$\begingroup\$ I think you mean "not divisible by" instead of "relatively prime with". 21 and 9 share a common factor of 3. \$\endgroup\$ – xnor Dec 7 '15 at 5:14

12 Answers 12

3
\$\begingroup\$

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
\$\endgroup\$
10
\$\begingroup\$

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.

\$\endgroup\$
2
  • 3
    \$\begingroup\$ Turning the foldr into another list comprehension saves two byes: ([x|x<-[5,9..],all((>0).mod x)[5,9..x-1]]!!) \$\endgroup\$ – nimi Dec 7 '15 at 16:47
  • \$\begingroup\$ @nimi Nice solution. You should post that, it's a different method. I'm sad it's shorter though because it's more direct to the definition and the repetition of the list is less pretty. \$\endgroup\$ – xnor Dec 9 '15 at 5:07
3
\$\begingroup\$

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.
\$\endgroup\$
0
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
2
  • \$\begingroup\$ @TomCarpenter Thanks! Now this answer is more yours than mine :-) \$\endgroup\$ – Luis Mendo Dec 8 '15 at 5:07
  • \$\begingroup\$ You're welcome :). It's still your logic, just applied a few tricks I've learnt along the way. \$\endgroup\$ – Tom Carpenter Dec 8 '15 at 5:21
0
\$\begingroup\$

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]]
\$\endgroup\$
2
  • 1
    \$\begingroup\$ 73 bytes: n->(a=[x=5];while length(a)<n x+=4;all(k->mod(x,k)>0,a)&&push!(a,x)end;x) \$\endgroup\$ – Alex A. Dec 8 '15 at 3:26
  • 1
    \$\begingroup\$ You can save some more by using endof instead of length and x%k instead of mod(x,k). \$\endgroup\$ – Alex A. Dec 8 '15 at 16:49
0
\$\begingroup\$

Jelly, 17 15 bytes

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

Try it online!

Uses 1-indexing (e.g. 1 -> 5, 2 -> 9, etc.), allowed by default on 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
\$\endgroup\$
0
\$\begingroup\$

Perl 5 -p, 56 bytes

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

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy