title: Fibonacci trees

text:
# Question
Title: Fibonacci trees
## Background

**Fibonacci trees** \\$T\_n\\$ are a sequence of rooted binary trees of height \\$n-1\\$. They are defined as follows:

* \\$T\_0\\$ has no nodes.
* \\$T\_1\\$ has a single node (the root).
* The root node of \\$T\_{n+2}\\$ has \\$T\_{n+1}\\$ as its left subtree and \\$T\_n\\$ as its right subtree.

```
T0 T1   T2      T3           T4
    O    O       O            O
        /       / \         /   \
       O       O   O       O     O
              /           / \   /
             O           O   O O
                        /
                       O

```

Each tree in this sequence is the most unbalanced possible state of an AVL tree of same height.

## Challenge

Given the number \\$n\\$, output the \\$n\\$-th Fibonacci tree.

By the usual rules, your function or program may behave as one of the following:

* Take \\$n\\$ as input, and output the \\$n\\$-th tree (\\$n\\$ can be 0- or 1-indexed; the given example is 0-based)
* Take \\$n\\$ as input, and output the first \\$n\\$ trees
* Take no input, and output the sequence of trees indefinitely

A binary tree can be output in any acceptable ways, including but not limited to

* a built-in tree object if your language has one,
* a nested array, an ADT, or its textual representation,
* a human-readable ASCII/Unicode art, or
* a flattened list of nodes labeled as numbers in level order.

Shortest code in bytes wins.

# Answer
> 18 votes
# , 14 bytes

```
(2{.];])^:[&a:

```

Try it online!

We use J boxes to represent the trees:

```
┌┐
││
└┘
---
┌──┬┐
│┌┐││
│││││
│└┘││
└──┴┘
---
┌─────┬──┐
│┌──┬┐│┌┐│
││┌┐││││││
│││││││└┘│
││└┘│││  │
│└──┴┘│  │
└─────┴──┘
---
┌──────────┬─────┐
│┌─────┬──┐│┌──┬┐│
││┌──┬┐│┌┐│││┌┐│││
│││┌┐│││││││││││││
││││││││└┘│││└┘│││
│││└┘│││  ││└──┴┘│
││└──┴┘│  ││     │
│└─────┴──┘│     │
└──────────┴─────┘

```

# Answer
> 9 votes
# Wolfram Language (Mathematica), 19 bytes

```
#<2||#0/@{#-1,#-2}&

```

Try it online!

1-indexed. Returns the \\$n\\$th tree.

Expressions in Mathematica are trees. `True` represents the absence of a node.

Visually:

# Answer
> 8 votes
# Jelly, 2 bytes

Try it online!

**Takes input from STDIN.** Outputs the `n`th Fibonacci tree in the form of a nested list, where a list represents a node and `0` represents NIL.

## Explanation

* `,` — Pair
* `¡` — Turn the preceding dyadic function f(x, y) into a triadic function g(x, n, y) such that:
    + g(x, 0, y) = x
    + g(x, 1, y) = f(x, y)
    + g(x, n, y) = f(g(x, n-1, y), g(x, n-2, y))

Since the link is called as a nilad, zeros are supplied for `x` and `y` and a number from STDIN is taken for `n`.

# Answer
> 6 votes
# Haskell, 34 bytes

```
data T=E|N T T
f=E:scanl N(N E E)f

```

Try it online!

`f` is the infinite list of Fibonacci trees, represented as a custom type defined in the first line (`E` is the empty tree, `N l r` is the tree with left subtree `l` and right subtree `r`).

## How?

Haskell is usually very well-suited for Fibonacci-related tasks. Assume we have a recurrence of the form $$ \begin{cases} \texttt{f}\_0=\texttt{a}\\ \texttt{f}\_1=\texttt{b}\\ \texttt{f}\_{n+2}=\texttt{g}(\texttt{f}\_{n+1},\texttt{f}\_n), \end{cases} $$ where \\$\texttt{g}\\$ is a binary operator. Then the corresponding Haskell definition is simply

```
f=a:scanl g b f

```

Unfortunately, Haskell is *not* very well-suited for problems involving trees, since it can't (natively) handle nested lists or tuples. Defining my own data type for trees was the shortest way I could find to solve this issue.

# Answer
> 5 votes
# Husk, ~~16~~ 12 bytes

```
ΘGȯf≠'"s,s0₀

```

Try it online!

Trees or arbitrarily nested lists are not a thing in Husk, so this builds a string representation of the tree, where a leaf is represented as "0" and a node with a Left child L and a right child R is represented as "(L,R)".

Returns the infinite list of Fibonacci trees, which get printed one per line.

### Explanation

I've started from what's probably the second shortest way of computing Fibonacci numbers in Husk (the shortest being the builtin `İf`):

```
ΘG+1₀

```

Try it online!

This puts a 0 at the beginning of the sequence (with `Θ`), then scans (`G`) recursively the same list  with `+`, starting from `1` and summing every time the last result to the next element in the list.

With this, we just need to alter the starting values and the `+` operator to make it compute Fibonacci trees.

The `1` now becomes `"0"` (`s0`, string representation of the number `0`) and the `0` turns into `""` automagically, thanks to Husk understanding that the list is now a list of strings rather than numbers. The operator that generates a new tree from the two previous ones becomes a bit more complex *(but not as complex as I originally made it, thanks Dominic van Essen!)*:

```
f≠'"s,         Input: left subtree "L", right subtree "R"
     ,         Join the two subtrees in a pair ("L","R")
    s          Convert the pair into a string "(\"L\",\"R\")"
Now we need to remove the extra quotes:
f              Keep only those characters
 ≠              that are different
  '"            than "

```

# Answer
> 4 votes
# , 39 bytes

```
f=function(n)if(n>0)list(f(n-1),f(n-2))

```

Try it online!

Output is a nested list of lists of 2 elements each.
Leaves are represented as lists with no child lists (both list elements are `NULL`).

# Answer
> 4 votes
# Python 3, ~~53~~ ~~50~~ ~~45~~ 44 bytes

```
f=lambda n:n and[n]if n<2else[f(n-1),f(n-2)]

```

Try it online!

Thanks @Dominic van Essen save 3 bytes.

Save 5 bytes changing the first `if` condition with `and`.

Thanks @user save 1 byte.

# Answer
> 3 votes
# JavaScript (Node.js), ~~29~~ 27 bytes

Saved 2 bytes with a suggestion from Jo King.

```
f=n=>n<1?[]:[f(n-1),f(n-2)]

```

Try it online!

A tree is represented by `[l, r]`. The absence of a child is represented by `[]`.

# Answer
> 3 votes
# 05AB1E, 6 bytes

```
õ¯‚λs‚

```

Outputs the infinite sequence, with an empty string as empty node (i.e. \\$T4\\$ will result in `[[[[],""],[]],[[],""]]`)

Try it online. (The footer is to print each tree on a separated line with newline-delimiters. Feel free to remove it to see the actual infinite list output.)

**Explanation:**

