title: Generate Recamán's sequence

text:
# Question
Title: Generate Recamán's sequence
Recamán's sequence (A005132) is a mathematical sequence, defined as such:

```
A(0) = 0
A(n) = A(n-1) - n if A(n-1) - n > 0 and is new, else
A(n) = A(n-1) + n

```

A pretty LaTex version of the above (might be more readable):

$$A(n) = \begin{cases}0 & \textrm{if } n = 0 \\ A(n-1) - n & \textrm{if } A(n-1) - n \textrm{ is positive and not already in the sequence} \\ % Seems more readable than %A(n-1) - n & \textrm{if } A(n-1) \> n \wedge \not\exists m \< n: A(m) = A(n-1)-n \\ A(n-1) + n & \textrm{otherwise} \end{cases}$$

The first few terms are `0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11`

To clarify, `is new` means whether the number is already in the sequence.

Given an integer `n`, via function argument or STDIN, return the first `n` terms of the Recamán sequence.

---

This is a code-golf challenge, so **shortest code wins.**

# Answer
> 11 votes
# CJam, ~~34~~ 33 bytes

```
0ali{_W=_I-__0<4$@#)|@I+@?+}fI1>`

```

Try it online.

### Example run

```
$ cjam <(echo '0ali{_W=_I-__0<4$@#)|@I+@?+}fI1>`') <<< 33
[0 1 3 6 2 7 13 20 12 21 11 22 10 23 9 24 8 25 43 62 42 63 41 18 42 17 43 16 44 15 45 14 46]

```

### How it works

```
0ali                               " Push S := [ 0 ] and read an integer N from STDIN.    ";
    {                      }fI     " For each I in [ 0 ... (N - 1) ]:                     ";
     _W=                           "   X := S[-1].                                        ";
        _I-                        "   Y := X - I                                         ";
            _0<                    "   A := (Y < 0)                                       ";
           _   4$@#)               "   B := (Y ∊ S)                                       ";
                     @I+           "   Z := X + I                                         ";
                    |   @?         "   C := (A || B) ? Z : Y                              ";
                          +        "   S += [C]                                           ";
                              1>`  " Push str(S[1:]).                                     ";

```

# Answer
> 11 votes
# Hexagony, 212 bytes

```
?\..$@.=.'">'_<>}/..&\_.._!\.\].\"&"&=(<_...>\[.+.<_$|_...{.|.....}'.../<..|&.....'/..".>$/{.<\.\$\>\._?...><?$$.\[._\_}$&..~.|"$\./..{&_$....$'.|_...$}|_.-..;_....'}".'...2.....$?&....3..=.<_.....?.-+{......}\</$.}

```

Try it online!

**Input:** a single, positive integer \\$n\\$ on `stdin`.

**Output:** all terms of Recaman's sequence up to and including \\$A(n)\\$, separated by spaces (note that this means the program will print a total of \\$n + 1\\$ terms).

# Expanded

# Explanation

Apologies if this is confusing, but it's my first time with Hexagony, so rest assured that it confuses me too.

Let \\$n = 6\\$. The instruction pointer (IP) starts out in the NW corner, moving along the black path. `?` reads \\$n\\$ from `stdin` and stores it in the current memory edge. Next, we copy \\$n\\$ three times while backing up the memory pointer. We also flip the memory pointer and decrement the edge it points to.

```
"&"&"&=(

```

The IP eventually wraps around to the upper left corner again, jumping over `\` and looping through the rest of the black path. This loop continues until the current edge is 0, at which point the graph looks like so:

This forms the skeleton of our memory layout. Each `vertical` edge now stores a value \\$i\\$ from 0 to 6; later, these same edges will store the terms \\$A(i)\\$ of the sequence as they are computed. Each `vertical` edge also has 4 contiguous edges that are used for later computations. Let's explain them now:

* `head` is used for several purposes, but never to store anything permanently because it is frequently overwritten by other operations.
* `tail` is generally used as a temporary variable, but it remains 0 for the last \\$i\\$ in the sequence, telling the program when to stop.
* `prev` stores the value of \\$A(i - 1)\\$
* `copy` straightforwardly stores a copy of \\$i\\$ or, later, \\$A(i)\\$

Once the program is done initializing its memory graph, it branches off the black path and onto the red path near the NE corner. First, `!` prints the decimal representation of `vertical` to `stdout`. Next, we move the memory pointer to `tail` and test for zero:

```
'<

```

If it is zero, `@` terminates the program immediately; otherwise, we move to `head` and set it to 32 (an ASCII space):

```
}=}?32

```

`;` then prints this space to `stdout`. Finally, we copy `vertical` to the next `prev`:

```
"?&"&

```

Now that the memory pointer is on the next term, we copy this term's `vertical` to *its* `copy` before moving to *its* `vertical`:

```
'&{=

```

`-` computes `prev` \- `copy`, which is really \\$A(i - 1) - i\\$, and stores it in `vertical`:

If `vertical` is not positive, `<` deflects the IP onto the green path, where `+` instead computes `prev` \+ `copy` (\\$A(i - 1) + i\\$) and stores it in `vertical`:

The IP then wraps around to the SW corner, eventually returning to the beginning of the red path and starting the cycle over again.

However, if `vertical` is positive, we have to make sure it doesn't already exist in the sequence before printing it. In this case, the `<` in the SE corner branches to the SE, wrapping around and staying on the red path. First, we copy `vertical` to `head`:

```
"?&

```

This puts the memory pointer in a position so that successive loops can enter at the next `|` mirror. Next, we copy `head` to the previous term's `tail` and move to *its* `head`.

```
"?&'

```

`-` computes `vertical` \- `tail` (\\$A(i - 1) - A(i)\\$) and stores it in `head`. Hexagony treats zero as a negative number, so we have to do some convoluted branching to test if `head` is exactly zero. All that's necessary to know is that if `head` is zero, we've found a duplicate term, and the program will branch onto the yellow path. Otherwise, it will return to the red path at the `{` instruction.

If `head` is zero, we return to the latest term of the sequence with `[`, which executes the subroutine along the pink and blue paths, before `+` computes \\$A(i - 1) + i\\$) like above. We then return to the red path.

If `head` is not zero, we check if the current term is zero:

```
{<

```

If it is, we call the subroutine and go back to the red path through a convoluted series of mirrors. If it isn't, we move to compare the next term, returning to the aforementioned `|` mirror.

---

Images created using Timwi's Hexagony Colorer and Esoteric IDE.

# Answer
> 8 votes
## Ruby, ~~71~~ 70 bytes

```
f=->n{a=[0];(n-1).times{|i|a+=[[b=a[-1]-i-1]-a!=[]&&b>0?b:b+2*i+2]};a}

```

A very "word-for-word" implementation of the definition.

# Answer
> 8 votes
# Haskell, 74

```
l=0:0#1
a§v|a<0||a`elem`r v=v|1<2=0-v
a#b=a+(a-b)§b:l!!b#(b+1)
r=(`take`l)

```

Example usage:

```
λ> r 20
[0,1,3,6,2,7,13,20,12,21,11,22,10,23,9,24,8,25,43,62]

```

# Answer
> 7 votes
## Python 2, ~~78~~ ~~75~~ ~~73~~ 69 Bytes

Kudos to xnor and flornquake
Now almost 10 bytes shorter than the initial answer

```
m=p,=0,
exec"p+=1;k=m[-1]-p;m+=k+2*p*(k*(k>0)in m),;"*input()
print m

```

# Answer
> 4 votes
# Golfscript (41 ~~45~~)

Try it online here:

```
(,1,\{:~1$=~)-:^1<\.^?)!!@|^\{~)2*+}*+}/

```

## Explanation

This is for the original 45 bytes solution, but it's still pretty much the same:

```
(,              # push array [0 .. n-1]
[0]\            # push sequence elements as [0] and reverse stack
{               # foreach element in [0 .. n-1] do:
  :m;           # store current element in m and discard
  .m=           # get the previous sequence element
  m)-:^         # subtract the current index from it and store in ^
  0>            # is that number greater than 0?
  \.^?)!        # is that number new to our sequence?
  @&            # logically and both checks
  {^}           # if true, push ^
  {^m)2*+}      # otherwise, add the index twice and push
  if
  +             # add new element to our sequence
}/
`               # make output pretty

```

*Edit #1:* Thanks to Dennis for shaving off 4 bytes.

# Answer
> 4 votes
# dc, 46 bytes

```
sn[z+z+d0r:a]sF0[pz-d1>Fd;a0<Fddd:azln!<M]dsMx

```

Try it online!

This program takes input from an otherwise empty stack and outputs to stdout (newline delimited).

I'm really proud of this one - it's beating everything that isn't a dedicated golfing language, and showcases three of my favorite dc golfing tricks:

* Stack size used as an index variable
* Refactoring "if A then B else C" into "unconditionally C, and if A then D" where C and D combine to make B
* the little-used random access array feature to solve a uniqueness constraint

# Explanation

```
sn             Stores the input in register n
[z+z+0r:a]sF   Defines the macro F, which:
    z+z+         adds twice the stack size/index variable
    0r:a         resets the "uniqueness" flag to 0 in the array a
               In context, F is the "D" in my description above,
               changing A(z-1)-z to A(z-1)+z
0              The main loop starts with the previous sequence member on top of
               the stack and total stack depth equal to the next index.
               Pushing a zero accomplishes both of these things.
[              Start of the main loop M
  p               Print the previous sequence member, with newline (no pop)
  z-             Calculate A(z-1)-z
  d1>F           If that's nonpositive, (F)ix it to be A(z-1)+z
  d;a            a is my array of flags to see if we've hit this value before
  0<F            If we have, (F)ix it! (nonzero = flag, since ;a is zero by
                 default, and also zero if we just (F)ixed and therefore
                 don't care about uniqueness right now)
  ddd            Make one copy to keep and two to eat
  :a             Flag this entry as "used" in the uniqueness array a
  zln!<M         If our "index variable" is n or less, repeat!
]dsMx          End of main loop - store it and execute

```

# Answer
> 3 votes
## JavaScript -  ~~81 80 79~~ 70

Kudos to edc65 for helping me save 9 bytes

```
f=n=>{for(a=[x=i=0];++i<n;)a[i]=x+=x>i&a.indexOf(x-i)<0?-i:i;return a}

```

# Answer
> 3 votes
## JavaScript, ES6, ~~74~~ 69 characters

Run the below code in latest Firefox's Web Console.

```
G=n=>(i=>{for(r=[t=0];++i<n;)r[i]=t+=i>t|~r.indexOf(t-i)?i:-i})(0)||r

```

Will try to golf it more later.

Example usage:

```
G(11) -> 0,1,3,6,2,7,13,20,12,21,11

```

# Answer
> 3 votes
# MATLAB, ~~83~~ 78 Bytes

Save the below as `f.m` (73 Bytes)

```
A=0;for i=1:n-1 b=A(i)-i;A(i+1)=b+2*i;if b>0&&~any(A==b) A(i+1)=b;end;end

```

Run from command window (5 bytes)

```
n=9;f

```

If the above is not legal, then it requires 90 bytes.

```
function A=f(n)
A=0;for i=1:n-1 b=A(i)-i;A(i+1)=b+2*i;if b>0&&~any(A==b) A(i+1)=b;end;end

```

# Answer
> 3 votes
# R: 96 characters

Golfed:

```
A=function(s,n,m,i){if(m==n){return(s)}else{t=i-m;if(t%in%s||t<0){t=i+m};s=c(s,t);A(s,n,m+1,t)}}

```

Ungolfed:

```
A = function(s,n,m,i) {
    if(m==n){return(s)}
    else{
        t=i-m
        if(t%in%s||t<0){t=i+m}
        s=c(s,t)
        A(s,n,m+1,t)
    }
}

```

Sample Run:

```
> An(0,34,1)
[1]   0   1   3   6   2   7  13  20  12  21  11  22  10  23   9  24   8
[18]  25  43  62  42  63  41  18  42  17  43  16  44  15  45  14  46  79

```

# Answer
> 3 votes
# JavaScript, 63 bytes

```
n=>(g=y=>n-x?g(a[++x]=a.includes(z=y-x)|z<0?+y+x:z):a)(a=[x=0])

```

Try it online

# Answer
> 3 votes
# 05AB1E, 19 bytes

```
¾ˆG¯¤N-DŠD0›*åN·*+ˆ

```

Try it online!

**Explanation**

