title: Make a +-#$%! interpreter

text:
# Question
Title: Make a +-#$%! interpreter
# Because we haven't had enough of these, let's do another weird language!

* `+` increments the accumulator
* `-` decrements the accumulator
* `#` outputs the character with the codepoint of the accumulator modulo 127, and then resets the accumulator
* `$` is like `#` but it doesn't reset the accumulator
* `%` reads a single character of input and then set the accumulator to that. If it is EOF, exit the program
* `!` sets the accumulator to 0

At the end of the program, if the accumulator is 0, exit, otherwise, start again from the beginning, preserving the accumulator state.

Note that this language has no implementation so it is defined by this post.

# Challenge

Given a valid `+-#$%!` program (containing only those characters) and the program input (containing only printable ASCII characters), return its output.

# Examples

```
program, input -> output // comments
%$, hello -> hello // CAT program
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++#+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++#++++++++++++++++++++++++++++++++#++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++#++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++#+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++#++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++#+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++#, -> Hi there
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++$+++++++++++++++++++++++++++++++++$++++++++++++++++++++++++++++++++++++++++++++++++++++++$++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++$+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++$++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++$+++++++++++++$++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++$!, -> Hi there

```

# Answer
> 11 votes
## \>\<\>, 112 bytes

You may be thinking "Is \>\<\> really the best language to write an interpreter in?", to which my answer is "no, but let's try anyway!"

```
i:}b(?v
0(?;v0<o}\.24;!?:}\    /}~51. /}1-32./}1+32./}~i:
6*bb< o:}\?="#":  \?(b:\?="!":\?="-":\?="+":\?="%":$%+

```

Try it online, or at the fish pond!

Takes input from STDIN: first the +-#$%! code, then optionally a newline and any extra input.

This could do with some explanation.

* The first loop is `i:}b(?v`. This reads from STDIN to the stack until it hits a character less than `b = 11`, which means either a newline (charcode 10) or EOF (charcode -1).
* Once that's done, the fish swims down…

```
  v
v0<
<

```

…into the main loop, adding a `0` to the stack to use as the accumulator.
* First, the fish sees `bb*6+%` — this computes `127 = 11*11+6` and takes the modulus of the accumulator. Then `$` brings forward the first character from the stack.
* Now, we get to the bulk of the code — reading the character. There are seven branches in this bit of the code. (I think I've tetrissed the branches as much as I can, but there might be more blank space that can be removed here.)

```
0(?;                                       /}~i:
                                           \?="%":

```

Note that the fish starts from the bottom right, moving left, and wraps when it hits the side of the code. If the character is a literal `"%"`, we shift it to the back of the stack for safekeeping, delete the accumulator, replace it with the first character in STDIN, check if that's EOF (that is, if its charcode is negative), and end the program if so. We then hit the start of the main loop again.

```
                             /}1-32./}1+32.
                             \?="-":\?="+":

```

If the character is `"+"`, we put it on the back of the stack again, add 1 to the accumulator, and jump to the start of the main loop. The `"-"` case is similar.

```
                      /}~51.
                      \?="!":

```

If the character is `"!"`, delete the accumulator and jump to just before the start of the main loop, where we first created the accumulator by adding a `0` to the stack.

```
         .24;!?:}\
                 \?(b:

```

If the character is EOF or newline, check if the accumulator is 0, and terminate the program if so; otherwise, jump back to the start of the main loop. We kept all the used characters on the stack, so now we're back at the start of the program anyway.

```
      o}\
        \?="#":

```

If the character is `"#"`, output the accumulator as a character. We're then conveniently back just before the main loop, where we created the accumulator with a `0`.

```

     o:}

```

If we've reached this branch, the character can only be `"$"`, since the stack only contained the characters `+-#$%!` and EOF or linefeed. Therefore we print a copy of the accumulator, and we're back at the start of the main loop.

# Answer
> 2 votes
# Python 2, 186 bytes

```
p,i=input()
a=0;f=1;r=''
while a^f:
 f=0
 for c in p:
	if c in'#$':r+=chr(a%127);a=a*(c>'#')
	if'%'==c:
	 if i:a=ord(i[0]);i=i[1:]
	 else:a=0;break
	a+=(c=='+')-(c>'+')-a*(c<'"')
print r

```

Try it online!

# Answer
> 2 votes
# Pyth, 89 bytes

```
KwJ1WJ=J0FHKIqH\+=+J1)IqH\-=-J1)IqH\#pC%J127=J0)IqH\$pC%J127)IqH\!=J0)IqH\%IqzkB=JChz=ztz

```

Takes the input in the first line and the output in the second. It's just a simple for loop over the input with some ifs. I'm sure it could be much shorter, but i don't care enough right now.

Try it!

### Python code it compiles to:

```
assign('z',input())
assign("K",input())
assign("J",1)
while J:
 assign('J',0)
 for H in num_to_range(K):
  if equal(H,"+"):
   assign('J',plus(J,1))
  if equal(H,"-"):
   assign('J',minus(J,1))
  if equal(H,"#"):
   Pprint(Pchr(mod(J,127)))
   assign('J',0)
  if equal(H,"$"):
   Pprint(Pchr(mod(J,127)))
  if equal(H,"!"):
   assign('J',0)
  if equal(H,"%"):
   if equal(z,k):
    break
   assign('J',Pchr(head(z)))
   assign('z',tail(z))

```

# Answer
> 1 votes
# Java 8, ~~225~~ ~~194~~ ~~187~~ 183 bytes

```
s->d(s,0);void d(char[]s,int n){for(int c:s){n+=c>44?-1:c/43;System.out.print(c>34&c<37?(char)(n%127):c==37?new java.util.Scanner(System.in).nextLine():"");n=c<36?0:n;}if(n>0)d(s,n);}

```

-15 bytes by converting Java 7 to Java 8.
-14 bytes thanks to *@Zacharý* by replacing String input with char-array input.
-2 bytes by some small fixes
-11 bytes thanks to *@ceilingcat*

**Explanation:**

Try it here: first test case with user-input.
Try it here: other two test-cases.

```
s->                           // Method (1) with char-array parameter and no return-type
  d(s,0);                     //  Call another method with the char-array and 0

void d(char[]s,int n){        // Method (2) with character-array and integer parameters
  for(int c:s){               //  Loop over the characters of the input
    n+=c>44?                  //   If the character is '-':
        -1                    //    Decrease `n` by 1
       :c/43;                 //   Else if the character is '+':
                              //    Increase `n` by 1
                              //   Else:
                              //    Leave `n` the same (by increasing with 0)
  System.out.print(c>34&c<37? //   If the character is '#' or '$':
    (char)(n%127)             //    Print the `n modulo 127` as character
   :c==37?                    //   Else-if the character is '%':
    new java.util.Scanner(System.in).nextLine()
                              //    Read & output the user-input
   :                          //   Else:
    "");                      //    Output nothing
  n=c<36?                     //   Then, if the character is '#' or '!':
     0                        //    Reset `n` to 0
    :                         //   Else:
     n;}                      //    Leave `n` the same
  if(n>0)                     //  If `n` is now larger than 0:
    d(s,n);}                  //   Do a recursive-call while leaving `n` as is

```

# Answer
> 1 votes
# Bash/gcc, ~~184~~ 172

This first reads the program on stdin, then after an EOF, reads program input. Looks valid to me.

```
gcc -x c -<<<"a;main(){do{$(sed -e's/#/$!/g' -e's/./&;/g' -e's/[+-]/a&&/g' -es/!/a=0/g -e's,%,a=getchar();if(a==-1)exit(0),g' -e's/\$/putchar(a%127)/g')}while(a);}"
./a.out

```

If you didn't already notice, I'm just constructing, compiling and running a C program on the fly. Note: your compiler might complain loudly about the horrible code generated, but I believe we were allowed extra output on stderr.

Before I began, I expected this to be shorter than it turned out; I'm really unhappy with the `%` handling. Suggestions welcome :)

# Answer
> 1 votes
# Python 3, 121 bytes

```
x,i=0,int
for c in input():
 if c in'$#':print(end=chr(x%128))
 x+=i(c=='+')-i(c=='-')-i(c in'!#')*x
 if'%'==c:x=input()

```

# Answer
> 0 votes
# C, 170 bytes

```
main(int c,char **v){for(int A=0,i=0;c=v[1][i++];A+1)A=c==0?i=0,A?A:-1:c=='+'?A+1:c=='-'?A-1:c=='!'?0:c=='$'?putchar(A%127),A:c=='#'?putchar(A%127),0:c=='%'?getchar():A;}

```

Ungolfed

```
main(int c,char **v){
    for(int A=0,i=0;c=v[1][i++];A+1)
        A=
            c==0 ? i=0, A?A:-1:    // EOF == -1
            c=='+' ? A+1:
            c=='-' ? A-1:
            c=='!' ? 0:
            c=='$' ? putchar(A%127),A:
            c=='#' ? putchar(A%127),0:
            c=='%' ? getchar():
            A;
}

```

6 bytes can be saved by replacing +-!$#% with decimal equivalents, but that would obfuscate the code. 9 bytes can be saved when using a K&R compatible compiler by moving the declaration *int A=0,i=0* to the start of main, *A,i,main(...* However I only posted code that I could test.

Corrected in response to comments by Dave. Also switched to using the value of EOF (-1) instead of "EOF".

# Answer
> 0 votes
# JavaScript (ES6), 197 bytes

```
(s,i="")=>(i=[...i].map(c=>c.charCodeAt()),a=0,o="",u=_=>{[...s].map(c=>eval(["a++","a--",p="o+=a?String.fromCharCode(a%127):''",r="a=0",p+","+r,"a=i.shift()"]["+-$!#%".indexOf(c)])),a&&u()},u(),o)

```

## Cleaned up

```
(s, i="") => (
    i = [...i].map(c=>c.charCodeAt()),
    a = 0,
    o = "",
    u = _ => {
        [...s].map(c => eval(
            ["a++", "a--", p="o+=a?String.fromCharCode(a%127):''", r="a=0", p+","+r, "a=i.shift()"][ "+-$!#%".indexOf(c) ]
        )),
        a && u()
    },
    u(),
    o
)

```

## Test Snippet

```
f=
(s,i="")=>(i=[...i].map(c=>c.charCodeAt()),a=0,o="",u=_=>{[...s].map(c=>eval(["a++","a--",p="o+=a?String.fromCharCode(a%127):''",r="a=0",p+","+r,"a=i.shift()"]["+-$!#%".indexOf(c)])),a&&u()},u(),o)
```

```
<style>*{font-family:Consolas;}</style>
Code:
<textarea id="C" rows="2" cols="50"></textarea><br>
Input: <input id="I"><br>
<button onclick="O.innerHTML=f(C.value, I.value)">Run</button><br>
<pre id="O"></pre>
```

# Answer
> 0 votes
# Ruby, ~~143~~ ~~149~~ 146 bytes

First line of STDIN is the code, the rest is the input.

Whoops, `getc` doesn't actually exist directly.

```
a=0
e=i=gets
i.chars{|c|eval Hash["+a+=1 -a-=1 #P;a=0 $P %a=$<.getc||exit !a=0".gsub(?P,"$><<(a%127).chr").scan /(\S)(\S+)/][c]||"";e=a}while e!=0

```

Try it online!

# Answer
> 0 votes
# C, ~~145~~ 139 bytes

```
c,a;f(){for(;~c;c=getchar())c==43?a++:c==45?a--:c==35?putchar(a%127),a=0:c==36?putchar(a%127):c==37?!~(a=getchar())?exit(0):0:c==33?a=0:0;}

```

That was easy. I definitely recommend compiling with all warnings off (`-w`). Will golf.

# Answer
> 0 votes
# shortC, 95 bytes

```
c,a;AO;~c;c=G)c==43?a++:c==45?a--:c==35?Pa%127),a=0:c==36?Pa%127:c==37?!~(a=G)?T0:0:c==33?a=0:0;

```

# Answer
> 0 votes
# OCaml, 202 bytes

```
let c c=print_char(char_of_int(c mod 127))
let rec f a p=match Array.fold_left(fun a->function '+'->a+1|'-'->a-1|'#'->c
a;0|'$'->c a;a|'%'->Scanf.scanf"%c"int_of_char|'!'->0|_->a)a p with
0->()|a->f a p

```

Takes the program as an array of char because OCaml does not have `String.fold*`

Try it online!

# Answer
> 0 votes
# APL (Dyalog Unicode), 112 bytes

```
a←0
f←⎕UCS 127|⊢
{⍎¨('∆'(≠⊆⊢)'a+←1∆a-←1∆⍞←f a⋄a←0∆⍞←f a∆a←⎕UCS{×≢⍵:⊃⍵⋄⎕UCS 0}i⋄i←1↓i∆a←0')['+-#$%!'⍳⍞]}⍣{a=0}i←⍞

```

Try it online!

maps each instruction to a string, then executes it.

Inputs are taken in reverse, output is given in the debug window.

---
Tags: code-golf, interpreter
---


title: The sequence of self-contained numbers

text:
# Question
Title: The sequence of self-contained numbers
Let's define a *self-contained number* as a positive integer, whose digits appear in runs of length equal to themselves only. In other words, any decimal digit **d** (excluding **0**) occurs only in runs of length exactly **d**.

# Task

You can choose any of the three methods listed below:

* Given an integer **n**, output the **n**th (either 0 or 1-indexed) self-contained number.
* Given an integer **n**, output the first **n** self-contained numbers.
* Print the sequence indefinitely.

# Examples

* **133322** is a self-contained number because **3** appears in a run of three **3**'s, **1** is single and **2** occurs in a run of two **2**'s.
* On the other hand, **35553355** isn't, because, although **5** and **3** occur five and three times respectively, they do not form runs of adjacent digits.
* **44422** is not self-contained, because **4** only occurs three times.
* **12222333** isn’t either, because **2** appears in a run of four **2**'s, and it cannot be treated as two separate runs of two **2**'s.

Not surprisingly, this is OEIS A140057, and its first few terms are:

```
1, 22, 122, 221, 333, 1221, 1333, 3331, 4444, 13331, 14444, 22122, 22333, 33322, 44441, 55555, 122122, 122333, 133322, 144441, 155555

```

---

You can take input and provide output through any of the standard methods, in any programming language, while noting that these loopholes are forbidden by default. This is code golf, so the shortest code in bytes (in every language) wins.

# Answer
> 8 votes
# Python 2, ~~104~~ ~~94~~ 83 bytes

-10 bytes thanks to Mr. Xcoder
-11 bytes thanks to Jonathan Allan

```
i=0
while 1:
 if`i`==''.join(d*int(d)for c,d in zip(`-i`,`i`)if d!=c):print i
 i+=1

```

Try it online!

# Answer
> 6 votes
# Mathematica, 66 bytes

Prints the sequence indefinitely

```
Do[##&&Print@t&@@(#==Tr[1^{##}]&@@@Split@IntegerDigits@t),{t,∞}]

```

Try it online!

In TIO you have to terminate the execution in order to see the result but in Mathematica works fine.

-12 bytes from Martin Ender

# Answer
> 6 votes
# JavaScript (ES6), ~~76~~ ~~71~~ 68 bytes

Returns the *n-th* term of the sequence, 0-indexed.

```
f=(n,k)=>+(k+'').replace(/(.)\1*/g,s=>s.length^s[0])||n--?f(n,-~k):k

```

*NB*: As always with recursive functions, the input range depends on Tail Call Optimization support and the stack size of your engine.

### Demo

```
f=(n,k)=>+(k+'').replace(/(.)\1*/g,s=>s.length^s[0])||n--?f(n,-~k):k

for(n = 0; n <= 10; n++) {
  console.log('a(' + n + ') = ' + f(n))
}
```

---

# Alt. version, 65 bytes

Takes no input and prints the results with `alert()`, one at a time.

```
f=k=>f(-~k,+(k+'').replace(/(.)\1*/g,s=>s.length^s[0])||alert(k))

```

Try it online! (Stops as soon as the maximum stack size is exceeded.)

# Answer
> 6 votes
# 05AB1E, 9 bytes

Returns the nth term of the sequence, 1-indexed.

```
µNÔNγ€gJQ

```

Try it online!

**Explanation**

```
µ           # loop over increasing N until counter equals input
 NÔ         # push N with consecutive equal elements deduplicated
   Nγ       # push N grouped into runs of consecutive equal elements
     €g     # get the length of each run
       J    # join to a number
        Q   # check for equality
            # if true, implicitly increment counter

```

# Answer
> 4 votes
# Jelly, 7 bytes

```
DŒrZEµ#

```

Try it online!

-4 bytes thanks to Mr. Xcoder's early suggestion.
-1 thanks to Jonathan Allan.

Takes input from STDIN.

# Answer
> 2 votes
# Haskell, 70 bytes

```
import Data.List
filter(all(\s->read[s!!0]==length s).group.show)[1..]

```

# Answer
> 2 votes
# CJam, 20 bytes

```
1{_Abe`::=:*{_p}&)}h