```
   λ    # Start a recursive environment
        # to output the infinite sequence,
õ       # starting at a(0)=""
 ¯‚     # and a(1)=[]
õ¯‚     # (Push an empty string ""; push an empty list []; pair them together)
        # And we calculate every following a(n) as follows:
        #  (implicitly push the values of a(n-2) and a(n-1)
    s   #  Swap them on the stack
     ‚  #  And pair them together: [a(n-1),a(n-2)]

```

# Answer
> 2 votes
# Charcoal, 18 bytes

```
ＦＮ⊞υ✂υ±¹±³±¹∧υ⭆¹⊟υ

```

Try it online! Link is to verbose version of code. Outputs nodes as arrays of between 0 and 2 elements. Explanation:

```
ＦＮ

```

Input `n` and loop `n` times.

```
⊞υ✂υ±¹±³±¹

```

Take the last and second last results (if any), and make them the children of the root of the next tree.

```
∧υ⭆¹⊟υ

```

Print the last tree, if any.

# Answer
> 2 votes
# APL(Dyalog Unicode), 14 bytes SBCS

```
{⍵>0:∇¨⍵-⍳2⋄0}

```

Try it on APLgolf!

Outputs as a nested list, where each list contains two elements which are the left and right children, and 0 is null.

-10 bytes thanks to Razetime and user, and also using a better online interface courtesy of Razetime

## Explanation

```
{            }  dfn
 ⍵>0:           if the argument is greater than 0
     ∇¨         - recurse; apply this dfn to each of
       ⍵-       - the argument minus        (vectorizes)
         ⍳2     -                    [1, 2]
           ⋄0   else, just return 0

```

# Answer
> 2 votes
# Branch, 35 bytes

```
/;{^\;{Z[{Z0]z^[/@^\@^0]~`L`Ln[0`P]

