title: Exponent of complex numbers

text:
# Question
Title: Exponent of complex numbers
Given two integers, which may be negative, zero, or positive, \\$a\\$ and \\$b\\$ (taken in any reasonable format, **including inputting a plain complex number**), convert it to \\$a + bi\\$ where \\$i\\$ is the imaginary number (square root of negative one). Then, raise it to the power of a third (positive integer) input variable, \\$c\\$ as to \\$(a + bi)^c\\$. You should then end up with something like \\$d + ei\\$. You must then output, or return, \\$d\\$ and \\$e\\$ in any reasonable format (**including outputting a plain complex number**).

Input and output may be taken or outputted in any order.

Examples:

```
5, 2, 2 -> 21, 20
1, 4, 2 -> -15, 8
-5, 0, 1 -> -5, 0

```

# Answer
> 8 votes
# Mathematica, 17 bytes

```
ReIm[(#+#2I)^#3]&

```

Try it online!

-8 bytes from alephalpha

but........ rules have changed...... so

# Mathematica, 5 bytes

```
Power

```

# Answer
> 7 votes
# Python 3, 3 bytes

```
pow

```

Try it online!

Input and output as complex numbers.

---

# Python 3, 47 bytes

```
def f(a,b,c):n=(a+b*1j)**c;return n.real,n.imag

```

Try it online!

Input and output as integers

---

# Python 2, ~~62~~ 60 bytes

*-2 bytes thanks to @Leonhard*

```
a,b,c=input();d=1;e=0
exec'd,e=a*d-b*e,a*e+b*d;'*c
print d,e

```

Try it online!

does not use complex number type

# Answer
> 5 votes
# Javascript (ES6), ~~51~~ 50 bytes

```
a=>b=>g=c=>c?([x,y]=g(c-1),[x*a-b*y,a*y+b*x]):"10"

```
* Takes input in currying form: `f(a)(b)(c)`
* Returns the result as an array: `[d, e]`

**Explanation**

```
a=>b=>g=c=>               // Input in currying syntax
    c?(                   // If `c` != 0:
        [x,y]=g(c-1),     //     Set [x, y] to the result of f(a)(b)(c-1)
        [x*a-b*y,a*y+b*x] //     Return (a + bi) * (x + yi)
    ):                    // Else: (when c = 0)
        "10"              //     Return [1, 0] (to end the recursion)

```

```
f=a=>b=>g=c=>c?([x,y]=g(c-1),[x*a-b*y,a*y+b*x]):"10"
```

```
<div oninput="o.innerText=f(a.value)(b.value)(c.value)"><input id=a type=number value=0><input id=b type=number value=0><input id=c type=number value=1 min=1><pre id=o>
```

# Answer
> 4 votes
# Jelly, 1 byte

```
*

```

Try it online!

Thanks to Mr. Xcoder for alerting me of rule updates (-6 as a result).
Thanks to someone for alerting me of rule updates (-2 as a result).

First argument: `(a+bj)`
Second argument: `c`
Returns: `(d+ej)`

# Answer
> 4 votes
# Pari/GP, 36 bytes

```
f(a,b,c)=divrem((a+b*x)^c%(x^2+1),x)

```

Try it online!

---

# Pari/GP, 36 bytes

```
f(a,b,c)=[real(d=(a+b*I)^c),imag(d)]

```

Try it online!

# Answer
> 3 votes
# Actually, 1 byte

Try it online!

Note that the rules have changed and complex numbers are valid I/O types (unfortunately this turns the post into a "perform this exponentiation" challenge). Original answer below.

# Actually, 3 bytes

```
Çⁿ╫

```

Try it online!

Returns the values separated by a newline. Takes the inputs in reverse order and returns the results in reverse order (See the tio link).

```
Çⁿ╫  - Full program. Reversed inputs.

Ç    - Return a+bi.
 ⁿ   - Exponentiation.
  ╫  - Pushes the real and imaginary parts of a.

```

# Answer
> 3 votes
# , 3 bytes

This is becoming boring. If input and output is allowed as a complex number, there is a builtin for a power function.

```
`^`

```

For example:

```
> (5+2i)^2
[1] 21+20i
> (1+4i)^2
[1] -15+8i
> (-5+0i)^1
[1] -5+0i

```

or

```
> `^`(5+2i,2)
[1] 21+20i
> `^`(1+4i,2)
[1] -15+8i
> `^`(-5+0i,1)
[1] -5+0i

```

# Answer
> 2 votes
# Pyth, ~~5~~ ~~12~~ ~~5~~ 2 bytes

```
^E

```

Takes in `c` first, followed by `a+bj`.

~~7 bytes of boilerplate because apparently output as an imaginary number is disallowed.~~ It's been re-allowed! Hurrah! And with taking in a complex number being a reasonable input, we can cut out an additional 3 bytes!

Previous solutions:

```
^.jEE

```

When complex numbers were not reasonable inputs.

```
m,edsd]^.jEE

```

When complex numbers were not reasonable outputs.

Test Suite.

# Answer
> 2 votes
# 05AB1E, 1 byte

```
m

```

Try it online!

Input: `c\n(a+bj)`
Output: `(d+ej)`

# Answer
> 2 votes
# C# (.NET Core), ~~62~~ 38 bytes

```
a=>c=>System.Numerics.Complex.Pow(a,c)

```

Try it online!

# Answer
> 2 votes
# 05AB1E, ~~20~~ ~~19~~ ~~17~~ 16 bytes