```
¾ˆ                    # Initialize the global list with 0
  G                   # for N in [1, input-1] do:
   ¯                  # push the global list
    ¤N-               # subtract N from the last item in the list
       D              # duplicate
        Š             # move the copy down 2 spots on the stack
         D            # duplicate again
          0›          # check if it is positive
            *         # multiply, turning negative results to zero
             å        # is the result already present in the list?
              N·*     # multiply by N*2
                 +    # add to the result
                  ˆ   # add this to the list

```

# Answer
> 3 votes
# Perl 6, ~~62~~ 57 bytes

~~{(0,{$*-@*+@*\*2\*($*!\>@*||$*-@*∈@*)given @*\[\*-1\]}...\*)\[^$*\]}~~

```
{(0,{($!=@_[*-1])+@_-@_*2*($!>@_&&$!-@_∉@_)}...*)[^$_]}

```

*-5 bytes thanks to Jo King*

Try it online!

# Answer
> 3 votes
# K (oK), 53 bytes

**Solution:**

```
{$[y>c:#x;o[x,(r;*|x+c)(r in x)|0>r:*|x-c;y];x]}[,0;]

```

Try it online!

**Explanation:**

Recursive solution.

```
{$[y>c:#x;o[x,(r;*|x+c)(r in x)|0>r:*|x-c;y];x]}[,0;] / the solution
{                                              }[,0;] / lambda with first arg set as list containing 0
 $[      ;                                  ; ]       / if[condition;true;false]
       #x                                             / length of x
     c:                                               / save as c
   y>                                                 / y greater than? (ie have we produced enough results?)
                                             x        / return x if we are done
          o[                             ;y]          / recurse with new x and existing y
                                      x-c             / subtract c from x
                                    *|                / reverse first, aka last
                                  r:                  / save result as r
                                0>                    / 0 greater than?
                               |                      / or
                       (      )                       / do together
                        r in x                        / r in x?
              ( ;     )                               / use result to index into this 2-item list
                   x+c                                / add c to x
                 *|                                   / reverse first, aka last
               r                                      / result
            x,                                        / append to x

```

# Answer
> 3 votes
# , 36 bytes

```
(,][`(+2*#)@.(e.+.0>[)~{:-#)^:(]`0:)

```

Try it online!

# Answer
> 3 votes
# Python 2, 65 bytes

```
n=a=0
v=[]
exec'a+=[n,-n][a+n in v];print a;n-=1;v+=a,n;'*input()

```

Try it online!

Avoids negative numbers by adding them to the list of already visited numbers.

# Answer
> 2 votes
## Java, 144

```
int[]f(int n){int[]a=new int[n];a[0]=0;int i,j,k,m;for(i=0;i<n-1;){k=a[i++]-i;m=0;for(j=0;j<i;)if(k==a[j++])m=1;a[i]=m<1&k>0?k:k+2*i;}return a;}

```

# Answer
> 2 votes
## Lua - ~~141 135 139~~ 135

```
function s(n)a,b={1},{[0]=0}for i=1,n do k=b[i-1]-i c=k+i+i if(k>0)and(a[k]==nil)then b[i],a[k]=k,1 else b[i],a[c]=c,1 end end return b end

```

readable version:

```
function s(n)
a,b={1},{[0]=0}
for i=1,n do
   k=b[i-1]-i
   c=k+i+i
   if (k>0) and (a[k]==nil) then
      b[i],a[k]=k,1
   else
      b[i],a[c]=c,1
   end
end
return b
end

```

I use 2 tables, the first one is called *a* and it is built so that a\[i\]=1 iff *i* has already appeared in the sequence, *nil* otherwise, while the second table actually holds the sequence

# Answer
> 2 votes
### Powershell (103)

```
$n=Read-Host;$a=@(0);$n-=1;1..$n|%{$x=$a[-1]-$_;if($x-gt0-and!($a-like$x)){$a+=$x}else{$a+=$x+2*$_}};$a

```

Another 'word-for-word' implementation down here as well. Surprisingly readable for PowerShell, too.

Sequence is stored in the array $a, and printed out one term per line.

For $n=20 if we run the statement `$a-join","` we get

```
0,1,3,6,2,7,13,20,12,21,11,22,10,23,9,24,8,25,43,62

```

# Answer
> 2 votes
## Python, 73

```
def f(x,t=0):
 if x:t=f(x-1);t+=2*x*(t*(t>0)in map(f,range(x)))
 return t

```

Edit 1: Thanks to @xnor's tips on the other Python answer! (I just realised that both look very similar.)

Edit 2: Thanks again, @xnor.

# Answer
> 2 votes
## Groovy : 122 118 111 chars

Golfed:

```
m=args[0] as int
a=[0]
(1..m-1).each{n->b=a[n-1];x=b-n;(x>0&!(x in a))?a[n]=x:(a[n]=b+n)}
a.each{print "$it "}

```

Ungolfed:

```
m = args[0] as int
a = [0]
(1..m-1).each { n->
    b = a[n-1]
    x = b-n
    ( x>0 & !(x in a) ) ? a[n] = x : (a[n] = b+n)
}
a.each{print "$it "}

```

Sample Run:

```
bash$ groovy Rec.groovy 14
0 1 3 6 2 7 13 20 12 21 11 22 10 23

```

# Answer
> 2 votes
## Clojure : 174 chars

Golfed:

```
(defn f[m a](let[n(count a)b(last a)x(- b n)y(if(and(> x 0)(not(.contains a x)))x(+ b n))](if(= m n)a(f m(conj a y)))))(println(f(read-string(first *command-line-args*))[0]))

```

Ungolfed:

```
(defn f[m a]
  (let [n (count a)
        b (last a)
        x (- b n)
        y (if (and (> x 0) (not (.contains a x))) x (+ b n)) ]
    (if (= m n) a (f m (conj a y))) ) )

(println (f (read-string (first *command-line-args*)) [0]) )

```

Sample run:

```
bash$ java -jar clojure-1.6.0.jar rec.clj 14
[0 1 3 6 2 7 13 20 12 21 11 22 10 23]

```

# Answer
> 2 votes
# Mathcad, 54 "bytes"

---

From user perspective, Mathcad is effectively a 2D whiteboard, with expressions evaluated from left-to-right,top-to-bottom. Mathcad does not support a conventional "text" input, but instead makes use of a combination of text and special keys / toolbar / menu items to insert an expression, text, plot or component. For example, type ":" to enter the definition operator (shown on screen as ":=") or "ctl-shft-#" to enter the for loop operator (inclusive of placeholders for the iteration variable, iteration values and one body expression). What you see in the image above is exactly what appears on the user interface and as "typed" in.

For golfing purposes, the "byte" count is the equivalent number of keyboard operations required to enter an expression.

# Answer
> 2 votes
# C (gcc), ~~116 111~~ 109 bytes

```
*f(n){int*a=calloc(4,n),i=0,j,k,m;for(;~i+n;a[i]=k+(m|k<1)*2*i)for(k=a[i++]-i,m=0,j=i;j--;)m=k-a[j]?m:1;n=a;}

```

Try it online!

# Answer
> 2 votes
# PHP, 89 bytes

```
$f=function($n){for(;$i<$n;$s[$r[$i++]=$p=$m]=1)if($s[$m=$p-$i]|0>$m)$m=$p+$i;return$r;};

```

Try it online!

Ungolfed:

```
$f = function ($n) {
    for (; $i < $n; $s[$r[$i++] = $p = $m] = 1) {
        if ($s[$m = $p - $i] | 0 > $m) {
            $m = $p + $i;
        }
    }

    return $r;
};

```
* `$r` for my result
* `$s` for tracking seens
* `$p` previous value
* `$m` *m*ext value

# Answer
> 2 votes
# Stax, 19 bytes

```
É╖C8½ΔL▄░▬L+≡ΩSa⌂¼╧

```

Run and debug it

Unpacked, ungolfed, and commented, it looks like this. It keeps the sequence so far on the stack, and remembers `A(n - 1)` in the X register. The iteration index is used for `n`. The first time through, it's 0, but in that iteration it generates the 0 without any special cases, so there's no need to adjust for the off-by-1 index.

```
0X      push 0 to main stack and store it in X register, which will store A(n - 1)
z       push an empty array that will be used to store the sequence
,D      pop input from input stack, execute the rest of the program that many times
  xi-Y  push (x-register - iteration-index) and store it in the Y register
        this is (A(n - 1) - n)
  0>    test if (A(n - 1) - n) is greater than 0 (a)
  ny#   count number of times (A(n - 1) - n) occurs in the sequence so far (b)
  >     test if (a) > (b)
    y   (A(n - 1) - n)
    xi+ A(n - 1) + n
  ?     if/else;  choose between the two values based on the condition
  X     store the result in the X register
  Q     print without popping
  +     append to sequence array

```

Run and debug this one

# Answer
> 2 votes
## Pyth, 31 bytes

```
VQ=+Y?Y?|>NeYhxY-eYN+eYN-eYNZ)Y

```

# Answer
> 2 votes
# Ruby, ~~56~~ 52 bytes

-2 bytes thanks to Jo King!
-2 bytes thanks to dingledooper!

```
->n{v,*d=0;n.times{|i|d<<v+=v<i||d!=d-[v-i]?i:-i};d}

```

Try it online!

**Commented**:

```
->n{ ... }                         # lambda function taking an integer
  v,*d=0                           # initialize list of sequence values d and previous value v
  n.times{|i| ... }                # run the following code for i = 0,1,...,n-1:
          v<i||d!=d-[v-i]?i:-i     #   i IF (v < i OR d != (d without v-i)) ELSE -i
       v+=                         #   add this to v
    d<<                            #   and append the new value of v to d
  d                                # return d

```

# Answer
> 2 votes
# x86 machine code, 29 bytes

```
00000034: 89 fe 31 c0 99 eb 11 29 d0 78 0a 60 89 f7 89 d1  ..1....).x.`....
00000044: f2 af 61 75 03 8d 04 50 ab 42 e2 eb c3           ..au...P.B...

```

Commented assembly:

```
        .intel_syntax noprefix
        .globl recaman
        // input: ECX: n, EDI: u32[n]
        // output: stored to EDI
recaman:
        // Save the array pointer to ESI
        mov     esi, edi
        // EAX (A(n)) = 0
        xor     eax, eax
        // EDX (n) = 0
        cdq
        // Store first word
        jmp     .Lstore
.Lloop:
        // A(n - 1) - n
        sub     eax, edx
        // if negative, do A(n - 1) + n
        js      .Lneg_or_dup
.Lnot_neg_or_dup:
        // We need to save both EDI and ECX, so we do a lazy PUSHA/POPA.
        pusha
        // EDI = start of array
        mov     edi, esi
        // ECX = current output length
        mov     ecx, edx
        // Search for A(n - 1) - n
        repnz   scasd
        // restore registers
        popa
        // If the zero flag is set, we found a match.
        // If not, go directly to store
        jnz     .Lstore
.Lneg_or_dup:
        // Convert A(n - 1) - n to A(n - 1) + n by adding n * 2
        // EAX = EAX + EDX * 2
        lea     eax, [eax + 2 * edx]
.Lstore:
        // Store a u32 to EDI and autoincrement
        stosd
        // Increment length
        inc     edx
        // Decrement counter and loop if non zero
        loop    .Lloop
        // Return
        ret

```

Try it online!

The input is a pointer to an `int32_t` array of `n` elements in `edi`, with `n` being in `ecx`.

The output will be stored into `edi`.

# Answer
> 1 votes
# C#: 140 characters

```
int i,w,t,y;int[]F(int n){var r=new int[n--];for(;i<n;y=0){w=r[i++]-i;for(t=0;y<i&&t<1;)t=w==r[y++]?1:0;r[i]=w>0&&t<1?w:r[i-1]+i;}return r;}

```

# Answer
> 1 votes
# C++: 180 characters (158 without cin and cout statements)

```
int a[5000000][2]={0},i,k,l;a[0][0]=0;a[0][1]=1;cin>>k;for(i=1;i<=k;i++){l=a[i-1][0];if(l-i>0&&a[l-i][1]!=1){ a[i][0]=l-i;a[l-i][1]=1;}else{ a[i][0]=l+i;a[l+i][1]=1;}cout<<a[i][0]<<endl;

```

# Answer
> 1 votes
# Mathematica - 81 bytes

```
Fold[#~Append~(#[[-1]]+If[#[[-1]]>#2&&FreeQ[#,#[[-1]]-#2],-#2,#2])&,{0},Range@#]&

```

## Usage