```

Try it online!

Explanation:

```
1                       push 1
 {                }h    while TOS is truthy (i.e. forever):            example iteration: 14444
  _                       duplicate                                                       14444 14444
   Ab                     convert to base 10 (get decimal digits)                         14444 [1 4 4 4 4]
     e`                   run-length encode (array of two-element arrays)                 14444 [[1 1] [4 4]]
       :                  map over the array:
        :                   fold between the two array elements with:
         =                    equality                                                    14444 [1 1]
          :               fold between the array elements with:
           *                multiplication (a.k.a. logical AND for 1 or 0)                14444 1
            {  }&         if this yields a result of 1:
             _              duplicate the number and                                      14444 14444
              p             print it                                                      14444 (output 14444)
                 )        increment the number                                            14445

```

# Answer
> 2 votes
# Brachylog, 10 bytes

```
≜ℕẹḅ⟨l=h⟩ᵐ

```

Try it online!

Infinitely generates elements of the sequence through its input variable. (If it actually has to do the printing itself, append `&ẉ⊥`.) This is essentially code to solve the corresponding with a  prepended to brute-force the smallest solutions first:

```
        ᵐ    For every
  ḅ          run of
 ẹ           digits in
             the input variable
ℕ            (which is a non-negative integer),
   ⟨l  ⟩     its length
   ⟨  h⟩     and its first element
   ⟨ = ⟩     are equal.

```

I expected this to only take 9 bytes, but  seems to require an explicit  to separate the digits of a number into runs.

# Answer
> 2 votes
# Stax, 10 bytes

```
Ç≡∟Öz≈¢αV¢

```

Run and debug it

This program filters all positive integers with a filter. The digits are run-length encoded. For each run, the digit must equal the run length.

# Answer
> 1 votes
# JavaScript 4, ~~83~~ 80 bytes

```
for(i=0;;)+(++i+'').replace(/(.)\1*/g,function(x,y){return y^x.length})||alert(i)

```

```
for(i=0;i<1000;)+(++i+'').replace(/(.)\1*/g,function(x,y){return y^x.length})||alert(i)
```

# Answer
> 1 votes
# Perl 6, 49 bytes

```
{(grep /^((\d)$0*:<?{$/.comb==$0}>)+$/,^Inf)[$_]}

```

Try it online!

Returns the `n`-th element of the sequence, zero-indexed.

# Answer
> 1 votes
# , 56 bytes

```
function(n)all((r=rle(el(strsplit(c(n,''),''))))$l==r$v)

```

Try it online!

Makes use of run length encoding on the split number. Returns true if all the lengths equal the values.

Note: I have loaded the `methods` library in TIO to get `el` to work.

# Answer
> 1 votes
# Husk, 10 bytes

```
fȯΛ§=L←gdN

```

Try it online!

Returns an infinite list.  is used to show first n elements since it times out.

# Answer
> 0 votes
# Pyth, 12

```
.f.AqMr8jZ10

```

Test online!

# Answer
> 0 votes
# Perl 5 `-p`, 48 bytes

```
++$\=~s|(.)\1*|$1-length$&&&redo|gre for 1..$_}{

```

Try it online!

Returns the n-th element, 1 indexed.

# Answer
> 0 votes
# Java 10, 121 bytes

A lambda from `int` to `int`. The function takes an index *n* and returns the *n*th (1-indexed) sequence value.

```
n->{int x=0,m=1;for(;n>0;n-=m,m=1)for(var p:(++x+"").split("(?<=(.))(?!\\1)"))m=p.length()==p.charAt(0)-48?m:0;return x;}

```

Try It Online

## Ungolfed

```
n -> {
    int x = 0, m = 1;
    for (; n > 0; n -= m, m = 1)
        for (var p : (++x + "").split("(?<=(.))(?!\\1)"))
            m = p.length() == p.charAt(0) - 48 ? m : 0;
    return x;
}

```

# Answer
> 0 votes
# Japt, 15 bytes

Returns the `n`th term, 1-indexed.

```
Èì òÎeÈÎ¶XÊÃ}iU

```

Try it