```
‚UTSsFXâP`(‚RŠ‚+

```

Try it online! Takes three separate inputs in the order `b, a, c` and outputs an array `[d, e]`. Edit: Saved 2 bytes thanks to @Datboi. Saved 1 byte thanks to @Adnan. Explanation:

```
‚                   Join a and b into a pair
 U                  Store in variable X
  T                 Push 10 to the stack
   S                Split into the pair [d, e] = [1, 0]
    s               Swap with c
     F              Repeat the rest of the program c times
      X             Get [a, b]
       â            Cartesian product with [d, e]
        P           Multiply each pair together [da, db, ea, eb]
         `          Push each product as a separate stack entry
          (         Negate eb
           ‚        Join with ea into a pair [ea, -eb]
            R       Reverse the pair [-eb, ea]
             Š      Push under da and db
              ‚     Join them into a pair [da, db]
               +    Add the two pairs [da-eb, db+ea]

```

# Answer
> 2 votes
# TI-BASIC, ~~25~~ ~~22~~ 8 bytes

Takes the complex number and the exponent as input, and stores output in `Ans` as a complex number. Drastic drop in bytes due to loosened restrictions on input/output.

```
Prompt C,E
C^E

```

# Answer
> 2 votes
# J, ~~10~~, ~~7~~, 1 byte~~s~~

```
^

```

Takes `c` as the right argument and the complex number `ajb` (how you represent `a + bi` in J) as the left argument.

Try it online!

## Other Solutions

### 7 bytes

Takes the complex number input as a list.

```
^~j./@]

```

### 10 bytes

This outputted the `a + bi` in the list `a b`.

```
+.@^~j./@]

```

I wanted to try something cute like `^~&.(j./)` but the inverse of `j./` is obviously not defined. Actually, `^~&.(+.inv)` works and you can make that `^&.(+.inv)` which is also 10 bytes if you reverse the order in which you take the args.

# Answer
> 2 votes
# 6502 machine code subroutine, 199 187 185 bytes

```
A2 03 B5 FB 95 26 CA 10 F9 88 D0 01 60 A5 26 85 61 A5 27 85 62 A5 FB 85 63 A5
FC 85 64 A9 20 85 6F D0 36 18 A5 6D 65 65 85 28 A5 6E 65 66 85 29 A5 4B 85 26
A5 4C 85 27 50 CF 38 A5 6D E5 65 85 4B A5 6E E5 66 85 4C A5 28 85 61 A5 29 85
62 A5 FB 85 63 A5 FC 85 64 06 6F A9 00 85 65 85 66 A2 10 46 62 66 61 90 0D A5
63 18 65 65 85 65 A5 64 65 66 85 66 06 63 26 64 CA 10 E6 A9 FF 24 6F 70 B9 30
02 F0 9E A5 65 85 6D A5 66 85 6E 24 6F 30 14 A5 28 85 61 A5 29 85 62 A5 FD 85
63 A5 FE 85 64 06 6F D0 B4 A5 26 85 61 A5 27 85 62 A5 FD 85 63 A5 FE 85 64 06
6F B0 A0

```
* *-12 bytes with improved "spaghetti" structure*
* *-2 bytes changing the register to pass the exponent, so we can make use of zeropage addressing mode in the initial copy loop*

This is position-independent code, just put it somewhere in RAM and call it with a `jsr` instruction.

The routine takes the (complex) base as two 16bit signed integers (2's complement, little-endian) in `$fb/$fc` (real) and `$fd/$fe` (imaginary), and the exponent as an unsigned 8bit integer in the `Y` register.

The result is returned in `$26/$27` (real) and `$28/$29` (imaginary).

---

### Explanation

This is still an interesting challenge on the 6502 CPU as there are no instructions for even multiplying. The approach is straight forward, implementing a complex multiplication and executing it as often as required by the exponent. Golfing is done by avoiding subroutines, instead creating kind of a "branch spaghetti", so the code for doing a simple 16bit multiplication that's needed multiple times is reused with the lowest possible overhead. Here's the commented disassembly:

```
 .cexp:
A2 03       LDX #$03            ; copy argument ...
 .copyloop:
B5 FB       LDA $FB,X
95 26       STA $26,X
CA          DEX
10 F9       BPL .copyloop       ; ... to result
 .exploop:
88          DEY                 ; decrement exponent
D0 01       BNE .mult           ; zero reached -> done
60          RTS
 .mult:                         ; multiply (complex) result by argument
A5 26       LDA $26             ; prepare to multiply real components
85 61       STA $61             ; (a*c)
A5 27       LDA $27
85 62       STA $62
A5 FB       LDA $FB
85 63       STA $63
A5 FC       LDA $FC
85 64       STA $64
A9 20       LDA #$20            ; marker for where to continue
85 6F       STA $6F
D0 36       BNE .mult16         ; branch to 16bit multiplication
 .mult5:
18          CLC                 ; calculate sum (a*d) + (b*c)
A5 6D       LDA $6D
65 65       ADC $65
85 28       STA $28             ; and store to imaginary component of result
A5 6E       LDA $6E
65 66       ADC $66
85 29       STA $29
A5 4B       LDA $4B             ; load temporary result (a*c) - (b*d)
85 26       STA $26             ; and store to real component of result
A5 4C       LDA $4C
85 27       STA $27
50 CF       BVC .exploop        ; next exponentiation step
 .mult3:
38          SEC                 ; calculate difference (a*c) - (b*d)
A5 6D       LDA $6D
E5 65       SBC $65
85 4B       STA $4B             ; and store to temporary location
A5 6E       LDA $6E
E5 66       SBC $66
85 4C       STA $4C
A5 28       LDA $28             ; prepare to multiply real component of result
85 61       STA $61             ; with imaginary component of argument
A5 29       LDA $29             ; (a*d)
85 62       STA $62
A5 FB       LDA $FB
85 63       STA $63
A5 FC       LDA $FC
85 64       STA $64
06 6F       ASL $6F             ; advance "continue marker"
 .mult16:
A9 00       LDA #$00            ; initialize 16bit multiplication
85 65       STA $65             ; result with 0
85 66       STA $66
A2 10       LDX #$10            ; bit counter (16)
 .m16_loop:
46 62       LSR $62             ; shift arg1 right
66 61       ROR $61
90 0D       BCC .m16_noadd      ; no carry -> nothing to add
A5 63       LDA $63             ; add arg2 ...
18          CLC
65 65       ADC $65
85 65       STA $65
A5 64       LDA $64
65 66       ADC $66
85 66       STA $66             ; ... to result
 .m16_noadd:
06 63       ASL $63             ; shift arg2 left
26 64       ROL $64
CA          DEX                 ; decrement number of bits to go
10 E6       BPL .m16_loop
A9 FF       LDA #$FF            ; check marker for where to continue
24 6F       BIT $6F
70 B9       BVS .mult3
30 02       BMI .saveres        ; have to save result to temp in 2 cases
F0 9E       BEQ .mult5
 .saveres:
A5 65       LDA $65             ; save result to temporary
85 6D       STA $6D
A5 66       LDA $66
85 6E       STA $6E
24 6F       BIT $6F             ; check "continue marker" again
30 14       BMI .mult4
 .mult2:
A5 28       LDA $28             ; prepare to multiply imaginary components
85 61       STA $61             ; (b*d)
A5 29       LDA $29
85 62       STA $62
A5 FD       LDA $FD
85 63       STA $63
A5 FE       LDA $FE
85 64       STA $64
06 6F       ASL $6F             ; advance "continue marker"
D0 B4       BNE .mult16         ; branch to 16bit multiplication
 .mult4:
A5 26       LDA $26             ; prepare to multiply imaginary component of
85 61       STA $61             ; result with real component of argument
A5 27       LDA $27             ; (b*c)
85 62       STA $62
A5 FD       LDA $FD
85 63       STA $63
A5 FE       LDA $FE
85 64       STA $64
06 6F       ASL $6F             ; advance "continue marker"
B0 A0       BCS .mult16         ; branch to 16bit multiplication

```

---

### Example program using it (C64, assembly source in ca65-syntax):

```
.import cexp

CEXP_A          = $fb
CEXP_AL         = $fb
CEXP_AH         = $fc
CEXP_B          = $fd
CEXP_BL         = $fd
CEXP_BH         = $fe

CEXP_RA         = $26
CEXP_RAL        = $26
CEXP_RAH        = $27
CEXP_RB         = $28
CEXP_RBL        = $28
CEXP_RBH        = $29

.segment "LDADDR"
                .word   $c000

.segment "MAIN"
                jsr     $aefd           ; consume comma
                jsr     $ad8a           ; evaluate number
                jsr     $b1aa           ; convert to 16bit int
                sty     CEXP_AL         ; store as first argument
                sta     CEXP_AH
                jsr     $aefd           ; ...
                jsr     $ad8a
                jsr     $b1aa
                sty     CEXP_BL         ; store as second argument
                sta     CEXP_BH
                jsr     $b79b           ; read 8bit unsigned into X
                txa                     ; and transfer
                tay                     ; to Y

                jsr     cexp            ; call our function

                lda     CEXP_RAH        ; read result (real part)
                ldy     CEXP_RAL
                jsr     numout          ; output
                ldx     CEXP_RBH        ; read result (imaginary part)
                bmi     noplus
                lda     #'+'            ; output a `+` if it's not negative
                jsr     $ffd2
noplus:         txa
                ldy     CEXP_RBL
                jsr     numout          ; output (imaginary part)
                lda     #'i'
                jsr     $ffd2           ; output `i`
                lda     #$0d            ; and newline
                jmp     $ffd2

numout:
                jsr     $b391           ; convert to floating point
                jsr     $bddd           ; format floating point as string
                ldy     #$01
numout_loop:    lda     $ff,y           ; output loop
                bne     numout_print    ; until 0 terminator found
                rts
numout_print:   cmp     #' '            ; skip space characters in output
                beq     numout_next
                jsr     $ffd2
numout_next:    iny
                bne     numout_loop

```

---

## Online demo

**Usage:** `sys49152,[a],[b],[c]`, e.g. `sys49152,5,2,2` (Output: `21+20i`)

# Answer
> 1 votes
# Casio-Basic, 6 bytes

```
a^b

```

Change to the rules to allow input and output as complex numbers made this significantly shorter.

3 bytes for the function, +3 to enter `a,b` in the parameters box.

# Answer
> 1 votes
# MATL, 1 byte

```
^

```

Inputs are `a+jb`, `c`.

**Try it online!**

## Old version: non-complex input and output, 8 bytes

```
J*+i^&Zj

```

Input order is `b`,`a`, `c`.

**Try it online!**

### Explanation

```
J           Push imaginary unit
 *          Multiply by implicit input b
  +         Add implicit input a
   i        Take input c
    ^       Power
     &Zj    Push real and imaginary parts. Implicitly display

```

# Answer
> 1 votes
# Dyalog APL, 10 bytes

```
⎕*⍨⊣+¯11○⊢

```

Try it online!

`a` is left argument, `b` is right argument, and `c` via input prompt.

Returns a complex number in the format `dJe`.

# Answer
> 1 votes
# C (gcc), 34 bytes

```
#define f(a,b,c)cpow((a)+1i*(b),c)

```

Try it online!

# Answer
> 0 votes
# Octave / MATLAB, 6 bytes

```
@power

```

Anonymous function that inputs two numbers and outputs their power.

**Try it online**!

## Old version: non-complex input and output, 30 bytes

```
@(a,b,c)real((a+j*b)^c./[1 j])

```

Anonymous function that inputs three numbers and outputs an array of two numbers.

**Try it online!**

# Answer
> 0 votes
# Perl 6,  ~~29 26 20 19~~  11 bytes

```
{$_=($^a+$^b*i)**$^c;.re,.im}

```

Try it

```
{(($^a+$^b*i)**$^c).reals}

```

Try it

```
((*+* *i)** *).reals

```

Try it

```
((*+* *i)***).reals

```

Try it

With the change of output restrictions it can be further reduced:

```
(*+* *i)***

```

Try it

The `***` part is parsed as `** *` because the `**` infix operator is longer than the `*` infix operator.

## Expanded:

```
#     __________________ 1st parameter
#    /   _______________ 2nd parameter
#   /   /         ______ 3rd parameter
#  /   /         /
# V   V         V
( * + * * i) ** *
#       ^    ^^
#        \     \________ exponentiation
#         \_____________ multiplication

```

# Answer
> 0 votes
# 8th, 38 bytes

**Code**

```
c:new dup >r ( r@ c:* ) rot n:1- times

```

**SED** (Stack Effect Diagram) is: `c a b -- (a + bi) ^ c`

*Warning*: `a + bi` is left on **r-stack**, but this doesn't affect subsequent computations.

**Ungolfed version with comments**

```
needs math/complex

: f \ c a b  -- (a + bi) ^ c
    c:new                      \ create a complex number from a and b
    dup                        \ duplicate a + bi
    >r                         \ store a + bi on r-stack
    ( r@ c:* ) rot n:1- times  \ raise ( a + bi ) to c
;

```

**Example and usage**

```
: app:main
    \ rdrop is not strictly required
    2 5 2 f . cr rdrop
    2 1 4 f . cr rdrop
    1 -5 0 f . cr rdrop
    bye
;

```

**Output of the previous code**

```
c:1:data:{"real":21,"imag":20}
c:1:data:{"real":-15,"imag":8}
c:2:data:{"real":-5,"imag":0}

```

# Answer
> 0 votes
# R, 25 bytes

simplest - since outputting complex is allowed.

```
function(a,b,c)(a+b*1i)^c

```

# Answer
> 0 votes
# Ruby, 9 bytes

Returns an anonymous function that takes a complex number and integer and returns a complex number.

```
proc &:**

```

This is equivalent to `->x,y{x**y}` (11 bytes).

Attempt This Online!

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


title: Implement the random Fibonacci sequence

text:
# Question
Title: Implement the random Fibonacci sequence
The random Fibonacci sequence is defined as follows:

$$ f\_n = \begin{cases} f\_{n-1}+f\_{n-2} \text{ with probability } 1/2 \\ f\_{n-1}-f\_{n-2} \text{ with probability } 1/2 \\ \end{cases} $$ $$ f\_1 = f\_2 = 1 $$

i.e. whether the next term is the sum or difference of the previous two is chosen at random, independently of previous terms. Your task is to implement this sequence.

Each random realization of the sequence must use consistent values. For example, if \\$f\_3 = 2\\$, \\$f\_4\\$ must then be either \\$2+1 = 3\\$ or \\$2-1 = 1\\$. This can be thought of as the sequence "remembering" previous values. This means that this example program is invalid, as previous values in the sequence are not maintained by later values. Furthermore, you should explain how your program meets the \\$1/2\\$ probability requirement.

As is standard for challenges, you can perform one of three tasks:

* Take a positive integer \\$n\\$ as input and output \\$f\_n\\$
* Take a positive integer \\$n\\$ as input and output \\$f\_1, f\_2, ..., f\_n\\$
* Output the sequence indefinitely with no end

Again, as is standard, you may use either \\$0\\$ or \\$1\\$ indexing, but the two initial values \\$f\_1 = f\_2 = 1\\$ must be used.

This is , so the shortest code, in bytes, wins.

## Examples

```
n -> possible values of f_n | probabilities of values
1 -> 1                      | 1
2 -> 1                      | 1
3 -> 2, 0                   | 1/2, 1/2
4 -> 3, 1, -1               | 1/4, 1/2, 1/4
5 -> 5, 3, 1, -1            | 1/8, 1/8, 3/8, 3/8
6 -> 8, 4, 2, 0, -2         | 1/16, 1/8, 1/4, 5/16, 1/4

```

# Answer
# 05AB1E, ~~8~~ 7 bytes

```
λ₂D(‚Ω+

```

-1 byte thanks to *@ovs*.

Prints the infinite sequence.

Try it online.

**Explanation:**

```
λ        # Create a recursive environment to output the infinite sequence,
         # implicitly starting at a(0)=1
         #  (push a(n-1) implicitly)
 ₂       #  Push a(n-2) (NOTE: all negative a(n) are 0, so a(-1)=0)
  D      #  Duplicate a(n-2)
   (     #  Negate the copy: -a(n-2)
    ‚    #  Pair them together: [a(n-2), -a(n-2)]
     Ω   #  Pop and push a random item
      +  #  And add it to the a(n-1)
         # (after which the infinite list is output implicitly)

```
> 12 votes

# Answer
# APL (Dyalog Unicode), 20 bytes

```
{⍵,(¯1*?2)⊥¯2↑⍵}/⎕⍴1

```

Try it online!

Takes n from stdin and prints first n terms.

```
{⍵,(¯1*?2)⊥¯2↑⍵}/⎕⍴1  ⍝ Full program. Input: n
{              }/⎕⍴1  ⍝ Reduce a vector of n ones...
           ¯2↑⍵  ⍝ Last two items ([0 1] for the first iteration)
   (¯1*?2)       ⍝ 1 or -1
          ⊥      ⍝ Base convert (or polynomial evaluate),
                 ⍝ giving f(x-2)+f(x-1) or -f(x-2)+f(x-1) with 50% chance each
 ⍵,              ⍝ Append to the previous iteration

```
> 8 votes

# Answer
# Japt, ~~14~~ ~~13~~ 11 bytes

Outputs the `n`th term, 1-indexed. Uses JavaScript's `Math.random()` as seen here.

```
@Zä+iÍö)Ì}g

```

Try it, check the first `n` terms or view the distributions across 10,000 runs

```
@Zä+iÍö)Ì}g     :Implicit input of integer U
@               :Function taking an array as argument via parameter Z
 Zä             :  Consecutive pairs of Z reduced by
   +            :    Literal "+"
    i           :    Insert
     Í          :      "n" at index 2 with wrapping, resulting in "n+"
                :      (Hooray for shortcut abuse!)
      ö         :    Random character from that string, where XnY=Y-X
       )        :  End reduction
        Ì       :  Get last element
         }      :End function
          g     :Starting with [0,1], repeatedly run it through that function,
                : pushing the result back to it each time
                :Implicit output of Uth element, 0-indexed

```

To explain how the shortcut abuse works here: `Í` is Japt's shortcut for `n2<space>` which is primarily intended to be used for converting binary strings to integers (e.g., `"1000"Í="1000"n2 =8`). However, when you pass a 2 character+space shortcut like that to another method - in this case `i` \- the space is used to close that method and the 2 characters are split & passed to that method as separate arguments. Which is handy here as the `i` method for strings expects one argument containing the string to be inserted and another, optional integer argument for the index it's to be inserted at.
> 7 votes

# Answer
# perl -061 -M5.010, 46 43 bytes

```
say$,while($,,$/)=($/,$/+$,-2*$,*(.5<rand))

```

Try it online!

This prints the infinite series.

Saved three bytes using a suggestion from Nahuel Fouilleul.

## How does it work?

First trick is the command line switch `-061`. This sets the input record to `1` (as the ASCII value of `1` is 49, aka 61 in octal). The input record separator is `$/`.

We then use two variables to keep state, `$,`, which initially is the empty string, but Perl will treat that as `0` when used as a number. `$/` is set to `1`, as discussed above. In an infinite loop, we set `$,` to `$/`, and `$/` to `$, + $/`, and then, with probability .5, subtract `2 * $,` from the latter. We then print `$,`.
> 6 votes

# Answer
# Jelly, 10 bytes

I'm pretty sure 10 is as good as it'll get in Jelly; I had some much longer solutions along the way.

```
1ṫ-ḅØ-XṭƲ¡

```

A monadic Link accepting an integer, which yields all values up to and including that 0-indexed index
(i.e. \\$n \to \[f\_0, f\_1,\cdots, f\_n\]\ |\ f\_0=f\_1=1 : f\_n = f\_{n-1} \pm f{n-2} \\$).

**Try it online!**

### How?

```
1ṫ-ḅØ-XṭƲ¡ - Link: integer, n
1          - set the left argument to 1
         ¡ - repeat this n times:
        Ʋ  -   last four links as a monad f(left):  e.g. left = [1,1,2,3,5,8]
 ṫ-        -     tail from 1-based, modular index -1            [5,8]
                 (tailing 1 from index -1 yields [1])
    Ø-     -     signs (a nilad)                                [-1,1]
   ḅ       -     convert from base (vectorises)                 [3,13]
                                        (i.e. [5×-1¹+8×-1°, 5×1¹+8×1°])
      X    -     random choice                                  3?
       ṭ   -     tack                                           [1,1,2,3,5,8,3]

```
> 6 votes

# Answer
# Wolfram Language (Mathematica), 45 bytes

Outputs f(n) using RandomInteger 0 or 1

```
#&@@Nest[+##|(-1)^Random@0[[0]]#&@@#&,0|1,#]&

```

Try it online!

*-6 bytes from @att*

I also tried this `46 bytes`

```
If[#>1,#0[#-1]+(-1)^RandomInteger[]#0[#-2],#]&

```

but the sequence could not "remember" the previous values
> 5 votes

# Answer
# Python 2, ~~66~~ 64 bytes

Outputs the sequence infinitely.

```
from random import*
a=b=1
while 1:print a;a,b=b,b+choice([-a,a])

```

Try it online!

### Python 2, 73 bytes

Outputs the nth term of the sequence.

```
from random import*
a,b=0,1
exec"a,b=b,b+choice([-a,a]);"*input()
print a

```

Try it online!
> 5 votes

# Answer
# JavaScript (ES6),  ~~68 67 66 53~~  52 bytes

*Saved 2 bytes thanks to @Shaggy*

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

```
f=(n,p=1,q=0)=>n?f(n-1,Math.random()<.5?p+q:p-q,p):p

```

Try it online!

### Commented

```
f = (                // f is a recursive function taking:
  n,                 //   n = 0-indexed input
  p = 1,             //   p = previous value
  q = 0              //   q = penultimate value
) =>                 //
  n ?                // if n is not equal to 0:
    f(               //   do a recursive call:
      n - 1,         //     decrement n
      Math.random()  //     set p to either:
      < 0.5 ? p + q  //       p + q
            : p - q, //       or p - q
      p              //     copy the previous value in q
    )                //   end of recursive call
  :                  // else:
    p                //   return the last value

```
> 4 votes

# Answer
# , ~~69~~ ... 55 bytes

-1 byte thanks to Giuseppe (which led to a further -4 bytes), and -1 byte thanks to Dominic van Essen (which led to a further -1 byte)

```
F=0:1;repeat cat(" ",{F=F[2]+F[1]*(0:-1)^sample(2)}[1])

```

Try it online!

Prints the sequence indefinitely, separated by spaces.

`F` is initialized as the vector `[1 1]`.

At each step, draw a random permutation of the vector `[1 2]` with `sample(2)`. This means that `(0:-1)^sample(2)` is either `[0^1 (-1)^2]=[0 1]` or `[0^2 (-1)^1]=[0 -1]` (with probability 1/2 each). In both cases, `F[1]` takes the previous value of `F[2]`, and depending on the random draw, `F[2]` becomes either `F[2]+F[1]`or `F[2]-F[1]`. Finish the step by printing the first value of `F`.

Note that I can make this 2 bytes shorter by using a stupid delimiter between sequence values: Try online a 53 byte version which uses the string `TRUE`  as delimiter.
> 4 votes

# Answer
# C (gcc), ~~58 57~~ 47 bytes

```
a,b;f(x){a=--x?f(b=x),b+=rand(x=b)%2?a:-a,x:1;}

```

Try it online!

* Saved 1 thanks to @ceilingcat
* Saved 10 thanks to @Dominic van Essen

Recursive solution which starts all the calls needed before executing them, the last call initialize values.

```
a,b;         - aux variables
f(x){        - function tacking an integer **n** and
               returning **n**th term 1 indexed.

a=           - return trough eax register
--x?f(b=x)   - call recursively before doing the job
x=b          - local x used as temp
,b+=rand()%2?a:-a  - rnd fib step
,x           - assign temp(x) to a
:1;}         - stop recursion and initialize a to 1

```
> 4 votes

# Answer
# , 28 22 bytes

*-6 thanks to Bubbler!*

```
0{1&({,]#.~_1^?@2)&1 1

```

Try it online!

```
0{1&({,]#.~_1^?@2)&1 1
  1&      …       &1 1 a verb that will apply 1&… on 1 1 y (the input) times
              ?@2        0 or  1
           _1^           1 or _1
       ]#.~              to base, e.g. 3 5:
                           (3* 1^1)+(5* 1^0) = 8 or
                           (3*_1^1)+(5*_1^0) = 2
     {,                  prepend tail of list, i.e. 5 8 or 5 2
0{                     take first element

```
> 4 votes

# Answer
# \>\<\>, 22 bytes

```
1|.00<-x+40.08&:{&:}n:

```

Try it Online!

This is usually a terrible language for challenges involving randomness, since the only source of randomness in \>\<\> is `x`.

But in this case things works out alright. `x` sends the instruction pointer in a random direction, so it either wraps around to itself in the y-direction, or hits a `+` or `-` with equal probability.
> 4 votes

# Answer
# Python 3, 77 bytes

```
from random import*
f=lambda n,t=0,o=1:o if n<2else f(n-1,o,o+choice((-t,t)))

```

A recursive function which accepts \\$n\\$ and yields a possible \\$f\_n\\$.

**Try it online!** Or see the first few as sampled 10K-distributions.
> 3 votes

# Answer
# Raku, 26 bytes

```
{1,1,*+* *(-1,1).pick...*}

```

Try it online!

Outputs a lazy infinite list. This is pretty much identical to the normal fibonacci program, but with `*(-1,1).pick` tacked on to randomly flip the sign of the second parameter.
> 3 votes

# Answer
# Dotty, 75 bytes

```
val| :Stream[Int]=1#::1#::(|zip|.tail map(_*((math.random*2).toInt*2-1)+_))

```

Try it online

Same as below.

# Scala, ~~91~~ ~~87~~ ~~85~~ 84 bytes

*Saved 4 bytes thanks to corvus\_192*

```
val| :Stream[Int]=1#::1#::(|zip|.tail map{t=>t._2+t._1*((math.random*2).toInt*2-1)})

```

Try it online

`|` is a `Stream` so that previous elements are remembered. To get the nth element, you can use `|(n-1)` (it's 0-indexed). To get the first n elements, use `|.take(n)` (`l.take(n).toList` to force it).
> 3 votes

# Answer
# Red, 75 bytes

```
func[n][a: b: 1 loop n - 1[set[a b]reduce[b b +(a * pick[1 -1]random 2)]]a]

```

Try it online!

Returns the `n`th term.
> 3 votes

# Answer
# , ~~55~~ ~~54~~ ~~53~~ ~~52~~ ~~51~~ ~~49~~ ~~48~~ 47 bytes

*Edit: -1 byte, and again -1 byte thanks to Giuseppe, -1 byte thanks to AZTECCO*

```
cat(1);repeat cat(" ",T<-sign(rt(1,1))*F+(F=T))

```

Try it online! or check the n=6 distribution.

Full program taking no input. Returns full random fibonacci sequence.

Program to return `n`th element using the same approach is 48 bytes.

Commented:

```
cat(1);             # First, print the first element (1)
                    # (T is initialized to 1 by default,
                    # and F is initialized to 0).
repeat              # Now, repeat indefinitely:
 cat(" ",           # output " ", followed by...
  T<-               #   T, updated to equal...
     sign(rt(1,1))  #   the sign of 1 randomization of
                    #     the t-distribution with 1 degree-of-freedom
                    #     (distribution is centred around zero,
                    #     so sign is [+1,-1] with probability [.5,.5])...
     *F             #   times F (second-last value)...
       +(F=T))      #   plus T (last value)...
                    #   while updating F to equal T.

```
> 3 votes

# Answer
# x86 machine code, 21 bytes

The rdtsc version is the same size for x86-64 machine code.

`rdrand reg` (3 bytes) gives us a truly random number. Branching on its sign bit is cheap. By testing only 1 bit, the 50/50 probability is obviously satisfied exactly with zero bias.

`rdtsc` (2 bytes) gives us a "reference cycle" timestamp whose low bits are *somewhat* random (it takes at least 25 cycles to run back-to-back RDTSC instructions, but the counter isn't running *that* much faster than we're sampling it). Testing one bit with `test al, 1` leads to significant correlation between consecutive decisions, but `test al,al` / `jnp` (branch on the parity flag, horizontal xor of the low 8 bits) gives surprisingly good results, and could be used on pre-IvyBridge machines that lack `rdrand`. Both of them golf to the same overall size in 32-bit mode.

Try it online! NASM listing for `rdrand` version: `EAX rfib(ECX)`, callable from C with MS `__fastcall`

```
21                         rfib:          ;;; 0-indexed.  ecx=5 gives the n=6 test case results.
22 00000020 31C0               xor eax, eax
23 00000022 99                 cdq                         ; EDX = fib[-1] = 0
24 00000023 40                 inc eax                     ; fib[0] = 1
25 00000024 E30E               jecxz   .done               ; ecx=0 : return 1 without looping

27                         .loop:
28 00000026 0FC7F7             rdrand  edi
29 00000029 85FF               test    edi, edi        ; 1 byte shorter than sar reg, imm / xor / sub 2's complement bithack
30 0000002B 7902               jns    .no_negate       ; the top bit is fully random
31 0000002D F7DA               neg    edx
32                         .no_negate:
33 0000002F 0FC1D0             xadd    eax, edx        ; like xchg + add, and same size
34 00000032 E2F2               loop   .loop
35                         .done:
36 00000034 C3                 ret
 size = 0x35 - 0x20 = 0x15 = 21 bytes

```

Note that `xadd` doesn't actually save any bytes vs. `xchg eax, edx` / `add eax, edx`. It's just fun. And it's "only" 3 uops, instead of 4 total, on Intel Skylake with register operands. (Normally the instruction is only used with the `lock` prefix and a memory destination, but it fully works with registers).

Test case:

```
  bash loop to test the ECX=5 case
$ asm-link -m32 -dn random-fib.asm &&
 { declare -A counts; counts=();
  for i in {1..10000}; do ./random-fib; ((counts[$?]++));done;
  for i in "${!counts[@]}"; do echo "result: $(( i > 128 ? i-256 : i )):
${counts[$i]} times";done }

result: 8:   617 times
result: 4:   1290 times
result: 2:   2464 times
result: 0:   3095 times
result: -2:   2534 times

```

---

NASM listing for **`rdtsc` version**: `EBX rfib2(ECX)`. This version would be the same size in 64-bit mode; doesn't need 1-byte `inc`. RDTSC writes EAX and EDX so we can't take advantage of `cdq` in the init.

```
 2                         rfib2:            ; 0-index count in ECX, returns in EBX
 3 00000000 31F6               xor  esi, esi
 4 00000002 8D5E01             lea  ebx, [esi+1]           ; fib[0] = 1, fib[-1] = 0
 5 00000005 E30D               jecxz .done
 6                         .loop:
 7 00000007 0F31               rdtsc                       ; EDX:EAX = TimeStamp Counter
 8
 9 00000009 84C0               test    al, al               ; low bits are essentially random; high bits not so much
10 0000000B 7B02               jnp    .no_negate
11 0000000D F7DE               neg     esi
12                         .no_negate:
13 0000000F 0FC1F3             xadd    ebx, esi
14 00000012 E2F3               loop   .loop
15                         .done:
16                             ; returns in EBX
17 00000014 C3                 ret
 size = 0x15 = 21 bytes

```

Test results for ECX=5:

```
result: 8:   668 times         (ideal: 625)
result: 4:   1217 times        (ideal: 1250)
result: 2:   2514 times        (ideal: 2500)
result: 0:   3135 times        (ideal: 3125)
result: -2:   2466 times       (ideal: 2500)

```

vs. with `test al, 1` / `jnz` to use just the low bit of the TSC as the random value:

```
  # test al,1  / jnz   version: correlation between successive results.
result: 8:   115 times
result: 4:   79 times
result: 2:   831 times
result: 0:   3070 times
result: -2:   5905 times

```

`test al,4` happens to work reasonably well for long runs on my Skylake CPU (i7-6700k) which ramps up to 3.9GHz at the energy\_performance\_preference=balance\_performance I'm using, vs. a reference (TSC) frequency of 4008 MHz (more info on x86 constant-TSC stuff). I imagine there's some strange alchemy of branch prediction, and `rdtsc` itself having ~25 cycle throughput (core clocks) on Skylake (https://uops.info).

Results are generally better distributed with `test al,al` / `jnp` though, so prefer that to take entropy from all 8 low bits. When CPU frequency is low (idle), so the TSC is not close to the same frequency as the core, taking entropy from a single bit might work even better, although the parity of the low 8 bits is probably still best.

I haven't tested on a CPU with turbo disabled where non-boost core clock exactly equals the TSC reference clock. That could more easily lead to bad patterns if the `rdtsc` throughput happens to be a power of 2 or something, perhaps favouring some sequence that lets branch prediction lock on.

All my testing has been with one invocation of the function per process startup. A Linux static executable is pretty efficient to start up, but is still *vastly* more expensive than calling the function in a loop from inside the process.
> 3 votes

# Answer
# Wolfram Language (Mathematica), 38 bytes

Prints the sequence indefinitely. Adapted from J42161217's answer.

```
#0[Echo@+##,RandomChoice@{#,-#}]&[0,1]

```

Try it online!

Ungolfed:

```
f[a_, b_] := ( Echo[a+b]; f[a+b, RandomChoice[{a,-a}]] );
f[0, 1]

```
> 3 votes

# Answer
# Charcoal, 28 bytes

```
≔⁰θ≔¹ηＦＮ«≔⁺η×θ⊖⊗‽²ι≔ηθ≔ιη»Ｉθ

```

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

```
≔⁰θ≔¹η

```

Start with 0 as the `i`th number and `1` as the `i+1`th number.

```
ＦＮ«

```

Loop `n` times.

```
≔⁺η×θ⊖⊗‽²ι

```

Calculate the next number.

```
≔ηθ≔ιη

```

Shuffle the values around.

```
»Ｉθ

```

Output the `n`th number.

29 bytes to output the first `n` numbers:

```
Ｆ²⊞υ¹ＦＮ⊞υ⁺§υ±¹×§υ±²⊖⊗‽²Ｉ✂υ⁰±²

```

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

```
Ｆ²⊞υ¹

```

Start with `1` as the first and second numbers.

```
ＦＮ

```

Loop `n` times.

```
⊞υ⁺§υ±¹×§υ±²⊖⊗‽²

```

Calculate the next number.

```
Ｉ✂υ⁰±²

```

Output all but two of the numbers.
> 2 votes

# Answer
# Icon, 70 bytes

```
procedure n()
f:=[1,1]
while write(f[2])&push(f,f[1]+?[1,-1]*f[2])
end

```

Try it online!

Prints the sequene indefinitely.
> 2 votes

# Answer
# C (gcc), ~~56~~ ~~53~~ 52 bytes

*Edit: -3 bytes thanks to AZTECCO, -1 byte thanks to ceilingcat*

```
x;y;r(n){for(x=y=1;--n;)x=~-(rand()&2)*y+(y=x);x=y;}

```

Try it online!

Non-recursive answer in C.
Function that returns `n`th (one-based) element of random fibonacci sequence.

```
x;y;                # x & y hold last and last-but-one elements;
r(n){               # n is index of element we're looking for;
for(x=y=1;          # initialise first two elements to 1;
 --n;)              # now loop by decreasing n until it is zero,
 x=                 # update x to become equal to:
   ~-(rand()&2)*y   # plus-or-minus y...
   +(y=x)           # plus x
                    # (while updating y to equal the current x).
    ;x=y;}          # after looping, return y.

```

**Note**: Following some discussion in the comments here and in AZTECCO's answer, a consensus was reached that it is not necessary to initialize the random seed *within a function*. Of course, that this means that the *calling program* should do so, or the function may give the same sequence of pseudo-random output every time the calling program is run. A 74 byte variant of the function can itself initialize the random seed itself (but only on first call, so that subsequent calls from the same program run give different output).
> 2 votes

# Answer
# Bash, 65 bytes

```
a=1;b=1;while :;do echo $a;t=$b;:$[b+=$RANDOM&1?$a:-$a];a=$t;done

```

Try it online!

Endlessly outputs the latest and greatest version of the sequence.
> 1 votes

# Answer
# Swift, 77 bytes

```
sequence(first:(1,1)){a,b in(b,.random() ?a+b:a-b)}.lazy.forEach{print($0.0)}

```

Outputs until `Int` overflow.
> 1 votes

# Answer
# Lua, 81 bytes

```
t={1,1}for i=1,...do t[i]=t[i]or t[i-1]+t[i-2]*(math.random(2)*2-3)print(t[i])end

```

Try it online!

Takes number of members to be printed as an argument. Replace `...` with `1/0`  to print sequence forever at const of one byte.
> 1 votes

# Answer
# Vyxal, 9 bytes

```
‡₍+-℅d11Ḟ

```

Try it Online!

Prints the infinite list.

```
        Ḟ # Create an infinite list from...
      11  # [1, 1]
‡    d    # And a function taking two arguments...
 ₍  ℅     # Choose randomly from...
  +-      # sum of previous two, difference of previous two

```
> 1 votes

# Answer
# Excel VBA, ~~49~~ 48 bytes

Saved 1 byte thanks to Taylor Raine and using the VBA native function instead of evaluating the Excel function.

```
b=1:Do:c=a+b*IIf(Rnd()<.5,1,-1):a=b:b=c:?a:Loop

```

Code is input and run in the immediate window. Output is the infinite sequence. Here's what it looks like if it was formatted into a subroutine instead:

```
b = 1
Do
    c = a + b * IIf(Rnd() < .5,1,-1)
    a = b
    b = c
    Debug.Print a
Loop

```

The Rnd() function outputs a value in the range \[0,1) hence the `<.5` check. I out the 6th term in the sequence 1,000 times (since that's an example in the question) and found the following distribution of values:

| **Value** | **Count** | **Percent** |
| --- | --- | --- |
| -8 | 45 | 4.5% |
| -4 | 48 | 4.8% |
| -2 | 252 | 25.2% |
| 0 | 322 | 32.2% |
| 2 | 264 | 26.4% |
| 4 | 47 | 4.7% |
| 8 | 22 | 2.2% |
> 1 votes

---
Tags: code-golf, sequence, random, fibonacci
---


# Question
Title: CGAC2022 Day 6: Shuffles with specific "magic number"
Part of **Code Golf Advent Calendar 2022** event. See the linked meta post for details.

---

On the flight to Hawaii for vacation, I'm playing with a deck of cards numbered from 1 to \\$n\\$. Out of curiosity, I come up with a definition of "magic number" for a shuffled deck:

* The magic number of a shuffle is the minimum number of swaps needed to put the cards back into the sorted order of 1 to \\$n\\$.

Some examples:

* `[1, 2, 3, 4]` has magic number 0, since it is already sorted.
* `[4, 3, 2, 1]` has magic number 2, since I can swap (1, 4) and then (2, 3) to sort the cards.
* `[3, 1, 4, 2]` has magic number 3. There is no way I can sort the cards in fewer than 3 swaps.

**Task:** Given \\$n\\$ and the magic number \\$k\\$, output all permutations of \\$n\\$ whose magic number is \\$k\\$.

You may assume \\$n \ge 1\\$ and \\$0 \le k \< n\\$. You may output the permutations in any order, but each permutation that satisfies the condition must appear exactly once. Each permutation may use numbers from 0 to \\$n-1\\$ instead of 1 to \\$n\\$.

Standard rules apply. The shortest code in bytes wins.

Trivia: The number of permutations for each \\$(n, k)\\$ is given as A094638, which is closely related to Stirling numbers of the first kind A008276.

## Test cases

```
n, k -> permutations
1, 0 -> [[1]]
2, 0 -> [[1, 2]]
2, 1 -> [[2, 1]]
3, 0 -> [[1, 2, 3]]
3, 1 -> [[1, 3, 2], [2, 1, 3], [3, 2, 1]]
3, 2 -> [[3, 1, 2], [2, 3, 1]]
4, 0 -> [[1, 2, 3, 4]]
4, 1 -> [[1, 2, 4, 3], [1, 3, 2, 4], [1, 4, 3, 2], [2, 1, 3, 4],
         [3, 2, 1, 4], [4, 2, 3, 1],
4, 2 -> [[1, 3, 4, 2], [1, 4, 2, 3], [2, 1, 4, 3], [2, 3, 1, 4],
         [2, 4, 3, 1], [3, 1, 2, 4], [3, 2, 4, 1], [3, 4, 1, 2],
         [4, 1, 3, 2], [4, 2, 1, 3], [4, 3, 2, 1]]
4, 3 -> [[2, 3, 4, 1], [2, 4, 1, 3], [3, 1, 4, 2], [3, 4, 2, 1],
         [4, 1, 2, 3], [4, 3, 1, 2]]

```

# Answer
# , 26 22 bytes

```
((=#"1-#@C.)#])!A.&i.]

```

Try it online!

*-4 thanks to Bubbler!*

Generates all perms, converts to cycle representation, take sum of "length of each cycle - 1" (this gives number of swaps needed to sort), then filter to only those elements whose swap count matches the input requirement.
> 8 votes

# Answer
# Python 3, 108 bytes

```
f=lambda n,k,*a:n and sum([f(n-1,k-1,v,*a[:i],n,*a[i+1:])for i,v in enumerate(a)],f(n-1,k,n,*a))or[a]*(k==0)

```

Try it online!
> 5 votes

# Answer
# Python, 97 bytes

```
f=lambda n,k:[[]][n+k*k:]or[L[:j]+[n]+(2*L[j:])[1:n-j]for j in range(n)for L in f(n-1,k-(-~j<n))]

```

Attempt This Online!

### Python, 134 bytes

```
def f(n,k,L=0):
 z=range(n);L=[*(L or z)];n-=1;s=L[n]
 for j in z:L[n]=L[j];L[j]=s;yield from([L][n-j:],f(n,k-(j<n),L))[k>0];L[j]=L[n]

```

Attempt This Online!

Enumerates the magic permutations. n is number of elements, k is magic number.

### How?

A modification of a textbook (I'd think) permutation enumerator: go from rightmost to leftmost position swapping each with any position to its left or not at all. All we are adding is fixing the number of swaps.
> 4 votes

# Answer
# 05AB1E, 29 bytes

```
Lœʒāøœ€.œ€`.Δε˜Á2ô€ËP}P}€g<OQ

```

Port of *@Jonah*'s J answer, but without cyclic permutation builtin†.

Inputs in the order \\$n,k\\$.

Try it online or verify all test cases.

**Equal bytes alternative actually performing swaps:**

```
ÝRεULœʒ©ãX.Æε®svyÂ‡}D{Q}à].»K

```

Inputs also in the order \\$k,n\\$.

Try it online or verify all test cases.

**Explanation:**

```
L             # Push a list in the range [1, first (implicit) input n]
 œ            # Get a list of all its permutations
  ʒ           # Filter this list of permutations by:
   āøœ€.œ€`.Δε˜Á2ô€ËP}P}
              #  Get the cyclic permutation of the current permutation-list†:
   ā          #   Push a list in the range [1,length] (without popping): [1,n]
    ø         #   Pair it together with each value in the current permutation
   œ          #   Get all permutations of this list
    €         #   Map over each permutation:
     .œ       #    Get all partitions
       €`     #   Flatten it one level down
   .Δ         #   Find the first partition of permutation of pairs of the current
              #   permutation-list that's truthy for:
     ε        #    Map over each part of the partition:
      ˜       #     Flatten the list of pairs
       Á      #     Rotate it once towards the right
        2ô    #     Split it back into parts
          €Ë  #     Check if the values in each individual pair are the same
            P #     Check if this is truthy for all of them (thus it's a cycle)
     }P       #    After the map: check if it's truthy for the entire partition
    }         #   Close the find_first, resulting in the cyclic permutation
     €g       #  Get the length of each inner cycle-list
       <      #  Decrease each length by 1
        O     #  Take the sum of those
         Q    #  Check if it's equal to the second (implicit) input k
              # (after which the filtered list of permutations is output implicitly)