```
Fold[#~Append~(#[[-1]]+If[#[[-1]]>#2&&FreeQ[#,#[[-1]]-#2],-#2,#2])&,{0},Range@#]&[30]
{0,1,3,6,2,7,13,20,12,21,11,22,10,23,9,24,8,25,43,62,42,63,41,18,42,17,43,16,44,15,45}

```

# Answer
> 1 votes
# Tcl, 103 bytes

```
proc A n {lappend L [expr {$n?[set x [lindex [set L [A [expr $n-1]]] e]]>$n&$x-$n ni$L?$x-$n:$x+$n:0}]}

```

Try it online!

# Answer
> 1 votes
## Common LISP (139 bytes)

```
(defun r(n)(do*(s(i 0(1+ i))(a 0(car s))(b 0(- a i)))((> i n)(nreverse s))(push(cond((= 0 i)0)((and(> b 0)(not(find b s)))b)(t(+ a i)))s)))

```

Ungolfed:

```
(defun recaman (n)
  (do*
   (series               ; starts as empty list
    (i 0 (1+ i))         ; index variable
    (last 0 (car s))     ; last number in the series
    (low 0 (- last i)))

   ((> i n)              ; exit condition
    (nreverse series))   ; return value

    (push                ; loop body
     (cond
       ((= 0 i) 0)       ; first pass
       ((and
         (> low 0) (not (find low s)))
        low)
       (t (+ last i)))
     series)))

```

# Answer
> 1 votes
# Rust, ~~154~~ 139 bytes

This is pretty big, but I like that it only uses one comparison per iteration instead of the 2 given, thanks to Saturating Subtraction generating a 0 if a\[n-1\]-n would be less than 0; and since 0 is already the first element, every would-be negative is saturated to 0 and is detected instead by the 'A already contains' comparison. Also... the size is not bad compared to Clojure, C#, C++, Common Lisp, lua..

```
fn r(n:usize)->Vec<usize>{let mut a=vec![0usize;n];for i in 1..n{a[i]=if a.contains(&(a[i-1].saturating_sub(i))){a[i-1]+i}else{a[i-1]-i}}a}

```

ungolfed

```
fn r(n:usize)->Vec<usize>{
  let mut a=vec![0usize;n];
  for i in 1..n {
     a[i] = if a.contains(&(a[i-1].saturating_sub(i)))
            {a[i-1]+i} else {a[i-1]-i}
 }a}

```

Try it on the rust playground

# Answer
> 1 votes
# Common Lisp, 122 bytes

```
(setf h(make-hash-table)n(read)j 0)(dotimes(i n)(when(or(<(decf j i)0)#1=(gethash j h))(incf j(+ i i)))(print(setf #1#j)))

```

Try it online!

The sequence is generated by from 0, the values are stored in a hash table. Here is the ungolfed version:

```
(setf h (make-hash-table)         ; create a hash table to store the results
      n (read)                    ; read the input in n
      j 0)                        ; initial value of the sequence
(dotimes (i n)                    ; loop for i from 0 below n
  (when (or (< (decf j i) 0)      ; the new value is the old - i; if negative
            (gethash j h))        ; or if the value has been already generated
    (incf j (+ i i)))             ; set j to A(n-1) + i (third case)
  (print (setf (gethash j h) j))) ; store the result in the table and print it

```

# Answer
> 1 votes
# F#, ~~117~~ 116 bytes

```
fun n->Seq.fold(fun(l:'a list)h->let a=l.[h-1]in if a-h>0&&not(Seq.contains(a-h)l)then l@[a-h]else l@[a+h])[0][1..n]

```

# Answer
> 1 votes
# Perl 5, 65 bytes

```
push@a,($t=$a[-1]-$_)+($t<0||grep$t==$_,@a)*$_*2for 0..<>;say"@a"

```

Try it online!

# Answer
> 1 votes
# Pyth, 24 bytes

```
tu+G-eG_W|g0J-eGH}JGHQ]0

```

Try it online!

```
tu+G-eG_W|g0J-eGH}JGHQ]0   Implicit: Q=eval(input())
 u                   Q     Reduce [0-Q)...
                      ]0   ... with initial value G=[0], next value as H:
              eG             Last value of G (sequence so far)
             -  H            Take H from the above
            J                Store in J
          g0J                0 >= J
                 }JG         Is J in G?
         |                   Logical OR of two previous results
       _W           H        If the above is true, negate H, otherwise leave as positive
    -eG                      Subtract the above from last value in G
  +G                         Append the above to G
                           The result of the reduction is the sequence with an extra leading 0
t                          Remove a leading 0, implicit print

```

# Answer
> 1 votes
# Haskell, ~~77~~ 73 bytes

```
f 0=[0]
f n|x<-g n,y<-last x=x++[last$y-n:[y+n|y<n||y-n`elem`x]]
g=f.pred

```

Try it online!

# Answer
> 1 votes
# Jelly, 15 bytes

```
_Ṫ»0ḟ⁸ȯ+Ṫ⁸;
Ḷç/

```

A monadic Link that accepts a **positive** integer, \\$n\\$, and yields a list of non-negative integers, the first \\$n\\$ terms of \\$A\\$.

**Try it online!**

### How?

```
_Ṫ»0ḟ⁸ȯ+Ṫ⁸; - Link 1, next prefix of Recamán: list, current_prefix; integer, next_n
                                  (1st call is actually made with current_prefix=0)
_           - (current_prefix) subtract (next_n)  -> [A(0)-n...,A(n-1)-n] (or A(0)-n when current_prefix=0)
 Ṫ          - tail                                -> A(n-1)-n
  »0        - maximum of that and zero            -> 0 or A(n-1)-n
    ḟ⁸      - filter discard if in current_prefix -> [] or [A(n-1)-n]
       +    - (current_prefix) add (next_n)       -> [A(0)+n...,A(n-1)+n] (or A(0)+n when current_prefix=0)
      ȯ     - (filtered) logical OR (added)       -> [A(n-1)-n] or [...,A(n-1)+n] (or A(0)+n when current_prefix=0)
        Ṫ   - tail                                -> A(n-1)-n or A(n-1)+n
         ⁸; - concatenate this to the current_prefix

Ḷç/ - Main Link: positive integer, n
Ḷ   - lowered range -> [0,1,2,...,n-1]
  / - reduce using:
 ç  -   last Link (Link 1) as a dyad

```

# Answer
> 1 votes
# JavaScript (ES6), 57 bytes

```
n=>(g=k=>n--?[p+=p<k|g[p-k]?k:-k,...g(g[p]=k+1)]:[])(p=0)

```

Try it online!

# Answer
> 1 votes
# 05AB1E, 16 bytes

```
0λ£Nλ₁N-Dd*åi+ë-

```

Try it online.

**Explanation:**

```
 λ              # Create a recursive environment
0               # which starts at a(0)=0
  £             # to output the first (implicit) input amount of values
                # (which will be output implicitly in the end)
                # and in each iteration, we calculate the next `a(n)` with:
     ₁          #  Push `a(n-1)`
      N-        #  Subtract the current `n`
        D       #  Duplicate this `a(n-1)-n`
         d      #  Check that it's non-negative (>= 0)
          *     #  Multiply it to `a(n-1)-n` (so it'll become 0 if it's negative)
    λ      åi   #  If it's in the list of previous [a(0), ..., a(n-1)] values:
   N         +  #   Add `n` to the implicit `a(n-1)`
            ë   #  Else:
   N         -  #   Subtract `n` from the implicit `a(n-1)` instead

```

# Answer
> 1 votes
# Japt, 20 bytes

```
@TwXµY *!ZøX ªX+YÑ}h

```

Try it

# Answer
> 1 votes
# Julia 1.0, ~~110~~ 81 bytes

```
[]|>v->0|>a->0:parse(Int,readline()).|>i->(println(a+=2(a-i in v)i-i);v=[v;a;~i])

```

Try it online!

-29 thx to Steffan!

# Answer
> 0 votes
# , 108 bytes

```
T[]r(T)(T n){T[]a=[0];T[T]b;foreach(i;1..n+1){T x=a[$-1];x+=(x>i)&&!((x-i)in b)?-i:i;a~=x;b[x]=1;}return a;}

```

Uses a function template shortcut syntax.

Try it online by pasting the following snippet to https://run.dlang.io/

```
T[]r(T)(T n){T[]a=[0];T[T]b;foreach(i;1..n+1){T x=a[$-1];x+=(x>i)&&!((x-i)in b)?-i:i;a~=x;b[x]=1;}return a;}
void main(){import std.stdio;writeln(r(10));}

```

# Answer
> 0 votes
## Clojure, 107 bytes

```
#(loop[s[0]i 1](if(= i %)s(recur(conj s(let[l(last s)N(- l i)](if(or(< N 0)((set s)N))(+ l i)N)))(inc i))))

```

Not many tricks here, `((set s)N)` evaluates to `N` if it is in the set and `nil` otherwise :)

# Answer
> 0 votes
# APL (Dyalog Unicode), 40 bytes<sup>SBCS</sup>

```
{⌽{⍵,⍨(((∊∘⍵∨≤∘0)r)×2×≢⍵)+r←(⊃-≢)⍵}⍣⍵⊢0}

```

Try it online! ~~I will be back for some more golfing and to write an explanation, just give me some hours.~~ Ok I need some more time, in golfing this I managed to make it longer.

---
Tags: code-golf, number-theory, sequence
---


title: Vandermonde Determinant

text:
# Question
Title: Vandermonde Determinant
Given a vector of \\$n\\$ values \\$(x\_1,x\_2,x\_3,\ldots,x\_n)\\$ return the determinant of the corresponding Vandermonde matrix

\\$V(x\_1, x\_2, \ldots, x\_n) = \begin{bmatrix}1 & x\_1 & x\_1^2 & x\_1^3 & \ldots &x\_1^{n-1} \\1 & x\_2 & x\_2^2 & x\_2^3 & \ldots &x\_2^{n-1} \\ \vdots & & & \vdots & & \vdots \\ 1 & x\_n & x\_n^2 & x\_n^3 & \ldots & x\_n^{n-1}\end{bmatrix}\\$.

This determinant can be written as:

\\$\det V(x\_1, x\_2, \ldots x\_n) = \prod\_\limits{1 \leqslant i \< j \leqslant n} (x\_j - x\_i)\\$

### Details

Your program/function has to accept a list of floating point numbers in any convenient format that allows for a variable length, and output the specified determinant.

You can assume that the input as well as the output is within the range of the values your language supports. If you language does not support floating point numbers, you may assume integers.

### Some test cases

Note that whenever there are two equal entries, the determinant will be `0` as there are two equal rows in the corresponding Vandermonde matrix. Thanks to @randomra for pointing out this missing testcase.

```
[1,2,2,3]            0
[-13513]             1
[1,2]                1
[2,1]               -1
[1,2,3]              2
[3,2,1]             -2
[1,2,3,4]           12
[1,2,3,4,5]        288
[1,2,4]              6
[1,2,4,8]         1008
[1,2,4,8,16]  20321280
[0, .1, .2,...,1]   6.6586e-028
[1, .5, .25, .125]  0.00384521
[.25, .5, 1, 2, 4]  19.3798828

```

# Answer
# Jelly, 5 bytes

```
œc2IP

```

`œc2` gets all combinations without replacement of length 2. `I` computes the difference list of each of those pairs, yielding a list like `[[1], [2], [3], ..., [1]]`. We take the `P`roduct.

Try it here!

---

In modern Jelly, `Œc` works as a short form of `œc2`, so `ŒcIP` is a 4-byte solution.
> 12 votes

# Answer
# Mathematica, 30 bytes

```
1##&@@(#2-#&@@@#~Subsets~{2})&

```

This is an anonymous function.

Expanded by Mathematica, it is equivalent to `(1 ##1 & ) @@ Apply[#2 - #1 & , Subsets[#1, {2}], {1}] &`. `1##&` is an equivalent for `Times` (thanks tips page), which is applied to each distinct pair of elements from the input list, generated by `Subsets[list, {2}]`. Note that `Subsets` does not check for uniqueness of elements.
> 10 votes

# Answer
# Ruby, ~~49~~ 47 bytes

```
->x{eval(x.combination(2).map{|a,b|b-a}*?*)||1}

```

This is a lambda function that accepts a real valued, one-dimensional array and returns a float or an integer depending on the type of the input. To call it, assign it to a variable then do `f.call(input)`.