```
Èì òÎeÈÎ¶XÊÃ}iU     :Implicit input of integer U
È                   :Function taking an integer X as argument
 ì                  :  To digit array
   ò                :  Partition between elements where
    Î               :    The sign of their difference is truthy (not 0)
     e              :  All true
      È             :  When passed through the following function as X
       Î            :    First element
        ¶           :    Is equal to
         XÊ         :    Length of X
           Ã        :  End function
            }       :End function
             iU     :Get the Uth integer that returns true

```

---
Tags: code-golf, math, sequence, integer
---


title: Is it in the polygon?

text:
# Question
Title: Is it in the polygon?
# The challenge

Given point and a path of points, say whether or not the point is in the polygon that is created by the path.

Also return `true` if the point is on an edge of the polygon.

# Input

A list of pairs of integers.

The first 2 integers represent the point.

The remaining pairs (3rd and 4th, 5th and 6th etc.) represent the vertices of the polygon.

The edges are in the order of the input pairs.

The path is assumed to loop back to the first point of the path.

The input is assumed to be valid.

No three points in the path are collinear.

ex. `123 82 84 01 83 42`

# Output

A truthy/falsy value.

# Test cases

Input -\> Output

`0 0 10 10 10 -1 -5 0` -\> `true`

`5 5 10 10 10 50 50 20` -\> `false`

`5 5 0 0 0 10 1 20 6 30 10 -40` -\> `true`

This is . Shortest answer in bytes wins.

# Answer
# Charcoal, ~~52~~ 50 bytes

```
≔⪪Ａ²θＦ⟦Ｅ³§θ⊖ιθ✂θ¹⟧⊞υ↔ΣＥι⁻×§κ⁰§§ι⊕λ¹×§κ¹§§ι⊕λ⁰⁼⊟υΣυ

```

Try it online! Link is to verbose version of code. Explanation:

```
≔⪪Ａ²θ

```

Split the input into pairs of coordinates.

```
Ｆ⟦Ｅ³§θ⊖ιθ✂θ¹⟧

```

Calculate the area of three polygons: the one formed by taking the last, first and second points; the one formed from all of the points (including the test point); the one formed from all of the points except the test point.

```
⊞υ↔ΣＥι⁻×§κ⁰§§ι⊕λ¹×§κ¹§§ι⊕λ⁰

```

Use the shoelace formula to calculate the area of that polygon.

```
⁼⊟υΣυ

```

Check whether the last area equals the sum of the first two. If this is the case, then the point lies within the polygon.
> 11 votes

# Answer
# Wolfram Language (Mathematica), 26 bytes

```
Polygon@#2~RegionMember~#&

```

Try it online!
> 10 votes

# Answer
# JavaScript (V8), 123 bytes

```
(x,y,...p)=>p.map((_,i)=>p.concat(p).slice(i,i+4)).reduce((n,[a,b,c,d],i)=>i%2<1&&a<x!=c<x&&y<b+(d-b)*(x-a)/(c-a)?!n:n,!1)

```

Ungolfed

```
(x, y, ...p)=>
  p.map((_, i) => p.concat(p).slice(i, i + 4)) // Group points into edges
  .reduce(
    (n, [a, b, c, d], i)=>                     // for every edge
      i % 2 < 1 &&                             // if it's actually an edge
      a < x != c < x &&                        // and x of point is within bounds
      y < b + (d - b) * (x - a) / (c - a) ?    // and point is below the line
      !n : n,                                  // then invert whether it's inside
    false
  )

```

TIO seems to be down for now, I'll add a link when I can (or if someone else happens to first)
> 6 votes

# Answer
# PostgreSQL 12, 91 bytes

```
create function f(a polygon,b point,out o bool)as $$begin return a~b;end$$language plpgsql;

```

PostgreSQL has built-in polygon and point types, and a built-in operator `@>` (also spelt `~` to save a byte) to test containment.

...Is this too boring?
> 4 votes

# Answer
# Java 10, ~~142~~ 141 bytes

```
a->{var p=new java.awt.geom.Path2D.Float();p.moveTo(a[2],a[3]);for(int i=3;++i<a.length;)p.lineTo(a[i],a[++i]);return p.contains(a[0],a[1]);}

```

Try it online.

**Explanation:**

```
a->{                         // Method with integer-array parameter and boolean return-type
  var p=new java.awt.geom.Path2D.Float();
                             //  Create a Path2D object
  p.moveTo(a[2],a[3]);       //  Set the starting position to the third and fourth values in the list
  for(int i=3;++i<a.length;) //  Loop `i` in the range (3, length):
    p.lineTo(                //   Draw a line to:
             a[i],           //    x = the `i`'th value in the array
             a[++i]);        //    y = the `i+1`'th value in the array
                             //        (by first increasing `i` by 1 with `++i`)
  return p.contains(a[0],a[1]);}
                             //  Check if the polygon contains the first two values as x,y

```
> 3 votes

# Answer
# Scala, 139 bytes

If the input is a `(Int, Int)` and a `List[(Int, Int)]` that doesn't have to be parsed, it's a bit easier

```
(x,p)=>(p.last->p.head::p.zip(p.tail)count{q=>(q._1._2<=x._2&x._2<=q._2._2|q._1._2>=x._2&x._2>=q._2._2)&(x._1<=q._1._1|x._1<=q._2._1)})%2>0

```

Try it online!

## Using winding number, 140 bytes

```
x=>y=>_.sliding(2).map{case Seq((a,b),(c,d))=>val(e,f,l)=(b>y,d>y,(a-x)*(d-y)-(c-x)*(b-y))
if(!e&f&l>0)1 else if(e& !f&l<0)-1 else 0}.sum!=0

```

Try it online!

Uses the algorithm described here

## With input as string, 186 bytes

```
i=>{val x::p=i split " "map(_.toInt)grouped 2 toList;(p.last->p.head::p.zip(p.tail)count{q=>(q._1(1)<=x(1)&x(1)<=q._2(1)|q._1(1)>=x(1)&x(1)>=q._2(1))&(x(0)<=q._1(0)|x(0)<=q._2(0))})%2>0}

```

Try it online!
> 2 votes

# Answer
# C (gcc), ~~171~~ \\$\cdots\\$ ~~129~~ 126 bytes

Saved a whopping ~~13~~ ~~19~~ 35 bytes thanks to ceilingcat!!!
Saved ~~2~~ 5 bytes thanks to user!!!

```
W,i,l;f(x,y,V,n)int*V;{for(W=i=0;i<n-2;W+=V[i-2]>y^V[i]>y?(l>0)-(l<0):0)l=(V[i++]-x)*(V[i+2]-y)-(V[i++]-y)*(V[i]-x);return W;}

```

Try it online!

Uses the winding number algorithm: if the winding number is truthy, the point lies inside the polygon, otherwise its falsey.
> 2 votes

# Answer
# Python 3.8 (pre-release), 134 bytes

```
lambda x,y,p:sum((p[i+3]>y)^(p[i+1]>y)and(0<(l:=(p[i+2]-p[i])*(y-p[i+1])-(x-p[i])*(p[i+3]-p[i+1])))-(l<0)for i in range(0,len(p)-2,2))

```

Try it online!
> 2 votes

# Answer
# , 105 bytes

```
function(P,m=matrix(c(P,P[3:4]),,2,T))!sd(sapply(3:nrow(m)-1,function(k)sign(det(diff(m[c(1,k+0:1),])))))

```

Try it online!

Assumes no three points are collinear. Extends the algorithm described, e.g., here.

If we call the query point \\$Q\\$ and the ordered points of the polygon \\$P\_1\dots P\_n\\$, this traverses the points of the polygon, checking to see which side of the segment it's on by computing the signed area of the triangle (using the shoelace method) formed by \\$Q,P\_{i},P\_{i+1}\\$: A positive sign means to the left, and negative to the right if you're going counterclockwise, otherwise it's reversed. If all the signs are the same (i.e., the standard deviation of the signs is 0), then the point is within the polygon.

My computational geometry professor would be somewhat ashamed it took me four days for me to remember this point-in-polygon method. If I can find my textbook/notes, I'll post its description of the algorithm...
> 2 votes

# Answer
# APL (Dyalog Unicode), 63 bytes

```
{⍵∊⍺:1⋄(¯1∊×d)∨1<|+/⍟d←(⊢÷1∘⌽)⍺-⍵}

```

Try it online!

Taken directly from an APLcart snippet. I'm not awfully sure of what's going on it it, and would be glad if someone could give a better explanation.

Input is taken as complex points.

Takes polygon on the left and point on the right.

## Explanation

```
{⍵∊⍺:1⋄(¯1∊×d)∨1<|+/⍟d←(⊢÷1∘⌽)⍺-⍵}
{⍵∊⍺:1                           } return 1 if point is in list, otherwise:
      ⋄                       ⍺-⍵  subtract the point from each edge
                                   (gives all lines to from vertices to the point)
                       (⊢÷1∘⌽)     divide it by itself rotated by 1
                     d←            save it in d
                    ⍟              take the natural logarithm of each point
                  +/               and sum the vectors
                 |                 take the modulus
                                   (I think this gets the sum of angles)
               1<                  check if 1 is lesser than it
              ∨                    or
       (¯1∊×d)                     any of the points' signums equal (-1,0)

```
> 2 votes

# Answer
# , ~~139~~ ~~127~~ ~~118~~ 116 bytes

*Edit: -23 bytes by improving shoelace calculations thanks to goading by Giuseppe*

```
function(i,S=function(m)abs(sum(m*c(1,-1)*m[2:1,c(2:ncol(m),1)])))S(P<-matrix(i,2))==S(P[,-1])-S(P[,c(1:2,ncol(P))])

```

Try it online!

Implements Neils beautiful approach of testing whether the 'slice of cake' formed by the triangle with the test-point + two perimeter points as vertices is equal in area to the area of the whole 'cake' (the test polygon) minus the area of the 'cake' with the 'slice' removed (the polygon using all points including the test point).

```
inside=
function(i)
    {                                           # S is helper function to calculate 2x the cake area using
                                                # the 'shoelace' formula:
    S=function(m)abs(sum(m*c(1,-1)*m[2:1,c(2:ncol(m),1)])/2)
    P=matrix(i,2)                               # 'cake with missing slice' = polygon including test point
    T=P[,c(1:2,ncol(P))]                        # 'slice of cake' = triangle of test point + adjacent polygon vertices
    O=P[,-1]                                    # 'the cake' = outer polygon excluding test point
    S(P)==S(O)-S(T)                             # do the areas add-up?
}

```
> 1 votes

# Answer
# \>\<\>, 92 bytes

