title: Gödel numbering of a string

text:
# Question
Title: Gödel numbering of a string
## Background

**Gödel numbers** are a way of encoding any string with a unique positive integer, using prime factorisations:

First, each symbol in the alphabet is assigned a predetermined integer code.

Then, to encode a string \\$ x\_1 x\_2 x\_3 \ldots x\_n \\$, where each \\$ x\_i \\$ represents an symbol's integer code, the resultant number is

$$ \prod\_{i=1}^n p\_i^{x\_i} = 2^{x\_1} \cdot 3^{x\_2} \cdot 5^{x\_3} \cdot \ldots \cdot p\_n^{x\_n} $$

where \\$ p\_i \\$ represents the \\$ i \\$th prime number. By the fundamental theorem of arithmetic, this is guaranteed to produce a unique representation.

For this challenge, we will only consider strings made of the symbols Gödel originally used for his formulae and use their values, which are:

* `0`: 1
* `s`: 3
* `¬`: 5
* : 7
* : 9
* `(`: 11
* `)`: 13

...although for simplicity the symbols `¬`, , and  can be replaced by the ASCII symbols `~`, `|`, and `A` respectively.

(I don't know why Gödel used only odd numbers for these, but they're what he assigned so we're sticking with it)

## Challenge

Given a string consisting only of the symbols above, output its Gödel encoding as an integer.

You may assume the input will consist only of character in the set `0s~|A()`.

## Example

For the string `~s0`:

* start with \\$ 1 \\$, the multiplicative identity
* the first character `~` has code \\$ 5 \\$; the 1st prime is \\$ 2 \\$, so multiply by \\$ 2 ^ 5 \\$; the running product is \\$ 32 \\$
* the 2nd character `s` has code \\$ 3 \\$; the 2nd prime is \\$ 3 \\$, so multiply by \\$ 3 ^ 3 \\$; the running product is \\$ 864 \\$
* the 3rd character `0` has code \\$ 1 \\$; the 3rd prime is \\$ 5 \\$, so multiply by \\$ 5 ^ 1 \\$; the running product is \\$ 4320 \\$
* so the final answer is \\$ 4320 \\$

## Test-cases

```
Input        Output
""           1
"A"          512
"~s0"        4320
"0A0"        196830
")("         1451188224
"sssss0"     160243083000
"~(~0|~s0)"  42214303957706770300186902604046689348928700000
"0s~|A()"    5816705571109335207673649552794052292778133868750

```

## Rules

* Your program does not have to work for strings that would produce larger integers than your programming language can handle, but it must work in theory
* You can accept input as a string, list of characters, or list of code-points
* You may use any reasonable I/O method
* Standard loopholes are forbidden
* This is , so the shortest code in bytes wins

# Answer
# JavaScript (ES7),  ~~75~~  72 bytes

Expects an array of ASCII codes.

```
a=>a.map(g=k=>--d-1?g(k,d=n%d?d:++n):p*=n**(17088/k%75%14|1),d=p=n=1)&&p

```

Try it online!

### Magic formula

The formula `17088/k%75%14|1` was found by injecting random values into several handcrafted templates.

More specifically, the template for this one was ``${p}/k%${m0}%${m1}|1`` with \\$0\<p\<10^5\\$, \\$0\<m\_0\<10^3\\$ and \\$12\le m\_1 \le 15\\$.

```
 char. |  k  | floor(17088 / k) | mod 75 | mod 14 | OR 1
-------+-----+------------------+--------+--------+------
  '('  |  40 |        427       |   52   |   10   |  11
  ')'  |  41 |        416       |   41   |   13   |  13
  '0'  |  48 |        356       |   56   |    0   |   1
  'A'  |  65 |        262       |   37   |    9   |   9
  's'  | 115 |        148       |   73   |    3   |   3
  '|'  | 124 |        137       |   62   |    6   |   7
  '~'  | 126 |        135       |   60   |    4   |   5

```

### Commented

```
a =>                // a[] = input
a.map(g = k =>      // for each ASCII code k in a[]:
  --d - 1 ?         //   decrement d; if d is not equal to 1:
    g(              //     do a recursive call to the callback function:
      k,            //       pass k unchanged
      d =           //       update d:
        n % d ? d   //         if d is not a divisor of n, leave d unchanged
              : ++n //         otherwise, increment n and set d = n
    )               //     end of recursive call
  :                 //   else (n is now the next prime):
    p *=            //     multiply p by
      n ** (        //     n raised to the power of
        17088 / k   //     the odd positive integer <= 13 which is obtained
        % 75 % 14   //     by applying our magic formula to k
        | 1         //
      ),            //
  d = p = n = 1     //   start with d = p = n = 1
) && p              // end of map(); return p

```
> 18 votes

# Answer
# Jelly,  ~~13~~  11 bytes

-2 thanks to Nick Kennedy! (I had a bug in my Python search code so failed to find the hash for a domain of `[1..7]`.)

```
⁽=ȧ,7ḥⱮḤ’ÆẸ

```

A monadic Link accepting a list of characters that yields the Gödel number.

**Try it online!**

### How?

```
⁽=ȧ,7ḥⱮḤ’ÆẸ - Link: list of characters, S
⁽=ȧ         - 16481
    7       - 7
   ,        - literal pair -> [16481, 7]
      Ɱ     - map across (c in S) with:
     ḥ      -   (c) hash (salt=16481, domain=[1..7])
       Ḥ    - double
        ’   - decrement
         ÆẸ - prime-index-exponentiate ([a,b,c,...]->2^a*3^b*5^c*...)

```
> 10 votes

# Answer
# 05AB1E, ~~16~~ 15 bytes

```
"0s~|A()"sk·>.Ó

```

Try it online! Link includes test suite. Takes input as a list of characters (test suite expects a list of lists) saving 1 byte thanks to @ovs. Explanation:

```
"0s~|A()"       Literal string of symbols
         s      Swap with implicit input
          k·>   Get the incremented doubled indices
             .Ó Decode as list of prime exponents

```

Previous version took input as a string, which is easier to use: Try it online!
> 6 votes

# Answer
# Husk, ~~21 20~~ 19 bytes

* Saved 1 byte thanks to caird coinheringaahing
* Saved 1 byte thanks to Dominic Van Essen

```
Πz`^İpmȯ←D€"0s~|A()

```

Try it online!

```
Πz`^İpmȯ←D€"0s~|A()
      m             For each character in the input
          €"0s~|A() Find its index in the string "0s~|A()"
         D          Double
        ←           and decrement to get the corresponding code
 z                  Zip this with
    İp              the list of prime numbers
  `^                by raising the prime numbers to the powers of the codes
Π                   Get the product of that

```
> 5 votes

# Answer
# AWK, ~~109~~ 102 bytes

-7 bytes; thank you, @ovs!

Pretty naïve.

```
a=1{for(p=2;i++<length;)for(a*=p++**(index("0s~|A()",substr($0,i,1))*(j=2)-1);j<p;)p%j++||p++<j=2}$0=a

```

Try it online!

## Ungolfed

```
{
# accumulator and currently seeing prime number
a=1;p=2;
for(i=1;i<=length($0);i++){
   # multiply p_i^(x_i)
   a*=p**(index("0s~|A()",substr($0,i,1))*2-1);
   # get next prime
   p++;
   for(j=2;j<p;)
      if(p%j!=0)
         j++;
      else{
         p++;j=2;}}
# finally
$0=a

```
> 4 votes

# Answer
# Python 2, 89 bytes

Takes input as a list of characters.

```
s=input()
P=k=r=1
while s:r*=P%k<1or k**(3+2*'s~|A()'.find(s.pop(0)));P*=k*k;k+=1
print r

```

Try it online!
> 4 votes

# Answer
# Japt, ~~26~~ ~~24~~ 23 bytes

Ew! Don't think I've ever been more jealous of languages with built-ins for lists of primes and exponents and what-not :\

Input is an array of codepoints. Saved a byte by borrowing Arnauld's formula.

```
£_j}iY p#ª88÷X%75%E|1Ã×

```

Try it

```
£_j}iY p#ª88÷X%75%E|1Ã×     :Implicit input of codepoint array
£                           :Map each X at index Y
 _                          :  Function taking an integer as argument
  j                         :    Is prime?
   }                        :  End function
    iY                      :  Get the Yth integer that returns true
       p                    :  Raise to the power of
        #ª88                :    17088
            ÷X              :    Divide by X
              %75           :    Mod 75
                 %E         :    Mod 14
                   |1       :    Bitwise OR with 1
                     Ã      :End map
                      ×     :Reduce by multiplication

