65
\$\begingroup\$

Write a program or function which will provably print all integers exactly once given infinite time and memory.

Possible outputs could be:

0, 1, -1, 2, -2, 3, -3, 4, -4, …

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, -1, -2, -3, -4, -5, -6, -7, -8, -9, 10, 11, …

This is not a valid output, as this would never enumerate negative numbers:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, …

  • The output must be in decimal, unless your language does not support decimal integer (in that case use the natural representation of integers your language uses).

  • Your program has to work up to the numbers with the biggest magnitude of the standard integer type of your language.

  • Each integer must be separated from the next using any separator (a space, a comma, a linebreak, etc.) that is not a digit nor the negative sign of your language.

  • The separator must not change at any point.

  • The separator can consist of multiple characters, as long as none of them is a digit nor the negative sign (e.g. is as valid as just ,).

  • Any supported integer must eventually be printed after a finite amount of time.

Scoring

This is , so the shortest answer in bytes wins

Leaderboard

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

\$\endgroup\$
24
  • 6
    \$\begingroup\$ If our language supports infinite lists, can we output the list from a function rather than printing? (Calling print on such a list would print its elements one at a time forever.) \$\endgroup\$
    – xnor
    Sep 16 '16 at 8:57
  • 7
    \$\begingroup\$ I feel like the requirement on arbitrary-size integers does nothing but discourage languages without such integers from participating. They either have to have an import they can use or solve a totally different challenge from everyone else. \$\endgroup\$
    – xnor
    Sep 16 '16 at 9:10
  • 3
    \$\begingroup\$ @xnor Changed, though that kinds of ruins the very name of the challenge. \$\endgroup\$
    – Fatalize
    Sep 16 '16 at 9:14
  • 6
    \$\begingroup\$ @xnor, languages with arbitrary precision integers still have to solve a different problem from everyone else, so all that that change has accomplished is to make this problem boringly trivial in a lot of languages. \$\endgroup\$ Sep 16 '16 at 9:54
  • 3
    \$\begingroup\$ @PeterTaylor Yeah, this is unfortunate. The wrapping solutions don't feel to me like they are printing any negatives, but I don't see a way to firmly specify the difference when it's a matter of representation. \$\endgroup\$
    – xnor
    Sep 16 '16 at 9:58

155 Answers 155

1 2 3 4 5
6
0
\$\begingroup\$

GolfScript, 11 bytes

0{.p.~p).}do

0            # push 0 to the stack
 {           # this block will execute at least once, even though the TOS is 0
  .p         # print the current number
    .~p      # print the bitwise NOT of the current number
       )     # increments the current number
        .}do # creates an infinite loop

Because the bitwise NOT of x = (-x - 1), as the number increments, the inverse decrements. The bitwise NOT of 0 is -1, therefore it can be trivially proven that all integers are counted exactly once.

I know there's already a (longer) GolfScript solution here, I apologise if this is breaking any rules.

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

AWK, 33 32 bytes

This code prints all integers in one line:

BEGIN{for(ORS=FS;;)print -i++,i}

An alternative 33-byte answer, which prints one integer per line:

BEGIN{for(;;)print n+=i++*(-1)^i}

Try it online!

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

Pure yash and echo (or POSIX-compatible shell), 42 bytes

Separator is space or LF.

while echo ${#a} ${a+-${#a}};do a=.$a;done

How it works

  • ${#a} is length of string contained in the variable.
  • ${a+xxx} is content of variable a, if a is null string; otherwise string xxx.
  • Undefined variable is expanded to null string.

Try it online!

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

JavaScript (Node.js), 38 bytes

for(n=-1;++n!=NaN;){console.log(n,-n)}

Try it online!

\$\endgroup\$
5
  • \$\begingroup\$ When will 0 be printed? \$\endgroup\$ 2 days ago
  • \$\begingroup\$ @thejonymyster fixed \$\endgroup\$
    – Bgil Midol
    2 days ago
  • \$\begingroup\$ This prints 0 and -0. Does that count as posting each integer exactly once? :P \$\endgroup\$ 2 days ago
  • \$\begingroup\$ @thejonymyster Yes, If you think 0 and -0 are the same. \$\endgroup\$
    – Bgil Midol
    2 days ago
  • \$\begingroup\$ Well that's the problem, I do think that 0 and -0 are the same, and your program prints both of them. Zero twice, more than "exactly once" \$\endgroup\$ 2 days ago
0
\$\begingroup\$

APL, 17 bytes

Pretty self explanatory

{∇⊃⎕←(⊢,-)1+⍵}⎕←0
\$\endgroup\$
1 2 3 4 5
6

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.