```

```
Ý             # Push a list in the range [0, first (implicit) input k]
 R            # Reverse it to [k,0]
  ε           # Map over each value:
   U          #  Pop the current value, and store it in variable `X`
   L          #  Push a list in the range [1, second (implicit) input n]
    œ         #  Get all permutations of this list
     ʒ        #  Filter it by:
      ©       #   Store the current list in variable `®` (without popping)
       ã      #   Get all pairs of this list
              #   (with duplicates by using cartesian power of 2)
        X.Æ   #   Get all X-sized combinations of these pairs
              #   (without duplicates by using combinations builtin)
      ε       #   Map over each list of pairs:
       ®      #    Push permuted list `®`
       s      #    Swap so the current list of pairs is at the top
        v     #    For-each over each pair `y`:
         y    #     Push the current pair `y`
          Â   #     Bifurcate it; short for Duplicate & Reverse copy
           ‡  #     Transliterate it in the list, basically swapping the values
        }D{Q  #    After the inner loop: check if the list is sorted
         D    #     Duplicate the resulting list with performed swaps
          {   #     Sort the copy
           Q  #     Check if both lists are the same
      }à      #   After the inner map: check if any was truthy
  ]           # Close both the filter and outer map
   .»         # Then left-reduce these lists by:
     K        #  Removing lists
              # (after which the reduced list of permutations is output implicitly)