```
> 4 votes

# Answer
# Japt, 24 bytes

Japt is fairly verbose when it comes to primes, taking 6 bytes to get the Nth prime. Takes input as an array of letters.

```
£Èj}iY p"0s~|A()"aX ÑÄÃ×
£                        // Map the input with X as values, Y as indexes.
 Èj}iY                   // Get the Y-th prime
       p         aX      // to the power of the index of X in
        "0s~|A()"        // string constant,
                    ÑÄ   // times two plus one to map to correct values.
                      Ã× // Finally, reduce with multiplication, return result.

```

Try it here.
> 3 votes

# Answer
# Mathematica, ~~120~~ ~~106~~ ~~102~~ 99 bytes

-14 bytes, thank you pxeger!

```
1##&@@(Prime[Range@Length@#]^#&@((Tr@StringPosition["0s~|A()",#]*2-1)&/@Characters@InputString[]))

```

First golfing, and would welcome feedback!
> 3 votes

# Answer
# MATLAB/Octave, ~~102~~ 97 bytes

```
@(x)prod(table(primes(intmax)).Var1(1:nnz(x)).^int32(2*arrayfun(@(y)find('0s~|A()'==y),x)-1),'n')

```

Try it on Octave Online!* - TIO has some problems with function and execution exceeds 60 seconds and is terminated.
Anonymous function. In theory could work forever but maxes out at `int32` limit.
Explaination:

```
% anonymous function - take product of first argument...
@(x)prod(

      primes(intmax)                % all prime numbers < than limit of int32
table(              ).Var1(        )% take elements of array
                           1:nnz(x) % vector 1 to length of input

.^           % element-wise power

int32(                                      )% casting to int32
        arrayfun(                      ,x)   % for each character in input
                 @(y)find('0s~|A()'==y)      % find index in '0s~|A()'
      2*                                  -1 % indices to symbol values

,'n') % shorthand 'native', return product of elements in same type as input

```

---

Alternative solution as full function, **103 bytes** long.

```
function r=g(x)
p=primes(intmax);r=int64(1);for n=1:nnz(x)
r=r*p(n)^(2*find('0s~|A()'==x(n))-1);end
end

```

Try it online!*
This one on the other hand maxes out at `int64` limit.
Ungolfed:

```
function result = g(x)
primeNumbers = primes(intmax);
result = int64(1);
for n=1:length(x)
    result = result * primeNumbers(n) ^ (2*find('0s~|A()'==x(n))-1);
end
end

```

---

It is possible to write a function that doesn't max out (...so easily) but it outputs symbolic numbers instead of integers (and has **105 bytes**). Very similar to first function:

```
@(x)prod(sym(table(primes(intmax)).Var1(1:nnz(x))).^sym(2*arrayfun(@(y)find('0s~|A()'==y),x)-1),'native')

```

---

\*it is adviced for testing to replace `primes(intmax)` with something like `primes(intmax/128)` to calculate fewer prime numbers and thus reduce the execution time (and it was done for TIO example). The result will max out much faster than you'll use up all prime numbers, so no worries about that.
> 2 votes

# Answer
# , 28 bytes

```
[:*/p:@i.@#^1+2*'0s~|A()'&i.

```

Try it online!
> 2 votes

# Answer
# Factor \+ `math.primes math.unicode`, 64 bytes

```
[ dup length nprimes swap [ "0s~|A()"index 2 * 1 + ] map v^ Π ]

```

Try it online!

## Explanation:

It's a quotation (anonymous function) that takes a string from the data stack as input and leaves an integer on the data stack as output. Assuming `"~s0"` is on the data stack when this quotation is called...

* `dup` Duplicate the object on top of the data stack (TOS).

**Stack:** `"~s0" "~s0"`
* `length` Take the length of a sequence.

**Stack:** `"~s0" 3`
* `nprimes` Obtain a list of the first number of primes indicated by TOS.

**Stack:** `"~s0" { 2 3 5 }`
* `swap` Swap the top two objects on the data stack.

**Stack:** `{ 2 3 5 } "~s0"`
* `[ "0s~|A()"index 2 * 1 + ]` Push a quotation for `map` to use later. This is a function that maps letters of our alphabet to numeric values.

**Stack:** `{ 2 3 5 } "~s0" [ "0s~|A()"index 2 * 1 + ]`
* `map` Apply a quotation to each element of a sequence, collecting the results into a sequence of the same length. Inside the quotation now during the first iteration...

**Stack:** `{ 2 3 5 } 126`
* `"0s~|A()"` Push our alphabet string to the stack.

**Stack:** `{ 2 3 5 } 126 "0s~|A()"`
* `index` Find the index of NOS (next on stack) in TOS.

**Stack:** `{ 2 3 5 } 2`
* `2 * 1 +` Multiply by 2, then add 1.

**Stack:** `{ 2 3 5 } 5`
* Now `map` will collect `5` into the sequence it's building and move on to the rest of the elements in our input string...

**Stack** `{ 2 3 5 } "\x05\x03\x01"`
* As a side note, strings in Factor are just arrays of code points. Often when we map over a string, we'll get a string result, but we can still do vector math and such with them. This string is equivalent to `{ 5 3 1 }`.
* `v^` Component-wise exponentiation.

**Stack:** `{ 32 27 5 }`
* `Π` Product.

**Stack:** `4320`
> 2 votes

# Answer
# , ~~98~~ 97 bytes

*Edit: -1 byte thanks to pajonk*

```
function(x,p=1){for(y in x){while(sum(!(T=T+1)%%2:T)>1)1;p=p*T^(regexpr(y,"0s~|A()",f=T)*2-1)};p}

```

Try it online!

Input is a vector of characters.

```
goedel_numbering=
function(x){                            # x is the input character vector;
p=1                                     # initialize p to 1 (one less than the first prime);
for(y in x){                            # now cycle through each character y in x:
  while(sum(!(p=p+1)%%2:p)>1)1          # update p to the next prime
  T=T*                                  # multiply T (initially 1) by
      p^                                # p to the power of
        (regexpr(y,"0s~|A()",f=T)       # the position of y in the string "0s~|A()"
                                 *2-1)  # times 2, minus 1;
  }
  +T                                    # finally, output T.
}

```
> 2 votes

# Answer
# JavaScript (Node.js), ~~103...~~ 94 bytes

```
n=>n.map(g=b=>(eval("for(j=++i;i%--j;);"),j)<2?l*=i*(i*i)**'0s~|A()'.indexOf(b):g(b),i=l=1)&&l

```

Try it online!

Takes input as an array of characters. A naïve implementation.

## How it works

For each character, multiplies counter `l` by the exponential expression if incremented `i` is prime. If not, recall `g` until we get a prime number. Then logical-ANDs (short-circuit) with `l`.
> 1 votes

# Answer
# JavaScript (Node.js), 81 bytes

```
s=>s.map(c=>q*=(g=v=>p%v--?g(v):v?g(p++):p*p)``**'0s~|A()'.indexOf(c)*p,q=p=1)&&q

```

Try it online!

Input as array of characters, output a number.

Saved 1 byte by Shaggy.

---

# JavaScript (Node.js), 79 bytes

```
s=>s.map(c=>q*=(g=v=>p%v--?g(v):v?g(p++):p*p)``**'056 3421'[c%30%9]*p,q=p=1)&&q

```

Try it online!

Input an array of codepoints, output a number.

Saved 1 byte by Shaggy.

I believe someone may find out better hash functions.
> 1 votes

# Answer
# 05AB1E, 19 bytes

```
εNØ"0s~|A()"yk·>m}P