```
l[l0$21.>&-0=n;
{$&:2-&?!v{:{:{:@*{:}@@}@@}@@*-@@+
:0$0(?$-v>]
3pl2-00.>&08
{{{{600.>&-&084p

```

Implements Neil's shoelace formula technique.
> 1 votes

# Answer
# Python 3, 133 bytes

Spatial packages to the rescue:

```
from shapely.geometry import*
def f(s):
 c=list(map(int,s.split()))
 o,*p=zip(c[::2],c[1::2])
 return Point(o).intersects(Polygon(p))

```

The geometric operation to use was a small gotcha. `Polygon.contains(Point)` does not cover the edge cases.
> 1 votes

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


title: Sequences of distinct positive integers

text:
# Question
Title: Sequences of distinct positive integers
The goal of this challenge is to take a positive integer `n` and output (in lexicographic order) all sequences \\$S = \[a\_1, a\_2, ..., a\_t\]\\$ of distinct positive integers such that \\$\max(S) = n\\$.

For example, for an input `n = 3` your program should output the following eleven sequences in the following order:

```
[
  [1, 2, 3],
  [1, 3],
  [1, 3, 2],
  [2, 1, 3],
  [2, 3],
  [2, 3, 1],
  [3],
  [3, 1],
  [3, 1, 2],
  [3, 2],
  [3, 2, 1],
]

```

(In general, for an input `n`, your program should output \\$A001339(n-1)\\$ sequences.)

---

This is a challenge, so the shortest code wins.

# Answer
> 3 votes
# Jelly, ~~10~~ ~~9~~ ~~8~~ 7 bytes

```
œ!RẎṢiƇ

```

Try it online!

-1 byte thanks to Sisyphus

-1 more byte thanks to Sisyphus

## How it works

```
œ!RẎṢiƇ - Main link. Takes n on the left
  R     - Yield [1, 2, ..., n]
œ!      - For each i = 1, 2, ..., n, yield all length-n permutations of [1, 2, ..., n]
   Ẏ    - Join into a single list
    Ṣ   - Sort
      Ƈ - Keep those where
     i  -   The 1-based index of n is non-zero (i.e n is in the list)

```

# Answer
> 8 votes
# Python 2, 78 bytes

```
f=lambda n,l=[]:sum([f(n,l+[i+1])for i in range(n)if~-(i+1in l)],[l]*(n in l))

```

Try it online!

Python 3 lets us save some bytes with set unpacking.

**Python 3, 74 bytes**

```
f=lambda n,l=[]:sum([f(n,l+[i])for i in{*range(1,n+1)}-{*l}],[l]*(n in l))

```

Try it online!

# Answer
> 7 votes
# Husk, 9 bytes

```
Of€¹umu´π

```

Try it online!

### Explanation

```
Of€¹umu´π
       ´π     All length n combinations of 1..n
     mu       Get the unique values of each list
    u         Get the unique lists
 f€¹          Filter by those that contain n
O             And sort lexographically

```

# Answer
> 4 votes
# Brachylog, 10 bytes

```
{⟦₆⊇,?p}ᶠo

```

Try it online!

* `{…}ᶠo`: order all results of:
* `⟦₆`: from `[1,2,…,N-1]`
* : try a subset (e.g. `[1,2]` then `[2]` then `[1]` then `[]`)
* `,?`: append the input `[1,2,3]`
* `p`: permute the list

# Answer
> 4 votes
# Haskell, 60 bytes

```
n!b=[[]|all(<n)b]++[k:c|k<-b,c<-n!filter(/=k)b]
f n=n![1..n]

```

Try it online!

Very much like xnor's Python approach, but my `b` is the complement of their `l`.

## Explanation

Definition: an `n`-SDPI is a sequence of distinct positive integers `1 ≤ i ≤ n`, among which is `n`.