```
> 2 votes

# Answer
# Charcoal, 52 bytes

```
⊞υ…Ｎ≔υθＦＮ«≔⟦⟧υＦθＦＬκＦ⁻⁻ＥλＥκ§κ⎇⁼πλμ⎇⁼πμλπυθ⊞υμ≔⁺θυθ»Ｉυ

```

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

```
⊞υ…Ｎ

```

Start with the identity permutation as the only permutation with magic number `0`.

```
≔υθ

```

Also set this as the list of permutations seen so far.

```
ＦＮ«

```

Loop through the magic numbers.

```
≔⟦⟧υ

```

Start with no permutations for the next magic number.

```
ＦθＦＬκＦ

```

Loop through the swaps of the permutations seen so far (including the ones whose swaps we've already seen but that's code golf for you).

```
⁻⁻ＥλＥκ§κ⎇⁼πλμ⎇⁼πμλπυθ

```

Generate the list of potential new permutations but remove any previously seen (including those already seen for this magic number).

```
⊞υμ

```

Append any new permutations for this magic number. (Or I could have just concatenated the lists I guess.)

```
≔⁺θυθ

```

Append all of the new permutations for this magic number to the list of those seen so far.

```
»Ｉυ

```

Output the permutations for the last magic number processed.
> 1 votes

# Answer
# PARI/GP, 48 bytes

```
f(n,k)=forperm(n,p,n-k-#permcycles(p)||print(p))

```

Attempt This Online!

A port of @Jonah's J answer.
> 1 votes

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

```
f=(n,k,a=[])=>n--?[f,...a].flatMap((v,i,[...b])=>f(b[b[0]=v,i]=n,k-!!i,b)):k?[]:[a]

```

Try it online!
> 1 votes

# Answer
# Jelly, 21 bytes

```
ŒcżU$œcⱮŻ}y@ƒ€€R{Ṛḟ/Q

```

A dyadic Link that accepts \\$n\\$ on the left and \\$k\\$ on the right and yields a list of those permutations of \\$\[1,n\]\\$ which require a minimum of \\$k\\$ pairwise swaps to sort.

**Try it online!**

### How?

Starting with the sorted deck the code performs all possible (up to rearrangement) swap sequences of lengths \\$j \leq k\\$ then takes those reachable with exactly \\$k\\$ swaps and removes any that were reachable with less.

```
ŒcżU$œcⱮŻ}y@ƒ€€R{Ṛḟ/Q - Link: integer, n; integer, k
Œc                    - unordered pairs (n) (e.g. n=3 -> [[1,2],[1,3],[2,3]])
    $                 - last two links as a monad - f(x=that):
   U                  -   reverse each pair
  ż                   -   (x) zip with (that) -> P = [[[a,b],[b,a]],...])
         }            - with chain's right argument:
        Ż             -   zero range (k) -> [0,1,2,...,k]
       Ɱ              - map (across j in that) with:
     œc               -   (P) combinations (j) -> all (ordered) length j pair-tuples
                {     - with chain's left argument:
               R      -   range (n) -> [1,2,3,...n]
              €       - for each (list of pair-tuples):
             €        -   for each pair-tuple:
            ƒ         -     reduce (pair-tuple) starting with (range(n)) using:
           @          -       with swapped arguments:
          y           -         translate (e.g. [3,1,2] y [[2,3],[3,2]] -> [2,1,3])
                 Ṛ    - reverse
                   /  - reduce by:
                  ḟ   -   filter-discard
                    Q - deduplicate

```
> 1 votes

# Answer
# Pyth, 29 bytes

```
LsmmXd_kk.cSQ2b{-F_myF]SQdUhE

```

Try it online!

### Explanation

```
L                                define y(b): applies every swap possible to every sequence in b
 sm           b                    for all d in b
   m     .cSQ2                     for all pairs of unique elements in range(1,n+1), k
    Xd_kk                          generate a sequence by swapping the elements of k in d
                   m      UhE    map d over range(k+1)
                    yF   d       apply y d times to
                      ]SQ        [range(1,n+1)]
                  _              reverse this
                -F               fold over subtraction (remove all states with fewer flips)
               {                 deduplicate

```
> 0 votes

---
Tags: code-golf, permutations
---


# Question
Title: Output the length of (the length plus a message)
The task is simple. You're given an arbitrary string message. Return that message prefixed with a number, such that the length of that number plus the message equals the number. In other words, the length in your output must be the total length of your output.

If multiple candidates exist, you can output any of them.

For example, take the following message: `pull the other one`, with a length of 18. Your final output should be `20` \+ `pull the other one`, because the total length of `20` \+ the total length of `pull the other one` is 20 ASCII characters.

Restrictions/clarifications:

* Your input and output can be given by any convenient method.
* The outputted length can be encoded in any way you like, as long as the encoding can represent any arbitrary positive number, and the encoding is consistent. You can, for example, output `10111` \+ `pull the other one` (10111 is 23 in binary, and the total length is 23). This also extends to types: e.g. a tuple of `(int, string)` is accepted as output, as long as you specify the encoding the integer must have.
* The input string can also have any encoding you like (well, except for the encoding in this question).
* Your program should be able to handle at least all messages of length \<= 1,048,575 (2^20-1).
* The program can be a full program or just a function; either is fine.
* Standard loopholes are forbidden.
* Shortest code wins.

Some more test cases:

```
# base 10
"hello world" -> "13" + "hello world"
"the axes"    -> "9"  + "the axes"
"the axes"    -> "10" + "the axes"    # both of these are valid outputs
""            -> "1"  + ""            # the empty message should result in simply the output "1"

# base 2
"hello world" -> "1111" + "hello world"
"test"        -> "111"  + "test"
"test"        -> "1000" + "test"        # both of these are valid outputs
""            -> "1"    + ""            # the empty message can result in simply the output "1"
""            -> "10"   + ""            # in binary, this is also a valid result for the empty message

```

# Answer
> 4 votes
# C (gcc), 43 bytes

```
f(b,s,n){for(;sprintf(b,"%d%s",++n,s)>n;);}

```

Try it online!

# Answer
> 3 votes
# Pyth, <sup>~~7~~</sup> 6 bytes

*-1 byte thanks to @isaacg*

```
+fql+Q

```

Attempt This Online!

## Explanation

```
+fql+QTT<None>Q
+                #  add
 f               #    first input (T) where
   l             #      length of
    +QT          #        testcase + T
  q    T         #      equals T
              Q  #  to the testcase

```

# Answer
> 3 votes
# Japt, 7 bytes

```
ÈsY}f+U