```

Try it online!
> 1 votes

# Answer
# C (gcc), <sup>~~116~~ ~~110~~</sup> 106 bytes

Saved 3 bytes thanks to the man himself Arnauld!!!
Saved 4 bytes thanks to ceilingcat!!!

```
d;g;p;r;f(char*s){for(p=r=1;*s;r*=pow(p,17088/ *s++%75%14|1))for(g=0;!g;)for(g=d=p++;d>1;)g=g&&p%d--;d=r;}

```

Try it online!

Inputs a string and returns its Gödel number.

Uses the Magic ASCII to Gödel value mapping formula from Arnauld's JavaScript answer.

### Commented Code (before some golfs)

```
d;g;p;r;f(char*s){                 // declare variables and function
        r=1                        // init return value r to 1
      p=                           // init prime number p to 1
  for(     ;*s;++s){               // loop over chars in s
    for(g=0;!g;)                   // loop until we find the next prime
              p++                  // start by bumping p
            d=                     // init divisor d to p-1
          g=                       // set g to non-zero p-1 as well
      for(       ;d>1;)            // loop over d until its 2
        g=g&&p%d--;                // g with only remain non-zero if
                                   // p is the next prime number
    r*=pow(p,                 );   // multiply r by p to the power of
             17088/ *s%75%14|1     // the Gödel value for the ASCII
                                   // code, need the space so it's not
  }                                // interpreted as start of comment
  d=r;                             // return r
}                                  //

```
> 1 votes

# Answer
# Pyth, 28 bytes

```
*F.b^Nhyx"0s~|A()"Y.fP_ZlQ)Q

```

Test suite

Naïve solution. Will attempt to find another solution... eventually.
> 1 votes

# Answer
# \[PHP\], 175 bytes

My first try here, so obviously this will suck…

```
<?php $G="0s~∨A()";$p=[0,2,3,5,7,11,13,17,19,23,29,31,37,41];$i="~s0";$t=1;for($k=0;$k<strlen($i);$k++){$r=strpos($G,$i[$k]);$r2=$r*2+1;$m=pow($p[$k+1],$r2);$t*=$m;}echo $t;?>

```

I couldn’t think of a formula to generate primes, so I entered them all in an array. One can obviously do better. Also, my server doesn’t accept just \<? as PHP marker, so I’m stuck with \<?php.
> 1 votes

# Answer
# Python 3, 190 bytes

```
def f(x):
    P,p=[2],3
    while len(P)<len(x):
        P.append(p)
        while 1:
            p+=1
            for i in P:
                if p%i==0:break
            else:break
    i=1
    for d,n in zip(x,P):i*=n**(2*"0s~|A()".find(d)+1)
    return i

```

Try it online! Generates enough primes to form the Gödel number, then finds the product.
> 1 votes

# Answer
# Haskell, 95 bytes

```
e=(product.zipWith(^)[p|p<-[2..],all((>0).mod p)[2..p-1]]<$>).mapM(`lookup`zip"0s~|A()"[1,3..])

```

Try it online!
> 1 votes

---
Tags: code-golf, string, number-theory, integer, primes
---


title: Train Route Planning

text:
# Question
Title: Train Route Planning
We can model a rail network as a directed graph, where each node is a train station and each edge is a train connecting two train stations. We'll assume that each train travels between its corresponding stations at a regular schedule and takes a fixed amount of time

Your code should take a list of trains, where each train is a tuple `(from, to, base, interval, duration)`, where

1. `from` is an integer denoting the station the train departs from.
2. `to` is an integer denoting the station the train arrives at.
3. `base` is the integer timestamp of an arbitrary departure of the given train.
4. `interval` is a positive integer denoting how often the train departs.
5. `duration` a positive integer denoting how long the train takes.

In other words, the departures are given by `base + n * interval`, and the corresponding arrivals by `base + n * interval + duration`, for integer `n`. For example, `0 2 -3 4 5` would describe a train going from station `0` to station `2`, which is at station `0` at times `..., -11, -7, -3, 1, 5, 9, 13, ...` and is at station `2` at times `..., -6, -2, 2, 6, 10, 14, 18, ...`.

If you are at some station `x` want to take a train from `x` to `y`, you must wait until the train from `x` to `y` is at station `x`. Then, after another `duration` units of time, you are at station `y`. For example, if at time `0` you're at station `0` and want to use the train described above, you'd need to wait until time `1`, then at time `6` you would be at station `2`.

Given these trains, your code should calculate the earliest arrival time at station `1`, given that you start at station `0` at time `0`. If no route is possible, you should return a distinguished value.

## Worked Example

Suppose we are given input:

```
0 2 -3 4 5
2 1 9 3 2
0 1 -1 7 9

```

From this, we can see the pairs of arrival and departure times of each train are:

```
..., (1, 6), (5, 10), (9, 14), (13, 18), (17, 22), (21, 26), (25, 30), ...
..., (0, 2), (3, 5), (6, 8), (9, 11), (12, 14), (15, 17), (18, 20), ...
..., (6, 15), (13, 22), (20, 29), (27, 36), (34, 43), (41, 50), (48, 57), ...

```

There are 2 routes from stations `0` to `1`: `0 -> 1` and `0 -> 2 -> 1`.

* For the route `0 -> 1`, we can board the train at time `6` and get off at time `15`.
* For the route `0 -> 2 -> 1`, we can get on train `0 -> 2` at time `1`, arrive at station `2` at time `6`, then immediately board train `2 -> 1`, arriving at station `1` at time `8`.

Out of these, `0 -> 2 -> 1` is the fastest, so we output `8`.

# Answer
# 05AB1E, 44 bytes

```
æʒø2£ø˜Á2ôćRJs€ËP*}ε0svy¦¦`U©%∞<®*+Dr@ÏнX+]ß

```