We can think about "using up" numbers as we write such a sequence: if `n=5` and we start by writing down a `2`, only `[1,3,4,5]` are left at our disposal (we can't reuse 2).

`n!b` computes all of the *continuations* of an `n`-SDPI where we have only the numbers in `b` left at our disposal. Let's call `b` our "bag" of numbers that could still go in the sequence.

For example: `4![1,3]` returns all the ways we can continue if we've already written down a 2 and a 4 (in some order), and we have a `1` and a `3` left in our bag.

Which continuations are there?

Either we stop here (yielding `[]`), or we turn to our bag (yielding some non-empty continuations).

1. If `n` is no longer in our bag (`all(<n)b`), then we've made a valid n-SDPI, so we're happy ending the list here and yield `[]` as a possible continuation.
2. Furthermore, for every `k` in our bag, we can place `k`, followed by every continuation `c` from `n!filter(/=k)b` (removing `k` from the bag).

Since `b` is always sorted, and we yield `[]` before non-empty lists, the result is also lexicographically sorted.

Finally, `f` asks which `n`-SDPIs we can make with a full bag (`[1..n]`).

# Answer
> 3 votes
# Scala 3, 130 bytes

```
| =>(for< <-1 to|;> <-1 to|combinations<if>toSet|;? <- >permutations yield?)sortBy(_.map("%10s"format _ replace(' ','0'))mkString)

```

Try it online!

Readable variable names are so overrated. Who needs `n` when you can have `|`?

# Scala, ~~140~~ 137 bytes

```
| =>(for{< <-1 to|
> <-1 to|combinations<if>toSet|
? <- >permutations}yield?)sortBy(_.map("%10s"format _ replace(' ','0')).mkString)

```

Wow, this got long.

Try it online

Ungolfed, with comments and sensible variable names:

n =>
 (for {
    i <- 1 to n                //For every i in the range [1..n]
    c <- 1 to n combinations i //Every subset of [1..n] of size i
    if c contains n            //Make sure the max is n first
    p <- c.permutations        //For every permutation of that subset
  } yield p                    //Yield that permutation
 ) sortBy( //Sort it with this function
     _.map(                    //For every number in the sublist
       "%10s"format _ replace(' ','0') //Pad it on the right to a width of ten using 0
      ).mkString //Smoosh it into one string
   )

```
</code></pre>

# Answer
> 3 votes
# SageMath, 93 bytes

```
lambda n:sorted(sum([[*Permutations(l)]for l in Subsets(range(1,n+1))if n in l],[]),key=list)

```

Try it online!

Inputs \\$n\\$ and returns a list of all permutations of every \\$s\\$ in \\$\\{s\subseteq\\{1,2,\dots,n\\} \mid n\in s\\}\\$ sorted lexicographically.

### Explanation

```
lambda n:                           # function taking integer n
                                    # returning a list of
  [*Permutations(l)]for l in        # all permutations
     Subsets(range(1,n+1))          # of all subsets of {1,2,...,n}
       if n in l                    # that have n as an element
         sum( . . . ,[])            # flattened
           sorted( . . . ,key=list) # and sorted lexicographically

```

# Answer
> 3 votes
# Wolfram Language (Mathematica), ~~55~~ 45 bytes

```
Do[i!=##2&&##~#0~i,{i,0!=##||Print@{##2};#}]&

```

Try it online!

Inspired by xnor's python solution, and borrows from my answers to some prior problems.

Prints the list of sequences.

Recursively traverses through all permutations of subsequences of `1..n` in lexicographic order, printing those which contain `n`.

```
0!=##||             (* If n is in the current sequence, *)
  Print@{##2};      (*   output. *)
{i, % ;#}           (* for i=1..n: *)
Do[i!=##2&&         (*   if i is not in the current sequence, *)
    ##~#0~i, % ]&   (*     append it and recurse. *)

```

# Answer
> 3 votes
# Scala, ~~132~~ ~~124~~ 117 bytes

```
n=>1.to(n-1).toSet.subsets().flatMap(_.+(n).toSeq.permutations).toSeq.sorted(Ordering.Implicits.seqOrdering[Seq,Int])

```
* Thanks to user for -7 characters!

Try it online!

# Answer
> 3 votes
# K (ngn/k), 24 bytes

```
{t@<t:(x=|/)#??'1++!x#x}

```

Try it online!

# Answer
> 3 votes
# JavaScript (ES6),  ~~89~~  82 bytes

This started as a port of @xnor's method and then was golfed the JS way from there.

```
f=(n,s=[],i)=>i>n?[]:[...!i^s.includes(i||n)?[]:i?f(n,[...s,i]):[s],...f(n,s,-~i)]

```

Try it online!

### Commented

```
f = (                      // f is a recursive function taking:
  n,                       //   n   = input
  s = [],                  //   s[] = current sequence
  i                        //   i   = counter, initially undefined
) =>                       //
  i > n ?                  // if i is greater than n:
    []                     //   stop the recursion and return an empty array
  :                        // else:
    [                      //   build a new array:
      ...                  //     append the following values:
      !i ^                 //       if i = 0 and s[] does not include n
      s.includes(i || n) ? //       OR i > 0 and s[] includes i:
        []                 //         append nothing
      :                    //       else:
        i ?                //         if i > 0:
          f(n, [...s, i])  //           append all the values returned by a
                           //           recursive call with i appended to s[]
        :                  //         else:
          [s],             //           append s[]
      ...                  //     append all the values returned
      f(n, s, -~i)         //     by a recursive call with i + 1
    ]                      //   end of new array

```

# Answer
> 3 votes
# Scala, 87 bytes

```
n=>1.to(n-1).toSet.subsets.toSeq.flatMap(_.toSeq:+n permutations)sortBy(_ mkString " ")

```

Try it online!

# Answer
> 2 votes
# Wolfram Language, 109 bytes

```
{a_,b___}~p~{c_,d___}:=If[a==c,{b}~p~{d},a~Order~c]
Sort[Join@@Permutations/@Append@#/@Subsets@Range[#-1],p]&

```

Try it online!

Thanks to @att for a suggestion that saves four bytes.

The first line of this answer is actually a lexicographic ordering function since the default sorting is not lexicographic. It checks if the first two terms of two lists are equal: if so it recurses on the remainder of the lists, and if not it returns the ordering of the two first elements. I expected to need to provide special cases for when one arrives at empty lists, but it appears that in the case of not returning a proper value, `Sort` falls back to the default `Order` function, which works fine.

The function itself generates all subsets of `{1,2,...,n-1}`, appends `n` to each, then generates the permutations of each. These are then sorted into lexicographic ordering using the function defined.

**att's impressive 74-byte answer:** (it feels improper to take credit for it, but I think it deserves recognition)

```
SortBy[Join@@Permutations/@Append@#/@Subsets@Range[#-1],aa~PadRight~#]&

```

is \\\[Function\].

# Answer
> 2 votes
# Charcoal, 46 bytes

```
Ｎθ≔⟦υ⟧ηＦθ«≔ηζ≔⟦υ⟧ηＦ⊕ιＦζ⊞η⁺⟦κ⟧Ｅλ⁺μ¬‹μκ»ＩΦ⊕η⁼θ⌈ι

```

Try it online! Link is to verbose version of code. Directly generates all sequences containing values up to `n` in lexicographical order and then prints those containing `n`. Outputs values on separate lines with sequences double-spaced. Explanation:

```
Ｎθ

```

Input `n`.

```
≔⟦υ⟧η

```

Start off with a list containing an empty sequence.

```
Ｆθ«

```

Loop `n` times.

```
≔ηζ

```

Save the previous list of sequences.

```
≔⟦υ⟧η

```

Start a new list containing an empty sequence.

```
Ｆ⊕ι

```

Loop from `0` to `i` inclusive.

```
Ｆζ

```

Loop over the previous list of sequences.

```
⊞η⁺⟦κ⟧Ｅλ⁺μ¬‹μκ

```

Make a space in the sequence for the inner index and add that at the beginning of the sequence. For example, if current sequence was `1 0`, then an inner index of `0` would give `0 2 1`, an inner index of `1` would give `1 2 0` and an inner index of `2` would give `2 1 0`. This is required so that the sequences are generated in lexicographical order. (Charcoal doesn't have an easy way to sort.)

```
»ＩΦ⊕η⁼θ⌈ι

```

Increment the sequences and print those containing `n`.

# Answer
> 1 votes
# 05AB1E, 10 bytes

```
Lœ€æ€`êʒIå

```

Try it online.

**Explanation:**

```
L           # Push a list in the range [1,(implicit) input]
 œ          # Get all permutations of this list
  €         # Map each permutation to:
   æ        #  Get its powerset
    €`      # Flatten it one level down
      ê     # Sort and uniquify this list of lists
       ʒ    # Filter it by:
        Iå  #  Check if the current list contains the input
            # (after which the result is output implicitly)

```

# Answer
> 1 votes
# APL (Dyalog Extended), 36 bytes

```
{∧∪{⍵/⍨w∊¨⍵}⊃,/⊃¨(⊢,,¨)/¨↓⌂pmat⊢w←⍵}

```

Try it online!

Uses Bubbler's APL tip for generating subsequences of a vector.

## Explanation

```
{∧∪{⍵/⍨w∊¨⍵}⊃,/⊃¨(⊢,,¨)/¨↓⌂pmat⊢w←⍵}
                                w←⍵  assign input to w for later
                          ⌂pmat⊢     generate matrix of all permutations of 1..input
                                     (⌂ is an extended symbol)
                         ↓           convert matrix to list of vectors
                 (⊢,,¨)/¨            generate all subsequences of each,
                                     which include the last item
            ⊃,/⊃¨                    remove nesting for each, and join into a list of vectors
    ⍵/⍨                              filter the vectors by:
       w∊¨⍵                          whether the input exists in them
  ∪                                  remove duplicates
 ∧                                   Sort lexicographically (Extended symbol)

```

# Answer
> 1 votes
# Perl 5, 52 bytes

```
$n=$_;map/(.).*\1|[^1-$n]/|!/$n/||say,sort 1..$n x$n

```

Try it online!

Can run like this for n=3:

```
echo 3 | perl -nlE'$n=$_;map/(.).*\1|[^1-$n]/|!/$n/||say,sort 1..$n x$n'

```

But doesn't work for n \> 9. For n=7 it used twelve seconds on my humble laptop and then about ten minutes for n=8.

# Answer
> 1 votes
# Gaia, 9 bytes

```
┅zf¦e¦Ė⁇ȯ

```

Try it online!

Generate all permutations of subsets of `[1..n]`, filter out those not containing `n`, and sort.

# Answer
> 1 votes
# Japt `-h`, ~~12~~ 11 bytes

```
õ à cá ÍüøU

```

Try it

```
õ à cá ÍüøU     :Implicit input of integer U
õ               :Range [1,U]
  à             :Combinations
    c           :Flat map
     á          :  Permutations
       Í        :Sort
        ü       :Group and sort by
         øU     :  Contains U?

```

# Answer
> 0 votes
# Perl 5 `-MList::Util=uniq -na`, 106 bytes

It's twice as long as the other Perl 5 answer, but it works (slowly) for any `n`;

```
map/\b@F\b/&&!/\b(\d+),.*\b\1\b/&&say,uniq sort map{s/,+/,/g;s/^,+|,+$//gr}glob join',',("{",1..$_,"}")x$_

```

Try it online!

---
Tags: code-golf, sequence, combinatorics
---


title: Show Ulam's spiral

text:
# Question
Title: Show Ulam's spiral
Similar to this but in this one you need to write spiral starting from the center where:

* space means composite number
* `.`(dot) means prime number.

Size of the spiral can be given as parameter or on `stdin`. By size I mean side of square NxN and also N will be always odd.

# Answer
> 3 votes
## Python, 219 chars

```
N=input()
A={0:' '}
d=1j
x=1
for p in range(2,N*N+1):
 A[x]=' .'[all(p%i for i in range(2,p))]
 if abs(x.imag)==abs(x.real):x+=(1-1j)*(d==1);d*=1j
 x+=d
R=range(N)
for y in R:print''.join(A[x-N/2+(N/2-y)*1j]for x in R)

```

Works for any odd `N`. For example:

```
$ echo 9 | ./ulam.py
    . .
 .     .
. .   .
   . . .
  .  .. .
 . .
.   .
 .   .
.     .

```

# Answer
> 3 votes
**JavaScript (~~240~~ ~~202~~ ~~195~~ 151 characters)**

Update: Another much smaller version without function (a lot of credits to @mellamokb):

```
for(x=3,e=d=f=a>>1,c=2;(x&1?x&2?++e<a-d:--e>d:x&2?++f<a-d-1:--f>d)||++x&3||d--;c
++)for(g=0;g<2*a*a;z[g+=c]=1)z[c]||z.getContext("2d").fillRect(e,f,1,1)

```

---

Works with this HTML:

```
<script>a = 50</script>
<canvas id=z width=50 height=50></canvas>

```

25x25 example (zoomed in) - 800x800 example

This new version now performs well and outputs the right size (NxN) for any odd `a`.

Found some small improvements (195 now). Thanks @mellamokb.

---

**Old version:**

```
c=1;i=e=0;b={};for(d=[];c<a*a;){d.push("");for(i+=e+=2;i--;)d[Math.min(e-2,i)]+=
j();d.unshift("");for(i-=e;++i<e;)d[g=Math.max(0,i)]=j()+d[g]}x.innerHTML=d.join
("\n");function j(){if(f=!b[++c])for(h=c*c;h<2*a*a;h+=c)b[h]=1;return f?".":" "}

```

Currently takes variable `a` as input and outputs to an element with the id `x`:

```
<script>a = 50</script>
<pre id=x>

```

I used the Sieve of Eratosthenes for prime generation, which works really well. Output is quite slow so far though. Don't expect this to run for huge n yet.

# Answer
> 2 votes
## Golfscript - 92 Characters

Based on my answer here:

```
~.(:S+,:R{S\-:|;R{S-:$|>' .'1/[|$.|]2/@:d|~)$<!^=~:$;:y.*4*$-y-)2d*$y-*+:$,{)$\%!},,2==}%n}%

```

# Answer
> 2 votes
## APL (85)

```
K[R↑+\(1+M-⍨N×M←⌈N÷2),(2/⍳N)/(2×N)⍴1(-N)¯1N]←K←⍳R←N×N←⎕⋄'. '[1+N N⍴K∊P/⍨P∊P∘.×P←1↓⍳R]

```

Explanation:

* Generating the spiral:
    + `K←⍳R←N×N←⎕`: Read N from the user. The array size N×N is stored in R. K is \[1..R\].
    + `(1+M-⍨N×M←⌈N÷2)`: The coordinate of the middle field.
    + `(2×N)1(-N)¯1N`: the delta coordinates for the next field (i.e. 1 right, up a line (so N fields to the left in a 1-dimensional array), then 1 left, then down a line.
    + `(2/⍳N)/`: duplicate the deltas to form an expanding spiral. 2/⍳N is `1 1 2 2 3 3 ... N N`, duplicating the deltas by these values gives `right up left left down down right right right...`
    + `R↑+\`: sum these values (giving absolute coordinates) and take the first R.
    + `K[`...`]←K`: assign K to K in the order given above. We now have K in spiral order.
* Generating the pattern:
    + `P/⍨P∊P∘.×P←1↓⍳R`: more or less the standard APL idiom for generating primes. P is \[2..R\], P∘.×P is a multiplication table for P. P∘.P therefore contains all composite numbers in the range \[1..R\]. P/⍨ then selects from P all values present in P∘.×P, giving a list of composite numbers.
    + `1+N N⍴K∊`: this selects from K all the composite numbers, giving a binary list in spiral order where there's an 1 if the number is composite. Then add 1 so that composite numbers are 2 and noncomposite (prime) numbers are 1. This is formatted as a N by N table.
    + `'. '[`...`]`: prime numbers (1) become `'.'` and composites (2) become `' '`.

# Answer
> 2 votes
# MATL, 13 bytes

```
UGlYLZp42*cwx

```

Try it online!

A clockwise outward spiral which starts from the right.

## Explanation

```
    U       % convert char matrix to numeric or to general array / square
    G       % paste from user-input clipboard G
    l       % array of ones
    YL      % Create spiral matrix
    Zp      % is prime / totient function
    42      % number literal
    *       % array product (element-wise, singleton expansion)
    c       % convert to character array
    w       % swap elements in stack
    x       % delete elements
            % (implicit) convert to string and display

```

# Answer
> 1 votes
## Python - 203 Characters

Similar to my answer here:

```
x=input();y=x-1;w=x+y
A=[];R=range;k,j,s,t=R(4)
for i in R(2,w*w):
 A+=[(x,y)]*all(i%d for d in R(2,i))
 if i==s:j,k=k,-j;s,t=s+t/2,t+1
 x+=j;y+=k
for y in R(w):print"".join(" ."[(x,y)in A]for x in R(w))

```

---
Tags: code-golf, primes
---


title: Check type of an integer

text:
# Question
Title: Check type of an integer
You will receive an integer less than 2000000000 and bigger than -2000000000 and you have to test what type(s) of number this is out of:

```
Factorial
Square
Cube
Prime
Composite
Triangular
Positive
Negative

```

Here is a definition of all the different types of numbers:

**Factorial** \- A number That is equal to the product of all positive integers less than the a certain positive integer - 5×4×3×2×1 = *120*
**Square** \- A number that is the product of two identical integers - 5×5 = *25*
**Cube** \- A number that is the product of three identical integers - −5×−5×−5 = *-125*
**Prime** \- A number that has only two divisors (1 and 0 are not) - *3*
**Composite** \- A number that has more than two divisors (also not 1 or 0) - *4*
**Triangular** \- A number that is equal the sum of all positive integers less than the a certain positive integer - 5+4+3+2+1 = *15*
**Positive** \- A number larger than 0 (not 0) - *7*
**Negative** \- A number less than 0 (not 0) - *−7*

### Test Cases

```
-8 = ["Cube","Negative"]
-2 = ["Negative"]
-1 = ["Cube","Negative"]
 0 = ["Cube", "Square", "Triangular"]
 1 = ["Cube","Factorial","Positive","Square","Triangular"]
 2 = ["Factorial","Positive","Prime"]
 3 = ["Positive","Prime","Triangular"]
 4 = ["Composite","Positive","Square"]
 5 = ["Positive","Prime"]
 6 = ["Composite","Factorial","Positive","Triangular"]
 7 = ["Positive","Prime"]
 8 = ["Composite","Cube","Positive"]
 9 = ["Composite","Positive","Square"]
10 = ["Composite","Positive","Triangular"]
11 = ["Positive","Prime"]
12 = ["Composite","Positive"]

```

Note: The Order of the Result Does Not Matter and it can be expressed with words **(Does Not Have To Be A List)**

Remember, this is a code golf so the smallest answer in bytes is what I'm looking for

# Answer
# APL (Dyalog Extended), ~~130~~ 119 bytesSBCS

Anonymous tacit prefix function.

```
((∊∘⎕A⊂⊢)'FactorialSquareTriangularCubePositiveNegativePrimeComposite')/⍨{⍵∊¨(⊂∘!,×⍨⍮+\)⍳|⍵},(|∊⍳∘|*3⍨),<,>,1∘⍭,0∘⍭∧1∘<

```

Try it online!

`(``)/⍨` filters the list of strings on the left by the bit mask on the right:

`(``)'Fac``ite'` apply the following tacit function to the long string:

`∊∘⎕A` element-wise membership of the uppercase alphabet

partitions (i.e. True begins a new partition)

the unmodified argument

The last **46 bytes** return a bit vector indicating `[Factorial, Square, Triangular, Cube, Positive, Negative, Prime, Composite]`:

```
{⍵∊¨(⊂∘!,×⍨⍮+\)⍳|⍵},(|∊⍳∘|*3⍨),<,>,1∘⍭,0∘⍭∧1∘<

```

Try it online!

`{``}` the first three bits (factorial, square, triangular) come from this anonymous lambda:

`⍵∊¨(``)`… is the argument a member of each of the following three lists?

`⊂∘!` the enclosed factorials

`,` followed by

`×⍨` the squares (lit. the multiplication selfies)

juxtaposed with

`+\` the running sum

of the integers one through

`|⍵` the absolute value of the argument

`(``)` the next bit (cube) comes from the following tacit function:

`|` is the absolute value of the argument

a member of

`⍳∘|` the integers 1 through the absolute value of the argument

`*` raised to the power of

`3⍨` three

`<` the next bit is simply whether it is positive (zero is less than)

`>` the next bit is simply whether it is negative (zero is more than)

`1∘⍭` the next bit is whether it is prime

`0∘⍭` the final bit is whether it is non-prime

`1∘<` one is less than it
> 6 votes

# Answer
# JavaScript (ES7),  ~~244 238~~  236 bytes

Returns an array of strings.

```
n=>'negative/positive/triangular/cube/square/factorial/prime/composite'.split`/`.filter((s,i)=>(k=!i)?n<0:i-1?i<5?(g=n=>(x=k++**(2+i%2))<n?g(n):x==n)(i-2?i&n<0?-n:n:8*n+1):(g=i-5?k=>n>1?n%--k?g(k):k<2^i>6:0:n=>n>1?g(n/++k):n==1)(n):n>0)

```

Try it online! or See a formatted version

## How?

We filter an array of number properties, keeping track of our current position in the index \\$i\\$:

```
 i | Property   | OEIS    | Test
---+------------+---------+---------------------------------------------------------
 0 | negative   | A001478 | n < 0
 1 | positive   | A000027 | n > 0
 2 | triangular | A000217 | look for k >= 0 such that k**2 = 8n+1
 3 | cube       | A000578 | look for k >= 0 such that k**3 = |n|
 4 | square     | A000290 | look for k >= 0 such that k**2 = n
 5 | factorial  | A000142 | divide n by 1, 2, 3, etc. until it's either 1 or < 1
 6 | prime      | A000040 | n > 1 and its largest proper divisor is equal to 1
 7 | composite  | A002808 | n > 1 and its largest proper divisor is greater than 1
```

### Case \\$i=0\\$ (negative)

We test whether \\$n \< 0\\$.

### Case \\$i=1\\$ (positive)

We test whether \\$n \> 0\\$.

### Case \\$2\le i \le 4\\$ (triangular, cube, square)

We use the following function, starting with \\$k=0\\$:

```
g = n =>                   // n = input
  (x = k++ ** (2 + i % 2)) // x = either k**3 if i = 3, or k**2 otherwise; increment k
  < n ?                    // if the above result is less than n:
    g(n)                   //   do a recursive call
  :                        // else:
    x == n                 //   test whether x is equal to n

```

If \\$i=2\\$ (triangular test), \\$g\\$ is called with \\$8n+1\\$ (i.e. we test whether \\$8n+1\\$ is a perfect square).

If \\$i=3\\$ (cube test), \\$g\\$ is called with \\$|n|\\$ (i.e. we test whether \\$|n|\\$ is a perfect cube).

If \\$i=4\\$ (square test), \\$g\\$ is called with \\$n\\$ (i.e. we test whether \\$n\\$ is a perfect square).

### Case \\$i=5\\$ (factorial)

We use the following function, starting with \\$k=0\\$:

```
g = n =>                   // n = input
  n > 1 ?                  // if n is greater than 1:
    g(n / ++k)             //   increment k and do a recursive call with n / k
  :                        // else:
    n == 1                 //   test whether n is equal to 1

```

### Case \\$i\>5\\$ (prime, composite)

We use the following function:

```
g = k =>                   // k = current divisor, initialized to n
  n > 1 ?                  // if n is greater than 1:
    n % --k ?              //   decrement k; if k is not a divisor of n:
      g(k)                 //     do a recursive call
    :                      //   else:
      k < 2 ^              //     test whether k = 1 (n is prime)
      i > 6                //     invert the result if i = 7
  :                        // else:
    0                      //   always return 0 (n is neither prime nor composite)

```
> 5 votes

# Answer
# Japt, ~~101~~ ~~96~~ 88 bytes

-5 bytes thanks to Oliver
-8 bytes thanks to Shaggy

```
`t„gÔ³dÖ%oÐÒdpoÐÓv‚šg…iv‚cu¼çyÜ)Ã$quÂÂpÎX`qd g[U*8Ä ¬v1 Uk ÅÊU¬U<0Uõ³øU UõÊøU U¬v1 Uj]ð

```

Try it online!
> 3 votes

# Answer
# Stax, ~~79~~ 71 bytes

```
ë∙☺H▓»░g▬äεê▄ú▓▒º₧Σ↓i∟I∩├▼┬√&A4¼╔uë[Ü▼╒π←=Å♥\aâ╬°Æ■v⌂♂δ┴▄·╠.ë¶<→`┬╪½¥6X

```

Run and debug it

Unpacked, ungolfed, and commented, it looks like this.

```
|c      peek input and terminate if falsey
12{|Fm  first 12 factorials
#       (1) is the input found in the array?
x       push original input from x register and
G       (2) execute program at trailing curly brace which tests for square-ness
x       push original input from x register
|n      get exponents of prime factorization
|g      gcd of array
3%!     (3) is not a multiple of 3
x1|M    push max(1, x) where x is the original input
c       copy value on the stack
|p      (4) is prime?
s       swap top two stack entries
|fD     (5) drop first element from prime factorization
x8*^    push 8x+1 where x is the original input
G       (6) execute program at trailing curly brace which tests for square-ness
x0>     (7) is original input greater than zero?
c!      (8) logically negate the value at (7)
`?|yL843smg!O5&;RVPC3&g9W!ISjvJN'n`
        compressed literal for "negative positive triangular composite prime cube square factorial"
        - these are the names in reverse order of the test results pushed at (1)-(8)
:.j     title case and split on spaces
f       filter list of names and implicitly output using the rest of the program as a predicate
  d     drop the name revealing the corresponding test result on top of the stack
        terminate program
}       `G` target from above; when done, resume execution
  c|qJ= copy, floor square-root, square, then test equality; this is a test for squareness

```

Run this one
> 3 votes

# Answer
# Jelly, 67 65 60 59 bytes

```
“R!i“Æ²“ŒR*3i“Ẓ“<2oẒ¬“ŻÄi“R“<0”vTị“*Ṙœȯ#Ḅṙ×¬`ɲṇṭY¤²nxẊ2ı»Ḳ¤

```

Try it online!

A monadic link that accepts an integer and returns a list of strings.

## Explanation

```
“R!i“Æ²“ŒR*3i“Ẓ“<2oẒ¬“ŻÄi“R“<0”   First part of main link
“                                 Begin list of strings separated by “
 R                                  Range: [1..n]
  !                                 Factorial [each]
   i                                Find index of argument
    “                             ,
     Æ²                             Is square?
       “                          ,
        ŒR                          Balanced range: [-n..n]
          *3                        Cube [each]
            i                       Find index of argument
             “                    ,
              Ẓ                     Is prime?
               “                  ,
                <2                  Is less than 2?
                  o                 Or
                   Ẓ                Is prime?
                    ¬               Negate
                     “            ,
                      Ż             Range with zero: [0..n]
                       Ä            Prefix sums
                        i           Find index of argument
                         “        ,
                          R         Range [used to test for positive]
                           “      ,
                            <0      Is less than 0?
                              ”   End list of strings

vTị“*Ṙœȯ#Ḅṙ×¬`ɲṇṭY¤²nxẊ2ı»Ḳ¤   Second part of main link
v                              Evaluate each with the argument
 T                             Indices of truthy elements
  ị                            Index into
                           ¤   (
   “*Ṙœȯ#Ḅṙ×¬`ɲṇṭY¤²nxẊ2ı»       Compressed string "Factorial Square Cube Prime Composite Triangular Positive Negative"
                          Ḳ      Split on spaces
                           ¤   )

```

*Thanks to caird for 60-\>59*
> 3 votes

# Answer
# 05AB1E, ~~76~~ 75 bytes

```
_i¯ë.±D(IÅ²IÄ©3zmDïQIpIÑg3@Id*®LηPIå®ÅTIå)”îË¢…ï©×Ä›ˆÉíšâialÓª”¨¨"ular"«#sÏ

```

Try it online or verify all test cases.

**Explanation:**

```
_i               # If the (implicit) input is 0:
  ¯              #  Push an empty list
 ë               # Else:
  .±             #  Push the signum of the (implicit) input (-1 if <0; 0 if 0; 1 if >0)
                 #   i.e. -8 → -1
  D(             #  Duplicate and take it's negative
                 #   i.e. -1 → 1
  IÅ²            #  Push the input, and check if it's a square
                 #  (negative values will result in the negative numbers themselves)
                 #   i.e. -8 → -8
  IÄ             #  Push the absolute value of the input
                 #   i.e. -8 → 8
    ©            #  Store it in the register (without popping) to reuse later
     3z          #  Push 1/3
       m         #  Take the absolute input to the power of 1/3
                 #  (NOTE: a^(1/3) is the same as ³√a)
                 #   i.e. 8 → 2.0
        DïQ      #  Check if this is an integer without decimal digits
                 #   i.e. 2.0 → 1 (truthy)
  Ip             #  Push the input, and check if it's a prime
                 #   i.e. -8 → 0 (falsey)
  IÑ             #  Push the input, and get a list of its divisors
                 #   i.e. -8 → [1,2,4,8]
    g            #  Take the length of that list
                 #   i.e. [1,2,4,8] → 4
     3@          #  And check if it's larger than or equal to 3
                 #  (the list includes 1, hence the check for >=3 instead of >=2)
                 #   i.e. 4 >= 3 → 1 (truthy)
       Id        #  Push the input again, and check if it's non-negative
                 #   i.e. -8 → 0 (falsey)
         *       #  Check if both are truthy
                 #   i.e. 1 and 0 → 0 (falsey)
  ®L             #  Create a list in the range [1, absolute value of the input]
                 #   i.e. 8 → [1,2,3,4,5,6,7,8]
    η            #  Get a list of prefixes of this list
                 #   → [[1],[1,2],[1,2,3],[1,2,3,4],[1,2,3,4,5],[1,2,3,4,5,6],[1,2,3,4,5,6,7],[1,2,3,4,5,6,7,8]]
     P           #  Get the product for each prefix-list
                 #   → [1,2,6,24,120,720,5040,40320]
      Iå         #  Check if the input is in this list
                 #   i.e. [1,2,6,24,120,720,5040,40320] and -8 → 0 (falsey)
  ®ÅT            #  Create a list of all triangular numbers below or equal to
                 #  the absolute value of the input
                 #   i.e. 8 → [0,1,3,6]
     Iå          #  Check if the input is in this list
                 #   i.e. [0,1,3,6] and -8 → 0 (falsey)
  )              #  Wrap all values on the stack into a single list
                 #   → [-1,1,-8,1,0,0,0,0]
  ”îË¢…ï©×Ä›ˆÉíšâialÓª”
                 #  Push dictionary string "Positive Negative Square Cube Prime Composite Factorial Triangle"
   ¨¨            #  Remove the last two characters (the "le" of "Triangle")
     "ular"«     #  Append "ular"
            #    #  Split this string by spaces
             s   #  Swap to take the earlier created list again
              Ï  #  And only leave the strings at the truthy indices
                 #  (NOTE: Only 1 is truthy in 05AB1E)
                 #   i.e. [-1,1,-8,1,0,0,0,0] → ["Negative","Cube"]
                 # (and output the result implicitly)

```

See this 05AB1E tip of mine (section *How to use the dictionary?*) to understand why `”îË¢…ï©×Ä›ˆÉíšâialÓª”` is `"Positive Negative Square Cube Prime Composite Factorial Triangle"`.
> 2 votes

# Answer
# Husk, ~~60~~ ~~65~~ ~~61~~ 59 bytes

*Edit: +5 bytes to fix zero as a square, cube & triangular, and to fix zero, one and negative numbers as non-composites (in line with test cases)...*

*...but then -4 bytes thanks to Razetime, by changing all the forks (`§:` and `§e`) to a mapping over a bigger list of functions*

```
f+m€⁰mëmΠm□m^3mΣΘḣ⁰mëṗȯ>2LḊ>0<0⁰w¨◄Γq□ṡ_ẏĊ8ζŀ⁸→PṘβ□θpż√₁□Ġë

```

Try it online!

**How?**

```
f                               # select each element if input satisfies:
 +                              # combine 2 lists of 4 together:
  m€⁰§:mΠ§:m□§em^3mΣΘḣ⁰         # first list:
  m€⁰                           # check whether input is
     §:  §:  §e                 # among
       mΠ                       # factorials of
           m□                   # or squares of
               m^3              # or cubes of
                  mΣ            # or triangular numbers of
                    Θḣ⁰         # series from 0..input
  mëṗȯ>2LḊ>0<0⁰                 # second list:
  m             ⁰               # map functions over input:
   ë                            # list of 4 functions
    ṗ                           # is prime?
     ȯ>2LḊ                      # is composite (more than 2 divisors)?
          >0                    # is positive?
            <0                  # is negative?

                                # elements to select:
w                               # split on spaces
 ¨◄Γq□ṡ_ẏĊ8ζŀ⁸→PṘβ□θpż√₁□Ġë     # compressed string
                                # "Factorial Square Cube Triangular Prime Composite Positive Negative"

```
> 2 votes

# Answer
# Python 3, ~~405~~ 259 bytes

Thanks to @ASCII-only

```
def z(n):
	x=y=1
	while x<n:x*=y;y+=1
	return"Factorial "*(x==n)+"Square "*(n>=0and n**.5%1==0)+"Cube "*(abs(n)**(1/3)%1==0)+"Negative "*(n<0)+"Positive "*(n>0)+"Triangular "*(n>0and(8*n+1)**.5%1==0)+["Composite ","Prime "][all(n%x for x in range(2,n))]*(n>1)

```

Try it online!

Old Code

Generates the squares, cubes, and factorials into lists to check against, has a function to check for primality (and consequently compositeness), uses a simple equality to check for positivity/negativity, and checks if `8n+1` is a perfect square to determine if `n` is a triangular number. Hardcoded the limits for the square, cube, and factorial lists. Returns the answer in a set, which I assume is acceptable (adding elements to a list requires more bytes).

```
p=lambda n:all(n%x!=0 for x in range(2,n))
def z(n):
	f,a,x,y,s,c=[],set(),1,1,[i*i for i in range(44721)],[i**3 for i in range(-1259,1259)]
	while x<2*10**9:f.append(x);x*=y;y+=1
	if n in f:a.add("Factorial")
	if n in s:a.add("Square")
	if n in c:a.add("Cube")
	if n>0:
		a.add("Positive")
		if 8*n+1 in s:a.add("Triangular")
	if n>1:a.add(("Composite","Prime")[p(n)])
	if n<0:a.add("Negative")
	return a

```

Try it online!
> 1 votes

# Answer
# C# (Visual C# Interactive Compiler), 286 bytes

```
n=>{int k=0;return(n>0?"Positive":n<0?"Negative":"")+(Math.Sqrt(8*n+1)%1==0?"Triangular":"")+(new int[n].Where((a,b)=>n%++b<1).Count()>2?"Composite":n<3?"":"Prime")+(Math.Pow(n,1/3d)%1>0?"":"Cube")+(Math.Sqrt(n)%1>0?"":"Square")+(g(k)?"Factorial":""));bool g(int i)=>i>1?g(i/++k):1==i;}

```

Try it online!
> 0 votes

# Answer
# 05AB1E, 63 bytes

```
ÅTIL3mILÄ!)IQO`Î‹Î›IÅ²IpD≠$‹*)“×ÄšâialîË¢…ï©›ˆÉí“#.•’α`ë\Ä•šsÏ™

```

Try it online! or Verify all test cases!

**Commented**:

```
ÅT                   # push the triangular numbers up to the input
  IL                 # push the range [1..input]
    3m               # take each number to the third power
      IL             # push the range [1..input]
        Ä            # take absolute values
         !           # take the factorial of each number
          )          # collect the three list in a list of lists
           IQ        # for each element chack if it is equal to the input
             O       # sum the sublists
              `      # and push all three values to the stack

Î‹                   # is 0 < input? (Î pushes 0 and the input)
  Î›                 # is 0 > input?
    IÅ²              # is the input a square number?
       Ip            # is the input prime?
         D≠          # duplicate this value and invert the copy
           $         # push 1 and the input
            ‹        # is 1 < input
             *       # is the input composite? (not prime & > 1)
              )      # collect all these values in a list

“×ÄšâialîË¢…ï©›ˆÉí“  # push compressed string "cube factorial positive negative square prime composite"
 #                   # split on spaces
  .•’α`ë\Ä•          # push compressed string "triangular"
           š         # and prepend it to the word list
            s        # swap the integer back to the top
             Ï       # keep all words where 1's are in the integer list
              ™      # titlecase all words

```
> 0 votes

---
Tags: code-golf, math, number-theory, integer, classification
---


title: Golomb's wobbly sequence

text:
# Question
Title: Golomb's wobbly sequence
OEIS has a variation (A111439) on Golomb's sequence. As in Golomb's sequence, `A(n)` describes how often `n` appears in the sequence. But in addition, no two consecutive numbers may be identical. While building up the sequence, `A(n)` is always chosen as the smallest positive integer that doesn't violate these two properties. Due to disallowed consecutive identical numbers, the series wobbles slightly up and down as it grows. Here are the first 100 terms:

```
1, 2, 3, 2, 3, 4, 3, 4, 5, 6, 5, 6, 5, 6, 7, 6, 7, 8, 7, 8, 9, 8, 9, 8, 9,
10, 9, 10, 9, 10, 11, 10, 11, 10, 11, 10, 11, 12, 11, 12, 13, 12, 13, 12,
13, 12, 13, 12, 13, 14, 15, 14, 15, 14, 15, 14, 15, 14, 15, 14, 15, 16, 15,
16, 17, 16, 17, 16, 17, 16, 17, 16, 17, 18, 17, 18, 17, 18, 19, 18, 19, 18,
19, 18, 19, 18, 19, 18, 19, 20, 19, 20, 21, 20, 21, 20, 21, 20, 21, 20

```

The full list of the first 10,000 numbers can be found on OEIS.

The challenge is to write a program or function which computes `A(n)`, given `n`. `n` is `1`-based to ensure that the self-describing property works.

## Rules

You may write a program or a function and use any of the our standard methods of receiving input and providing output.

You may use any programming language, but note that these loopholes are forbidden by default.

This is , so the shortest valid answer – measured in *bytes* – wins.

## Test Cases

```
n     A(n)
1     1
4     2
10    6
26    10
100   20
1000  86
1257  100
10000 358

```

# Answer
# Mathematica, ~~69~~ 68 bytes

*Thanks to Martin Ender for finding an extra –1 byte for me!*

```
Last@Nest[{##&@@#,1//.x_/;x==Last@#||#~Count~x==#[[x]]->x+1}&,{},#]&

```

Unnamed function taking a positive integer `n` as input and returning a positive integer. We construct the entire list of the first `n` elements of this sequence, then take the `Last` element. The list is constructed by starting with the empty list `{}` and operating on it with a function `n` times in a row (via `Nest`).

The function in question is `{##&@@#,1//.x_/;x==Last@#||#~Count~x==#[[x]]->x+1}&`, which takes a partial list of sequence values (essentially `##&@@#`) and appends the next value to it. The next value is computed by starting with `x=1`, then repeatedly replacing `x` by `x+1` as long as the condition `x==Last@#||#~Count~x==#[[x]]` is met—in other words, if either `x` is the previous element, or else `x` is already in the list the correct number of times. This function spits some errors, since (for example) we shouldn't be calling the `x`th element of the initial list `{}`; however, the values are all correct.
> 5 votes

# Answer
## Haskell, 67 bytes

```
f k|k<4=k|p<-k-1=[n|n<-[1..],n/=f p,sum[1|a<-[1..p],f a==n]<f n]!!0

```

Defines a function `f`. Try it online! It's very slow, computing `f 15` times out on TIO.

## Explanation

Just going with the definition: at every stage, choose the minimal positive number `n` that satisfies the constraints (not equal to previous entry, and has not occurred `f n` times yet).

```
f k             -- Define f k:
 |k<4=k         -- If k < 4, it's k.
 |p<-k-1=       -- Otherwise, bind k-1 to p,
  [n|           -- compute the list of numbers n where
   n<-[1..],    -- n is drawn from [1,2,3,...],
   n/=f p,      -- n is not equal to f p, and
   sum[1|       -- the number of
    a<-[1..p],  -- those elements of [1,2,3,...,p]
    f a==n]     -- whose f-image equals n
   <f n]        -- is less than f n,
  !!0           -- and take the first element of that list.

```
> 5 votes

# Answer
# Python 2, 99 86 bytes

Thanks to @Dennis for several improvements totaling 13 bytes!

```
s=0,1,2,3
exec't=1\nwhile t==s[-1]or s.count(t)/s[t]:t+=1\ns+=t,;'*input()
print s[-4]

```

The program proceeds pretty naively: It keeps track of the list of values it's determined so far, and looks to append the next value. It tries to append a `1` to the end of the list if it can; if not, then it tries a `2` and so on until something is allowed.

Now, we start by seeding the results for `1,2,3` to be `1,2,3`. This is done to avoid any problems with the list of already-computed values being too short: I **conjecture** that if `n` is at least `4` then `a(n)` is strictly less than `n`. (In this program, `s[n]` is equal to `a(n)`. Our list actually is initialized to be `[0,1,2,3]` because lists are `0`-indexed in Python. So for instance `a(1)=s[1]=1`, and `a(2)=s[2]=2`.)

So, let's say we're trying to determine `s[m]`, meaning that our list already includes `s[0], s[1], ..., s[m-1]`. We'll start at `t=1` and try to set `s[m]=1`. When that doesn't work, we go to `t=2` and try to set `s[m]=2`. Each time we increment `t`, we check whether `s.count(t)==s[t]`...but the right-hand side won't produce an error so long as we never have to go as high as `t=m`. The conjecture says that we never have to, since the first value we compute is actually `s[4]`.

This implementation computes 3 more values of the sequence than it needs to. For example if `n` is `8`, it'll compute up through `s[11]` before it returns the value of `s[8]`.

I'd be happy to see a proof of the conjecture. I believe it can be proven by (strong?) induction.

Edit: Here is a **proof of the conjecture**. We actually prove a slightly stronger form of the statement, since it involves no extra work.

**Theorem:** For all `n` greater than or equal to `4`, the term `a(n)` is less than or equal to `(n-2)`.

Proof (by Strong Induction): (Base `n=4`): The statement is true for `n=4`, since `a(4) = 2 = 4-2`.

Now assume `a(k)` is less than or equal to `k-2` for all `k` from `4` through `n`, inclusive (and assume `n` is at least `4`). In particular, this means that all previous terms of the sequence were at most `(n-2)`. We need to show that `a(n+1)` will be at most `(n-1)`. Now, by definition, `a(n)` is the smallest positive integer that doesn't violate any of the conditions, so we just need to show that the value `(n-1)` will not violate any of the conditions.

The value `(n-1)` will not violate the "no consecutive repeats" condition, because by the induction hypothesis the previous entry was at most `(n-2)`. And it won't violate the "`a(m)` is the number of times `m` appears" condition, unless `(n-1)` had already been reached `a(n-1)` times. But by the strong induction assumption, `(n-1)` had previously been reached `0` times, and `a(n-1)` is not equal to `0` since `a(m)` is positive for all `m`.

Therefore `a(n+1)` is less than or equal to `n-1 = (n+1)-2`, as desired. QED.
> 5 votes

# Answer
# Jelly, 17 bytes

```
Ṭ€S<;1Tḟ®Ḣ©ṭ
⁸Ç¡Ṫ

```

The last three test cases are too much for TIO. I've verified **1000** and **1257** locally.

Try it online! or verify the first 100 terms.

### How it works

```
⁸Ç¡Ṫ          Main link. No arguments.

⁸             Yield [].
 Ç¡           Execute the helper link n times (where n is an integer read from
              STDIN), initially with argument [], then with the previous return
              value as argument. Yield the last return value.
              Tail; yield the last element of the result.

Ṭ€S<;1Tḟ®Ḣ©ṭ  Helper link. Argument: A (array)

Ṭ€            Untruth each convert each k into an array of k-1 zeroes and one 1.
  S           Sum; column-wise reduce by +, counting the occurrences of all
              between 1 and max(A).
   <          Compare the count of k with A[k] (1-indexed), yielding 1 for all
              integers that still have to appear once or more times.
    ;1        Append a 1 (needed in case the previous result is all zeroes).
      T       Truth; find all indices of ones.
       ḟ®     Filter-false register; remove the value of the register (initially 0)
              from the previous result.
         Ḣ©   Head copy; yield the first (smallest) value of the result and save
              it in the register.
           ṭ  Tack; append the result to A.

```
> 3 votes

# Answer
# Python 2, ~~77~~ 74 bytes

```
f=lambda n,k=1:n*(n<4)or map(f,range(n)+k*[n-1]).count(k)<f(k)or-~f(n,k+1)

```

This is a recursive implementation of @mathmandan's algorithm.

The implementation is **O(insane)**: input **9** takes 2 seconds locally, input **10** 52 seconds, and input **11** 17 minutes and 28 seconds. However, if declared as a regular function rather than a lambda, memoization can be used to verify the test cases.

Try it online!

Note that even with memoization, TIO cannot compute **f(1257)** or **f(10000)** (both verified locally).
> 3 votes

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

```
XˆXˆG[N¯2(è<›¯¤NÊsN¢¯Nè‹&&#]N.ˆ

```

Try it online!

**Explanation**

```
XˆXˆ                             # initialize global list as [1,1]
    G                            # input-1 times do:
     [                    #]     # loop until expression is true
      N¯2(è<›                    # n > list[-2]-1
             ¯¤NÊ                # list[-1] != N
                 sN¢¯Nè‹         # count(list, N) < list[N]
                        &&       # logical AND of the 3 expressions
                            N.ˆ  # add N to global list
                                   and output last value in list and end of program

```

We are technically in loop `G` when we add **N** to global list, but all loops in 05AB1E use the same variable **N** as index, so the inner loop `[...]` has overwritten the **N** of `G` meaning we can add it outside the loop.

Issues with nested loops and conditionals prevents us from doing this inside the loop.
> 2 votes

# Answer
# Befunge, ~~141~~ 136 bytes

```
<v9\0:p8\2:*2:-1<9
v>p1+:3\8p0\9p:#^_&
>1-:#v_1.@>$8g.@
*+2%\>1-:!|>$!:::9g!\!9g!*\:8g\!8g`
9\+1g9::< \|`g9\g8+2::p
g2+\8p2+^:<>:0\9p::8

```

Try it online!

Because of Befunge's memory limitations, it's not really practical to keep track of all previous entries entries in the sequence, so this solution uses an algorithm with a lower memory footprint which calculates the values more directly.

That said, we're still limited by the cell size, which in the Befunge-93 reference interpreter is a signed 8-bit value, so the highest supported even number in the sequence is `A(1876) = 126`, and the highest supported odd number is `A(1915) = 127`.

If you want to test larger values, you'll need to use an interpreter with a larger cell size. That should include most Befunge-98 implementations (Try it online!).
> 2 votes

# Answer
# Husk, 18 bytes

```
!¡λḟ≠→¹f§<!#¹ŀΘ)ḣ3

```

Try it online!

I decided to spare my soul and do it without combinators, and it's still the same size with them. Fun sequence.

just need to save a single byte...

## Explanation

```
!¡λḟ≠→¹f§<!#¹ŀΘ)ḣ3
                ḣ3 start with [1,2,3]
 ¡λ            )   apply the following repeatedly:
             ŀΘ    prepend zero, get range [1..length+1]
                   → [1,2,3,4]
       f§          filter out values where:
           #¹      frequency in sequence
         <         is not less than
          ! ¹      projected frequency in sequence
                   → [2,3]
   ḟ               find the first element
    ≠→¹            which isnt equal to the most recent element
                   → 2
!                  take the nth element of this infinite list

```
> 2 votes

# Answer
# Python 2, 117 bytes

Meh. Not that short. The simple iterative solution.

```
L=[1,2,3]
n=input()
while len(L)<n:
 for i in range(2,n):
    if L.count(i)<L[i-1]and L[-1]!=i:L+=[i];break
print L[n-1]

```

**Try it online**

Here's a really bad attempt at a recursive solution (129 bytes):

```
def f(n,L=[1,2,3]):
 if len(L)>=n:print L[n-1];exit(0)
 for i in range(2,n):
    if L.count(i)<L[i-1]and L[-1]!=i:f(n,L+[i])
 f(n,L)

```
> 0 votes

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