We get all combinations of size 2 using `.combination(2)` and get the differences for each pair using `.map {|a, b| b - a}`. We join the resulting array into a string separated by `*`, then `eval` this, which returns the product. If the input has length 1, this will be `nil`, which is falsey in Ruby, so we can just `||1` at the end to return 1 in this situation. Note that this still works when the product is 0 because for whatever reason 0 is truthy in Ruby.

Verify all test cases online

Saved 2 bytes thanks to Doorknob!
> 8 votes

# Answer
# MATL, 9

```
!G-qZRQpp

```

**Try it online!**

This computes a matrix of all differences and then keeps only the part below the main diagonal, making the other entries `1` so they won't affect the product. The lower triangular function makes the unwanted elements `0`, not `1`. So we subtract `1`, take the lower triangular part, and add `1` back. Then we can take the product of all entries.

```
t     % take input. Transpose
G     % push input again
-     % subtract with broadccast: matrix of all pairwise differences
q     % subtract 1
ZR    % make zero all values on the diagonal and above
Q     % add 1
p     % product of all columns
p     % product of all those products

```
> 4 votes

# Answer
## J, 13 bytes

```
-/ .*@(^/i.)#

```

This is a monadic function that takes in an array and returns a number. Use it like this:

```
  f =: -/ .*@(^/i.)#
  f 1 2 4
6

```

## Explanation

I explicitly construct the Vandermonde matrix associated with the input array, and then compute its determinant.

```
-/ .*@(^/i.)#   Denote input by y
            #   Length of y, say n
         i.     Range from 0 to n - 1
       ^/       Direct product of y with the above range using ^ (power)
                This gives the Vandermonde matrix
                 1 y0     y0^2     ... y0^(n-1)
                 1 y1     y1^2     ... y1^(n-1)
                   ...
                 1 y(n-1) y(n-1)^2 ... y(n-1)^(n-1)
-/ .*           Evaluate the determinant of this matrix

```
> 4 votes

# Answer
## Pyth, ~~15~~ ~~13~~ ~~12~~ 11 bytes

```
*F+1-M.c_Q2

```

```
         Q    take input (in format [1,2,3,...])
        _     reverse the array: later we will be subtracting, and we want to
                subtract earlier elements from later elements
      .c  2   combinations of length 2: this gets the correct pairs
    -M        map a[0] - a[1] over each subarray
  +1          prepend a 1 to the array: this does not change the following
                result, but prevents an error on empty array
*F            fold over multiply (multiply all numbers in array)

```

Thanks to @FryAmTheEggman and @Pietu1998 for a byte each!
> 3 votes

# Answer
# Mathematica, 32 bytes

```
Det@Table[#^j,{j,0,Length@#-1}]&

```

I was surprised not to find a builtin for Vandermonde stuff. Probably because it's so easy to do it oneself.