Outputs an empty string if no valid route can be found.

What a mess.. Those arbitrary `base`-times are pretty annoying to deal with.
Ah well, it works.. Will try to golf it some more later on.

Try it online or verify all test cases.

**Explanation:**

Step 1: Get all valid routes:

```
æ                # Get the powerset of the (implicit) input-list of quintuplets
 ʒ               # Filter it by:
  ø              #  Zip/transpose; swapping rows/columns
   2£            #  Keep the first two inner lists
     ø           #  Zip/transpose back
                 #  (we now have a list of all [from,to]-pairs for the current potential
                 #  route)
      ˜          #  Flatten it
       Á         #  Rotate it once towards the left
        2ô       #  Split it back into pairs
  ć              #  Extract the head
   R             #  Reverse it
    J            #  Join it together to a string
                 #  (note: only 1 is truthy in 05AB1E, including "01")
  s              #  Swap so the remainder-list is at the top
   €Ë            #  Check for each pair whether they're equal
     P           #  Check if this is truthy for all of them
  *              #  Check if both are truthy
 }               # Close the filter

```

Try just the first step online.

Step 2: Calculate the time each route takes, and leave the smallest as result:

```
ε                # Map over each valid route:
 0               #  Start at time 0 (let's call this the `current_time`)
  s              #  Swap so the route-list is at the top of the stack
   vy            #  For-each over its quintuplets:
     ¦¦          #   Remove the `from` and `to` from the quintuplet
     `           #   Pop and push the remaining three values to the stack
      U          #   Pop the top one (`duration`), and store it in variable `X`
      ©          #   Store the next top (`interval`) in variable `®` (without popping)
       %         #   Pop both values, and calculate base modulo interval
     ∞<          #   Push an infinite non-negative list: [0,1,2,...]
       ®*        #   Multiply each by interval `®`: [0,interval,2*interval,...]
         +       #   Add the (base modulo interval) to each
          D      #   Duplicate the infinite list
           r     #   Reverse the values on the stack
            @    #   Check for each value in the infinite list if it's >= `current_time`
             Ï   #   Only keep the values in the infinite list at the truthy indices
              н  #   Pop and push the first/lowest
     X+          #   Add duration `X` to it,
                 #   which is the next iteration's `current_time`
]                # Close both the loop and map
 ß               # Pop and push the minimum
                 # (which is output implicitly as result)

```
> 3 votes

# Answer
# JavaScript (ES6), 102 bytes

Expects an array of tuples `[ from, to, base, interval, duration ]`. Returns \\$+\infty\\$ if there's no solution.

```
f=(a,p,t=0,m)=>p^1?Math.min(...a.map(([A,B,b,i,d])=>p^A|m>>B&1?1/0:f(a,B,t+((b-t)%i+i)%i+d,m|1<<B))):t

```

Try it online!

Or 86 bytes if the graph is guaranteed to be acyclic.

### Commented

```
f = (                       // f is a recursive function taking:
  a,                        //   a[] = list of routes
  p,                        //   p = current position
  t = 0,                    //   t = current time
  m                         //   m = mask of visited stations
) =>                        //
p ^ 1 ?                     // if the current position is not 1:
  Math.min(...              //   take the minimum of ...
    a.map(                  //     for each route in a[] going from
    ([A, B, b, i, d]) =>    //     A to B with parameters (b, i, d):
      p ^ A |               //       if the current position is not A
      m >> B & 1 ?          //       or B was already visited:
        1 / 0               //         return +Infinity
      :                     //       else:
        f(                  //         do a recursive call:
          a,                //           pass a[] unchanged
          B,                //           set p = B
          t +               //           compute the updated time
          ((b - t) % i + i) //           by adding the delay before
          % i               //           departure
          + d,              //           and the duration
          m | 1 << B        //           mark B as visited
        )                   //         end of recursive call
    )                       //     end of map()
  )                         //   end of Math.min()
:                           // else:
  t                         //   destination reached: return t

```
> 3 votes

# Answer
# Python3, 111 bytes:

```
f=lambda t,s=0,D=0:min(m)if(m:=[D]*(s==1)+[K for a,b,c,d,e in t if a==s and(K:=f(t,b,max(c%d-D,0)+D+e))])else[]