```

Try it here

```
ÈsY}f+U     :Implicit input of string U
È           :Function taking a string and a 0-based iteration index Y as arguments
 sY         :  Slice the string from the Yth character
   }        :End function
    f       :Get the first string that returns falsey (empty string)
     +U     :  Where each string is U appended to the current iteration index

```

# Answer
> 3 votes
# Vyxal, 4 bytes

```
3(Lp

```

Try it Online! -1 thanks to lyxal, -2 thanks to Kevin Cruijjsen.

```
3(   # Three times
   p # Prepend to input
  L  # Length of current value

```

# Answer
> 3 votes
# Charcoal, 10 bytes

```
⁺Ｌ⁺Ｌ⁺Ｌθθθθ

```

Try it online! Link is to verbose version of code. Explanation: Charcoal doesn't really do recursion, but the recursive approach of repeatedly taking the length of the string with the previous length prefixed to it never needs to iterate more than twice.

```
      θ     Input string
     Ｌ      Take the length
    ⁺       Concatenated with
       θ    Input string
   Ｌ        Take the length
  ⁺         Concatenated with
        θ   Input string
 Ｌ          Take the length
⁺           Concatenated with
         θ  Input string
            Implicitly print

```

# Answer
> 3 votes
# Pyth, 4 bytes

```
+Chl

```

Try it online!

Length encoded using Python `chr`.

# Answer
> 2 votes
# JavaScript (ES6), 31 bytes

*-1 thanks to @Shaggy*

Uses a decimal prefix.

```
s=>(g=n=>(S=++n+s)[n]?g(n):S)``

```

Try it online!

# Answer
> 2 votes
# Husk, 10 bytes

```
,ḟS=ȯL+¹sN

```

Try it online!

```
,ḟS=ȯL+¹sN
 ḟ          # get the first
         N  # integer from 1..infinity
  =         # that equals
   ȯ        # (compose 3 functions)
    L       #   the length of
     +¹     #   the input added to
       s    #   itself as a string
,           # finally, construct a pair of
            # this number and the input

```

# Answer
> 2 votes
# Python, 24 bytes

```
lambda a:chr(len(a)+1)+a

```

Attempt This Online!

---

# Python, 50 bytes

```
f=lambda a,b=1:(len(s:=str(b)+a)==b)*s or f(a,b+1)

```

Attempt This Online!

---

# Python 2, 49 bytes

```
f=lambda a,b=1:(len(`b`+a)==b)*(`b`+a)or f(a,b+1)

```

Attempt This Online!

Python 2 solution suggested by Dominic van Essen

# Answer
> 2 votes
# Ly, 15 bytes

```
iys>l`Sys<l+u&o

```

Try it online!

```
iys              - Read STDIN onto the stack, push stack size, save it
   >l`           - Switch to new stack, load saved size, increment by 1
      Sys        - Convert number to digits, get size of stack, save it
         <       - Switch back to the original stack (w/ STDIN and strlen)
          l+     - Load number of digits in the "strlen + 1", add to strlen
            u    - Write length as a number
             &o  - Write STDIN codepoints as characters

```

# Answer
> 2 votes
# 05AB1E, 4 bytes

```
3Fgì

```

Similar as my answer for the related challenge, but with a prepend instead of append. Will therefore also use base-10, and always use the smallest (`9` instead of `10`) if more than one option is available.

Try it online or verify all test cases.

**Explanation:**

```
3F    # Loop 3 times:
  g   #  Pop the current string, and push its length
      #  (which will use the implicit input-string in the first iteration)
   ì  #  Prepend this length to the (implicit) input-string
      # (after which the result is output implicitly)

```

# Answer
> 2 votes
# AWK, 41 38 bytes

```
{a=length;$0=length(length(a)+a)+a$0}1

# E.g.
awk '{a=length;$0=length(length(a)+a)+a$0}1' <<< "input"

```

Try it online

Remove the space (`" "`) between the final length and the string as suggested by @Dominic van Essen (-3 bytes)

# Answer
> 1 votes
# Python, 65 bytes

I'm not 100% sure I understood the question right

```
lambda a,b=0:(z:=len(a)+len(str(b)))and((z,a)if z==b else f(a,z))

```

Attempt This Online!

# Answer
> 1 votes
# Nibbles, 4.5 bytes (9 nibbles)

```
/\`.$:,$@

```

Inspired by Pacmanboss's comment.

```
  `.            # iterate while unique
    $           # starting from the input:
     :          #   prepend
      ,$        #   its length
        @       #   to the original input
 \              # then, reverse the list
/               # and fold over it
                # getting the left-hand argument each time
                # (so getting the first element)

```

---

Previous approach:

# Nibbles, 5.5 bytes (11 nibbles)

```
:/|,~~-,:`p

```

Nibbles adds implicit variables to the end of each program if they are needed for the arity of the functions used.
In this case, this works particularly well.

```
  |             # filter
   ,~           # 1..infinity
     ~          # for elements that are falsy for
       ,        #   the length of
         `p     #    the string represention
                #    (implicitly: of each element)
        :       #    concatenated with
                #    (implicitly: the input)
      -         #   minus
                #   (implicitly: itself)
 /              # now, fold over this list
                #   returning for each pair
                #   (implicitly: the left-hand argument)
                #   (so the fold returns the first element)
:               # finally, prepend this to
                #   (implicitly: the input)

```

# Answer
> 1 votes
# Python, 47 bytes

```
f=lambda a,b=1:(b*f"{b}{a}")[-b:b*b]or f(a,b+1)

```

Attempt This Online!

# Answer
> 1 votes
# Ruby, ~~39~~ 34 bytes

```
->c,a=0{a+=1while(b=[a]*c+c)[a];b}

```

-5 bytes thanks to observations from jdt's C and Arnauld's JS.

Attempt This Online!

# Answer
> 1 votes
# MathGolf, 6 bytes

```
£▌£▌£▌

```

Try it online.

**Explanation:**

```
£       # Pop and push the length of the (implicit) input-string
 ▌      # Prepend it to the (implicit) input-string
  £     # Pop and push the length of that
   ▌    # Prepend it to the (implicit) input-string
    £▌  # Rinse and repeat
        # (after which the entire stack is output implicitly)

```

# Answer
> 1 votes
# \>\<\>, ~~43~~ 41 bytes

```
r1>:0v >o<
1(?v$>1+$a,:
2l~<.03+1v?=@:$+-

```

Try it online! or Try without input

**Explanation**

```
r1                  # initialize with length as 1 (L)
  >:0v              # initialize length of (L) as 0 (N)
1(?v$>1+$a,:        # calculate (N)
2l~<     v?=@:$+-   # if the length of string (S) + (N) = (L)
       >o<          # print L followed by the string
    .03+1           # else, increment (L) and go back to calculation of (N)

```

The length is output as a charcode.

# Answer
> 1 votes
# Go, 95 bytes

```
import."fmt"
func f(s string)string{S:=Sprint
return S(len(s)+len(S(len(s)+len(S(len(s))))),s)}

```

Attempt This Online!

##### Go, Old 125 bytes

```
import(."fmt";."strings")
func f(s string)string{S:=Repeat("-",len(s))+s
for range`---`{S=Sprintf("%d%s",len(S),s)}
return S}

```

Attempt This Online!

# Answer
> 1 votes
# Excel, ~~21~~ 27 bytes

```
=LEN(LEN(LEN(A1)&A1)&A1)&A1

```

Admittedly boring. I tried to do something fancy with `LOG()` but it's longer than this solution.

# Answer
> 1 votes
## SAS, ~~47~~ 58 bytes

Fix `something` error. I just find this anwser is same with the Excel one.

```
%macro e(m);
%put%length(%length(%length(&m)&m)&m)&m;
%mend;

```

Try some example:

```
%e(hello world);
13hello world

%e(something);
11something

%e(the axes);
9the axes

```

# Answer
> 1 votes
# JavaScript, 29 bytes

```
s=>(g=x=>x.length+s)(g(g(s)))

```

Try it online!

# Answer
> 1 votes
## SQL (24 bits)

```
print len(@)+len(len(@))

```

Assuming we have: `declare @ as varchar(max) = 'any-string'`

# Answer
> 0 votes
# PLIS, 81 bytes

```
&R($Z(strlen($0))$D(1+@(H@({$0^2}{$0-spT@$0-Z}a))@0)catat(48+digits(D),spT@D,$0))

```

Takes a string sequence as input, and returns a string sequence as output.

```
print(R("hello world"));        #=> 13hello world
print(R("the axes"));           #=> 9the axes
print(R("pull the other one")); #=> 20pull the other one
print(R(""));                   #=> 1

```

## Explanation

Here is an equivalent, commented, ungolfed version of the above, with shortnames expanded.

```
&R(
  # set Z to strlen(input)
  $Z(strlen($0))
  # set D to 1 + the first index where
  $D(
    1 + @(
      # we find a 0 in
      A000007@(
        # the squared sequence of (i.e. absolute value of)
        {$0^2}
          # the difference between increasing positive integers ($0),
          # the length of that integer (A055642), and the input
          # string's length (Z)
          {$0 - A055642@$0 - Z} A000027
      )
    )@0
  )
  # D is now the appropriate number we need to prepend
  # 48 + digits(D) gives the ASCII version of this sequence
  # catat(A,n,B) will use the first  n  entries of  A  followed by
  # the entries in  B
  # this line has the effect we want
  catat(48 + digits(D), A055642@D, $0)
)

```

# Answer
> 0 votes
# Terse, 4 bytes

```
地用找儿

```

Try it here

```
地　　　　　Length
　用　　　　+1
　　找　　　To character
　　　儿　　Append input

```

---
Tags: code-golf, math, base-conversion, encoding, recursion
---