29
\$\begingroup\$

The plus-minus sequence

The plus-minus sequence is one that starts with two seeds, a(0) and b(0). Each iteration of this sequence is the addition and subtraction of the previous two members of the sequence. That is, a(N) = a(N-1) + b(N-1) and b(N) = a(N-1) - b(N-1).

Objective Produce the plus-minus sequence, in infinitude or the first K steps given K. You may do this using an infinite output program, a generator, or a function/program that gives the first K steps. The output order does not matter, so long as it is consistent. (I.e., b(K) a(K) or a(K) b(K), with some non-numeric, non-newline separator in between.) The output must start with the input.

Test cases

For inputs 10 2 (of a(0) b(0), this is a possible output for the first K approach (or a subsection of the infinite approach):

10     2
12     8
20     4
24     16
40     8
48     32
80     16
96     64
160    32
192    128
320    64
384    256
640    128
768    512
1280   256
1536   1024
2560   512
3072   2048
5120   1024
6144   4096
10240  2048
12288  8192
20480  4096
24576  16384
40960  8192
49152  32768
81920  16384
98304  65536

For inputs 2 20 10 (a(0) b(0) k):

2     20
22   -18
4     40
44   -36
8     80
88   -72
16    160
176  -144
32    320
352  -288

This is a , so the shortest program in bytes wins.

Catalog

The Stack Snippet at the bottom of this post generates the catalog 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 = 76983; var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe"; var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk"; var OVERRIDE_USER = 12012; 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\$
14
  • \$\begingroup\$ I notice a(2n) = a(0)·2ⁿ and b(2n) = n(0)·2ⁿ, but that's probably not useful here. \$\endgroup\$
    – Neil
    Commented Apr 3, 2016 at 21:18
  • \$\begingroup\$ Can the non-numeric separator between a and b be a newline? \$\endgroup\$
    – Suever
    Commented Apr 3, 2016 at 22:32
  • \$\begingroup\$ @Suever No, it cannot. \$\endgroup\$ Commented Apr 3, 2016 at 22:33
  • \$\begingroup\$ @CᴏɴᴏʀO'Bʀɪᴇɴ Thanks for the clarification! \$\endgroup\$
    – Suever
    Commented Apr 3, 2016 at 22:34
  • 1
    \$\begingroup\$ Returning a sequence is fine @guifa \$\endgroup\$ Commented Jun 28, 2019 at 14:24

42 Answers 42

1
2
1
\$\begingroup\$

R, 41 bytes

The recursive solution, based on xnor's python solution:

f=function(a,b){cat(a,b,"\n");f(a+b,a-b)}

For the first-k method, the code size doubles to 82 bytes:

function(a,b,k=Inf,i=1){cat(a,b,"\n");while(i<k){cat(a<-a+b,b<-a-b*2,"\n");i=i+1}}

This function takes a and b as input, plus optionally k. If k is unspecified, it continues forever. (Well, until i overflows, which is a very big number, much larger than the recursion limit.)

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

Perl 5 -a, 41 bytes

@F=($F[0]+$F[1],$F[0]-$F[1])while say"@F"

Try it online!

Outputs the sequence infinitely.

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

dc, 27 bytes

rfr[rd3Rd_3R+p_3R-plxx]dsxx

Try it online!

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

Forth (gforth), 46 bytes

: f 0 do 2dup swap . . cr 2dup + -rot - loop ;

Takes in A(0) B(0) and K

Try it online!

Code Explanation

: f           \ start a new word definition
  0 do        \ loop from 0 to k-1 (inclusive)
    2dup      \ duplicate A(n) and B(n)
    swap . .  \ print them out (swap the order so we get A(n) first)
    cr        \ print a newline
    2dup      \ duplicate A(n) and B(n) again
    + -rot -  \ Add A(n) and B(n), move the result, then subtract B(n) from A(n)
  loop        \ end the counted loop
;             \ end the word definition
\$\endgroup\$
1
\$\begingroup\$

JavaScript - 4438/120 Bytes

38 Bytes from n = 0 to infinity

f=(a,b)=>{console.log(a,b);f(a+b,a-b)}

Try it online!

120 Bytes from n = 0 to n = k

f(10,2,20);
f(2,20,20);

function f(a,b,k){for(o=[[a,b]],i=1;i<k;i++)o.push([o[i-1][0]+o[i-1][1],o[i-1][0]-o[i-1][1]]);console.log(o.join("\n"))}

Pascal - 71 70 Bytes

program A;

procedure F(a:integer;b:integer);begin WriteLn(a,' ',b);F(a+b,a-b)end;

begin { main program }
   F(10,2);
   F(2,20);
end.

Try it online!

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

Stax, 8 bytes

≈└i≈√=æ`

Run and debug it

Takes input in the form a(0) b(0) k.

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

Appleseed, 36 bytes

(def S(q(P(cons P(S(sum P)(apply - P

A function that takes two arguments and returns an infinite list. Try it online!

Explanation

(def S               Define S to be
 (q                  the following list, which can be treated as a function
  (P                 where P is the argument list (or in this case, pair):
   (cons              Construct a list
    P                 consisting of P
    (S                followed by the result of a recursive call with arguments:
     (sum P)           Sum of the pair of arguments
     (apply - P)))))   The first argument minus the second
\$\endgroup\$
1
\$\begingroup\$

Vyxal, 6 bytes

‡÷₍+-Ḟ

Try it Online! Outputs an infinite list.

     Ḟ # Create an infinite list by repeatedly calling on the input...
‡      # A function
 ÷₍    # Push each  value, and wrap...
   +-  # Their sum and difference
\$\endgroup\$
1
\$\begingroup\$

C (gcc), 62 bytes

int f(int a,int b){for(;1;b=(a+=b)-2*b)printf("%d %d\n",a,b);}

Try it online!

Theoretically outputs indefinitely, however, it only outputs the sequence until integer overflow occurs.

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

Fuzzy Octo Guacamole, 17 16 bytes

^^(:C.Zs.aZ.s.-)

This was hard to make, due to client-side errors. But I got it!

Walkthrough:

^^                # Get input twice, pushes it to the stack.
  (               # Start a infinite loop.
   :              # Prints the stack, and since it has [a,b] is just the output.
    C             # Copy the active stack to the inactive stack.
     .            # Shift the active stack.
      Z           # Reverse the stack.
       s          # Move the top item on the active stack to the top of the inactive.
        .         # Switch stacks again.
         a        # Add the top 2 items, giving the first new item.
          Z       # Reverse the stack, so we keep the 'a' safe and prepare for the 'b'.
           .      # Switch stacks.
            s     # Move the top item on the active stack to the top of the inactive stack.
             .    # Switch stacks.
              -   # Minus the top 2 items, giving 'b'.
               )  # End infinite loop.
\$\endgroup\$
4
  • \$\begingroup\$ I don't know FOG all that well, but can't you move the : to the beginning of the loop and eliminate the need for printing twice? \$\endgroup\$ Commented Apr 5, 2016 at 15:29
  • \$\begingroup\$ oooooh @CᴏɴᴏʀO'Bʀɪᴇɴ thanks. \$\endgroup\$
    – Riker
    Commented Apr 5, 2016 at 16:06
  • \$\begingroup\$ Don't forget to update the explanation ;) \$\endgroup\$ Commented Apr 5, 2016 at 16:45
  • \$\begingroup\$ @CᴏɴᴏʀO'Bʀɪᴇɴ whadda ya mean? :P \$\endgroup\$
    – Riker
    Commented Apr 5, 2016 at 18:41
0
\$\begingroup\$

Mathcad, 52 bytes

Two versions: one uses Mathcad's range variables (a form of iterator) and the second uses a for-loop inside a function.

enter image description here

The Mathcad user interface is a 2D "whiteboard", wherein expressions (which may be equations, text, plots or results) are evaluated in left-to-right, top-to-bottom order. Identifier names are usually typed letter-by-letter, but there are also many combinations that allow the user to enter Mathcad specific operators. For example, typing "=" will enter the definition operator (:=) and ";" will enter the range operator (..). Typing ctl-m brings up the matrix dialog, and typing the number of row and columns will create a matrix of that size. For golfing purposes, a Mathcad "byte" is taken to be the number of keyboard characters necessary to enter a letter/number/operator.

{the augment function is just there to make the display more table like but doesn't count to the byte total}

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

JavaScript (Node.js), 44 bytes, finite

k=>F=(a,b)=>k--&&F(a+b,a-b,console.log(a,b))

Try it online!

The function should be called with currying syntax (k)(a,b).

\$\endgroup\$
1
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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