This one explicitly constructs the transpose of a VM and takes its determinant (which is of course the same as the original's). This method turned out to be significantly shorter than using any formula I know of.
> 3 votes

# Answer
## Haskell, 34 bytes

```
f(h:t)=f t*product[x-h|x<-t]
f _=1

```

A recursive solution. When a new element `h` is prepended to the front, the expression is multiplied by the product of `x-h` for each element `x` of the list. Thanks to Zgarb for 1 byte.
> 3 votes

# Answer
# APL (Dyalog Extended), 19 bytes

```
{×/-∊(⍳≢⍵)↓¨↓∘.-⍨⍵}

```

Dfn producing the pairs, then taking the product.

`↓∘.-⍨⍵` all pairs (with repeats)

`(⍳≢⍵)` range from 1 to the length of the input

`↓¨` drop 1 2 3 4... elements to avoid repeats

`-∊` flatten and negate

`×/` take the product

Try it online!
> 3 votes

# Answer
# Husk, <sup>~~12 9~~</sup> 8 bytes

```
ΠṁhṠzM-ḣ

```

Try it online!

(Apparently the only one of the three which was correct)

-3 bytes by calculating difference instead of pairs.

-1 from Jo King

## Explanation

```
ΠṁhṠzM-ḣ
   Ṡz    zip the input with
       ḣ prefixes
     M-  subtract the input from each
 ṁh      remove first element of each, join
Π        product

```
> 3 votes

# Answer
# Matlab, 26 bytes

(noncompeting)

Straightforward use of builtins. Note that (once again) Matlab's `vander` creates Vandermonde matrices but with the order of the rows flipped.

```
@(v)det(fliplr(vander(v)))

```
> 2 votes

# Answer
# Perl, 38 ~~41~~ bytes

Include +1 for `-p`

Give the numbers on a line on STDIN. So e.g. run as

```
perl -p vandermonde.pl <<< "1 2 4 8"

```

Use an evil regex to get the double loop:

`vandermonde.pl`:

```
$n=1;/(^| ).* (??{$n*=$'-$&;A})/;*_=n

```
> 2 votes

# Answer
# Pari/GP, 35 bytes

```
a->matdet(matrix(#a,,i,j,a[i]^j--))

```

Try it online!
> 2 votes

# Answer
## Rust, 86 bytes

```
|a:Vec<f32>|(0..a.len()).flat_map(|x|(x+1..a.len()).map(move|y|y-x)).fold(1,|a,b|a*b);

```

Rust, verbose as usual...

Explanation will come later (it's pretty straightforward, though).
> 1 votes

# Answer
## JavaScript (ES6), 61 bytes

```
a=>a.reduce((p,x,i)=>a.slice(0,i).reduce((p,y)=>p*(x-y),p),1)

```

I tried an array comprehension (Firefox 30-57) and it was 5 bytes longer:

```
a=>[for(i of a.keys(p=1))for(j of Array(i).keys())p*=a[i]-a[j]]&&p

```

The boring nested loop is probably shorter though.
> 1 votes

# Answer
## Haskell, 53 bytes

```
 f x=product[x!!j-x!!i|j<-[1..length x-1],i<-[0..j-1]]

```

Usage example: `f [1,2,4,8,16]` -\> `20321280`.

Go through the indices `j` and `i` in a nested loop and make a list of the differences of the elements at position `j` and `i`. Make the product of all elements in the list.

Other variants that turned out to be slightly longer:

`f x=product[last l-i|l<-scanl1(++)$pure<$>x,i<-init l]`, 54 bytes

`import Data.List;f i=product[y-x|[x,y]<-subsequences i]`, 55 bytes
> 1 votes

# Answer
## CJam, 16 bytes

```
1l~{)1$f-@+:*\}h

```

In response to A Simmons' post, despite CJam's lack of a combinations operator, yes it is possible to do better :)

-1 byte thanks to @MartinBüttner.

Try it online | Test suite

```
1                   Push 1 to kick off product
 l~                 Read and evaluate input V
   {          }h    Do-while loop until V is empty
    )                 Pop last element of V
     1$               Copy the prefix
       f-             Element-wise subtract each from the popped element
         @+           Add the current product to the resulting array
           :*         Take product to produce new product
             \        Swap, putting V back on top

```
> 1 votes

# Answer
# Japt v1.4.5, 8 bytes

```
à2 ®rnÃ×

```

Try it (includes all test cases)

```
à2 ®raÃ×     :Implicit input of array
à2           :Combinations of length 2 (using v1.4.5 avoids a bug here in later versions)
   ®         :Map
    r        :  Reduce by
     n       :  Inverse subtraction
      Ã      :End map
       ×     :Reduce by multiplication

```
> 1 votes

# Answer
# 05AB1E, 6 bytes

```
η-€¨˜P

```

Try it online!

**Commented**:

```
η         # prefixes of the input
 -        # subtract those from the input
  €       # for each sublist:
   ¨      #   remove the last element (i=j)
    ˜     # flatten the list
     P    # take the product

```

There are a few alternatives at the same length, such as `ηõš-˜P`.
> 1 votes

# Answer
# Desmos, 10+39=49 bytes

```
n=a.length
\prod_{i=1}^n\prod_{j=i+1}^n(a[j]-a[i])

```

View it in Desmos

There's not a lot to be golfed here other than "caching" `a.length` in an array, but I would like to point out that Desmos can handle the `...` notation in arrays!
> 1 votes

# Answer
# Python 3, 91 bytes (does NOT work yet)

```
lambda x:eval("*".join([str(b-a) for a,b in combinations(x,2)]))or 1
from itertools import*

```

Try it online!

Port of Alex A.'s answer.

Fixing currently.
> 1 votes

# Answer
# Factor \+ `math.matrices math.matrices.laplace`, 45 bytes

```
[ dup length vandermonde-matrix determinant ]

```

Attempt This Online!
> 1 votes

# Answer
# CJam, 32 bytes

```
1q~La\{1$f++}/{,2=},{~-}%~]La-:*

```

I'm sure someone can golf this better in CJam... The main issue is that I can't see a good way of getting the subsets so that uses up most of my bytes. This generates the power set (using an idea by Martin Büttner) and then selects the length-2 elements.
> 0 votes

# Answer
# , 41 bytes

```
function(v)det(outer(v,1:sum(v|1)-1,"^"))

```

Try it online!

I was surprised not to see an R answer here!
> 0 votes

# Answer
# Perl 5 `-pa`, 36 bytes

```
$\=1;map$\*=$q-$_,@F while$q=pop@F}{

```

Try it online!
> 0 votes

# Answer
# Arn, 27 bytes

```
ùW®š¡'‡ùHÓáâ§○iò;êñ⁺bì&B"$7

```

Try it!

# Explained

Unpacked: `*{*v{v-:{}\.{}\[_ _{.{}->--((:s)#`

```
* ... \                  % Fold with multiplication after mapping
  {                      % Begin block
    * ... \
      v{                 % Block with key of `v`
          v              % Variable with identifier `v`
        -                % Minus
            _            % Variable intialized to STDIN; implied
          :{             % Head
      }                  % End block
              _          % Implied
            .{           % Beheaded
  }
        [                % Begin sequence
          _              % Entry equal to STDIN
          _{             % Block with key of `_` (needed otherwise the first `_` will be grabbed)
              _          % Last entry; implied
            .{           % Beheaded
          }
          ->             % Of length
            --           % Reduced by one
              (          % Begin expression
                  (
                      _  % Implied
                    :s   % Split on spaces
                  )      % End expression
                #        % Length
              )          % Implied
        ]                % End of sequence; implied

```

Had to fix a few major bugs I only found because of this challenge! Also made me consider adding a few quality of life features (including an upgrade to precedence and `#` automatically casting to a vector).

Speaking of bugs, I am 100% certain this works on the downloadable version, and it should be working on the online version very soon.
> 0 votes

---
Tags: code-golf, math, matrix, linear-algebra
---


title: Form tiles in a rectangular ring

text:
# Question
Title: Form tiles in a rectangular ring
Given the input `tilesX` and `tilesY` create a method that would make a rectangular ring from the tiles.

The function must order the tiles in a ring like this:

* `tilesX` and `tilesY` are always positive integer values, cannot be 0
* `tilesX` and `tilesY` are not always equal, expect values like: `2x5`, `6x3` etc.
* Checking for invalid input is not necessary
* You can use any way to display the tiles, including 2d arrays, ASCII art or printed text.
* There's no strict way how the input is passed as long as it's two integers.
* Cannot be a line, drawing a rectangle size of `tilesX` and `tilesY` pixels is not valid
* The shortest code wins

# Answer
# Dyalog APL, 8 bytes

```
×/¨1<⊂|⍳

```

This monadic function train takes height and width as right arguments and returns a 2D array of **0**'s (border) and **1**'s (interior). Test it on TryAPL.

### How it works

```
×/¨1<⊂|⍳  Right argument: h w

       ⍳  Generate all index pairs (1-based) of a h×w array.
     ⊂    Enclose (h w), so it depth matches the one of the index array.
      |   For each pair (i j) compute the remainders of the division by (h w).
   1<     Compare all remainders with 1.
×/¨       Reduce each pair of Booleans by multiplication.

```
> 7 votes

# Answer
# MATL, 10 bytes

```
2$lO6Lt4$(

```

This outputs an array containing zeros and ones.

**Try it online!**

```
2$l    % Implicit inputs M, N. Generate M×N array of ones
O      % Push number 0
6Lt    % Push [2 -1] twice, corresponding to index "2:end-1"
4$(    % Fill the center of the array with value 0. Implicit display

```

---

For graphical output, add `1YG` at the end to display the array as an image (**13 bytes**) :

```
2$Ol6Lt4$(1YG

```

Try it at **MATL Online!** For example,

```
>> matl 2$Ol6Lt4$(1YG
> 5
> 7

```

produces
> 5 votes

# Answer
# MATLAB, ~~32~~ 31 bytes

```
@(x)conv2(ones(x),eye(3),'s')>2

```

This creates an anonymous function which can then be run as `ans([4 5])` within the workspace.

Input is `[height, width]` and output is a matrix with 1 in the center and 0 for the boundary.

The way that this works is a matrix of ones the size of the input is created. It is then convolved with a 3 x 3 identify matrix with ones on the diagonal. We use the `same` input to `conv2` (shortened to `'s'` here) to keep the result the same size as the input.

We then want to convert the output to a binary value with 0 around the boundary and 1 inside. We use the inequality `>2` because all edge pixels will have a result \< 3 and all non-boundary elements will have a result equal to 3.

For graphical output:

```
@(x)imagesc(conv2(ones(x),eye(3),'s')>8)
ans([6,9])

```
> 5 votes

# Answer
# MATL, 10 bytes

```
2$l3XyZ+3=

```

Input arguments are height and width as integers. The output is a matrix of size `height x width` where the boundary tiles are 0 and the inner values are 1.

**Try it Online!**

**Explanation**

Same logic as my other answer with fewer bytes.

```
        % Grab two input parameters implicitly
2$l     % Create a matrix of ones that has the dimensions specified as inputs
3       % Number literal 3
Xy      % Create a 3x3 identity matrix
Z+      % Perform 2D convolution (preserving size)
3=      % Create a logical matrix where values == 3 are 1 and 0 otherwise (boundary)
        % Implicitly display output.

```
> 5 votes

# Answer
## HTML/JS/CSS, ~~198~~ 194 bytes

Graphical output version. The byte count doesn't include `f=` nor the three `<input>` elements which are used for demonstration purposes only. Saved 3 bytes thanks to @IsmaelMiguel.

```
f=(n,m)=>{with(d.style)width=n*25+'px',height=m*25+'px'}
```

```
<input id=w placeholder=width><input id=h placeholder=height><input type=button value=Go! onclick=f(w.value,h.value)>
<div id=d style="border-image:radial-gradient(#fff 0,#fff 0)0 fill/25px;background:radial-gradient(#000 0,#000 8px,#fff 9px)0 0/25px 25px">
```
> 4 votes

# Answer
# Jelly, 10 bytes

```
p%€,>1P€G

```

Returns a grid of **0**'s (border) and **1**'s (interior). Try it online!

### How it works

```
p%€,>1P€sG  Main link. Arguments: h (height), w (width)

p           Cartesian product; return all pairs in [1, ..., h] × [1, ..., w].
   ,        Yield the pair [h, w].
 %€         For each pair [i, j] in the product, compute [i % h, j % w].
    >1      Compare all resulting moduli with 1.
      P€    Compute the product of each pair of Booleans.
        s   Split the resulting flat list into rows of length w.
         G  Display the results in a 2D grid.

```
> 3 votes

# Answer
# Julia, ~~46~~ 34 bytes

```
f(n,m)=[n>i>1<j<m for i=1:n,j=1:m]

```

This is a function that accepts two integers and returns a 2-dimensional boolean array.

We construct an *n* × *m* matrix using an array comprehension with a double `for` loop. For each index from 1 to *n* and 1 to *m*, i.e. each element of the matrix, we set the value to `true` if *n* \> *i* \> 1 and 1 \< *j* \< *m*. This is true everywhere but the boundaries, so the resulting array will have `true`s in the middle and `false`s around the border.

Examples:

```
julia> f(n,m)=[n>i>1<j<m for i=1:n,j=1:m]
f (generic function with 1 method)

julia> f(4,4)
4x4 Array{Bool,2}:
 false  false  false  false
 false   true   true  false
 false   true   true  false
 false  false  false  false

julia> f(1,1)
1x1 Array{Bool,2}:
 false

julia> f(2,5)
2x5 Array{Bool,2}:
 false  false  false  false  false
 false  false  false  false  false

```

Saved 12 bytes thanks to Dennis!
> 3 votes

# Answer
# , 12 bytes

```
*/&(<:*@|i.)

```

Try it online!

Coming back to this, almost 3 years later. An idea inspired by Dennis answer, though not a translation.

* `i.` Create 0 based index lists from each arg
* `<: |` remainders when divided by the arg minus 1
* `*@` signup the results. Now, eg, if an arg was 4, we'll have a list like `0 1 1 0`
* `*/` Create a multiplication table of those lists.

## Original Answer, 16 bytes

```
0(<2#<<0 _1)}$&1

```

Use shape `$` to create a rectangle of all ones the size of the inputs, and then use the complementary form of Amend `}` to turn the interior to zeros.

Try it online!
> 3 votes

# Answer
## Pyke, ~~16~~ 15 bytes

```
jQ]Uajt%!RQt%!|

```

Try it here!

Explanation:

```
                - Q = eval_input()
j               - j = eval_input()
jQ]             - [Q,j]
   U            - create a 3d array sized Q by j with coords
    a           - for each coord (2d for)
     jt%!       -   not (coord_1 % j-1)
              | -  ^ or V
          Qt%!  -   not (coord_2 % Q-1)

```

For prettified output, use this code.

Or 13 bytes with a zeroed out mask round the edge (middle chars non-zero)

```
jQ]Uajt%RQt%&

```

Try it here!
> 2 votes

# Answer
## CJam, 20 bytes

```
l~S*a*{3a.f|W%z}4*N*

```

Input should be in the form `height width`, output is an ASCII grid using spaces for the centre and `#` for the boundary.

Test it here.

### Explanation

```
l~       e# Read and evaluate input, dumping h and w on the stack.
S*       e# Create a string of w spaces.
a*       e# Create an array of h copies of that string.
{        e# Repeat this block 4 times...
  3a.f|  e#   For each character in the first row, take its bitwise OR with 3, turning
         e#   spaces into # and leaving # unchanged.
  W%z    e#   Reverse and transpose the grid, rotating it by 90 degrees.
}4*
N*       e# Join the lines of the result with linefeeds.

```
> 2 votes

# Answer
# JavaScript (ES6), 80 ~~82 85~~

**Edit** 3 bytes saved thx @Neil
**Edit** 2 bytes saved using `reduce` for once

Anonymous function returning a multi line string

```
(w,h)=>[...Array(h)].reduce(o=>o+(w>1?'O'+' O'[!--h|!o].repeat(w-2):'')+`O
`,'')

```

**Test**

```
f=(w,h)=>[...Array(h)].reduce(o=>o+(w>1?'O'+' O'[!--h|!o].repeat(w-2):'')+`O
`,'')

function test(){
  var [w,h] = I.value.match(/\d+/g)
  w=+w,h=+h // convert to numeric
  O.textContent=f(w,h)
}

test()
```

```
<input value='5 4' id=I><button onclick='test()'>Test</button><pre id=O></pre>
```
> 2 votes

# Answer
# Ruby, 63 bytes

Anonymous function, prints to STDOUT. Border is `#`.

```
->x,y{h=?#;puts t=h*x,y>1?[[h+(x<2?'':' '*(x-2)+h)]*(y-2),t]:p}

```
> 2 votes

# Answer
# Perl 5, 45 + 1 (`-p`) = 46 bytes

```
$_=join$/,(1x$_)x<>;1while s/
.+\K1(?=.+
)/ /

```

following 45 bytes doesn't handle tileY=1

```
$_=1x<>.$/;say$_.s/(?!^.|.$)./ /gr x(<>-2).$_

```

Try it online
> 2 votes

# Answer
## JavaScript (ES6), 97 bytes

```
(n,m)=>Array(n).fill(' '.repeat(m).replace(/^ | $/g,0)).join`
`.replace(/^.+|.+$/g,'0'.repeat(m))

```

Creates a ring of `0`s. Probably a terrible approach but I wanted to avoid edge cases.
> 1 votes

# Answer
# JavaScript (ES6), 77 bytes

```
h=>w=>[...Array(i=h)].map(_=>(a=Array(w).fill(h-i--&&i?0:1),a[0]=a[w-1]=1,a))

```
> 1 votes

# Answer
## Retina, ~~45~~ 43 bytes

```
\d+
$*
S_`1(?=.* (1+))|.
T`1`#`^.+|.+$|.?¶.

```

Input should be in the form `height width`, output is an ASCII grid using `1` for the centre and `#` for the boundary.

Try it online!

### Explanation

```
\d+
$*

```

Convert each number `N` to a string of `N` ones (i.e. convert the input to unary).

```
S_`1(?=.* (1+))|.

```

Match each `1` in `height` and replace it with `width`, while also matching everything else and removing it. We do this by abusing a split stage. This creates a `w x h` grid.

```
T`1`#`^.+|.+$|.?¶.

```

Finally we replace every `1` with a `#` that is either found in the first line, the last line or at the beginning or end of a line.
> 1 votes

# Answer
## Actually, 23 bytes

```
;'#*;))¬' *'#;)@+(+nXX(

```

Try it online!

This approach is very similar to my approach in this related challenge.

Explanation:

```
;'#*;))¬' *'#;)@+(+nXX(
                         (implicit) push all input to stack
;'#*                     push a string containing X #s
    ;))                  dupe, and push both to bottom of stack
       ¬' *              push a string containing (X-2) spaces
           '#;)@+(+      add a # to the front and the back of the string
                   nXX   make (Y-2) copies
                      (  bring one of the "#"*X strings back to the top
                         (implicit) pop and print each stack item, separated by newlines

```
> 1 votes

# Answer
# TSQL, ~~107~~ ~~105~~ 97 bytes

```
DECLARE @ INT=3,@y INT=5

PRINT REPLICATE(1,@)+ISNULL('
'+REPLICATE('1'+ISNULL(SPACE(@-2),'')+'1
',@y-2)+REPLICATE(1,@),'')

```

> 1. generating first line
> 2. adding hollow lines + line breaks
> 3. adding last line(when needed)
> 1 votes

# Answer
# QBasic, 69 bytes

```
INPUT x,y
FOR i=1TO y
FOR j=1TO x
?i MOD y<2OR j MOD x<2;
NEXT
?
NEXT

```

Takes dimensions as `width,height`. The boolean value from the is-it-on-the-border test is simply printed: `-1` for true and `0` for false. A sample run looks like:

```
? 5,3
-1 -1 -1 -1 -1
-1  0  0  0 -1
-1 -1 -1 -1 -1

```

**Bonus: Graphical version, 88 bytes**

```
INPUT x,y
SCREEN 9
FOR i=1TO y
FOR j=1TO x
PSET(j*3,i*3),i MOD y<2OR j MOD x<2
NEXT
NEXT

```

I believe this counts as "not a line." When the `MOD` expression is false (0), `PSET` plots a black pixel; when it's true (-1), `PSET` apparently plots a white pixel. Here's `17,31`, shown at 2x size:
> 1 votes

# Answer
# Unicorn, ~~26~~ 23 bytes

```
P3G$PG@PS@S$L2B$T1B@T1N

```

Because who doesn't like unicorns?!

Explanation ("list program" output):

```
P3  Paint current square with 3
G$P Get: sets $ from input P
G@P Get: sets @ from input P
S@  Subtract 1 from @
S$  Subtract 1 from $
L2  ~Loop 2 times
B$  ~Brush $ more square
T1  ~Turn 1 right angle clockwise
B@  ~Brush @ more square
T1  ~Turn 1 right angle clockwise
N   ~Next (loop)

```

Output for `tilesX` = 3, `tilesY` = 5:

Note: This version only works for `tilesX` up to 6 and `tilesY` up to 5. The question does not mention what range we need to support though, so I'm assuming this is OK. Otherwise, a small addition to the program produces this alternative, which supports a slightly larger range:

# Unicorn, ~~30~~ 27 bytes

```
x0y9P3G$PG@PS@S$L2B$T1B@T1N

```

By adding `x0y9`, which starts the box at (0,9), the program works for `tilesX` up to 9 and `tilesY` up to 9 (because input only goes up to 9).
> 1 votes

# Answer
# Perl 5, 76 + 1 (`-a`) = 77 bytes

```
print(1x($a=$F[0]),$/,((1,$"x($a-2),1 x($a>1),$/)x($F[1]-2),1x$a)x($F[1]>1))

```

Try it online!
> 1 votes

# Answer
# 05AB1E, 6 bytes

```
«¾6ÅÈΛ

```

Input as a pair of integers, where the first is the height and the second is the width.
Outputs with `0` as characters.

Try it online.

**Explanation:**

```
     Λ  # Use the Canvas builtin with the following three options:
        # (after which the resulting shape is output implicitly immediately afterwards)
«       # - line lengths: use the (implicit) input-integer, merged with itself: [h,w,h,w]
  6ÅÈ   # - the directions: push a list of even integers <= 6: [0,2,4,6]
 ¾      # - what to draw: push the counter variable, which is 0 by default

```

The Canvas builtin uses three arguments to draw a shape:

* Character/string to draw: character `0`, which could alternatively be `1`/`2` by replacing the `¾` with `X`/`Y` respectively.
* Length of the lines we'll draw: the input-list twice. Since there is more than one input-length, these are leading for the Canvas builtin, so we'll need the additional merge `«` at the start, otherwise it would only draw the top and left borders, instead of the entire box.
* The direction to draw in: `[0,2,4,6]`. The digits in the range \\$\[0,7\]\\$ each represent a certain direction:

```
7   0   1
  ↖ ↑ ↗
6 ← X → 2
  ↙ ↓ ↘
5   4   3

```

So the `[0,2,4,6]` in this case translate to the directions \\$\[↑,→,↓,←\]\\$.

Here a step-by-step explanation of the output (we'll use input-lengths `[3,5]` as example here):

Step 1: Draw 3 `0` characters in direction `0↑`:

```
0
0
0

```

Step 2: Draw 5-1 `0` characters in direction `2→`:

```
00000
0
0

```

Step 3: Draw 3-1 `0` characters in direction `4↓`:

```
00000
0   0
0   0

```

Step 4: Draw 5-1 `0` characters in direction `6←`:

```
00000
0   0
00000

```

See this 05AB1E tip of mine for an in-depth explanation of the Canvas builtin.
> 1 votes

# Answer
# Charcoal, 4 bytes

```
ＢＮＮ*

```

First input is the width, second input is the height.

Try it online (verbose) or try it online (pure).

**Explanation:**

```
ＢＮＮ*
Box(InputNumber(),InputNumber(),"*")

```

Builtin: draw a box using the two input as width/height respectively and character `*` as border. (The `*` can be replaced with other ASCII characters that are available in the Charcoal codepage.)
> 0 votes

# Answer
# Python 3, ~~71~~ ~~67~~ 63 bytes

```
lambda n,m:[[n>i+1>1<j+1<m for i in range(n)]for j in range(m)]

```

Returns a 2 dimensional array. Try it online!

Port of Alex A.'s answer.

-4 thx to @Steffan
> 0 votes

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


# Question
Title: Determine if an integer is a palindrome in a given radix (base)
Write a program that reads from stdin two integers, each newline terminated, hereafter called "number" and "radix", and:

1. Prints any fixed message you want if the number is a palindrome in that radix (e.g. `true`, `t`, `1`)
2. Prints any different fixed message you want if the number is not a palindrome in that radix (e.g. `false`, `f`, `0`, etc.)
3. These messages must be the same per each run, but there are no rules about what they must be (whatever's best for golfing).
4. You may assume the input is valid, two positive integers. "number" will not exceed `2147483647`, "radix" will not exceed `32767`.
5. You may not use external resources, but you may use any math function included by default in your language.

**Note:** a radix is just the base of the number.

Sample runs:

```
16
10
false

16
3
true

16
20
true

121
10
true

5
5
false

12346
12345
true

16781313
64
true

16781313
16
true

```

# Answer
# J (23 char) and K (19) double feature

The two languages are very similar, both in general and in this specific golf. Here is the J:

```
(-:|.)#.^:_1~/".1!:1,~1

```
* `,~1` \- Append the number 1 to itself, making the array `1 1`.
* `1!:1` \- Read in two strings from keyboard (`1!:1` is to read, and `1` is the file handle/number for keyboard input).
* `".` \- Convert each string to a number.
* `#.^:_1~/` \- `F~/ x,y` means to find `y F x`. Our `F` is `#.^:_1`, which performs the base expansion.
* `(-:|.)` \- Does the argument match (`-:`) its reverse (`|.`)? `1` for yes, `0` for no.

And here is the K:

```
a~|a:_vs/|.:'0::'``

```
* `0::'``` \- Read in (`0::`) a string for each (`'`) line from console (``` is the file handle for this).
* `.:'` \- Convert (`.:`) each (`'`) string to a number.
* `_vs/|` \- Reverse the pair of numbers, so that the radix is in front of the number, and then insert (`/`) the base expansion function `_vs` ("vector from scalar") between them.
* `a~|a:` \- Assign this resulting expansion to `a`, and then check if `a` matches (`~`) its reverse (`|`). Again, `1` for yes, `0` for no.
> 5 votes

# Answer
### GolfScript, 10 characters

```
~base.-1%=

```

That is an easy one for GolfScript if we do it the straightforward way. The output is `0`/`1` for false/true.

```
~       # Take input and evaluate it (stack: num rdx)
base    # Fortunately the stack is in the correct order for
        # a base transformation (stack: b[])
.       # Duplicate top of stack (stack: b[] b[])
-1%     # Reverse array (stack: b[] brev[])
=       # Compare the elements

```
> 8 votes

# Answer
## APL (20)

```
⎕{≡∘⌽⍨⍵⊤⍨⍺/⍨⌊1+⍺⍟⍵}⎕

```

Outputs `0` or `1`, e.g:

```
      ⎕{≡∘⌽⍨⍵⊤⍨⍺/⍨⌊1+⍺⍟⍵}⎕
⎕:
      5
⎕:
      5
0
      ⎕{≡∘⌽⍨⍵⊤⍨⍺/⍨⌊1+⍺⍟⍵}⎕
⎕:
      16781313
⎕:
      64
1

```

Explanation:

* `⎕{`...`}⎕`: read two numbers, pass them to the function.  is the first number and  is the second number.
* `⌊1+⍺⍟⍵`: `floor(1+⍺ log ⍵)`, number of digits necessary to represent  in base .
* `⍺/⍨`: the base for each digit, so  replicated by the number we just calculated.
* `⍵⊤⍨`: represent  in the given base (using numbers, so it works for all values of ).
* `≡∘⌽⍨`: see if the result is equal to its reverse.
> 4 votes

# Answer
## Perl, 82 77 73 69 bytes

```
$==<>;$.=<>;push(@a,$=%$.),$=/=$.while$=;@b=reverse@a;print@a~~@b?1:0

```

The input numbers are expected as input lines of STDIN and the result is written as `1` or `0`, the former meaning the first number is a palindrome in its representation of the given base.

**Edit 1:** Using `$=` saves some bytes, because of its internal conversion to int.

**Edit 2:** The smartmatch operator `~~` compares the array elements directly, thus the conversion to a string is not needed.

**Edit 3:** Optimization by removing of an unnecessary variable.

**65 bytes**: If the empty string is allowed as output for `false`, the last four bytes can be removed.

## Ungolfed version

```
$= = <>;
$. = <>;
while ($=) {
    push(@a, $= % $.);
    $= /= $.; # implicit int conversion by $=
}
@b = reverse @a;
print (@a ~~ @b) ? 1 : 0

```

The algorithm stores the digits of the converted number in an array `@a`. Then the string representation of this array is compared with the array in reverse order. Spaces separates the digits.
> 3 votes

# Answer
## Sage, 45

Runs in the interactive prompt

```
A=Integer(input()).digits(input())
A==A[::-1]

```

Prints `True` when it is a palindrome, prints `False` otherwise
> 2 votes

# Answer
## Javascript 87

```
function f(n,b){for(a=[];n;n=(n-r)/b)a.push(r=n%b);return a.join()==a.reverse().join()}

```

`n` argument is the number, `b` argument is the radix.
> 2 votes

# Answer
### Perl ~~54 56~~ 62

```
$==<>;$-=<>;while($=){$_.=$/.chr$=%$-+50;$=/=$-}say$_==reverse

```

To be tested:

```
for a in $'16\n3' $'16\n10' $'12346\n12345' $'12346\n12346' $'21\n11' $'170\n16';do
    perl -E <<<"$a" '
        $==<>;$-=<>;while($=){$_.=$/.chr$=%$-+50;$=/=$-}say$_==reverse
    '
  done

```

will give:

```
1

1

1

```

So this output `1` for `true` when a palindrome is found and *nothing* if else.

### Ungolfing:

```
$==<>;                            # Stdin to `$=`  (value)
$-=<>;                            # Stdin to `$-`  (radix)
while ( $= ) {
    $_.= $/. chr ( $= % $- +50 ); # Add *separator*+ chr from next modulo to radix to `$_`
    $=/= $-                       # Divide value by radix
}
say $_ == reverse                 # Return test result

```

**Nota**:

* `$_` is the current line buffer and is empty at begin.
* `$=` is a *reserved* variable, originaly used for line printing, this is a line counter. So this variable is an **integer**, any calcul on this would result in a truncated integer like if `int()` was used.
* `$-` was used for fun, just to not use traditional letters... (some more obfuscation)...
> 2 votes

# Answer
# Mathematica ~~77~~ 43

`IntegerDigits[n,b]` represents n as a list of digits in base b. Each base-b digit is expressed decimally.

For example, 16781313 is not a palindrome in base 17:

```
IntegerDigits[16781313, 17]

```

> {11, 13, 15, 11, 14, 1}

However, it **is** a palindrome in base 16:

```
IntegerDigits[16781313, 16]

```

> {1, 0, 0, 1, 0, 0, 1}

---

If the ordered pairs in the above examples were entered,

```
(x=Input[]~IntegerDigits~Input[])==Reverse@x

```

would return

> False (\* (because {11, 13, 15, 11, 14, 1} != {1, 14, 11, 15, 13, 11} ) \*)
>
> True (\* (because {1, 0, 0, 1, 0, 0, 1} is equal to {1, 0, 0, 1, 0, 0, 1} ) \*)
> 1 votes

# Answer
**Haskell (80 chars)**

```
tb 0 _=[]
tb x b=(tb(div x b)b)++[mod x b]
pali n r=(\x->(x==reverse x))(tb n r)

```

Call it with `pali $number $radix`. True, when number is a palindrome, False if not.
> 1 votes

# Answer
**Ruby - 76 chars**

```
f=->(n,b){n==0?[]:[n%b,*f.(n/b,b)]};d=f.(gets.to_i,gets.to_i);p d==d.reverse

```
> 1 votes

# Answer
# Perl 6, 27 bytes (22 without stdin/out)

```
say (+get).base(get)~~.flip

```

Try it online!

```
  get()                     # pulls a line of stdin
 +                          # numerificate
(      ).base(get())        # pull the radix and call base to
                            #  convert to string with that base
                    ~~      # alias LHS to $_ and smartmatch to
                      .flip # reverse of the string in $_

```

Perl6, king of readable golfs (golves?) (and also some not so readable).

# Perl 6 function (not stdin/stdout), 22 bytes

```
{$^a.base($^b)~~.flip}

```

Try it online!
> 1 votes

# Answer
# dg - 97 bytes

Trying out dg:

```
n,r=map int$input!.split!
a=list!
while n=>
 a.append$chr(n%r)
 n//=r
print$a==(list$reversed a)

```

Explained:

```
n, r=map int $ input!.split!      # convert to int the string from input
a = list!                         # ! calls a function without args
while n =>
 a.append $ chr (n % r)           # append the modulus
 n //= r                          # integer division
print $ a == (list $ reversed a)  # check for palindrome list

```
> 0 votes

# Answer
# C, 140 132

```
int x,r,d[32],i=0,j=0,m=1;main(){scanf("%d %d",&x,&r);for(;x;i++)d[i]=x%r,x/=r;i--;for(j=i;j;j--)if(d[j]-d[i-j])m=0;printf("%d",m);}

```
* radix 1 is not supported:)
> 0 votes

# Answer
# Haskell - 59

Few changes to Max Ried's answer.

```
0%_=[]
x%b=x`mod`b:((x`div`b)%b)
p=((reverse>>=(==)).).(%)

```
> 0 votes

# Answer
# LaTeX, 165 bytes

Example at desmos.com

`k`, the radix, is an adjustable input

```
b=\floor \left(\log _k\left(\floor \left(x\right)\right)\right)
f\left(x\right)=k^bx-x-\left(k^2-1\right)\sum _{n=1}^bk^{\left(b-n\right)}\floor \left(xk^{-n}\right)

```

If `f(x)=0`, `x` is a palindrome in base `k`.
> 0 votes

# Answer
# Pyth, 4 bytes

```
_IjF

```

**Try it here** or check out a **test suite** (Takes ~10-15 seconds).
> 0 votes

# Answer
# 05AB1E,  ~~4~~  3 bytes

```
вÂQ

```

Try it online or verify all test cases.

**Explanation:**

```
в      # The first (implicit) input converted to base second (implicit) input
       #  i.e. 12345 and 12346 → [1,1]
       #  i.e. 10 and 16 → [1,6]
 Â     # Bifurcate the value (short for duplicate & reverse)
       #  i.e. [1,1] → [1,1] and [1,1]
       #  i.e. [1,6] → [1,6] and [6,1]
  Q    # Check if they are still the same, and thus a palindrome
       #  i.e. [1,1] and [1,1] → 1
       #  i.e. [1,6] and [6,1] → 0

```
> 0 votes

# Answer
# dc, 39 bytes

The length is a palindrome, of course (`33₁₂`).

```
[[t]pq]sgod[O~laO*+sad0<r]dsrx+la=g[f]p

```

The number and radix should be on the top of the stack (in the current number base); number must be at least 0, and radix must be at least 2. Output is `t` if it's a palindrome and `f` if not. As it's not specified in the challenge, I've assumed that numbers never have leading zeros (so any number ending in `0` cannot be a palindrome).

## Explanation

As a full program:

```
#!/usr/bin/dc

# read input
??

# success message
[[t]pq]sg

# set output radix
o

# keep a copy unmodified
d

# reverse the digits into register a
[O~ laO*+sa d0<r]dsrx

# eat the zero left on stack, and compare stored copy to a
+ la=g

# failure message
[f]p

```
> 0 votes

# Answer
# Perl 6, 34 bytes

*-4 bytes thanks to PhilH*

```
{@(polymod $^a: $^b xx*)~~[R,] $_}

```

Try it online!
> 0 votes

# Answer
# C (gcc), 79 bytes

```
n,r,m;main(o){for(scanf("%d %d",&n,&r),o=n;n;n/=r)m=m*r+n%r;printf("%d",m==o);}

```

Try it online!

## Rundown

```
n,r,m;main(o){
for(scanf("%d %d",&n,&r),       Read the number and the radix.
o=n;                            ...and save the number in o
n;                              Loop while n is non-zero
n/=r)                           Divide by radix to remove right-most digit.
m=m*r+n%r;                      Multiply m by radix to make room for a digit
                                and add the digit.
printf("%d",m==o);}             Print whether we have a palindrome or not.

```

Based on the fact that for a palindrome, the reverse of the number must equal the number itself.

Suppose you have the three-digit number ABC in some base. Multiplying it by base will always result in ABC0, and dividing it by base in AB with C as remainder. So to reverse the number we pick off the right-most digit from the original number and insert it to the right on the reversed number. To make room for that digit, we multiply the reverse by base before-hand.

Basically:

```
n       rev
ABC     0
AB      C
AB      C0
A       CB
A       CB0
0       CBA

```
> 0 votes

# Answer
# Jelly, 3 bytes

```
bŒḂ

```

Try it online!

## How it works

```
bŒḂ - Main link. Takes a number n on the left and a radix r on the right
b   - Convert n to base r
 ŒḂ - Is palindrome?

```
> 0 votes

# Answer
# Python 3.8 (pre-release), ~~167~~ ~~162~~ ~~65~~ 63 bytes

```
a,b=map(int,open(s:=0))
o=a
while a:s=s*b+a%b;a//=b
print(s==o)

```

Try it online!

Massive -99 thx to @Steffan
> 0 votes

---
Tags: code-golf, decision-problem, base-conversion, palindrome
---


title: Normal Subgroups of \$S_4\$

text:
# Question
Title: Normal Subgroups of \$S_4\$
# Objective

Given a permutation of 4 distinct items, classify the permutation by the normal subgroup(s) it belongs.

# Input/Output Format

You gotta choose the followings as the hyperparameters for your submission:

* The 4 distinct items.
* The permutation serving as the identity permutation.

The input format is to accept a permutation of the items you chose. The items must be computably distinguishable.

The output format is flexible; you can output anything as long as the classes are computably distinguishable.

Standard loopholes apply.

In any case, an input not fitting into your format falls into *don't care* situation.

# Classification

For example, suppose you chose the numbers `0`, `1`, `2`, and `3` as the 4 items, and chose the string `0123` as the identity permutation.

* The identity permuation `0123` is classified as the member of the trivial group \\$\textbf{0}\\$.
* The permutations consisting of two non-overlapping swaps are classified as members of the Klein-four group \\$K\_4\\$ minus the trivial group. Those are `1032`, `2301`, and `3210`.
* The permutations that fixes exactly one item are classified as members of the alternating group \\$A\_4\\$ minus the Klein-four group. Those are `0231`, `0312`, `1203`, `1320`, `2013`, `2130`, `3021`, and `3102`.
* The remaining permuations are classified as members of the symmetric group \\$S\_4\\$ minus the alternating group.

# Examples

Let's say you chose the string `READ` as the identity permutation, and chose to output the classes as numbers `0`, `1`, `2`, and `3`, respectively to the list above.

* Given the string `ADER`, output `3`.
* Given the string `ADRE`, output `1`.
* Given the string `RADE`, output `2`.
* Given the string `READ`, output `0`.

# Answer
# Jelly, 8 bytes

```
ỤƑḤ_=JSƊ

```

A monadic Link that accepts a permutation of `[1, 2, 3, 4]` and yields:

| classification | output |
| --- | --- |
| \\$e\\$ | -2 |
| rest of \\$K\_4\\$ | 2 |
| rest of \\$A\_4\\$ | -1 |
| rest of \\$S\_4\\$ | 0 |

**Try it online!** Or see all cases.

### How?

```
ỤƑḤ_=JSƊ - Link: list of integers from [1..4], P
 Ƒ       - is (P) invariant under the application of:
Ụ        -   grade-up -> 1-indexed indices sorted by value
  Ḥ      - double -> X = 2 or 0
       Ɗ - last three links as a monad - f(P):
     J   -   range of length -> [1,2,3,4]
    =    -   (P) equals (that) (vectorises)
      S  -   sum -> Y
   _     - (X) minus (Y)

```
> 4 votes

# Answer
# JavaScript (ES6), 23 bytes

Expects a permutation of the string `"4567"` and returns `0` ... `3`.

```
s=>962578>>s%530%13*2&3

```

Try it online!

### How?

Below is a view of the lookup bitmask and where each possible input is mapped once the expression \\$(n \bmod 530)\bmod 13\\$ is applied.

```
00 00 11 10 10 11 00 00 00 01 00 10
11 10  9  8  7  6  5  4     2  1  0
 |  |  |  |  |  |  |  |     |  |  |
 |  |  |  |  |  |  |  |     |  |  +--> 7654
 |  |  |  |  |  |  |  |     |  +-----> 4657, 7564
 |  |  |  |  |  |  |  |     +--------> 4567
 |  |  |  |  |  |  |  +--------------> 5746, 6754, 7645
 |  |  |  |  |  |  +-----------------> 4765, 6547
 |  |  |  |  |  +--------------------> 4675, 6457, 6574, 7465
 |  |  |  |  +-----------------------> 5476
 |  |  |  +--------------------------> 6745
 |  |  +-----------------------------> 4756, 5647, 5764, 7546
 |  +--------------------------------> 5674, 7456
 +-----------------------------------> 4576, 5467, 6475

```
> 10 votes

# Answer
# Python NumPy, 26 bytes

```
lambda A:(2*A-A@A).trace()

```

Attempt This Online!

Uses as the four distinct items the vectors `[1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]`. With this convention the input, conveniently, becomes a permutation matrix.

Outputs `2 x # fixed points A - # fixed points AA`. This maps the identity to 4, the rest of the Klein four group to -4, the rest of the alternating group to 1 and everything else to 0.

# Python, 48 bytes

```
lambda A:sum(2*(A[a]==a)-(A[A[a]]==a)for a in A)

```

Attempt This Online!

Same logic but uses items `0,1,2,3` and indexing instead of matrix operations.
> 7 votes

# Answer
# , 14 bytes

```
5|1#.2^~#@>@C.

```

Attempt This Online!

Found while experimenting with the cycle decomposition of each permutation.

* Category 1 (`0 1 2 3`) has four individual cycles of length 1.
* Category 2 (e.g. `1 0 3 2`) has two cycles of length 2.
* Category 3 (e.g. `0 2 3 1`) has one cycle of length 3 and another cycle of length 1.
* Category 4 (e.g. `0 1 3 2` or `1 2 3 0`) has either
    + three cycles of length 1, 1, 2, or
    + a single cycle of length 4.

By squaring and summing the cycle lengths, we get

* Category 1: 4
* Category 2: 8
* Category 3: 10
* Category 4: 6 or 16

Now we can take these values modulo 5 to get 4, 3, 0, 1 for each category.

```
5|1#.2^~#@>@C.  Takes a permutation containing 0, 1, 2, 3
            C.  Cycle decomposition
        #@>@    Length of each cycle
     2^~        Square
  1#.           Sum
5|              Modulo 5

```
> 6 votes

# Answer
# Charcoal, ~~22~~ 19 bytes

```
§SAKS0⊘ΣＥθ⁺⁼ικ⁼ι⌕θκ

```

Try it online! Link is to verbose version of code. Takes input as a list of 4 integers `0..3` (+2 bytes to take input as a string of digits) and outputs a code letter `0KAS` (-5 bytes to port @Albert.Lang's answer, and probably also the same length to port @JonathanAllan's answer). Explanation: Calculates the number of elements of cycle length `1` plus the number of elements of cycle length `1` or `2` (so elements of cycle length `1` get counted twice) and looks up the result.

```
 SAKS0              Literal string `SAKS0`
§                   Indexed by
         θ          Input list
        Ｅ           Map over elements
            ι       Current element
           ⁼        Equals
             κ      Current index
          ⁺         Plus
               ι    Current element
              ⁼     Equals
                ⌕   Index of
                  κ Current index in
                 θ  Input list
       Σ            Take the sum
      ⊘             Halved
                    Implicitly print

```

| Cycles | Order | Sign | Length 1 | Length 2 | Total | Classification |
| --- | --- | --- | --- | --- | --- | --- |
| 1+1+1+1 | 1 | `+` | 4 | 0 | 8 | `0` |
| 2+1+1 | 2 | `-` | 2 | 2 | 6 | `S` |
| 2+2 | 2 | `+` | 0 | 4 | 4 | `K` |
| 3+1 | 3 | `+` | 1 | 0 | 2 | `A` |
| 4 | 4 | `-` | 0 | 0 | 0 | `S` |

* My original answer counted the number of elements of cycle length `1` and then distinguished between `2+2` and `4` by checking for an element of cycle length `2` rather than counting the number of such elements.
* @alephalpha's answer checks the sign of the permutation and returns `0` if it's `-` or the order if it's `+`.
* @Albert.Lang's answer subtracts the number of elements of cycle length `2` from the number of elements of cycle length `1`.
* @JonathanAllan's answer subtracts the number of elements of cycle length `1` from `2` if the order is a factor of `2` or `0` if it is not.
> 4 votes

# Answer
# PARI/GP, 33 bytes

```
p->if(permsign(p)>0,permorder(p))

```

Attempt This Online!

Takes input as a `VecSmall` of integers 1, 2, 3, 4.

If the input is an odd permutation, returns `0`. Otherwise returns its order.
> 4 votes

# Answer
# K (ngn/k), 14 bytes

```
{5!#,/(x@)\'x}

```

Try it online!

Port of my own J solution.

The K code above executes the process a bit differently:

```
{5!#,/(x@)\'x}   Takes a permutation containing 0, 1, 2, 3
      (  )\'x    For each number in x, repeat and collect all values:
       x@          Index into x
   #,/           Length of flattened list
 5!              Modulo 5

```
> 3 votes

# Answer
# Factor \+ `math.combinatorics`, ~~70~~ 61 bytes

```
[ "READ"<permutations> index "0332233123322323133223313"nth ]

```

Try it online!

-9 bytes by using the string from corvus\_192's Scala 2 answer.
> 2 votes

# Answer
# Scala 2, ~~61~~ 60 bytes

```
s=>"033223312332232313322331"("abcd".permutations indexOf s)

```

Takes a permutation of "abcd" and returns an ascii digit by indexing into the given string.

Attempt This Online!
> 2 votes

# Answer
# Haskell, ~~89 8~~ 87 bytes

```
import Data.List
f s="033223312332232313322331"!!head(elemIndices s$permutations"abcd")

```

Attempt This Online!

A port of my scala answer.
> 2 votes

# Answer
# 05AB1E, ~~18~~ 11 bytes

```
<èāQ·Iā-0¢-

```

-7 bytes by porting *@JonathanAllan*'s Jelly answer, since I've been unable to find anything short myself.

`[1,2,3,4]` is the identity permutation. Outputs:

* `-2` for this identity permutation itself;
* `2` for the three members of \\$K\_4\\$;
* `-1` for the eight members of \\$A\_4\\$;
* `0` for the remaining twelve members of \\$S\_4\\$.

Try it online or verify all test cases.

**Explanation:**

```
<      # Decrease each value in the (implicit) input-permutation by 1
 è     # 0-based index each into the (implicit) input-permutation
  ā    # Push a list in the range [1,length]: [1,2,3,4]
   Q   # Check if the two lists are equal
    ·  # Double this check (2 or 0)
I      # Push the input-permutation again: [z,y,x,w]
 ā     # Push list [1,2,3,4] again
  -    # Decrease the values at the same positions of the two lists: [z-1,y-2,x-3,w-4]
   0¢  # Count how many 0s are in the list (how many item were already at the correct
       # position)
-      # Subtract this amount from the earlier doubled check
       # (after which the result is output implicitly)

```

---

**Original straight-forward approach (18 bytes):**

```
{œIk•Lû¾hΔ>¬o∊Ì•sè

```

`"abcd"` is the identity permutation. Outputs:

* `1` for this identity permutation itself;
* `3` for the three members of \\$K\_4\\$;
* `2` for the eight members of \\$A\_4\\$;
* `0` for the remaining twelve members of \\$S\_4\\$.

Try it online or verify all test cases.

**Explanation:**

```
{             # Sort the characters of the (implicit) input-permutation string
 œ            # Pop and get all its permutations
  Ik          # Pop and get the index of the input-permutation
•Lû¾hΔ>¬o∊Ì•  # Push compressed integer 100220032002200230022003
 s            # Swap so the earlier index is at the top
  è           # Index it into the the earlier integer to get a digit
              # (which is output implicitly as result)

```

See this 05AB1E tip of mine (section *How to compress large integers?*) to understand why `•Lû¾hΔ>¬o∊Ì•` is `100220032002200230022003`.
> 2 votes

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

```
s=>eval(`try{${s.slice(1)}}catch{3}`);bcd=0;adc=dab=cba=1;cdb=dbc=cad=dca=abd=bda=acb=bac=2

```

Try it online!

Input a string with letter "a", "b", "c", "d". Output 0~3.
> 1 votes

# Answer
# Python 3, 84 bytes

```
lambda s:locals().get(s[1:],3)
bcd=0
adc=dab=cba=1
cdb=dbc=cad=dca=abd=bda=acb=bac=2

```

Try it online!

Essentially a port of tsh's JS answer.
> 1 votes

# Answer
# Julia 1.0, ~~26~~ 24 bytes

```
!s=962578>>2(s%530%13)&3

```

Try it online!

Port of Arnuald's JS answer.

-2 thx to @Steffan
> 1 votes

# Answer
# Python 3, 31 bytes

```
lambda s:962578>>2*(s%530%13)&3

```

Try it online!

Port of Arnuald's JS answer.
> 1 votes

# Answer
# Python 3, 159 bytes

```
lambda x,y:{'1032':1,'2301':1,'3210':1,'0231':2,'0312':2,'1203':2,'1320':2,'2013':2,'2130':2,'3021':2,'3102':2,'0123':0}.get(''.join(map(str,map(x.find,y))),3)

```

I couldn't really interpret the logic. So I went with an overkill approach.

Try it online!
> 0 votes

# Answer
# Python 3, 105 bytes

```
def f(s):
 bcd=0;adc=dab=cba=1;cdb=dbc=cad=dca=abd=bda=acb=bac=2
 try:return eval(s[1:])
 except:return 3

```

Try it online!

Port of tsh's JS answer. Input as a string with letters `a`, `b`, `c`, `d`. Output as a number, 0 to 3.
> 0 votes

---
Tags: code-golf, math, permutations, abstract-algebra, classification
---


title: Calculate my income tax

text:
# Question
Title: Calculate my income tax
### Background

Here in the UK1, these are the income tax rules:

* You get a personal allowance (untaxed) of up to £12,570:
    + If you earn less than £100,000, you get the full £12,570 as personal allowance
    + For every £2 over £100,000, your personal allowance goes down by £1
* After the personal allowance, the next £37,700 is taxed at the "basic rate" of 20%
* After that, the next £99,730 is taxed at the "higher rate" of 40%
* Finally, anything above this is taxed at the "additional rate" of 45%

1: This isn't actually the case in Scotland; only England, Wales and Northern Ireland.

### Your task

Using the above tax rules, take in an annual salary (as a positive integer) and calculate the income tax.

### Test cases

```
Input    Output
12570    0
50000    7486
80000    19432
120000   39432
200000   75588.5

```

Note: the final test case can be any of 75588, 75588.5, or 75589 (any is fine)

### Clarifications

* You can choose whether to make the personal allowance an integer or keep it as a float
    + e.g. if the input is £100,003, the personal allowance can be £12,569, £12,568.50, or £12,568
* The same goes for the final output. If it ends up as a float, you can make it an integer or keep it as a float
    + (see the final test case)
* This is , so shortest answer in bytes wins!

# Answer
# 05AB1E, ~~32~~ 31 bytes

```
5ÐD(20)zI•5HwŸJ}Ütæ•žFвT*-Dd**O

```

Port of *@Neil*'s Charcoal answer, so make sure to upvote him as well!

Try it online or verify all test cases.

**Explanation:**

```
5            # Push a 5
 ÐD          # Triplicate + Duplicate so there are four 5s on the stack
   (         # Negate the top one
    20       # Push 20
      )      # Wrap all five values on the stack into a list: [5,5,5,-5,20]
       z     # Get 1/value for each of them: [0.2,0.2,0.2,-0.2,0.05]
I            # Push the input
 •5HwŸJ}Ütæ• # Push compressed integer 90598507370046338479
  žFв        # Convert 90598507370046338479 to base-16384 as list:
             #  [1257,5027,10000,12514,13743]
     T*      # Multiply each by 10: [12570,50270,100000,125140,137430]
I      -     # Subtract each from the input
        D    # Duplicate this list
         d   # Pop and do a non-negative (>=0) check for each
          *  # Multiply the values at the same positions (negative values have become 0)
*            # Multiply the values at the same positions with list [0.2,0.2,0.2,-0.2,0.05]
 O           # Sum everything together
             # (which is output implicitly as result)

```

See this 05AB1E tip of mine (sections *How to compress large integers?* and *How to compress integer lists?*) to understand why `•5HwŸJ}Ütæ•` is `90598507370046338479` and `•5HwŸJ}Ütæ•žFв` is `[1257,5027,10000,12514,13743]`.
> 3 votes

# Answer
# JavaScript (ES6), 99 bytes

Works with floats and rounds the final result.

```
n=>[137430.45,37700.4,.2].map(v=>x+=v%1*(n-(n-=m(n-~~v))),x=0,n-=(m=v=>v>0&&v)(12570-m(n-1e5)/2))|x

```

Try it online!

```
n =>                 // n = input
[                    // in this array, the integer part is the threshold (T)
                     // and the decimal part is the tax rate (R)
  137430.45,         //   T = 99730 + 37700, R = 45%
  37700.4,           //   T = 37700, R = 40%
  .2                 //   T = 0, R = 20%
]                    //
.map(v =>            // for each entry v:
  x +=               //   add to x:
    v % 1 *          //     the tax rate multiplied by
    ( n -            //     the difference between the current value of n
      ( n -=         //     and the updated value of n, which is:
          m(n - ~~v) //       n - max(0, n - threshold)
      )              //
    ),               //
  x = 0,             //   start with x = 0
  n -=               //   start by applying the personal allowance
    ( m = v =>       //   m is a helper function taking v ...
      v > 0 && v     //   ... and returning max(0, v)
    )                //
    (                //   personal allowance:
      12570 -        //     12570 - max(0, n - 100000) / 2
      m(n - 1e5) / 2 //
    )                //
)                    // end of map()
| x                  // return the final value of x

```
> 9 votes

# Answer
# Python, ~~83~~ ~~80~~ 77 bytes

*-3 thanks to @Max by removing the `0` from the beginning of the floating points.*

*-3 thanks to @tsh by using integers which are then divided instead of floats and changing the personal allowance operation.*

```
lambda m:sum(([4]*37700+[8]*99730+[9]*m)[:m-max(0,min(62570-m//2,12570))])/20

```

Attempt This Online!

Fun use of Python indexing and list multiplication.
> 7 votes

# Answer
# Charcoal, 49 bytes

```
ＩΣ×Ｉ⪪”‴⌈↷¶»^w⁷k²zV” Ｅ⁻ＮＩ⪪”←¶➙～!¬‴″ζＣＥR⁵kςⅈ” ∧›ι⁰ι

```

Attempt This Online! Link is to verbose version of code. Explanation:

```
           Ｎ            Input as a number
          ⁻             Vectorised subtract
              ...       Compressed string `12570 50270 100000 125140 137430`
             ⪪          Split on spaces
            Ｉ           Cast to number
         Ｅ              Map over values
                    ι   Current value
                   ›    Is greater than
                     ⁰  Literal integer `0`
                  ∧     Logical And
                      ι Current value
  ×                     Vectorised multiply by
     ...                Compressed string `.2 .2 .2 -.2 .05`
    ⪪                   Split on spaces
   Ｉ                    Cast to number
 Σ                      Take the sum
Ｉ                       Cast to string
                        Implicitly print

```

73 bytes for a version that calculates the personal allowance as an integer first:

```
Ｎθ≔⟦⁹⁹⁷³⁰¦³⁷⁷⁰⁰⌈⟦⁰⁻¹²⁵⁷⁰÷⌈⟦⁰⁻θＸχ⁵⟧²⟧⟧η≔⁰ζＦ³«≔⌊⟦θ⊟η⟧ε≧⁺×∕ι⁵εζ≧⁻εθ»Ｉ⁺ζ×θ·⁴⁵

```

Try it online! Link is to verbose version of code.
> 6 votes

# Answer
# Haskell, ~~132~~ 129 bytes

*-3 bytes thanks to @The Thonnu*

```
r#(-1.0)=r;r#l=min r l
g(t,r)(l,p)=(t+r#l*p/20,r-r#l)
f x=fst$foldl g(0,x)$zip[max(12570-max(x-1e5)0/2)0,37700,99730,-1][0,4,8,9]

```

Attempt This Online!
> 5 votes

# Answer
# Vyxal, ~~58 48~~ 33 bytes

```
5D:N20WĖ⁰»+gḊ6ß/ċi∴o@t»k4τ-:0≥**∑

```

Try it online!

* -15 thanks to lyxal

Port of Neil's Charcoal answer

### Explanation

```
5D:                             # Push 5 and quadruplicate
   N                            # Negate the top one
    20                          # Push 20
      W                         # Wrap the stack in a list
       Ė                        # Reciprocal of each
        ⁰                       # Push the input
         »...»                  # Push the base-255 compressed integer 12570050270100000125140137430
              k4τ               # Convert to list: [12570,50270,100000,125140,137430]
                 -              # Subtract each from the input
                  :             # Duplicate this list
                   0≥           # Check if each element is ≥0
                     *          # Multiply with the list so negative values are now 0
                      *         # Multiply together
                       ∑        # And sum, outputting implicitly

```
> 2 votes

# Answer
# QB64, 183 bytes

```
p=12570:If i>100000Then
p=p-Int((i-100000)/2):If p<0Then p=0
endif
l=p+37700:m=l+99730:If i>m Then
t=.45*(i-m):i=m
endif
If i>l Then
t=t+.4*(i-l):i=l
endif
If i>p Then t=t+.2*(i-p)
?t

```
> 2 votes

# Answer
# C (gcc), ~~120~~ ~~107~~ 102 bytes

* -18 thanks to ceilingcat

```
#define F+fdim(i
f(i){i=fmin(37700,i=F,F-i+12570,F,1e5)/2)))/5+.4*fmin(99730,i=F,37700))F,99730)*.45;}

```

Try it online!
> 1 votes

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