18
\$\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\$
  • \$\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
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\$
11
\$\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\$
  • 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
4
\$\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\$
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\$
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\$
  • \$\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\$
  • 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

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.