```

Try it on the online Branch interpreter!

Of course, it's only natural that a language based on binary trees would have a way to solve this challenge. Branch is still in development; I'm not sure how I could've solved this before adding a bunch of bugfixes and a couple of new helpers.

Pretty-printing the tree was actually around from the start though. I used it as a debug feature; never thought I would've found a challenge so soon to use a debug feature as output formatting for :P

## Explanation

The command line argument is automatically loaded into the first and only node in the binary tree. Note that `[...]` is the same as in BF; that is, it's a while loop, so if the current value is 0 at `[`, it skips to `]`, and if the current value is non-zero at `]`, it jumps back to `[`. Therefore, `[...0]` will only run if the value is non-zero, but then the value is zeroed at the end and so it never runs more than once. Essentially, this is an if statement.

```
/;{            Go to the left child, copy the parent, and decrement
^\;{           Go back to the parent, go to the right child, copy, and decrement
Z              Save the value to register Z
[  0]          If that value is not zero
 {Z            Decrement and save to Z (we need to save the value because it gets zeroed to allow the if statement to end)
z              Restore Z; this is (parent value - 2) if parent value is not 1, and otherwise just 0
^              Go back to the parent
[      0]      If the node is non-zero
 /@            Go to the left child and run this line on that, returning here when done
   ^\@         Go to the right sibling and run this line on that, returning here when done
      ^        Go to the parent, then zero it to end the if statement
~              Return to @, if we are currently in a sub-evaluation. If not, this gets skipped, and we can end the program
`L             Delete all leaves; every node with leaves is a 0 with -1 and -2 as children; these shouldn't be output
`L             Delete all leaves again; it might be valid to output such that these leaves are considered the "null" elements like my APL solution and the 2-byte jelly solution do, but I decided to remove them for style and this code is long enough as it is
[   ]          While this node is non-zero (input 0 and 1 give the same tree, so we need to suppress output if the value was 0)
 0             Zero the top node; this turns the while loop into an if statement and also prevents the final output from having the value there
  `P           Pretty-print the tree; this was created for debugging purposes, but conveniently enough, lets us answer this challenge quite nicely

```

# Answer
> 1 votes
# Retina, 34 bytes

```
K`¶
"$+"+`(.*)¶(.*)
[$1,$2]¶$1
0G`

```

Try it online! Outputs a tree of tuples. No test suite due to the program's use of history. Explanation:

```
K`¶

```

Replace the input with a newline, representing two empty trees.

```
"$+"+`

```

Repeat the number of times given by the original input...

```
(.*)¶(.*)
[$1,$2]¶$1

```

... create a node containing the previous two trees, and forget the second last tree.

```
0G`

```

Keep only the last tree.

# Answer
> 1 votes
## Common Lisp, 58 bytes

```
(defun f(n)(case n(0())(1 0)(t(cons(f(1- n))(f(- n 2))))))

```

Example:

```
USER> (loop for i from 0 to 7 do (print (f i)))

NIL
0
(0)
((0) . 0)
(((0) . 0) 0)
((((0) . 0) 0) (0) . 0)
(((((0) . 0) 0) (0) . 0) ((0) . 0) 0)
((((((0) . 0) 0) (0) . 0) ((0) . 0) 0) (((0) . 0) 0) (0) . 0)

```

Additionally, if you `(ql:quickload :memoize)`, you can do `(memoize-function 'f)` and it will cache intermediate results.

# Answer
> 1 votes
# Stax, ~~12~~ 10 bytes

```
z1]Wn|uPbs2l

```

Run and debug it

A bit long since the trees need to be printed as a string to be observed.

## Explanation

```
z1]Wn|uPbs2l
z1]            push empty list and [1] (base cases)
   W           loop forever
    n          copy the second to last element
     |u        uneval (JSON.Stringify)
       P       pop & print with newline
        b      copy top two elements
         s     swap
          2l   two element list

```

# Answer
> 1 votes
# Kotlin, ~~85~~ 71 bytes

Thanks to @user, saved 14 bytes

```
fun f(n:Int):Any=when(n){0->"0"
1->"[1]"
else->"[${f(n-1)},${f(n-2)}]"}

```

Try it online!

# Answer
> 1 votes
# tinylisp, ~~46~~ 45 bytes

```
(d F(q((N)(i(l N 1)0(c(F(s N 1))(c(F(s N 2))(

```

Try it online!

A function submission that takes an integer and returns a list:

* The empty tree is represented by `0`
* A nonempty tree is represented by a two-element list containing its left and right subtrees

### Ungolfed

Recursively implements the definition: if N is less than 1, returns `0`; otherwise, constructs a list containing the results of two recursive calls, one for N-1 and one for N-2.

```
(load library)

(def F
 (lambda (N)
  (if (less? N 1)
   0
   (cons
    (F (- N 1))
    (cons
     (F (- N 2))
     ())))))

```

# Answer
> 1 votes
# Pari/GP, 30 bytes

```
f(n)=if(n>0,[f(n-1),f(n-2)],0)

```

Try it online!

# Answer
> 0 votes
# C (gcc), ~~214~~ 175 bytes

-39 bytes thanks to ceilingcat

```
char m[12][50];c(n){f(n,!memset(m,32,600),n*n);}f(n,i,j){m[i][j]=48;n-1?n-2?m[i+1][j-n/2]=47,m[i+1][j+n/2]=92,f(n-1,i+2,j-n),f(n-2,i+2,j+n):(m[++i][--j]=47,m[++i][--j]=48):0;}

```

Try it online!

I chose the ASCII art for fun.
The code consists of a function `c()` whose role is to call `f()`, just once. `f()` is a very creative recursive function with a passion for drawing trees on blank arrays.

Only the first 5 trees are correct. To display bigger trees I should use an exponential law for the spacing between the nodes, but if I do so, then the highest nodes would be so distant from each other that you wouldn't recognize bigger trees anyway.

I will post a conceptually right solution.

# Answer
> 0 votes
# Pyth, 19 bytes

```
L?b?qb1]b,ytbyttbby

```

Try it online!

---

Near literal translation of n1k9's Python 3 answer.

---
Tags: code-golf, sequence, fibonacci, binary-tree
---


title: Khinchin's constant bad estimate

text:
# Question
Title: Khinchin's constant bad estimate
Inspired by `How to write down numbers having an infinity of decimals?` Link

## Background

From Wikipedia: for almost all real numbers \\$x\\$, coefficients \\$a\_i\\$ of the continued fraction expansion of \\$x\\$ have a finite geometric mean that is independent of the value of \\$x\\$ and is known as `Khinchin's Constant`.

Khinchin's Constant can be calculated using the following method:

1. Using the \\$n\\$ first terms of the `simple continued fraction` of a real number (For example Pi).
2. Compute their product
3. Apply the \\$n^{\text{th}}\\$ root on the absolute value of product calculated above

## What is a simple continued fraction

It can be expressed as: $$x=\[a\_0; a\_1, a\_2, \dots, a\_n\]$$ Or $$ x=a\_0+ \cfrac{1}{a\_1+ \cfrac{1}{a\_2+ \cfrac{1}{\ddots{+ \cfrac{1}{a\_n}}}}} $$

And can be calculated using the following:

1. Separate \\$x\\$ into its integer part \\$a\_n\\$ and decimal part \\$d\\$
    * \\$a\_n = \lfloor x \rfloor\\$
    * \\$d = x - \lfloor x \rfloor\\$
2. Repeat using the inverse of \\$d\\$ in place of \\$x\\$ while \\$d\\$ is not 0

It is a `simple` continued fraction because the numerator is always 1.

For negative numbers, the same rule applies, the first term of the sequence will be negative.

For example for \\$π\\$: $$ π = \[a\_0; a\_1, a\_2, a\_3, \dots\] = \[3; 7, 15, 1, 292, \dots\] $$

$$ π=3+\cfrac{1}{7+ \cfrac{1}{15+ \cfrac{1}{1+ \cfrac{1}{292+ \cdots}}}} $$

And \\$-π = \[-4; 1, 6, 15, 1, 292, \dots\]\\$

## Challenge

Using the method used to approximate `Khinchin's Constant` described above:
Given a number of terms \\$n\\$ and a real number \\$x\\$, compute the geometric mean of the coefficients of the continued fraction expansion of \\$x\\$.

Standard rules apply.

## Test cases:

| Terms to use | Real number | Expected Result | Note |
| --- | --- | --- | --- |
| 1 |  | 3 |  |
| 2 |  | 4.5825... |  |
| 3 |  | 6.8040... |  |
| 7 |  | 5.1179... |  |
| 7 | - | 5.2165... |  |
| 15 |  | 1.8156... |  |
| 15 | - | 1.9164... |  |
| 20 | - | 1.0717... |  |
| 20 |  | 1 |  |
| 100 |  | 1 | Optional, might not work because of consecutive floating point errors |

# Scoring

This is , so the answer with the least amount of bytes wins.

# Answer
# Husk, 14 bytes

```
^\¹Π↑¡§,o\%1⌊²

```

Try it online! for the last test case (or try it here for n=7, number=pi).

```
     ¡          # Apply function repeatedly to first results,
                # collecting second results into infinite list:
      §,     ²  #  combine pair of results of functions applied to arg 2:
            ⌊   #   floor
        o\%1    #   reciprocal of fractional part
    ↑           # Now take arg1 elements from list,
   Π            # calculate the product,
^               # and raise to the power of
 \¹             # reciprocal of arg1

```
> 4 votes

# Answer
# Factor \+ `math.continued-fractions math.unicode`, 66 bytes

```
[ 1vector over [ dup next-approx ] times 1 head* Π abs nth-root ]

```

Try it online!

## Explanation

It's a quotation (anonymous function) that takes an integer signifying the number of terms to use and a real number and returns a real number. Assuming `3 3.141592653589793` is on the data stack when this quotation is called...

| Snippet | Comment | Data stack (top on right) |
| --- | --- | --- |
| `1vector` | Make a vector out of the object on top of the data stack. This is how `next-approx` expects to take its input. | `3 V{ 3.141592653589793 }` |
| `over` | Put a copy of the object second from the top on top of the data stack. | `3 V{ 3.141592653589793 } 3` |
| `[ dup next-approx ]` | Push a quotation to the data stack for `times` to use later. | `3 V{ 3.141592653589793 } 3 [ dup next-approx ]` |
| `times` | Take an integer and a quotation and call the quotation that many times. In this case, equivalent to `dup next-approx dup next-approx dup next-approx` |  |
|  | Inside the quotation now... | `3 V{ 3.141592653589793 }` |
| `dup` | Copy the top data stack object | `3 V{ 3.141592653589793 } V{ 3.141592653589793 }` |
| `next-approx` | Add the next term in the continued fraction to our vector. `next-approx` has stack effect `( seq -- )` so we made a copy so we don't lose it | `3 V{ 3 7.062513305931052 }` |
| `dup next-approx` | Iteration 2 | `3 V{ 3 7 15.9965944066841 }` |
| `dup next-approx` | Iteration 3 | `3 V{ 3 7 15 1.003417231015 }` |
| `1 head*` | Remove last element | `3 V{ 3 7 15 }` |
| `Π` | Take the product | `3 315` |
| `abs` | Take the absolute value | `3 315` |
| `nth-root` | Take the nth root of a number. In this case, take the cube root of 315 | `6.804092115953367` |
> 4 votes

# Answer
# Mathematica, 42 38 bytes

```
N@1##&@@ContinuedFraction[#2,#]^(1/#)&

```

Corrected formatting and size reduced by @theorist.

Inputting n=100 and variable as Pi we get the output as

```
2.69405

```

You can save 2 bytes by removing N@ but this will give an exact expression and not numeric.

The code also passes all the tests giving the exact value for each number except for -Pi for which it returns a complex number. However the magnitude of this complex number is exactly the same as that given in the expected value.
> 3 votes

# Answer
# JavaScript (ES7), 47 bytes

Expects `(n)(real)`.

```
n=>v=>(g=n=>n?~~v*g(n-1,v=1/(v%1)):1)(n)**(1/n)

```

Try it online!

Note: With 40+ terms, the last test case will diverge from 1 because of cumulated floating point errors.
> 2 votes

# Answer
# Ruby, 57 bytes

```
->n,l,r=1{n=n.abs;l.times{r*=n.to_i**(1.0/l);n=1/n%=1};r}

```

Try it online!
> 1 votes

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


title: Combinator quines

text:
# Question
Title: Combinator quines
# Background

You have just learned what combinatory logic is. Intrigued by the various combinators you spend quite a bit of time learning about them. You finally stumble upon this particular expression:

```
(S I I (S I I))

```

You notice that when trying to reduce it to its normal form, it reduces to itself after three steps:

```
(S I I (S I I))
= (I (S I I) (I (S I I)))  (1)
= (S I I (I (S I I)))      (2)
= (S I I (S I I))          (3)

```

You are determined to find other expressions which share this trait and begin to work on this immediately.

# Rules

* You may use any combination of the following combinators:

```
B f g x = f (g x)
C f x y = f y x
I x     = x
K x y   = x
S f g x = f x (g x)
W f x   = f x x

```
* Application is left associative, which means that `(S K K)` is actually `((S K) K)`.
* A reduction is **minimal** there is no other order of reduction steps which uses fewer steps. Example: if `x` has reduction `y`, then the correct minimal reduction of `(W f x)` is:

```
(W f x)
= (W f y) (1)
= f y y   (2)

```

and not

```
(W f x)
= f x x   (1)
= f y x   (2)
= f y y   (3)

```
* Standard loopholes apply.

# Task

We define the **cycle** of an expression to be the minimal number of reductions in between two same expressions.

Your task is to find the expression, with the number of combinators used \< 100, which produces the longest cycle.

# Scoring

Your score will be determined by the length of the cycle of your expression. If two people's expression have the same cycle, the answer which uses fewer combinators wins. If they both use the same number of combinators, the earlier answer wins.

Good luck and have fun!

# Answer
> 7 votes
Gotta start with something

```
1:(((C (C I) (W I)) (C (C I) (W I)) I I) (W I) (W (C I) (W (C I)) (W (C I))) ((I (W I)) (W I) (W I) I))

2:(((C I (C (C I) (W I))) (W I) I I) (W I) ((C I) (W (C I)) (W (C I)) (W (C I))) ((W I) (W I) (W I) I))

3:(((I (W I)) (C (C I) (W I)) I I) (W I) (I (W (C I)) (W (C I)) (W (C I))) ((I (W I)) (W I) (W I) I))

4:(((W I) (C (C I) (W I)) I I) (W I) (W (C I) (W (C I)) (W (C I))) ((W I) (W I) (W I) I))

5:(((I (C (C I) (W I))) (C (C I) (W I)) I I) (W I) ((C I) (W (C I)) (W (C I)) (W (C I))) ((I (W I)) (W I) (W I) I))

6:(((C (C I) (W I)) (C (C I) (W I)) I I) (W I) (I (W (C I)) (W (C I)) (W (C I))) ((W I) (W I) (W I) I))

7:(((C I (C (C I) (W I))) (W I) I I) (W I) (W (C I) (W (C I)) (W (C I))) ((I (W I)) (W I) (W I) I))

8:(((I (W I)) (C (C I) (W I)) I I) (W I) ((C I) (W (C I)) (W (C I)) (W (C I))) ((W I) (W I) (W I) I))

9:(((W I) (C (C I) (W I)) I I) (W I) (I (W (C I)) (W (C I)) (W (C I))) ((I (W I)) (W I) (W I) I))

10:(((I (C (C I) (W I))) (C (C I) (W I)) I I) (W I) (W (C I) (W (C I)) (W (C I))) ((W I) (W I) (W I) I))

11:(((C (C I) (W I)) (C (C I) (W I)) I I) (W I) ((C I) (W (C I)) (W (C I)) (W (C I))) ((I (W I)) (W I) (W I) I))

12:(((C I (C (C I) (W I))) (W I) I I) (W I) (I (W (C I)) (W (C I)) (W (C I))) ((W I) (W I) (W I) I))

13:(((I (W I)) (C (C I) (W I)) I I) (W I) (W (C I) (W (C I)) (W (C I))) ((I (W I)) (W I) (W I) I))

14:(((W I) (C (C I) (W I)) I I) (W I) ((C I) (W (C I)) (W (C I)) (W (C I))) ((W I) (W I) (W I) I))

15:(((I (C (C I) (W I))) (C (C I) (W I)) I I) (W I) (I (W (C I)) (W (C I)) (W (C I))) ((I (W I)) (W I) (W I) I))

16:(((C (C I) (W I)) (C (C I) (W I)) I I) (W I) (W (C I) (W (C I)) (W (C I))) ((W I) (W I) (W I) I))

17:(((C I (C (C I) (W I))) (W I) I I) (W I) ((C I) (W (C I)) (W (C I)) (W (C I))) ((I (W I)) (W I) (W I) I))

18:(((I (W I)) (C (C I) (W I)) I I) (W I) (I (W (C I)) (W (C I)) (W (C I))) ((W I) (W I) (W I) I))

19:(((W I) (C (C I) (W I)) I I) (W I) (W (C I) (W (C I)) (W (C I))) ((I (W I)) (W I) (W I) I))

20:(((I (C (C I) (W I))) (C (C I) (W I)) I I) (W I) ((C I) (W (C I)) (W (C I)) (W (C I))) ((W I) (W I) (W I) I))

21:(((C (C I) (W I)) (C (C I) (W I)) I I) (W I) (I (W (C I)) (W (C I)) (W (C I))) ((I (W I)) (W I) (W I) I))

22:(((C I (C (C I) (W I))) (W I) I I) (W I) (W (C I) (W (C I)) (W (C I))) ((W I) (W I) (W I) I))

23:(((I (W I)) (C (C I) (W I)) I I) (W I) ((C I) (W (C I)) (W (C I)) (W (C I))) ((I (W I)) (W I) (W I) I))

24:(((W I) (C (C I) (W I)) I I) (W I) (I (W (C I)) (W (C I)) (W (C I))) ((W I) (W I) (W I) I))

25:(((I (C (C I) (W I))) (C (C I) (W I)) I I) (W I) (W (C I) (W (C I)) (W (C I))) ((I (W I)) (W I) (W I) I))

26:(((C (C I) (W I)) (C (C I) (W I)) I I) (W I) ((C I) (W (C I)) (W (C I)) (W (C I))) ((W I) (W I) (W I) I))

27:(((C I (C (C I) (W I))) (W I) I I) (W I) (I (W (C I)) (W (C I)) (W (C I))) ((I (W I)) (W I) (W I) I))

28:(((I (W I)) (C (C I) (W I)) I I) (W I) (W (C I) (W (C I)) (W (C I))) ((W I) (W I) (W I) I))

29:(((W I) (C (C I) (W I)) I I) (W I) ((C I) (W (C I)) (W (C I)) (W (C I))) ((I (W I)) (W I) (W I) I))

30:(((I (C (C I) (W I))) (C (C I) (W I)) I I) (W I) (I (W (C I)) (W (C I)) (W (C I))) ((W I) (W I) (W I) I))

31:(((C (C I) (W I)) (C (C I) (W I)) I I) (W I) (W (C I) (W (C I)) (W (C I))) ((I (W I)) (W I) (W I) I))

```

# Answer
> 8 votes
# Cycle: \\$f\_{\omega^{\omega^{\omega^{\omega^\omega}}}}(65536)\\$, combinators: 98

```
W (B (S I)) (W (B (S I))) (C (C (S (C I W) (C (C (C I K))))) (C (C (C (C (C (C (S (B (S (B (S (B (S (B (S (B (B (B (B (B (B (B W)))))) (B (B (B (B (B C)))))) (B (B (B (B (B W)))))) (B (B (B (B C))))) (B (B (B (B W))))) (B (B (B C)))) (B (B (B W)))) (B (B C))) (B (B W))) (B C)) (B W))) (C I))) (S B))) (C (C (C (C (W B) (W B)) (W B))) (W B))))

```

This expression is similar to `Y I`, that has this reduction:

```
0:  Y I
1:  I (Y I)
2:  Y I

```

After the first reduction there were two possible reductions: `I (Y I) -> Y I` and `I (Y I) -> I (I (Y I))`. This is not a problem since the second will clearly take longer to finish.

We will replace the `I` with `j`, `j` does the same thing `I` does, but it needs `n` reductions. `n` is an arbitrarily large Church numeral that cannot be reduced without an argument.

```
j = C (C (S (C I W) (C (C (C I K))))) n
y = Y j      <- This is just to make it easier to read later.

```

To make sure that there is no reduction of `y` that takes less than `n` steps, most of the time there will be only one possible reduction.

Imagine we have an expression `a b` that can be reduced to `c`, we can change it to `C (C a) b`. This new expression cannot be reduced, but if we give it another argument it can:

```
C (C a) b d
C a d b
a b d
c d

```

This way we can lock an expression to be reduced later. This can be seen in `j`, it can only be reduced with an argument.

In these first reductions only the leftmost combinator can be reduced.

```
0:  Y (C (C (S (C I W) (C (C (C I K))))) n)
1:  C (C (S (C I W) (C (C (C I K))))) n y    <- From now on y can always be reduced,
2:  C (S (C I W) (C (C (C I K)))) y n           but as we have seen before this makes
3:  S (C I W) (C (C (C I K))) n y               the cycle longer, so we can imagine
4:  C I W n (C (C (C I K)) n) y                 it cannot be reduced.
5:  I n W (C (C (C I K)) n) y
6:  n W (C (C (C I K)) n) y

```

Now n received an argument, it can be reduced and it is the only possible reduction.

For now let's reduce `n` completely before reducing anything else.

```
?:  W (W (W (...(W (W  (C (C (C I K)) n)  ))...))) y
    ^  ^  ^  ^^^ ^  ^   there are n 'W's here

```

`C (C (C I K)) n` needs an argument and each `W` needs two, so the first `W` is the only reduction allowed.

```
?:  W (W (W (...(W (W (C (C (C I K)) n)))...))) y
?:  W (W (...(W (W (C (C (C I K)) n)))...)) y y
?:  W (...(W (W (C (C (C I K)) n)))...) y y y
?:  ...(W (W (C (C (C I K)) n)))... y y y y
    ...
?:  W (W (C (C (C I K)) n)) y ... y y y
?:  W (C (C (C I K)) n) y y ... y y y
?:  C (C (C I K)) n y y y ... y y y        <- Let's call this line L
                      ^ ^ ^^^ ^ ^ ^  there are n 'y's after the first 'y'

```

Now `C (C (C I K)) n` has an argument, the only way this can happen is if `n` has been fully reduced and there are no `W`s left. Here we assume `n` has not been designed to avoid line `L`, when defining `n` later I will show how this can be done.

After reduction 6 we reduced `n` completely, this was not necessary, the only other thing we could reduce besides `n` was the `W`s. It doesn't matter what order we reduce it, it will always eventually reach line `L`. When `n` is reduced it makes `n` copies of `W`, this can be done in many ways and maybe even in less than `n` reductions, but the `W`s make `n` copies of `y` one by one, this takes `n` reductions independently of when it happens or if the `W`s were copied efficiently. From line 6 to line `L` the reductions can be made in many possible orders, but it will take at least `n` reductions to make all the copies of `y`.

Continuing from line `L`:

```
>n  :   C (C (C I K)) n y y y ... y y y
>n+1:   C (C I K) y n y y ... y y y
>n+2:   C I K n y y y ... y y y
>n+3:   I n K y y y ... y y y
>n+4:   n K y y y ... y y y

```

The only thing we can do now is reduce the `n` and the `K`s. For the same reason as before this also takes at least `n` reductions.

Each one of the `n` `K`s deletes one of the `(n+1)` `y`s, resulting in just one `y`. Reducing `n` completely before reducing the `K`s would look like this:

```
>n+5:       K (K (K (...(K (K y))...))) y y y ... y y
>n+6:       K (K (...(K (K y))...)) y y ... y y
>n+7:       K (...(K (K y))...) y ... y y
            ...
>2n-2:      K (K y) y y
>2n-1:      K y y
>2n  :      y

```

Here is one complete example of this with `n = 3 = S B (W B)`, which should take more than 6 reductions:

`^` represents the possible reductions and `(^)` represents the reduction that will be done. If there is more than one option, one of them will be chosen at random.

```
0:  Y (C (C (S (C I W) (C (C (C I K))))) (S B (W B)))
   (^)
1:  C (C (S (C I W) (C (C (C I K))))) (S B (W B)) y
   (^)
2:  C (S (C I W) (C (C (C I K)))) y (S B (W B))
   (^)
3:  S (C I W) (C (C (C I K))) (S B (W B)) y
   (^)
4:  C I W (S B (W B)) (C (C (C I K)) (S B (W B))) y
   (^)
5:  I (S B (W B)) W (C (C (C I K)) (S B (W B))) y
   (^)
6:  S B (W B) W (C (C (C I K)) (S B (W B))) y       <- beginning of the reduction of n
   (^)
7:  B W (W B W) (C (C (C I K)) (S B (W B))) y
    ^   (^)
8:  B W (B W W) (C (C (C I K)) (S B (W B))) y
   (^)
9:  W (B W W (C (C (C I K)) (S B (W B)))) y
   (^) ^
10: B W W (C (C (C I K)) (S B (W B))) y y           <- 1st copy of y
   (^)
11: W (W (C (C (C I K)) (S B (W B)))) y y           <- end of the reduction of n
   (^)
12: W (C (C (C I K)) (S B (W B))) y y y             <- 2nd copy of y
   (^)
13: C (C (C I K)) (S B (W B)) y y y y               <- 3rd copy of y
   (^)
14: C (C I K) y (S B (W B)) y y y
   (^)
15: C I K (S B (W B)) y y y y
   (^)
16: I (S B (W B)) K y y y y
   (^)
17: S B (W B) K y y y y                             <- beginning of the second reduction of n
   (^)
18: B K (W B K) y y y y
   (^)   ^
19: K (W B K y) y y y
    ^ (^)
20: K (B K K y) y y y
   (^) ^
21: B K K y y y                                     <- 1st y deleted
   (^)
22: K (K y) y y                                     <- end of the second reduction of n
   (^)
23: K y y                                           <- 2nd y deleted
   (^)
24: y                                               <- 3rd y deleted

```

We can see that indeed it took more than 6 reductions.

`Y` is not allowed in this challenge, but we can replace it with `W (B (S I)) (W (B (S I)))`:

```
0:  W (B (S I)) (W (B (S I))) j
1:  B (S I) (W (B (S I))) (W (B (S I))) j
2:  S I (W (B (S I)) (W (B (S I)))) j        <- Here we don't reduce the W for the
3:  I j (W (B (S I)) (W (B (S I))) j)           same reason we don't reduce Y twice
4:  j (W (B (S I)) (W (B (S I))) j)             before the end of the cycle.
5:  W (B (S I)) (W (B (S I))) j

```

Now we just need to choose some `n` to put in the expression:

```
W (B (S I)) (W (B (S I))) (C (C (S (C I W) (C (C (C I K))))) n)

```

Using this strategy we can guarantee that for a number `n` this expression will need at least `2n` reductions, but `n` has three restrictions:

* `n` must need an argument to be reduced
* `n` must have 80 combinators or less (so far we used 19 of the 99)
* `n` must not avoid line `L`

`n` could be designed to avoid line `L`:

```
n = 1 = C B (B I)
C B (B I) W (C (C (C I K)) n) y
B W (B I) (C (C (C I K)) n) y
W (B I (C (C (C I K)) n)) y
B I (C (C (C I K)) n) y y
I (C (C (C I K)) n y) y

```

In the last line if we reduce the `I` it becomes line `L`, but we can also reduce `C (C (C I K)) n y`. The way we will define `n` avoids this because we will add 1 many times to a number that doesn't skip line `L`. It would have been harder to find a definition that does run into this problem, almost anything we can do is naturally forced to reach line `L`.

Let `[a]` be a function that represents \\$f\_a\\$ in the fast-growing hierarchy. We will also need some other functions that will be implemented later, here are their definitions:

```
d1 f x       = x f x
d2 f g x     = x f g x
d3 f g h x   = x f g h x
d4 f g h i x = x f g h i x
...

```

By definition, applying `[a]` `x` times to `x` is equivalent to `[a+1] x`:

```
x [a] x = d1 [a] x = [a+1] x

```

Applying `d1` to `[a]` increases `a` by 1, doing this `x` times gives:

```
x d1 [a] x = d2 d1 [a] x = [a+x] x = [a+w] x

```

Now that we can add \\$\omega\\$, we can do this `x` times:

```
x (d2 d1) [a] x = d2 (d2 d1) [a] x = [a+wx] x = [a+w^2] x

```

Here we have a pattern:

```
d1 [a] x              = [a+1  ] x
d2 d1 [a]             = [a+w  ] x
d2 (d2 d1) [a] x      = [a+w^2] x  <- we stopped here
d2 (d2 (d2 d1)) [a] x = [a+w^3] x
...
k  d2 d1 [a] x        = [a+w^k] x
d3 d2 d1 [a] x        = [a+w^w] x

```

And here another:

```
d1 [a] x                = [a+1] x
d2 d1 [a] x             = [a+w] x
d3 d2 d1 [a] x          = [a+w^w] x     <- we stopped here
d4 d3 d2 d1 [a] x       = [a+w^w^w] x
d5 d4 d3 d2 d1 [a] x    = [a+w^w^w^w] x
d6 d5 d4 d3 d2 d1 [a] x = [a+w^w^w^w^w] x

```

I won't prove these patterns are correct, it would take many lines and would be very repetitive, this is left as an exercise to the reader.

We will use that last function, with `[a] = [0] = S B`.

These are the definitions of the `d`s:

```
d1 =                                                                                B W (C I)
d2 =                                                                             B (B W) (B C (C I))
d3 =                                                                B (B (B W)) (B (B C) (B C (C I)))
d4 =                                               B (B (B (B W))) (B (B (B C)) (B (B C) (B C (C I))))
d5 =                          B (B (B (B (B W)))) (B (B (B (B C))) (B (B (B C)) (B (B C) (B C (C I)))))
d6 = B (B (B (B (B (B W))))) (B (B (B (B (B C)))) (B (B (B (B C))) (B (B (B C)) (B (B C) (B C (C I))))))

```

Each function uses part of the previous, this can be used to reduce the number of combinators to this expression:

```
S (B (S (B (S (B (S (B (S (B (B (B (B (B (B (B W)))))) (B (B (B (B (B C)))))) (B (B (B (B (B W)))))) (B (B (B (B C))))) (B (B (B (B W))))) (B (B (B C)))) (B (B (B W)))) (B (B C))) (B (B W))) (B C)) (B W) (C I) (S B) x

```

This expression is reducible, we can use the `C (C a) b` trick to solve this problem:

```
C (C (C (C (C (C (S (B (S (B (S (B (S (B (S (B (B (B (B (B (B (B W)))))) (B (B (B (B (B C)))))) (B (B (B (B (B W)))))) (B (B (B (B C))))) (B (B (B (B W))))) (B (B (B C)))) (B (B (B W)))) (B (B C))) (B (B W))) (B C)) (B W))) (C I))) (S B))) x

```

The only thing missing is the input, we can use 13 combinators to reach some big number that cannot be reduced without an argument.

The largest number I found was 65536 using 12 combinators:

```
C (C (C (C (W B) (W B)) (W B))) (W B)

```

Putting everything together gives an expression with 98 combinators and a cycle of at least \\$2 f\_{\omega^{\omega^{\omega^{\omega^\omega}}}}(65536)\\$ reductions.

```
W (B (S I)) (W (B (S I))) (C (C (S (C I W) (C (C (C I K))))) (C (C (C (C (C (C (S (B (S (B (S (B (S (B (S (B (B (B (B (B (B (B W)))))) (B (B (B (B (B C)))))) (B (B (B (B (B W)))))) (B (B (B (B C))))) (B (B (B (B W))))) (B (B (B C)))) (B (B (B W)))) (B (B C))) (B (B W))) (B C)) (B W))) (C I))) (S B))) (C (C (C (C (W B) (W B)) (W B))) (W B))))
'-----------.-----------'                                     '----------------------------------------------------------------------------------------------------------------------.----------------------------------------------------------------------------------------------------------------------'  '-----------------.-----------------'
            Y                                                                                f_w^w^w^w^w                                                                                65536
                           '------------------------------------------------------------------------------------------------------------------------------------------------------------.------------------------------------------------------------------------------------------------------------------------------------------------------------'
                                                                                j

```

---
Tags: code-challenge, quine, busy-beaver, combinatory-logic
---


title: Greedy queens sequence

text:
# Question
Title: Greedy queens sequence
### Challenge

Implement the "greedy queens" sequence (OEIS: A065188).

### Details

*Taken from the OEIS page.*

This permutation \[of natural numbers\] is produced by a simple greedy algorithm: starting from the top left corner, walk along each successive antidiagonal of an infinite chessboard and place a queen in the first available position where it is not threatened by any of the existing queens. In other words, this permutation satisfies the condition that \\$p(i+d) \neq p(i) \pm d\\$ for all \\$i\\$ and \\$d \geq 1\\$.

\\$p(n) = k\\$ means that a queen appears in column \\$n\\$ in row \\$k\\$.

**Visualisation**

```
+------------------------
| Q x x x x x x x x x ...
| x x x Q x x x x x x ...
| x Q x x x x x x x x ...
| x x x x Q x x x x x ...
| x x Q x x x x x x x ...
| x x x x x x x x x Q ...
| x x x x x x x x x x ...
| x x x x x x x x x x ...
| x x x x x Q x x x x ...
| ...

```

### Rules

Standard rules apply, so you can:

* Take an index \\$n\\$ and output the \\$n^{th}\\$ term, either 0 or 1 indexing.
* Take a positive integer \\$n\\$ and output the first \\$n\\$ terms.
* Output whole sequence as an infinite list.

This is , so shortest answer (per language) wins!

### Test cases

First `70` terms:

```
1, 3, 5, 2, 4, 9, 11, 13, 15, 6, 8, 19, 7, 22, 10, 25, 27, 29, 31, 12, 14, 35, 37, 39, 41, 16, 18, 45, 17, 48, 20, 51, 53, 21, 56, 58, 60, 23, 63, 24, 66, 28, 26, 70, 72, 74, 76, 78, 30, 32, 82, 84, 86, 33, 89, 34, 92, 38, 36, 96, 98, 100, 102, 40, 105, 107, 42, 110, 43, 113

```

(See also: https://oeis.org/A065188/b065188.txt)

# Answer
# APL (Dyalog Unicode), 38 bytes

```
1+{⍵,⊃⍸|⊃×/×(⌽⍳≢⍵)(⊢×+×-)⍵-⊂⍳3×≢⍵}⍣⎕⊢⍬

```

Try it online!

Kinda port of tsh's JS and Python answers. They actually need some explanation of *why* it works, rather than *how*.

Instead of going through antidiagonals, this solution simply goes through the columns and places a queen on the smallest available row number (testing up to `3×(current column number-1)`).

### Why it works

The first question is why generating by column works.

**Claim:** If the \\$n\\$-th column has its queen on the \\$k\\$-th row by generating by antidiagonals, it does so by generating by columns.

**Proof:** The premise means that all cells at \\$(x,y)\\$ (column, row) where \\$x+y \< n+k\\$ or \\$x+y = n+k \\;\wedge\\; x \< n \\$ are either occupied by a queen or attacked by an existing queen. Then, any queen placed up to the \\$n-1\\$-th column cannot attack \\$(n,k)\\$ since \\$(n,k)\\$ is strictly above the rightward attack vector of all available cells up to \\$n-1\\$-th column. Therefore, \\$(n,k)\\$ is guaranteed to be available when \\$n-1\\$ columns are filled, and therefore a queen is placed at that precise position. \\${\blacksquare}\\$

Now, let's dig into the magic formula `(u-=v)**3-u*m*m` in the JS answer. The entire `a.every(...)` part can be ungolfed into `a.every((u,i)=>(u-v)*(u-v+n-1-i)*(u-v-n+1+i))`. `1+i` part is induced by 0-indexing of JS, so let's adapt it to 1-indexing instead.

**Claim:** Given the current sequence \\$a=(a\_1,a\_2,\cdots,a\_{n-1})\\$, \\$a\_n\\$ is determined as the smallest integer \\$k\\$ that satisfies \\$\forall i, (a\_i-k)(a\_i-k+n-i)(a\_i-k-n+i) \ne 0\\$, i.e. \\$(a\_i-k)^3 - (a\_i-k)(n-i)^2 \ne 0\\$.

**Proof:** Since the column numbers are all distinct, it suffices to check the horizontal and two diagonal directions. The queen to place is at \\$(n,k)\\$ (again, column then row) and the queens already placed are at \\$(i, a\_i)\\$.

* Horizontal: row numbers should be distinct. \\$a\_i \ne k\\$; \\$a\_i - k \ne 0\\$
* Main diagonal: the difference between the row and column should be distinct. \\$a\_i-i \ne k-n\\$; \\$a\_i-k+n-i \ne 0\\$
* Antidiagonal: the sum of the row and column should be distinct. \\$a\_i+i \ne k+n\\$; \\$a\_i-k-n+i \ne 0\\$

Take the product of the three to get the inequality we want. \\${\blacksquare}\\$

Finally, I'm using `3(n-1)` as the search limit, instead of searching towards infinity. That is simply because each queen in the previous columns can attack at most 3 cells on the current column, and there are only `n-1` queens placed so far, and `(1,1)` can attack at most two. So at most `3n-3-1` cells can be attacked in total.

### The code

```
1+{⍵,⊃⍸|⊃×/×(⌽⍳≢⍵)(⊢×+×-)⍵-⊂⍳3×≢⍵}⍣⎕⊢⍬
1+{...}⍣⎕⊢⍬    Given input n, generate n terms
               (1+ is to compensate the first term being 0
                which is the result for empty list)
⍳3×≢⍵    Candidate row numbers
⍵-⊂      a_i - k
(⌽⍳≢⍵)   n - i
(⊢×+×-)  (a_i-k) × ((a_i-k) + (n-i)) × ((a_i-k) - (n-i))
|⊃×/×    Test for each row number that all values are nonzero
⍵,⊃⍸     Take the first nonzero index and append to ⍵

```
> 13 votes

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

```
f=n=>a=n?[...f(--n),(g=v=>a.every(u=>(u-=v)**3-u*m*m--,m=n)?v:g(v+1))(1)]:[]

```

Try it online!
> 9 votes

# Answer
# Jelly, 19 bytes

```
Ṁ×3Rḟḟ+;_ɗJ$Ṃ;
1Ç¡Ḣ

```

Try it online!

A full program taking a zero-indexed n as the argument and printing the relevant term.

Here’s the first twenty terms with a slightly modified pair of links that can be passed an argument from within (rather than always using the command line argument).

## Explanation

### Helper link - extend sequence z

```
Ṁ              | Max
 ×3            | Times 3
   R           | Range (1..this)
    ḟ          | Filter out existing sequence members z
     ḟ     $   | Filter out values guven by the following applied to the current sequence:
      +;_ɗJ    | - z plus indices of z concatenated to z minus indicies of z
            Ṃ  | Min
             ; | Concatenate existing sequence z

```

### Main link

```
1Ç¡  | Starting with 1, call the helper link the number of times indicated by the argument
   Ḣ | Head

```
> 6 votes

# Answer
# JavaScript (ES6),  ~~58~~  55 bytes

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

```
f=(n,x=0,y=1)=>n-x?f(n,++x*x/(d=y-f(n-x))^d?x:!++y,y):y

```

Try it online!

Because of the nested recursion, this is slow as hell for \\$n\>9\\$. We can speed it up drastically by adding a cache (66 bytes).

### How?

Given a candidate value \\$y\>0\\$ for a queen at column \\$x\>0\\$, we compute the difference \\$d\\$ between \\$y\\$ and each previous value in the sequence.

The way the sequence is built, the queens are already guaranteed to be on different columns. But we additionally want:

* \\$d\neq 0\\$, meaning that the queens are on different rows.
* \\$|d|\neq |x|\\$, meaning that the queens are not on the same diagonal or anti-diagonal.

The second condition can also be written as \\$d^2\neq x^2\\$. If \\$d\neq 0\\$, it can be further modified into \\$x^2/d\neq d\\$.

In the JS code, we actually use a XOR:

```
x * x / d ^ d

```

The decimal part of the division is lost in the process. This is fine because the integer part of \\$x^2/d\\$ is guaranteed to be different from \\$d\\$ whenever we have \\$x\neq d,\\:d\neq 0\\$.

If \\$d=0\\$, the above expression is `Infinity ^ 0`, which evaluates to \\$0\\$, forcing the solution to be rejected as expected. So we don't need to test \\$d=0\\$ explicitly and this works for all cases.

### Commented

```
f = (                // f is a recursive function taking:
  n,                 //   n = input
  x = 0,             //   x = counter to test the solution against
                     //       all previous terms
  y = 1              //   y = current solution for a(n)
) =>                 //
  n - x ?            // if x is not equal to n:
    f(               //   do a recursive call:
      n,             //     pass n unchanged
      ++x * x /      //     increment x
      ( d =          //     compute:
        y - f(n - x) //       d = y - f(n - x)
      ) ^ d ?        //     if int(x²/d) is not equal to int(d):
        x            //       leave x unchanged
      :              //     else:
        !++y,        //       increment y and reset x to 0
      y              //     pass y
    )                //   end of recursive call
  :                  // else:
    y                //   success: return y

```
> 5 votes

# Answer
# APL (Dyalog Unicode), 64 bytes

```
{a←⍬⋄⍵↑1+-/¨a[⍋⌽¨a]⊣{a,←1↑(⍸∘.≥⍨w)~a∘.+(¯1+⍳3 2)∘.×w←⍳3×⍵}¨⍳3×⍵}

```

Try it online!

tsh's arithmetic formula looks quite nice, I'll try to incorporate that in this answer later.

### How it works

In this code, each cell is labeled as `(antidiagonal number, horizontal coordinate)` so that the antidiagonals are generated and tested in a horizontal fashion (which suits well to APL primitives).

```
(1,1) (2,2) (3,3) (4,4)
(2,1) (3,2) (4,3)
(3,1) (4,2)
(4,1)
...to...
(1,1)
(2,1) (2,2)
(3,1) (3,2) (3,3)
(4,1) (4,2) (4,3) (4,4)

```

Then, instead of accumulating "until we have all coordinates for columns 1..n", it simply collects until 3n columns are available, and at k-th iteration, first 3k antidiagonals are tested for the new point to add to `a`.

In this new coordinate system, the Queen's attack vectors are signified with `(1,0)` (S), `(2,1)` (SE), `(1,1)` (E), and `(0,1)` (NE). NE is needed to prevent taking another coordinate from the same antidiagonal. I add `(0,0)` (staying still) and `(2,0)` (S twice) for the sake of golfiness, so that all the vectors are easily generated as `¯1+⍳3 2`.

When the accumulation ends, `a` is sorted by the column number, and row numbers are evaluated and the first n terms are extracted from that.
> 4 votes

# Answer
# Python 3, 68 bytes

```
f=lambda n,i=1:i*all(n-m!=abs(i-f(m))>0for m in range(n))or f(n,i+1)

```

Try it online!
> 4 votes

# Answer
# \>= 4.1, 68 bytes

```
\(n)Reduce(\(x,y)c(setdiff(1:(3*y),c(x,x+(a=seq(x)),x-a))[1],x),1:n)

```

Try it online!

A function taking an integer n and returning the sequence of the first n terms in reverse order.
> 3 votes

# Answer
# Perl 5, 103 bytes

```
$s{$i}=!grep{$t=$_;grep$s{$i-$_*$t},999..1001}1..$i++/1e3and say$r=$i%1e3and$i-=$r-1e3or redo for 1..$_

```

Try it online!
> 2 votes

# Answer
# Stax, 22 bytes

```
╙½#≡]☺è60S|f♣V♦i+é(ç░m

```

Run and debug it

Runs as an infinite loop producing output. It's very brute-force.
> 2 votes

# Answer
# Jelly, 17 bytes

```
+;_ɗJ;⁸1ḟ1#;
1Ç¡Ḣ

```

A full program that accepts a non-negative integer, \\$n\\$, and prints the sequence element at that (0-indexed) index.

**Try it online!**

### How?

Keeps the natural numbers (i.e. 1-indexed row indices) in a list (initially `[1]` (well, `1` but Jelly :D)) and repeatedly finds the first row in which a queen may be placed in the next column by counting up from 1 until a number is reached that is not on an any, thus far, occupied row, leading diagonal, or trailing diagonal.

```
+;_ɗJ;⁸1ḟ1#; - Link 1, prefix with next element: list (current elements in reverse), E
    J        - range of length -> [1,2,...,length(E)]
   ɗ         - last three links as a dyad - f(E, J(E)):
+            -   add (vectorises) -> occupied trailing diagonal row indices
  _          -   subtract (vectorises) -> occupied leading diagonal row indices
 ;           -   concatenate these together
     ;⁸      - concatenate E
       1 1#  - start with 1 and count up, collecting the first 1 that are truthy under:
        ḟ    -   filter discard -> singleton list containing the next available row index
           ; - concatenate E -> a new, slightly longer, list of elements in reverse

1Ç¡Ḣ - Main Link: non-negative integer, n (0-indexed)
1    - start with 1
 Ç¡  - repeat Link 1 n times
   Ḣ - head of the resulting list

```
> 2 votes

# Answer
# Charcoal, 30 bytes

```
ＦＮ«≔¹θＷ⊙υ№×Ｅ³⊖ν⁻ιμ⁻θλ≦⊕θ⊞υθ»Ｉυ

```

Try it online! Link is to verbose version of code. Outputs the first `n` terms. Explanation:

```
ＦＮ«

```

Loop `n` times.

```
≔¹θ

```

Start by trying to place the queen in the first row.

```
Ｗ⊙υ№×Ｅ³⊖ν⁻ιμ⁻θλ

```

For each previously placed queen, check whether its row offset equals its column offset multiplied by any one of `-1`, `0` and `1`.

```
≦⊕θ

```

If any queen is in the same row or diagonal then try the next row.

```
⊞υθ

```

Push the newly placed queen to the predefined empty list.

```
»Ｉυ

```

Print the list of queens.
> 2 votes

# Answer
# APL(Dyalog Unicode), ~~104~~ 70 bytes SBCS

```
{⊢/↑⍸⍉{1@(⊂⊃{⍵[⍋⊢/↑⍵]}⍸~⊃∨/(≢⍵)∘{⊃∘.(=∨0=×)/|⍵-⊂⍳⍺}¨⍸⍵)⊢⍵}⍣⍵⊢1↑⍨2/2×⍵}

```

Try it on APLgolf!

A dfn submission which takes the number of terms to output.

A bit ungolfed, most of the bytecount is finding the cancelled out squares.

Instead of going by antidiagonal, goes column by column and places greedily.

-34 bytes from dzaima.
> 1 votes

---
Tags: code-golf, sequence, chess
---