```

Try it online!
> 3 votes

# Answer
# Python 3, 119 bytes

```
f=lambda a,n=0,t=0:t*(n==1)or min([f(a-{(x,y,s,i,d)},y,s-(s-t)//i*i+d)for x,y,s,i,d in a if x==n]or[max(sum(a,()))**2])

```

Try it online!
> 2 votes

---
Tags: code-golf, graph-theory, path-finding
---


title: The plus-minus sequence

text:
# Question
Title: The plus-minus sequence
# 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>
```

# Answer
> 14 votes
# Jelly, 5 bytes

```
ṄI;Sß

```

This is a recursive approach. Due to tail call optimization, the only limit is the ability to fit both integers into memory. Output is one list per line.

Try it online!

### How it works

```
ṄI;Sß  Main link. Argument: [b[n], a[n]] (n = 0 for original input)

Ṅ      Print [b[n], a[n]] to STDOUT.
 I     Compute the increments of the list, i.e., [a[n] - [b[n]].
   S   Compute the sum of the list, i.e., b[n] + a[n].
  ;    Concatenate the results to the left and to the right.
    ß  Recursively call the main link.

```

# Answer
> 5 votes
## Haskell, 19 bytes

```
a#b=a:b:(a+b)#(a-b)

```

Produces an infinite sequence of numbers. Usage example:

```
Prelude> take 20 $ 2#20

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

```

# Answer
> 5 votes
## Python 2, 31 bytes

```
def f(a,b):print a,b;f(a+b,a-b)

```

Prints forever. Well, eventually you exceed the recursion limit, but that's a system limitation.

# Answer
> 5 votes
# MATL, 10 bytes

```
`tDtswPdhT

```

This version will output an infinite number of elements in the plus-minus sequence.

**Try it Online!** (stop it after running due to infinite loop)

**Explanation**

```
    % Implicitly grab input as a two-element array [a,b]
`   % do...while loop
tD  % Duplicate and display the top of the stack
ts  % Duplicate [a,b] and add them together
w   % Swap the top two elements on the stack
P   % Swap the order of b and a in preparation for diff
d   % Compute the difference between b and a
h   % Horizontally concatenate [a+b, a-b]
T   % Explicit TRUE to make it an infinite loop
    % Implicit end of the do...while loop

```

# Answer
> 4 votes
# Julia, 25 bytes

```
a<|b=[a b]|>show<a+b<|a-b

```

Maximum syntax abuse. Julia is *weird*. Try it online!

### Alternate version, 29 bytes

Note that the output will eventually overflow unless you call `<|` on a *BigInt*. Unfortunately, `show` will prefix each array with `BigInt` in this case. At the cost of four more bytes, we can generated whitespace-separated output for all numeric types.

```
a<|b="$a $b
"|>print<a+b<|a-b

```

Try it online!

### How it works

We define the binary operator `<|` for out purposes. It is undefined in recent versions of Julia, but still recognized as an operator by the parser. While `\` (not explicitly defined for integers) is one byte shorter, its high precedence would require replacing `a+b<|a-b` with `(a+b)\(a-b)` (+3 bytes) or `\(a+b,a-b)` (+2 bytes).

When `a<|b` is executed, it starts by calling `show` to print **\[a b\]** to STDOUT. Then, `a+b<|a-b` recursively calls `<|` on the sum or the difference.

Since the recursion is (supposed to be) infinite, the comparison `<` is never performed; it sole purpose is chaining the two parts of the code. This saves two bytes over the more straightforward alternative `([a b]|>show;a+b<|a-b)`.

# Answer
> 3 votes
# Pyth, ~~10~~ 9 bytes

*Thanks to @isaacg for 1 byte.*

```
#=Q,s
Q-F

```

Prints an infinite sequence of pairs.

```
$ pyth plusminus.p <<< "[10,2]" | head -n 15
[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]

```

# Answer
> 3 votes
# 05AB1E, 7 bytes

Uses the **first-k** method. Input in the following for:

```
k
[a, b]

```

Code:

```
FD=OsÆ‚

```

Explanation:

```
F        # For N in range(0, k).
 D=      # Duplicate top of the stack and print without popping.
   O     # Sum up the array.
    sÆ   # Swap and perform a reduced subtraction.
      ‚  # Pair the top two elements. a, b --> [a, b]

```

Uses the **CP-1252** encoding. Try it online!

# Answer
> 3 votes
# C, 81 bytes

```
a,b;main(c){for(scanf("%d%d%d",&a,&b,&c);c--;a+=b,b=a-b-b)printf("%d %d\n",a,b);}

```

# Answer
> 3 votes
# k, 12

```
{(+;-).\:x}\

```

.

```
k){(+;-).\:x}\[10;10 2]
10  2
12  8
20  4
24  16
40  8
48  32
80  16
96  64
160 32
192 128
320 64

```

Could also be called in the form of

```
k)10{(+;-).\:x}\10 2

```

# Answer
> 3 votes
## APL, 37 chars

```
{⍺←3⊃3↑⍵⋄⎕←z←2↑⍵⋄⍺=1:⋄(⍺-1)∇(+/,-/)z}

```

Can be used as

```
    {⍺←3⊃3↑⍵⋄⎕←z←2↑⍵⋄⍺=1:⋄(⍺-1)∇(+/,-/)z} 10 2
10 2
12 8
20 4
24 16
40 8
48 32
80 16
[...]

```

or

```
      {⍺←3⊃3↑⍵⋄⎕←z←2↑⍵⋄⍺=1:⋄(⍺-1)∇(+/,-/)z} 10 2 6
10 2
12 8
20 4
24 16
40 8
48 32

```

# Answer
> 3 votes
# MathGolf, 8 bytes

```
ô`αp‼+-∟

```

Try it online!

Takes input in reverse order, but that's simply because that's how they are pushed onto the stack. Otherwise it'd be 1 byte longer. 2-3 bytes comes from the output. Without the need of actually printing one pair per line, the program could be `æ`‼+-∟` (fills the stack with the elements of the sequence indefinitely), or `É‼+-∟` (prints all elements of the sequence except the first one to debug, as long as `-d` flag is active).

## Explanation

```
ô      ∟   do-while-true
 `         duplicate the top two items
  αp       wrap last two elements in array and print
    ‼      apply next two operators to the top stack elements
     +     pop a, b : push(a+b)
      -    pop a, b : push(a-b)

```

# Answer
> 2 votes
# Reng v.3.2, 9 bytes (self-answer, non-competing)

```
ii¤ææö±2.

```

Takes two inputs (`a b`) and outputs `b a`. Try it here!

`i` takes input twice, `¤` duplicates the stack, `æ` prints a number and a space (and does so twice, there being two), `ö` prints a newline, `±` does what you might expect, and `2.` skips the next two characters, wrapping around the input getting characters.

# Answer
> 2 votes
## Batch, 54 bytes

```
@echo %1 %2
@set/aa=%1+%2
@set/ab=%1-%2
@%0 %a% %b%

```

Note that CMD.EXE is limited to 32-bit signed integers, so it will quickly overflow and print garbage and error messages.

# Answer
> 2 votes
# Python 3.5, 55 43 bytes:

```
def q(a,b):
 while 1:print(a,b);a,b=a+b,a-b

```

Prints out the correct sequence seemingly forever. I have been able to let this go on for about 30 minutes without any error being raised, and the program had printed out 2301 digits for the first number, and 1150 digits for the second! Based on this, I guessing that, being provided sufficient hardware to run on, this can go on for WAY longer and print out WAY more digits, and also has theoretically no recursion limit, courtesy of the `while` loop!

# Answer
> 2 votes
## Python 2.7, ~~56~~, 42 bytes:

```
a,b=input()
while 1:print a,b;a,b=a+b,a-b

```

Simple loop that either prints forever(ish).

# Answer
> 2 votes
# Perl 6, 23 bytes (infinite)

Edit: thanks to JoKing, the sequence version is now the shortest (also removed `.say` per clarification from OP:

```
{@_,{.sum,[-] |$_}...*}

```

TIO:InfiniteSeq

Old functional answer

```
->\a,\b {(a,b).say;f(a+b,a -b)}

```

TIO:InfiniteFunc

Note that Perl 6 has no per se recursion limit, it is purely based upon memory available, so this will reach the millions before bombing out.

# Answer
> 2 votes
# Rust, 78 bytes

```
|a,b,k|{let mut x=(a,b);for _ in 0..k{println!("{:?}",x);x=(x.0+x.1,x.0-x.1)}}

```

Try it online!

For fun, here's also an iterator that'll give you this sequence:

```
|a,b|(0..).scan((a,b),|x,_|{let i=*x;*x=(x.0+x.1,x.0-x.1);Some(i)})

```

# Answer
> 1 votes
# Factor, 62 bytes

```
:: f ( a b -- x ) a b "%s %s" printf a b + a b - f ; recursive

```

`recursive`, or else the callstack runs out too quickly.

# Answer
> 1 votes
# Ruby, 25 bytes

Based on xnor's Python solution. Perhaps I'll make a generator in another answer, but this will print `a`, then `b`, then the new `a`, then the new `b`, ad infinitum.

```
f=->a,b{p a,b;f[a+b,a-b]}

```

# Answer
> 1 votes
# Python 3, 42 bytes

I wanted to write a generator for this function, and so I did.

```
def f(a,b):
 while 1:yield a,b;a,b=a+b,a-b

```

In Python 3, the sequence is generated in this way:

```
>>> gen = f(2, 20)
>>> next(gen)
(2, 20)
>>> next(gen)
(22, -18)
>>> next(gen)
(4, 40)
>>> next(gen)
(44, -36)
>>> next(gen)
(8, 80)

```

# Answer
> 1 votes
## Common Lisp, 57

```
(lambda(a b)(loop(print`(,a,b))(psetf a(+ a b)b(- a b))))

```

Uses `psetf`, which affects values to variables in parallel, and the simple `loop` syntax.

# Answer
> 1 votes
# bash + GNU coreutils, 75 bytes

```
a=$1
b=$2
for i in `seq $3`;{ echo -e "$a\t$b";c=$a;a=$((c+b));b=$((c-b));}

```

Invocation:

```
./codegolf.sh 2 10 5

```

# Answer
> 1 votes
# CP/M 8080, 47 bytes

z80 mnemonics but nothing the 8080 doesn't have, source commented once I decided to count the output rather than the input but terse function names retained, hand assembled so forgive the 'xx's where I know the number of bytes but haven't worked out the output addresses or offsets:

```
# setup
ld c, 2     0e 02

# loop
.s

# update H (temporarily in B)
ld a, h     7c
add l       85
daa         27
ld b, a     46

# update L
ld a, h     7c
sub l       95
daa         27
ld l, a     6f

# copy B back to H, output H
ld h, b     60
call +o     cd xx xx

# output L
ld b, l     45
call +o     cd xx xx

# repeat
jr -s       18 xx

# output a two-digit BCD value followed by a space
.o

# output high digit
ld a, b     78
rra         1f
rra         1f
rra         1f
rra         1f
call +ob    cd xx xx

# output low digit
ld a, b     78
call +ob    cd xx xx

# output a space
ld e, #$20  1e 20
call 5      cd 00 05

# return
ret         c9

# output a single BCD digit
.ob
and #$f     e6 0f
add #$30    c6 30
ld e, a     5f
call 5      cd 00 05
ret         c9

```

# Answer
> 1 votes
# Clojure, 44 bytes

```
#(iterate(fn[[a b]][(+ a b)(- a b)])[%1 %2])

```

Function that produces an infinite lazy sequence.

# Answer
> 1 votes
# Perl 5, 40 bytes

requires `-E` (free)

```
sub a{say"@_";($c,$d)=@_;a($c+$d,$c-$d)}

```

~~or (same length)~~

~~```
$_=<>;{say;/ /;$_=$`+$'.$".($`-$');redo}

```~~

(I struck through the latter because it should have rounding errors for some iterations.)

Hat-tip.

But I suspect there must be a shorter Perl 5 solution.

# Answer
> 1 votes
# RETURN, 21 bytes

```
[¤.' ,$.'
,¤¤+2ª-F]=F

```

`Try it here.`

Recursive operator-lambda. Usage:

```
[¤.' ,$.'
,¤¤+2ª-F]=F10 2F

```

# Explanation

```
[                 ]=F  declare function F for recursion
 ¤.' ,$.'␊,            output top 2 stack items along with trailing newline
           ¤¤+2ª-      get plus and minus of top 2 stack items
                 F     recurse!

```

# Answer
> 1 votes
# \>\<\>, 26 bytes

```
:?!;1-r:n48*o:@@:nao:@+}-$

```

Call with `a`, `b`, `n` on the stack, where `n` is the number of turns or a negative value for infinite output. Outputs `a` and `b` separated by a space.

As an explanation, here is how the stack evolves during runtime :

```
abn
nba
nbaa
naab
naabb
nabab
nab+
+nab
+n-
+-n

```

You can try it on the online interpreter with a positive amount of turns but you will need to use the official python interpreter to test the infinite mode.

> ```
> $ python fish.py -c ':?!;1-r:n48*o:@@:nao:@+}-$' -t 0.01 -v 10 2 -1
> 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
> 163840 32768
> 196608 131072
> 327680 65536
> 393216 262144
> 655360 131072
> 786432 524288
> 1310720 262144
> [...]
>
> ```

# Answer
> 1 votes
# 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.

```

# Answer
> 1 votes
## Seriously, 12 bytes

```
,,1WX■@│+)-1

```

Outputs an infinite stream, format is `b(n) a(n)`, one pair of outputs per line.

No online link because TryItOnline doesn't do so well with infinite loops.

Explanation:

```
,,1WX■@│+)-1
,,1           push a(0), push b(0), push 1
   W          while loop:
    X           discard the 1 (only used to make sure the while loop always runs)
     ■          print all stack elements, separated by spaces, without popping
      @│        swap, duplicate entire stack
        +)      push a(n) + b(n) (a(n+1)) and move it to the bottom of the stack
          -     push a(n) - b(n) (b(n+1))
           1    push 1 to make sure the loop continues

```

# Answer
> 1 votes
# J, ~~16~~ 12 bytes

```
0&(]+/,-/)~<

```

Produces only the first *k* values for the sequence based on the given seeds.

Saved 4 bytes using the trick (or syntactic sugar) shown by @randomra in this comment.

## Usage

```
   f =: 0&(]+/,-/)~<
   2 20 f 10
  2   20
 22  _18
  4   40
 44  _36
  8   80
 88  _72
 16  160
176 _144
 32  320
352 _288

```

# Answer
> 1 votes
# C#, 50 bytes

```
f=(a,b)=>{Console.WriteLine(a+" "+b);f(a+b,a-b);};

```

Full source, including test case:

```
using System;
using System.Numerics;

namespace PlusMinusSequence
{
    class Program
    {
        static void Main(string[] args)
        {
            Action<BigInteger,BigInteger>f=null;
            f=(a,b)=>{Console.WriteLine(a+" "+b);f(a+b,a-b);};
            BigInteger x=10, y=2;
            f(x,y);
        }
    }
}

```

The BigInteger data type is used so the numbers don't overflow and become 0. However, since it is a recursive solution, expect a stack overflow.

# Answer
> 1 votes
# 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.)

# Answer
> 1 votes
# Perl 5 `-a`, 41 bytes

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

```

Try it online!

Outputs the sequence infinitely.

# Answer
> 1 votes
# dc, 27 bytes

```
rfr[rd3Rd_3R+p_3R-plxx]dsxx

```

Try it online!

# Answer
> 1 votes
# JavaScript - ~~44~~38/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!

# Answer
> 1 votes
# 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

```

# Answer
> 1 votes
# Stax, 8 bytes

```
≈└i≈√=æ`

```

Run and debug it

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

# Answer
> 1 votes
# 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

```

# Answer
> 1 votes
# 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

```

# Answer
> 0 votes
# 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.

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*}

# Answer
> 0 votes
# 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)`.

# Answer
> 0 votes
# 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.

---
Tags: code-golf, math, number, sequence, arithmetic
---


# Question
Title: Convert from postfix notation to infix notation
This question may not be that creative, but I believe that it is different enough to pose a new challenge.

## The Challenge

Your challenge is to write the shortest program possible that can take any valid expression in Reverse Polish Notation and convert it to infix notation that obeys the order of operations and has the necessary parentheses.

## Input

Your program will receive a valid RPN expression on STDIN. This expression will consist of numbers and operators. There can be an arbitrary number of spaces between each item, but there will always be a space between two numbers. Likewise, there will never be a space within a number. Here is a formal grammer description, stolen and modified from the linked question above.

```
expression := expression expression operator | number
operator   := "+" | "-" | "*" | "/" | "^"
number     := digit number | digit
digit      := "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

```

Here are some simple examples

```
2 3 -10000 +
16 4    12 3 / * -
1 2 +2 3 +^

```

In the first example, that is not a negation sign, it is a subtraction operator.

## Output

Your program should output an equivalent infix expression to STDOUT, which should be a valid infix expression, with numbers, operators, and parentheses.

Here is a formal grammer description, again stolen.

```
expression     := number | subexpression | expression operator expression
subexpression  := "(" expression ")"
operator       := "+" | "-" | "*" | "/"
number         := digit | digit number
digit          := "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

```

With infix notation, there must be an order of operations and a way to group subexpressions. The order of operations will be this:

```
Expressions inside parentheses
Exponents right to left
Multiplication and division (of equal importance) left to right
Addition and subtraction (of equal importance) left to right

```

As an example, 2^3^2-(2^3)^2 should equal 448.

The output should not contain any unneeded parentheses. ((2+1))-1 should reduce to 2+1-1. Also, you should not evaluate any expression. You should also not assume the commutative or associative properties. This means that, while the operators will move around, the numbers will always remain in the same order.

Here are the outputs for the above inputs. Note that what would normally be unneeded parenthesis are in the second example: removing them would invoke the associative property.

```
2-3+10000
16-4*(12/3)
(1+2)^(2+3)

```

I will add more examples later.

## Rules, Regulations, and Notes

This is code golf, standard rules apply.

# Answer
> 3 votes
## C, 305 chars

A good challenge! I'm finding this much harder to golf than the previous one. But here's what I have so far:

```
char*p,b[99];l[99],o[99],r[99],s[99],h,t;
q(e,a,d){int n=o[e]%47%2+(o[e]<48),f=a-n?a>n:d-!n;
l[e]?printf("("+f),q(l[e],n,1),q(r[e],n,!putchar(o[e])),
printf(")"+f):printf("%d",o[e]);}main(){for(p=gets(b);*p;)
*p%24>9?l[++h]=s[t-2],r[h]=s[--t],o[s[t-1]=h]=*p++:
*p-32?o[s[t++]=++h]=strtol(p,&p,10):++p;q(*s,3);}

```

# Answer
> 2 votes
## Clojure - 282 279 271 268 characters

```
(dorun(map pr((reduce(fn[s v](let[p '{e 2,* 1,/ 1,+ 0,- 0}[t z](rseq s)a
#(if(and(seq? %)(<=(p v)(p(nth % 1))))%`(~%))](if(p v)(conj(pop(pop s))
`(~@(a z)~({'e(symbol"^")}v v)~@(a t)))(conj s v))))[](map read-string
(re-seq #"\d+|[e+*/-]"(.replace(read-line)\^\e))))0)))

```

(line breaks are totally optional, only included for clarity, if removed ensure there is a single space between `a` and `#(` between the first two lines. all other spaces between the lines may be removed).

Assumes input will end after the first line, passes the example programs (outputs more spaces sometimes, but the right number of parentheses :)

Program can be tested here: http://ideone.com/gxykA

Ungolfed:

```
(defn stackify [s v]
  (let[p '{e 4,* 3,/ 3,+ 2,- 2}
       [t n] (rseq s)
       a #(if (and (coll? %) (<= (p v) (p (nth % 1)))) % `(~%))]
    (if (p v)
      (conj (pop (pop s))
            `(~@(a n) ~({'e(symbol"^")} v v) ~@(a t)))
      (conj s v))))

(defn read-postfix [s]
  "takes a string instead of reading from *in*"
  (->> (.replace s \^ \e)
       (re-seq #"\d+|[e+*/-]")
       (map read-string)
       (reduce stackify [])
       first
       (map pr)
       dorun))

```

(woo, first stackexchange post)

# Answer
> 2 votes
## Flex - 326 288 chars

```
 *s[99],**p=s,q[99],*n=q,t;main(){yylex();}
 #define W(c) p--;if(*--n c t)asprintf(p,"(%s)",*p);
 #define X asprintf(p++,"%s%s%s",*p,yytext,*(p+1));*n++=t;
 #define Z W(<=)W(<)X
%%
[0-9]+ *p++=strdup(yytext);*n++=9;
\+ t=1;Z
- t=1;Z
\* t=2;Z
\/ t=2;Z
\^ t=3;W(<)W(<=)X
\n puts(*--p);
. ;

```

trailing newline is needed

Compile with `flex makeinfix.l && gcc lex.yy.c -lfl`

Edit: fixed for new spec about `4 12 3 / * => 4*(12/3)` and made quite a bit shorter

# Answer
> 1 votes
# Regex (PCRE2), ~~140~~ 146 bytes

`s~(\d++|\((?1)(?3)(?1)\)) *((?1)) *([*-/^])|(?<=[*/^]()|[+-]|())\(((?1)(?>\^()|[+-]()|.)(?1))\)(?!\^|(?!\7)\4|\8(?!\5($|[+-])))~${1:+($1$3$2):$6}~`

Try it online!

This is a single regex substitution to be repeatedly applied until it has nothing to match (or until there is no change, which has the same effect though slightly less efficient).

The assumption is made that there is no leading or trailing space, only possible space between items. This seems a reasonable interpretation of the challenge's rules as stated.

In the following explanation,  represents a space:

```
s~                  # Begin substitution - match the following:
    # Match an expression that shall be converted to infix, with parentheses
    # added.
    (               # Define subroutine (?1) as an argument to an operator, and
                    # on the outermost level, capture this in $1:
        \d++        # Any number of digit characters, minimum one; force all of
                    # them to be consumed (prevent backtracking).
    |        # or...
        \(          # An opening parenthesis
        (?1)        # An argument
        (?3)        # An operator
        (?1)        # An argument
        \)          # A closing parenthesis
    )
    ␣*              # Any number of spaces, minimum zero.
    (               # $2 = the following:
        (?1)        # second argument
    )
    ␣*              # Any number of spaces, minimum zero.
    ([*-/^])        # Define subroutine (?3): Match an operator. The use of a
                    # range means "," and "." can be matched, but that's okay
                    # since they're guaranteed not to be in the input.
|   # Or, match an expression from which the surrounding parentheses shall be
    # removed. This can only match once everything matchable by the above has
    # already been processed.
    (?<=            # Atomic lookbehind
        [*/^]()     # \4 = set if preceded by '*' or '/' or "^"
    |
        [+-]        # set nothing if preceded by "+" or "-"
    |
        ()          # \5 = set if not preceded by any operator
    )
    \(              # An opening parenthesis (to be deleted)
    (               # $6 = the following:
        (?1)        # An argument
        (?>         # Atomic group – lock in the match once this expression
                    # completes.
            \^()    # \7 = set if the operator is "^"
        |
            [+-]()  # \8 = set if the operator is "+" or "-"
        |
            .       # set nothing if the operator is "*" or "/"; it's fine to
                    # use ".", because nothing besides an operator can be
                    # between two arguments (we've removed all the spaces by
                    # this point) and this expression is in an atomic group.
        )
        (?1)        # An argument
    )
    \)              # A closing parenthesis (to be deleted)
    (?!             # Negative lookahead – assert the following can't match:
        \^          # Followed by the operator "^"
    |
        (?!\7)      # Not using the operator "^", and:
        \4          # Preceded by the operator "*" or "/" or  "^"
    |        # or...
        \8          # Using the operator "+" or "-", and:
        (?!         # Not matching the following:
            \5      # Not preceded by any operator, and:
            (
                $       # Followed by nothing
            |           # or
                [+-]    # Followed by the operator "+" or "-"
            )
        )
    )
~                   # Replace with the following:
${1                 # Conditional upon whether \1 is set:
    :+($1$3$2)      # if \1 is set, concatenate $1 + $3 + $2 and surround that
                    # with parentheses.
    :$6             # otherwise, replace with $6 (which is what was matched in
                    # the second alternative, minus its parentheses).
}
~                   # No flags, not even global, which means each substitution
                    # will only make one match, and then the next one will
                    # start its search for a match from the beginning of the
                    # string again. This is slightly less efficient, and done
                    # for golf purposes.

```

This uses `PCRE2_SUBSTITUTE_EXTENDED`, which provides a syntax for conditional replacement. Sadly, neither PHP, R, nor Julia support this, even though the option has existed in PCRE2 for nearly 7 years now.

This allows almost anything to be done in a single substitution, where before it would have required multiple substitutions. Without it, this problem would not have been possible in a single substitution, because its first stage inserts parentheses into a string that has none to begin with, but the second stage needs to remove parentheses without adding any.

Some things may still be impossible with a single substitution. The entire state is represented by the current value of the string, and if a later stage needs to go pass through a state that intersects with the possible states of an earlier stage, it would be processed by that earlier stage rather than the later one.

# Regex (Boost), ~~144~~ 146 bytes

`s~(\d++|\((?1)(?3)(?1)\)) *((?1)) *([*-/^])|((?<=[*/^]()|[+-])|())\(((?1)(?>\^()|[+-]()|.)(?1))\)(?!\^|(?!\8)\5|\9(?!\6($|[+-])))~?1\($1$3$2\):$7~`

Try it online!

Ported to Boost's syntax, which uses parentheses, thus those in the replacement expression need to be backslash-escaped.

Boost does not support alternatives of different widths in one lookbehind, so the `|(?<!\))()` alternative was moved outside. It also does not support bare backreference syntax with `\10` or higher (it'd have to be done as `\k<10>` instead), but that ended up not mattering (no non-capturing groups had to be used).

# Answer
> 0 votes
## Python3, 140 chars

Difficult to golf, but I've got it sub 200, so I guess it will do.

```
s=[]
for k in input().split():
    if k in ['+','-','*','/']:p=len(s);s=s[0:p-2]+['('+s[p-2]+k+s[p-1]+')'];
    else:s.append(k)
print(s[0])

```

Pushes and pops data to the stack and converts to infix

---
Tags: code-golf, math
---


# Question
Title: Find number components with lowest distribution
* Let us assume that we have number `X`.
* Let us assume that we have positive integer "components" (`C`) of this `X` number.
* We can add these components together like `C1+C2+...+Cn = X`.
* We have `N` as limit of number of components.
* We have `B` as limit of biggest component
* Distribution: if we have `[8;8;5]` then avg of components is `7`, distribution is `abs(8-7)+abs(8-7)+abs(5-7) = 4`
* Lowest distribution: `dist([8;8;5])=4 dist([7;7;7])=0` -\> lowest distribution from these sets is `[7;7;7]`
* Component order does not matter.
* Components shall be the same number except one item which can be lower.

Examples

```
X = 17
N = 3
B = 8

```
* Then possible component sets are `[8;8;1]`, `[7;7;3]` and `[6;6;5]`.
* The lowest distribution between the components is in `[6;6;5]`, that's what we need.

---

```
X = 21
N = 3
B = 8

```
* Possible sets: `[8;8;5]` and `[7;7;7]`.
* Winner is `[7;7;7]`.

---

```
X = 22
N = 3
B = 8

```
* Possible sets: `[8;8;6]` and no more.
* Winner: `[8;8;6]`

---

---

```
X = 25
N = 3
B = 8

```
* Possible sets: - (due to B = 8)

---

I'm looking for the shortest script for this problem written in Javascript. I have a 10 Line solution.

My solution:

```
const findComponents = (X, B, N) => {
    let S = null;
    let mainComponent = Math.ceil(X / N);
    if (mainComponent <= B){
      let otherComponent = X % mainComponent;
      S = Array(N - 1).fill(mainComponent);
      S.push(otherComponent == 0 ? mainComponent : otherComponent);
    }
    return S;
  }

```

# Answer
> 2 votes
# Jelly,  ~~16 10~~  9 bytes

```
÷Ċ¬>¡⁵⁸sẈ

```

A full program that accepts `X N B` and prints a list or errors if no solution is possible.

**Try it online!** Or see the test-suite (Thanks, Steffan!)

...if erroring is not acceptable then \\$10\\$ with `s÷Ċ¥Ẉ«Ƒ⁵ȧƊ` (TIO) prints `0` instead.

### How?

```
÷Ċ¬>¡⁵⁸sẈ - Main Link: integer, X; integer, N
÷         -   (X) divided by (N)
 Ċ        -   round up to an integer (let's call this R)
     ⁵    - set the right argument to the program's third argument = B
    ¡     - repeat...
   >      - ...number of times: (R) greater than? (B)
  ¬       - ...action: logical NOT
              i.e. replace R with 0 if R>B (let's call this P)
      ⁸   - chain's left argument = X
       s  - (implicit [1,2,...,X]) split into chunks of length (P)
            Note: trailing elements are kept e.g. 7s3 -> [[1,2,3],[4,5,6],[7]]
        Ẉ - length of each
          - implicit print

```

# Answer
> 1 votes
# Vyxal `R`, ~~22~~ ~~12~~ 9 bytes

```
/⌈~≥[¹ẇvL

```

Try it Online!

*-10 bytes by porting Jonathan Allan's answer*

Outputs a positive integer for no solution.

If that's not allowed:

# Vyxal `R`, 10 bytes

```
/⌈~<ßQ¹ẇvL

```

Try it Online!

For no solution, produces no output.

# Answer
> 1 votes
# JavaScript (Node.js), 61 bytes

```
(x,n,b)=>(a=[...Array(--n).fill(y=(x+n)/-~n|0),x-n*y],y>b||a)
```

Attempt This Online!

Similar to Jonathan Allan's answer.

# Answer
> 1 votes
# Python, 53 bytes

```
lambda x,n,b:[y:=b>=(y:=-(-x//n))and y]*~-n+[~-x%y+1]
```

Attempt This Online!

Port of my JS answer (which is a port of Jonathan Allan's Jelly answer). Errors for no possible solution.

# Answer
> 1 votes
# 05AB1E, 13 bytes

```
ÅœIùʒ@P}ʒ¦Ë}θ

```

Inputs in the same order as the challenge description: \\$X,N,B\\$.

Try it online or verify all test cases.

**Explanation:**

```
Åœ       # Get all lists of positive integers that sum to the first (implicit) input `X`
  Iù     # Only keep the lists with a length equal to the second input `N`
    ʒ    # Filter this list by:
     @   #  Check if the third (implicit) input `B` is >= the current value
      P  #  Check that it's truthy for all values in the list
    }ʒ   # After the filter: filter again:
      ¦  #  Remove the first value of the list
       Ë #  Check if all other values are the same
     }θ  # After the filter: pop and keep the last list
         # (which is output implicitly as result)

```

---
Tags: code-golf, integer
---