title: Find i^n, given n

text:
# Question
Title: Find i^n, given n
**The Challenge**

In as few characters as possible, find the value of \\$i^n\\$, given \\$n\\$, a positive integer greater than 0. This should be outputted as a String.

For those that don't know, \\$i\\$ is defined such that \\$i^2=-1\\$. So:

* \\$i^1=i\\$
* \\$i^2=-1\\$
* \\$i^3=-i\\$
* \\$i^4=1\\$

This then repeats..

**Rules**

* If your language supports complex numbers, don't use any functions or arithmetic that could work this out.
* Floating point inaccuracies are fine for answers that would return decimals anyway, but integer inputs should give exact results

**Bonus Points**

-5 if you can work the value out where n is also negative

-15 if you can work out the value for any real number (this bonus includes the -5 from the above bonus)

Good luck!

# Answer
# Ruby, score -2

(13 bytes, -15 bonus)

```
->n{[1,90*n]}

```

Features include: no rounding errors! (if you pass the input as a Rational)

---

**posted by the author, Kezz101**

> If you support any real number you can output in any valid complex form.

Negatives scores make my adrenaline rush forth. Thus the rules get abused are made use of to achieve this noble goal.

Creates an anonymous function and outputs an array with 2 entries representing a complex number in polar form (angular unit: degrees).
> 20 votes

# Answer
# CJam, 12 characters - 5 = 7

```
1'iW"-i"]li=

```

Test it here.

Supports negative inputs.

```
1              "Push 1.";
 'i            "Push the character i.";
   W           "Push -1.";
    "-i"       "Push the string -i.";
        ]      "Wrap all four in an array.";
         li    "Read STDIN and convert to integer.";
           =   "Access array. The index is automatically taken module the array length.";

```

The result is printed automatically at the end of the program.

# Mathematica, ~~22~~ ~~20~~ 19 characters - 15 = 4

```
Sin[t=π#/2]i+Cos@t&

```

This is an anonymous function, which you can use like

```
Sin[t=π#/2]i+Cos@t&[15]

```

(Or assign it to `f` say, and then do `f[15]`.)

Supports reals and gives exact results for integer input.

Note that the `i` is *not* Mathematica's complex *i* (which is `I`). It's just an undefined variable.

Also, despite the order of the expression, Mathematica will reorder the output into `R+Ci` form.
> 14 votes

# Answer
## Python 2 - (24-5)=19

```
lambda n:'1i--'[n%4::-2]

```

Most credit belongs to @user2357112, I just golfed his answer from the comments on this answer a bit more.

Explanation: Starts at the index `n%4` in the string `'1i--'`. Then iterates backwards in steps of two over each letter in the string. So, for example, `n=6` would start at index 2, the first `-`, then skip the `i` and take the `1`, to return `-1`.

@xnor pointed out a same-length solution:

```
lambda n:'--i1'[~n%4::2]

```

## Pyth \- (14-5)=9

I can only seem to get 14, no matter how I try to reverse/slice/etc. :'(

```
%_2<"1i--"h%Q4

```

Which is essentially the same as the above python answer, but in 2 steps, because pyth doesn't support the full indexing options of python. Try it online.

I'm going to go have a talk with isaacg about Pyth indexing ;)
> 14 votes

# Answer
## TI-BASIC (NSpire) - 5 (20 characters-15)

```
cos(nπ/2)+sin(nπ/2)i

```

If you want to recieve a complex return value, replace the `i` at the end with (complex i).
> 11 votes

# Answer
# Marbelous, 43 bytes

Not really a winner, but Marbelous is fun. :)

```
}0
^0
=0&2
&1
}0
^1\/
=0&02D3169
\/\/&0&1&2

```

This is a program which reads the input as a single integer from the first command-line argument. Note that the input is taken modulo 256, but this doesn't affect validity of the result for inputs greater than 255, because 256 is divisible by 4.

## Explanation

Marbelous is a 2D programming language, which simulates "marbles" (byte values) falling through a bunch of devices. The board is made up of 2-character wide cells (the devices), which can process the marbles. Everything that falls off the bottom of a board is printed to STDOUT.

Let's go through the devices in use:

* `}0` is where the first command-line argument goes. I've used two instances of this device, so I get two copies of the input value (at the same time).
* `^n` checks for the `n`th bit of the input marble (where `n=0` is the least significant bit), and produces `1` or `0` depending on the bit.
* `=0` checks for equality with `0`. If the input marble is equal, it just drops straight through, if it isn't it is pushed to the right.
* `\/` is a trash can, so it just swallows the input marble and never produces anything.
* `2D` is the ASCII code of `-`, `31` is the ASCII code of `1` and `69` is the ASCII code of `i`.
* The `&n` are synchronisers. Synchronisers stall a marble until all synchronisers with the same `n` hold a marble, at which point they'll all let their stored marble fall through.

So in effect, what I do is to hold the three relevant characters in three synchronisers, and release those depending on how the least significant bits are set in the input.

For more information, see the spec draft.
> 7 votes

# Answer
# JavaScript (ES6) 29-5 = 24

Supports negative power.

```
f=n=>(n&2?'-':'')+(n&1?'i':1)

```

ES5 :

```
function f(n){return (n&2?'-':'')+(n&1?'i':1)}

```
> 6 votes

# Answer
# APL (Dyalog), 8 chars - 15 bonus = score -7

The built-in (and thus prohibited) function is `0J1*⊢`, but this uses @blutorange's method.

```
¯12○.5×○

```

The challenge author, Kezz101, wrote:

> If you support any real number you can output in any valid complex form.

This returns a complex number in the form `aJb` which is the normal way for APL to display complex numbers.

Try it online!

### Explanation

`¯12○` find the unit vector which has the angle in radians of

`.5×` one half times

the argument multiplied by (the circle constant)
> 6 votes

# Answer
# Python 28 bytes - 5 = 23

Supports -ve inputs.

Assuming lambda functions are acceptable (Thanks FryAmTheEggman!):

```
lambda n:n%4/2*'-'+'1i'[n%2]

```

### otherwise 31 bytes - 5 = 26

```
print[1,"i",-1,"-i"][input()%4]

```
> 5 votes

# Answer
# Pari/GP, 14 bytes - 5 = 9

As a ring, \\$\mathbb{C}\\$ is isomorphic to \\$\mathbb{R}\[x\]/(x^2+1)\\$.

```
n->i^n%(i^2+1)

```

The `i` here is just a symbol, not the imaginary unit (which is `I` in Pari/GP).

Try it online!
> 5 votes

# Answer
# (Emacs) Lisp – 34

Just for fun, in (Emacs) Lisp:

```
(lambda(n)(elt[1 i -1 -i](% n 4)))

```

If you want to use it, use a `defun` or use `funcall`:

```
(funcall
 (lambda (n) (elt [1 i -1 -i] (% n 4)))
 4) => 1

(mapcar
 (lambda(n)(elt[1 i -1 -i](% n 4)))
 [0 1 2 3 4 5 6 7 8])
 => (1 i -1 -i 1 i -1 -i 1)

```
> 4 votes

# Answer
# , 29 - 5 = 24 bytes

```
c(1,"i",-1,"-i")[scan()%%4+1]

```

Try it online!

Same as most methods above, takes a modulo of 4, and increases that by 1, because R's arrays are 1-indexed. Works for negative integers as well.

I was worried about mixed outputs here, but Giuseppe pointed out that R coerces numeric types to string types when they are mixed.
> 4 votes

# Answer
# PowerShell, 28 bytes -5 = 23

```
('i',-1,'-i',1)["$args"%4-1]

```

Try it online!

Port of all the cyclic indexing
> 4 votes

# Answer
# Pure bash, 29 bytes - 5 = 24

Supports -ve inputs.

```
a=(1 i -1 -i)
echo ${a[$1%4]}

```
> 3 votes

# Answer
# Befunge-98, ~~41-5 = 36~~ ~~35-5 = 30~~ 32-5 = 27

```
&4%:01-`!4*+:2%'8*'1+\2/d*' +,,@

```

Supports negative integers. Not going to win any awards with this solution, but whatever.

It just accepts a number as input, does some trickery on the modulus (which, frustratingly, doesn't work like usual modulus for negative numbers in the interpreter I used to test it) to make negatives work, and then does some silly conditionals to decide what each character should be.

I'm sure this can be golfed down plenty further. For now, here's another solution that doesn't accept negatives, but makes up for the loss of the bonus by being shorter:

# Befunge-98, ~~32~~ ~~26~~ 23

```
&4%:2%'8*'1+\2/d*' +,,@

```

*Edit* \- Now takes advantage of the fact that "-" is 13 (0xd) characters away from " ".

*Edit 2* \- Now, again, takes advantage of the fact that "i" is 56 (0x38, or `'8`) characters away from "1".
> 3 votes

# Answer
# MATLAB, 33 bytes - 5 = 28

```
x={'i','-1','-i','1'};x(mod(n,4))

```

Even though it's a few bytes more (37-5=32), I actually like this approach better:

```
x='1i -';x((mod([n/2,n],2)>=1)+[3,1])

```
> 3 votes

# Answer
# **Java 8 Score: 72**

In Java, the worst golfing language ever! Golfed:

```
java.util.function.Function s=n->{new String[]{"i","-1","-i","1"}[n%4]};

```

Expanded:

```
class Complex{

    java.util.function.Function s = n -> {new String[]{"i","-1","-i","1"}[n%4]};

}

```

Note: I'm not used to Java 8. I also do not have the runtime for it yet. Please tell me if there are any syntax errors. This is also my first golf.

**Edit:** Removed `import`.

**Edit:** Removed class declaration.

Another answer with score = 87 - 15 = 72

```
java.util.function.Function s=n->{Math.cos(n*Math.PI/2)+"+"+Math.sin(n*Math.PI/2)+"i"};

```

Expanded:

```
class Complex{

    java.util.function.Function s = n -> {Math.cos(n * Math.PI/2) + " + " + Math.sin(n * Math.PI/2) + "i"};

}

```
> 3 votes

# Answer
# C 77

```
main(){int n;scanf("%d",&n);char c[]={n%4>1?'-':' ',~n%2?'1':'i',0};puts(c);}

```

Improved thanks to Ruslan

# C 74-5=69

Oh and of course the most obvious approach

```
main(){unsigned n,*c[]={"1","i","-1","-i"};scanf("%d",&n);puts(c[n%4]);}

```
> 3 votes

# Answer
# Java: ~~151~~ 131-5=126

Golfed:

```
class A{public static void main(String[]a){int n=Integer.parseInt(a[0]);System.out.print(n%4==0?"1":n%4==1?"i":n%4==2?"-1":"-i");}}

```

Ungolfed:

```
class A {
    public static void main(String[] a) {
        int n = Integer.parseInt(a[0]);
        System.out.print(n % 4 == 0 ? "1" : n % 4 == 1 ? "i" : n % 4 == 2 ? "-1" : "-i");
    }
}

```

### As a function: 72-5=67

Golfed:

```
void f(int n){System.out.print(n%4==0?"1":n%4==1?"i":n%4==2?"-1":"-i");}

```

Ungolfed:

```
public void f(int n) {
    System.out.print(n % 4 == 0 ? "1" : n % 4 == 1 ? "i" : n % 4 == 2 ? "-1" : "-i");
}

```

Yes, yet another Java reply - and golfed even worse than ever. But you work with what you can...

***EDIT***: added function version.

***EDIT 2***: so, after a bit of trial and error, here's a version that tries to do it by the book, without exploring the cycle loophole. So…

### Java with value calculation: 146-15=131

Golfed:

```
class B{public static void main(String[]a){float n=Float.parseFloat(a[0]);System.out.print(Math.cos((n*Math.PI)/2)+Math.sin((n*Math.PI)/2)+"i");}}

```

Ungolfed:

```
class B {
    public static void main(String[] a) {
        float n = Float.parseFloat(a[0]);
        System.out.print(Math.cos((n * Math.PI) / 2) + Math.sin((n * Math.PI) / 2) + "i");
    }
}

```

(at least, I think I can claim the top bonus, correct me otherwise)
> 3 votes

# Answer
# OCaml 47

```
let m n=List.nth["1";"i";"-1";"-i"](n mod 4);;

```

Not an award winning solution, but this is my first time code-golfing, so I'm not exactly sure of what I'm doing. I tried to use pattern matching, but that got me over 58.
> 3 votes

# Answer
# 05AB1E, score 5 (10 bytes \- 5 bonus)

```
1'i®„-i)Iè

```

Try it online or verify some more test cases.

**Explanation:**

```
1           # Push 1
 'i        '# Push character "i"
   ®        # Push -1
    „-i     # Push string "-i"
       )    # Wrap everything on the stack into a list: [1,"i",-1,"-i"]
        Iè  # Use the input to (modular 0-based) index into it
            # (and output the result implicitly)

```
> 3 votes

# Answer
# Scala, 7 bytes - 15 = -8

Port of @blutorange's devious Ruby answer. Go upvote that!

```
1->_*90

```

Try it online!

Takes a `BigDecimal` as input, outputs `(Int,BigDecimal)`, but honestly, you could make it work for any type with a `*` method.

## Crazier solution, 3 bytes - 15 = -12

```
90*

```

Try it online!

First component is assumed to be 1, so it only returns the second.

## Boring solution, ~~30~~ 27 bytes

```
" 1 i-1-i"drop _%4*2 take 2

```

Try it online!
> 3 votes

# Answer
# Arn, 13 bytes \- 5 = 8

```
◄š<f5®…┘┤ï\Î±

```

Try it!

# Explained

Unpacked: `[1"i"n_1"-i"]?%4`

```
  [        Begin sequence
    1      Literal one
    "i"    String
    n_     Negate
      1
    "-i"
  ]        End sequence
?          Indexed by
    _      Variable initialized to STDIN; implied
  %        Modulo
    4      Literal four

```
> 3 votes

# Answer
# Husk, (~~14~~ 11 bytes - 5) = 6

*Edit: -3 bytes thanks to Razetime*

```
!C2¨¹-1-i 1

```

Try it online!
> 3 votes

# Answer
# Husk, (30 bytes - 15) = 15

```
m₁m*1.57Ṡe-1
Σz*İ_m§/Π`^⁰↑99İ1

```

Try it online!

(The header in TIO rounds the rational number output into a fraction with maximum 3-digit numerator & demominator, for readability)

Calculations with real numbers are a bit ticky in Husk, since it doesn't have any trigonometric functions. So here I implement -sin(x) as `Σz*İ_m§/Π`^⁰↑99İ1` (99 iterations of the Taylor series), and use `1.57` as a very rough approximation for pi/2.

To make matters even more difficult, Husk natively outputs rational numbers as fractions, rather than decimals. So there aren't any 'floating point' inaccuracies (but there are, of course, inaccuracies!). The byte-count to round-away the (non-floating-point) inaccuracies for integer inputs is currently not included in the score. Add +10 bytes to include it.
> 3 votes

# Answer
# Ruby 32-5=27

```
puts(%w[1 i -1 -i][gets.to_i%4])

```

Works for negative powers!
> 2 votes

# Answer
## Perl, 26 - 5 = 21

```
say qw(1 i -1 -i)[pop()%4]

```

works as a standalone program (argument on the commandline) or the body of a function.
> 2 votes

# Answer
## Python - 31

```
print[1,'i',-1,'-i'][input()%4]

```

I have only recently started learning python. Even though I know it's not good, it's the best I can do.
> 2 votes

# Answer
# Haskell GHCi, 29 Bytes - 15 = 14

```
i p=[cos(p*pi/2),sin(p*pi/2)]

```

Usage:

```
*Main> i 0
[1.0,0.0]
*Main> i pi
[0.22058404074969779,-0.9753679720836315]
*Main> i (-6.4)
[-0.8090169943749477,0.5877852522924728]

```
> 2 votes

# Answer
# Jelly, 2 - 20 = -18 bytes

```
ı*

```

Try it online!

It doesn't use an `i ^ x` builtin but it uses builtins for `1j` and `**` so not sure if allowed.
> 2 votes

# Answer
## Swift, 27

```
{["1","i","-1","-i"][$0%4]}

```

Try it online
> 2 votes

# Answer
# Perl 6, 19 bytes - 5 = 14

```
{<1 i -1 -i>[$_%4]}

```

The result of `%` has the same sign as the divisor in this language.

Try it online!
> 2 votes

# Answer
# C (gcc), 30 bytes

```
f(x){printf(L"iㄭ椭1"+x%4);}

```

Try it online!
> 2 votes

# Answer
# C (gcc), 44 bytes -15=29

```
#define f(x)cos(x*acos(0))+1i*sin(x*acos(0))

```

Try it online!

Handles signed and noninteger arguments.
> 2 votes

# Answer
# , (29 bytes -15) = 14

```
cos(m<-scan()*pi/2)+sin(m)*1i

```

Try it online!

Conventional complex number output; works for negative and real inputs.

(for completeness, there is also `c(1,scan()*90)` for a score of -1, using blutorange's ~~dubious~~ inventive polar output format in degrees)
> 2 votes

# Answer
# Rust ~~34~~ 33 bytes

```
fn main() {
	// closure:
	// |n:usize|["1","i","-1","-i"][n%4]

	// call with:
	print!("{}", (|n:usize|["1","i","-1","-i"][n%4])(3));
}

```

Try it online!

The closure itself:

```
|n:usize|["1","i","-1","-i"][n%4]

```
> 2 votes

# Answer
# Haskell, 29 bytes - 5 = 24

```
f n=words"1 i -1 -i"!!mod n 4

```

Works for negative powers.

I had a pointfree version worked out, but it turns out it's actually longer.

```
f=(words"1 i -1 -i"!!).(`mod`4)

```
> 1 votes

# Answer
## C 105, was 117

```
char c[2];
int main()
{
int n,i,j=0;scanf("%d",&n);i=n%4;
i>1?c[j++]='-':c[j+1]='\0';
c[j]=i&1?'i':'1';
puts(c);
}

```
> 1 votes

# Answer
## Clojure (~~64~~ ~~54~~ 31 chars)

```
(defn i2n[n](println(case(mod n 4) 1 "i" 2 "-1" 3 "-i" 0 "1")))

```

## Edit

Per @SeanAllred's suggestion, here's a version which uses a literal vector instead of a `case` function:

```
(defn i2n[n](println (["1" "i" "-1" "-i"] (mod n 4))))

```

## Edit 2

By counting on the REPL to print out the resultant collection and coding the function using the `#()` shortcut we can reduce it to

```
#(["1" "i" "-1" "-i"](mod % 4))

```

(Which is actually much more Clojure/Lisp-ish as the function now actually returns the generated result, allowing the function to be used with `map`, as in

```
(map #(["1" "i" "-1" "-i"](mod % 4)) [0 1 2 3 4 5 6 7 8])

```

which prints

```
("1" "i" "-1" "-i" "1" "i" "-1" "-i" "1")

```

Share and enjoy.
> 1 votes

# Answer
# C# 63-5 = 58

public string m(int n)=\>n%2==0?(n%4==0?"1":"-1"):(m(n-1)+"i");
> 1 votes

# Answer
# Groovy: 27-5 = 22

```
f={n->[1,'i',-1,'-i'][n%4]}

```
> 1 votes

# Answer
# Ruby, 208 - 15 = 193

```
p=Math::PI/2;t=gets.to_f*p;l=->n{Math::cos(n).round(2)};k=l.call(t);if k!=0;k=k.to_i if k.abs==1;print k;end;m=l.call(t+p);if m!=0;r="i";r='-'+r if m==-1;r="#{m}"+r if 1>m && -1<m;r=" + "+r if k!=0;puts r end

```

This implementation completely conforms to the spec! 1.0 is written as 1, -1.0i is written as -i, etc. I don't see any other solution that incorporates this along with supporting floating points, except for maybe the TI-Calculator.

Ungolfed:

```
p=Math::PI/2
t=gets.to_f*p
l=->n{Math::cos(n).round(2)}

k=l.call(t)
if k!=0
  k=k.to_i if k.abs==1
  print k
end

m=l.call(t+p)
if m!=0
  r="i"
  r='-'+r if m==-1
  r="#{m}"+r if 1>m && -1<m
  r=" + "+r if k!=0
  puts r
end

```
> 1 votes

# Answer
# C, 61

```
main(n){scanf("%d",&n);printf("%c%c",n%4/2*45,n%4%2?'i':49);}

```

Try it here.
> 1 votes

# Answer
# PARI/GP, 26 - 5 = 21

```
n->Str([1,I,-1,-I][n%4+1])

```

`n->cos(t=Pi*n/2)+I*sin(t)` is one character shorter, but doesn't handle exact answers. Of course `n->I^n` is disallowed, and presumably also PARI's `powIs`.
> 1 votes

# Answer
# Java (OpenJDK 8), 39 bytes

```
n->new String[]{"1","i","-1","-i"}[n%4]

```

Try it online!
> 1 votes

# Answer
# Haskell, 27 bytes

```
(cycle(words"1 i -1 -i")!!)

```

Try it online!
> 1 votes

# Answer
# Tcl, 50 bytes

```
proc I n {expr $n%4==3?"-i":$n%4==2?-1:$n%4?"i":1}

```

Try it online!
> 1 votes

# Answer
# 05AB1E, 12 bytes

```
®sfgm¹Éi1'i:

```

Try it online!

---

```
®             # Push -1 onto the stack.
 sfg          # Push the number of prime factors of input.
    m         # -1^(number_prime_factors)
     ¹Éi      # is input even?
        1'i:  # if input was even, replace 1 with i.

```
> 1 votes

# Answer
# Forth (gforth), 53 bytes - 5 bytes (bonus) = 48 bytes

```
: f 4 mod dup 1 > if ." -"then 2 mod 56 * '1 + emit ;

```

Try it online!

This works for both positive and negative numbers

### Code Explanation

```
: f             \ start a new word definition
  4 mod dup     \ get result of n % 4 (and make a copy)
  1 > if        \ if result is 2 or 3
    ." -'       \ print a minus sign
  then          \ end the if
  2 mod 56 *    \ get result modulo 2 and multiply by 56 (difference between ascii for '1' and 'i')
  '1 +          \ add to ascii value of '1'
  emit          \ output the character for the given value
;               \ end the word definition

```
> 1 votes

# Answer
# Zsh, 30 bytes, score 25 (-5)

```
a=({,}{,-}{1,i})
<<<$a[$1%4+5]

```

Try it online!

Based on the bash answer, but with some changes needed:

* `%4` results in a value in the range -3 to 3 (negative inputs give negative outputs), so we shift up with `+5`.
* Arrays are 1-indexed, hence `+5` instead of `+4`.
* We make our array twice as long by using brace expansion: `{,}foo` expands to `foo foo`.
> 1 votes

# Answer
# Google Sheets, 32-15=17

* Input is in A1
* B1: `A1/2*PI(`
* Result: `=COMPLEX(COS(B1),SIN(B1`
> 1 votes

# Answer
# Stax, 9 - 5 = 4 bytes

```
ü▲τ}εT├?á

```

Run and debug it
> 1 votes

# Answer
# Branch, 38 bytes

```
^\4^%/;c1^>/0c45^?[.0]anc2^%/49c105^?.

```

Try it on the online Branch interpreter!

## Explanation

```
      Implicit - the initial node's value is set to the first argument
^\4   Create a parent and sibling and set the right child to 4
%     Modulo
/;    Go to the left child and copy the mod result
c1    Go to the right child (automatically assigned register C) and set it to 1
^     Return to the parent (the mod result)
>     1 if the mod result is greater than 1, 0 otherwise
/0    Go to the left child and set to 0
c45   Go to the right child and set it to 45 (codepoint for "-")
^     Return to the parent
?     Conditional - if the mod was greater, go to the right child (45), and left child (0) otherwise
[  ]  While the value isn't 0
 .    Output it
  0   And set it to zero (this is basically an if statement)
an    Go to the left child and load the first argument (register N by default)
c2    Go to the right child and set it to 2
%     Modulo
/49   Go to the left child and set it to 49 (codepoint for "1")
c105  Go to the right child and set it to 105 (codepoint for "i")
^     Go to the parent
?     Conditional - if the exponent was even, go left, otherwise, go right
.     Output

```
> 1 votes

# Answer
# Lua, 33 - 5 = 28 bytes

```
print(({1,'i',-1,'-i'})[...%4+1])

```

Try it online!
> 1 votes

# Answer
# Go, ~~75~~ 57 bytes, no bonus

```
func(n int)string{return[]string{"1","i","-1","-i"}[n%4]}

```

Try it online!

`if n<0{n=4+n}` is included here because the `%` operator in Go returns negative if the dividend is negative.
> 1 votes

# Answer
# Keg, 15 - 5 = 10 bytes

```
1i0;`-i`¿4%⊙&ø&

```

Try it online!

Pushes the four different possibilities and then takes the input modulo 4 and indexes the stack.
> 0 votes

# Answer
# Vyxal, `r`, 5 - 15 = -10 bytes

```
90*1"

```

Try it Online!

Well if the Ruby answer's output method is valid, so is this. Outputs in "polar form (angular unit: degrees)".

## Explained

```
90*1"
90*   # Multiply the input by 90
   1" # Push one and pair the two inputs. The `-r` flag makes dyads take their arguments in reverse.

```
> 0 votes

# Answer
# Thunno 2, 10 - 5 = 5 bytes

```
`-iu'i1K$i

```

Attempt This Online!

Port of Kevin Cruijssen's 05AB1E answer.

#### Explanation

```
`-iu'i1K$i  '# Implicit input
`-i          # Push the string "-i"
   u         # Push the number -1
    'i      '# Push the string "i"
      1      # Push the number 1
       K     # Wrap the stack into a list
             # -> [1, "i", -1, "-i"]
        $i   # Index the input in
             # (0-based, modular)
             # Implicit output

```
> 0 votes

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


title: Stable Game of Life

text:
# Question
Title: Stable Game of Life
# Challenge:

Given a matrix (or 2d array) of 0s and 1s, output the number of steps it takes for Conway's game of life to reach a stable state, or -1 if it never reaches one. A stable state is a state in which no cells are turned on or off each step. The game must run in the given matrix, with the top and bottom connected, and the sides connected. (i.e. given a 4x3 matrix it should run on a 4x3 torus) The input matrix will not be larger than 15x15.

Note: If the matrix starts in a stable state, the output should be 0.

# Samples:

**Input:**

```
[[0,0,0],
 [0,1,1],
 [0,1,0]]

```

**Output:**

2

**Process:** (this does not need to be displayed)

```
[[0,0,0],
 [0,1,1],
 [0,1,0]]

[[1,1,1],
 [1,1,1],
 [1,1,1]]

[[0,0,0],
 [0,0,0],
 [0,0,0]]

```

**Input:**

```
[[0,0,1,1],
 [0,1,1,1],
 [0,1,0,0],
 [0,1,1,1]]

```

**Output:**

2

**Process:**

```
[[0,0,1,1],
 [0,1,1,1],
 [0,1,0,0],
 [0,1,1,1]]

[[0,0,0,0],
 [0,1,0,1],
 [0,0,0,0],
 [0,1,0,1]]

[[0,0,0,0],
 [0,0,0,0],
 [0,0,0,0],
 [0,0,0,0]]

```

**Input:**

```
[[0,1,0,0],
 [0,1,0,0],
 [0,1,0,0],
 [0,0,0,0]]

```

**Output:**

-1

**Process:**

```
[[0,1,0,0],
 [0,1,0,0],
 [0,1,0,0],
 [0,0,0,0]]

[[0,0,0,0],
 [1,1,1,0],
 [0,0,0,0],
 [0,0,0,0]]

[[0,1,0,0],
 [0,1,0,0],
 [0,1,0,0],
 [0,0,0,0]]

```

repeating forever

**Input:**

```
[[0,0,0,0],
 [0,0,0,1],
 [0,1,1,1],
 [0,0,1,0]]

```

**Output:**

4

**Process:**

```
[[0,0,0,0],
 [0,0,0,1],
 [0,1,1,1],
 [0,0,1,0]]

[[0,0,0,0],
 [1,0,0,1],
 [1,1,0,1],
 [0,1,1,1]]

[[0,1,0,0],
 [0,1,1,1],
 [0,0,0,0],
 [0,1,0,1]]

[[0,1,0,1],
 [1,1,1,0],
 [0,1,0,1],
 [1,0,1,0]]

[[0,0,0,0],
 [0,0,0,0],
 [0,0,0,0],
 [0,0,0,0]]

```

**Input:**

```
[[0,0,0,0],
 [0,1,1,0],
 [0,1,1,0],
 [0,0,0,0]]

```

**Output:**

0

**Process:**

The beginning state is stable.

# Rules of the Game of Life

If a cell that is off (0) is next to exactly three on (1) cells, it is turned on. Otherwise, it is left off. If a cell that is on is next to 2 or 3 on squares, it says on. Otherwise, it is turned off.

# Answer
## Mathematica, ~~130~~ 129 bytes

```
#&@@FirstPosition[Partition[CellularAutomaton[{224,{2,{{2,2,2},{2,1,2},{2,2,2}}},{1,1}},#,2^Length[Join@@#]],2,1],{x_,x_},0,1]-1&

```

I wouldn't recommend trying more than 4x4 inputs, because it's going to take forever (and a *lot* of memory).

### Explanation

This simply simulates the Game of Life for *2N* steps where *N* is the number of cells in the input. This guarantees that if the system settles into a stable state, we've reached it. Afterwards, we find the first pair of consecutive identical states in the simulated history.

Let's go through the code:

```
2^Length[Join@@#]

```

This computes *2N*, since `Join@@` is used to flatten a 2D list.

```
CellularAutomaton[{224,{2,{{2,2,2},{2,1,2},{2,2,2}}},{1,1}},#,...]

```

This simulates the Game of Life for *2N* generations. The 3x3 matrix specifies the neighbourhood of a totalistic 2D automaton and `224` is the rule number of standard Game of Life. I've written about how to compute this number over here on Mathematica.SE.

```
Partition[...,2,1]

```

This gets all consecutive (overlapping) pairs of generations.

```
FirstPosition[...,{x_,x_},0,1]

```

This finds the first pair of identical generations, defaulting to `0` if none is found and limiting the search to depth `1`. If such a pair *is* found, the result is returned in a list though. So we use:

```
#&@@...

```

To extract the first element from that list (the default value of `0`, being atomic, is unaffected by this).

```
...-1

```

Finally we subtract one because the challenge expects `0`-based indices and `-1` for failure.
> 11 votes

# Answer
## Lua, ~~531~~ ~~509~~ ~~488~~ ~~487~~ ~~464~~ ~~424~~ ~~405~~ 404 Bytes

Who wants a massive submission? \o/

**Edit: Improved it, but don't know how to golf it anymore, so... ~~explanations are coming~~ comments added :)**

**Saved ~60 bytes with the help of @KennyLau**

**small golfing cutting one more byte by renaming `a` into `Y` to prevent the inlined hexadecimal conversion**

```
function f(m)c={}t=table.concat::z::c[#c+1]={}p=c[#c]Y={}for i=1,#m do k=m[i]p[#p+1]=t(k)Y[i]={}for j=1,#k
do v=m[i%#m+1]l=j%#k+1w=m[(i-2)%#m+1]h=(j-2)%#k+1Y[i][j]=v[l]+k[l]+w[l]+v[h]+v[j]+w[h]+w[j]+k[h]end
end s=''for i=1,#m do k=m[i]for j=1,k do
x=Y[i][j]k[j]=k[j]>0 and((x<2or x>3)and 0or 1)or (x==3 and 1or 0)end
s=s..t(k)end for i=1,#c do
if(s==t(c[i]))then return#c>i and-1or i-1
end end goto z end

```

### Ungolfed

```
function f(m)                -- takes a 2D array of 0 and 1s as input
  c={}                       -- intialise c -> contains a copy of each generation
  t=table.concat             -- shorthand for the concatenating function
  ::z::                      -- label z, used to do an infinite loop
    c[#c+1]={}               -- initialise the first copy
    p=c[#c]                  -- initialise a pointer to this copy
    a={}                     -- initialise the 2D array of adjacency
    for i=1,#m               -- iterate over the lines of m
    do
      k=m[i]                 -- shorthand for the current line
      p[#p+1]=t(k])          -- saves the current line of m as a string
      a[i]={}                -- initialise the array of adjacency for the current line
      for j=1,#k             -- iterate over each row of m
      do
                             -- the following statements are used to wraps at borders
        v=m[i%#m+1]          -- wrap bottom to top
        l=j%#k+1             -- wrap right to left
        w=m[(i-2)%#m+1]      -- wrap top to bottom
        h=(j-2)%#k+1         -- wrap left to right

        a[i][j]= v[l]        -- living cells are 1 and deads are 0
                +k[l]        -- just add the values of adjacent cells
                +w[l]        -- to know the number of alive adjacent cells
                +v[h]
                +v[j]
                +w[h]
                +w[j]
                +k[h]
      end
    end

    s=''                     -- s will be the representation of the current generation
    for i=1,#m               -- iterate over each line
    do
      k=m[i]                 -- shorthand for the current line
      for j=1,#k             -- iterate over each row
      do
        x=a[i][j]            -- shorthand for the number of adjacent to the current cell
                             -- the next line change the state of the current cell
        k[j]=k[j]>0          -- if it is alive
                and((x<2     --   and it has less than 2 adjacent
                    or x>3)  --   or more than 3 adjacent
                  and 0      --     kill it
                  or 1)      --     else let it alive
                or           -- if it is dead
                  (x==3      --   and it has 3 adjacent
                  and 1      --     give life to it
                  or 0)      --     else let it dead
      end
      s=s..t(k)              -- save the representation of the current line
    end
    for i=1,#c               -- iterate over all the generation done until now
    do
      if(s==t(c[i]))         -- if the representation of the current generation
      then                   -- is equal to one we saved
        return#c>i           -- check if it is the latest generation
              and-1          -- if it isn't, it means we are in a loop -> return -1
              or i-1         -- if it is, we did 2 generations without changing
                             --  -> return the number of generation
      end
    end
  goto z                     -- if we reach that point, loop back to the label z
end

```

### Test cases

Here's some test cases

```
function f(m)c={}t=table.concat::z::c[#c+1]={}p=c[#c]a={}for i=1,#m do k=m[i]p[#p+1]=t(k)a[i]={}for j=1,#k
do v=m[i%#m+1]l=j%#k+1w=m[(i-2)%#m+1]h=(j-2)%#k+1
a[i][j]=v[l]+k[l]+w[l]+v[h]+v[j]+w[h]+w[j]+k[h]end
end s=''for i=1,#m do k=m[i]for j=1,k do
x=a[i][j]k[j]=k[j]>0 and((x<2or x>3)and 0or 1)or (x==3 and 1or 0)end
s=s..t(k)end for i=1,#c do
if(s==t(c[i]))then return#c>i and-1or i-1
end end goto z end

print(f({{0,0,0},{0,1,1},{0,1,0}}))
print(f({{0,1,0,0},{0,1,0,0},{0,1,0,0},{0,0,0,0}}))
-- 53 generation, 15x15, takes 50-100 ms on a bad laptop
print(f({{0,0,0,0,1,1,0,1,0,0,0,0,1,0,0},
       {0,1,1,0,1,1,1,1,1,1,1,0,0,0,0},
       {0,1,1,1,0,1,0,1,0,0,0,0,1,0,0},
       {0,0,1,0,1,1,1,0,0,1,1,1,0,1,1},
       {1,1,0,0,1,1,1,0,1,1,0,0,0,1,0},
       {0,0,0,0,1,1,0,1,0,0,0,0,1,0,0},
       {0,1,1,0,1,1,1,1,1,1,1,0,0,0,0},
       {0,1,1,1,0,1,0,1,0,0,0,0,1,0,0},
       {0,0,1,0,1,1,1,0,0,1,1,1,0,1,1},
       {1,1,0,0,1,1,1,0,1,1,0,0,0,1,0},
       {0,0,1,0,1,1,1,0,0,1,1,1,0,1,1},
       {1,1,0,0,1,1,1,0,1,1,0,0,0,1,0},
       {0,0,0,0,1,1,0,1,0,0,0,0,1,0,0},
       {0,0,0,0,1,1,0,1,0,0,0,0,1,0,0},
       {0,1,1,0,1,1,1,1,1,1,1,0,0,0,0}}))
-- Glider on a 15x14 board
-- 840 distinct generation
-- loop afterward -> return -1
-- takes ~4-5 seconds on the same bad laptop
print(f({{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,0,1,0,0,0,0,0,0,0,0,0,0},
       {0,0,0,0,0,1,0,0,0,0,0,0,0,0,0},
       {0,0,0,1,1,1,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,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,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},
       {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,0,0,0,0,0,0,0,0,0,0,0,0}}))

```
> 8 votes

# Answer
# Perl, ~~154~~ ~~151~~ ~~144~~ ~~140~~ ~~137~~ ~~133~~ 129 bytes

Includes +3 for `-ap0`

Run with the input as a line of groups of digits separated by space

```
life.pl <<< "0000 0001 0111 0010"

```

This is only really needed in case the input is immediately stable. In all other cases you can also more conveniently give it as seperate lines of digits:

```
life.pl
0000
0001
0111
0010
^D

```

Giving input this way would however give 1 instead of 0 for an immediately stable configuration.

`life.pl`:

```
#!/usr/bin/perl -ap0
map{@f=map$F[$_%@F]x3,$i-1..++$i;s%.%"0+($&+33)=~grep\$_,map{(//g)[@--1..@+]}\@f"%eeg}@Q=@F;$_=/@Q/?keys%n:$n{$_="@Q"}--||redo

```

Almost beating Mathematica on this one...

Only on older perl versions (where you could use a constant as a variable) does this 126 byte solution work:

```
#!/usr/bin/perl -p0a
map{@f=map$F[$_++%@F]x2,-1..1;s%.%"0+($&+33)=~grep\$_,map{(//g)[@--1..@+]}\@f"%eeg}@Q=@F;$_=/@Q/?keys%n:$n{$_="@Q"}--||redo

```

In case there are certain to be at least 2 rows this 123 byte solution works on all perl versions:

```
#!/usr/bin/perl -p0a
@F=@F[-$#F..!s%.%"0+($&+33)=~grep\$_,map{(//g,//g)[@--1..@+]}\@F[-1..1]"%eeg]for@Q=@F;$_=/@Q/?keys%n:$n{$_="@Q"}--||redo

```
> 6 votes

# Answer
# Jelly, ~~26~~ 25 bytes

```
ṙ-r1¤SZµ⁺_|=3
ÇÐĿ-LiṪÇ$$?

```

Try it online! or verify all test cases.

Larger test cases (from @Katenkyo's answer): 15×15 stable | 15×14 glider

### How it works

```
ṙ-r1¤SZµ⁺_|=3  Helper link. Argument: G (grid)
               This link computes the next state of G.

    ¤          Evaluate the three links to the left as a niladic chain.
 -               Yield -1.
   1             Yield 1.
  r              Range; yield [-1, 0, 1].
ṛ              Rotate the rows of G -1, 0 and 1 units up.
     S         Compute the sum of the three resulting grids.
               Essentially, this adds the rows directly above and below each given
               row to that row.
      Z        Zip; transpose rows and columns.
       µ       Convert the preceding chain into a link and begin a new chain.
        ⁺      Apply the preceding chain once more.
               This zips back and adds the surrounding columns to each column.
         _     Subtract G from the result.
               Each cell now contains the number of lit cells that surround it.
          |    That the bitwise OR of the result and G.
               Notably, 3|0 = 3|1 = 2|1 = 3.
           =3  Compare each resulting number with 3.

ÇÐĿ-LiṪÇ$$?    Main link. Argument: G (grid)

ÇÐL            Repeatedly apply the helper link until the results are no longer
               unique. Collect all unique results in a list.
         $     Evaluate the two links to the left as a monadic chain:
        $        Evaluate the two links to the left as a monadic chain:
      Ṫ            Pop the last element of the list of grids.
       Ç           Apply the helper link to get the next iteration.
     i           Get the index of the grid to the right (the first non-unique one)
                 in the popped list of grids. This yields 0 iff the popped list
                 doesn't contain that grid, i.e., the grid reached a stable state.
          ?    If the index is non-zero:
   -             Return -1.
    L            Else, return the length of the popped list of grids.

```
> 5 votes

# Answer
# Julia, ~~92~~ 88 bytes

```
f(x,r...)=x∈r?(r[k=end]==x)k-1:f(sum(i->circshift(x,[i÷3,i%3]-1),0:8)-x|x.==3,r...,x)

```

### Verification

```
julia> f(x,r...)=x∈r?(r[k=end]==x)k-1:f(sum(i->circshift(x,[i÷3,i%3]-1),0:8)-x|x.==3,r...,x)
f (generic function with 1 method)

julia> f([0 0 0;0 1 1;0 1 0])
2

julia> f([0 0 1 1;0 1 1 1;0 1 0 0;0 1 1 1])
2

julia> f([0 1 0 0;0 1 0 0;0 1 0 0;0 0 0 0])
-1

julia> f([0 0 0 0;0 0 0 1;0 1 1 1;0 0 1 0])
4

julia> f([0 0 0 0;0 1 1 0;0 1 1 0;0 0 0 0])
0

julia> f([0 0 0 0 1 1 0 1 0 0 0 0 1 0 0;0 1 1 0 1 1 1 1 1 1 1 0 0 0 0;0 1 1 1 0 1 0 1 0 0 0 0 1 0 0;0 0 1 0 1 1 1 0 0 1 1 1 0 1 1;1 1 0 0 1 1 1 0 1 1 0 0 0 1 0;0 0 0 0 1 1 0 1 0 0 0 0 1 0 0;0 1 1 0 1 1 1 1 1 1 1 0 0 0 0;0 1 1 1 0 1 0 1 0 0 0 0 1 0 0;0 0 1 0 1 1 1 0 0 1 1 1 0 1 1;1 1 0 0 1 1 1 0 1 1 0 0 0 1 0;0 0 1 0 1 1 1 0 0 1 1 1 0 1 1;1 1 0 0 1 1 1 0 1 1 0 0 0 1 0;0 0 0 0 1 1 0 1 0 0 0 0 1 0 0;0 0 0 0 1 1 0 1 0 0 0 0 1 0 0;0 1 1 0 1 1 1 1 1 1 1 0 0 0 0])
53

julia> f([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 0 1 0 0 0 0 0 0 0 0 0 0;0 0 0 0 0 1 0 0 0 0 0 0 0 0 0;0 0 0 1 1 1 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 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 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;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 0 0 0 0 0 0 0 0 0 0 0 0])
-1

```
> 2 votes

# Answer
# ruby, 207 bytes

```
->a{r=[];(r<<a;a=(0...a.size).map{|i|(0...a[i].size).map{|j|n=0;(-1..1).map{|u|(-1..1).map{|v|n+=a[(i+u)%a.size][(j+v)%a[i].size]}};[n==3,n>2&&n<5][a[i][j]]?1:0}})while(!r.index(a));(a==r[-1])?r.index(a):-1}

```

I keep a history of each board, so if I get a board I have seen before I know one of two thing happened. first it could be that we have found a stable position, in which case it will be the most resent in our history. the other possibility is that we have a loop.
> 1 votes

# Answer
# Python 3.8, 268 262 260 bytes

Had fun w a little convolution. Code stores prev generations as byte array. Cuts off at 1000 iterations for the sake of not chasing an infinite starting matrix, but can be easily changed to any number of iterations or removed.

note: There's a deprecation for scipy arrays coming in scipy 2.0.0 so this only works on previous versions.

```
import scipy as s
def g(b,n=0,L=[0]):
 if n>1e3:return-1
 b=s.array(b);j=b.tobytes()
 if j==L[-1]:return n-1
 if j in L: return-1
 L+=[j];f=[[1]*3]*3;f[1][1]=0
 x=s.ndimage.convolve(b,f,mode='wrap')
 b[x<2]=0;b[x>3]=0;b[x==3]=1
 n=g(b,n+1,L)
 return n

```

I'm sure there's more to shave off, please lmk!
> 1 votes

# Answer
# Octave, ~~275~~ ~~213~~ ~~206~~ 202 bytes

Implementation.

Saved 73 bytes thanks to the comment of @ceilingcat

---

Golfed version. Try it online!

```
function s=f(x);p=[];for s=0:1e3;if isequal(x,p);--s;return;end;[m,n]=size(y=p=x);for i=1:m;for j=1:n;z=x(i,j);s=sum(x(mod(i-2:i,m)+1,mod(j-2:j,n)+1)(:))-z;y(i,j)=s==2&z==1|s==3;end;end;x=y;end;s=-1;end

```

Ungolfed version. Try it online!

```
function steps = f(x)
  max_iterations = 1000;  % set a max limit to stop infinite loops
  prev_x = [];
  for steps = 0:max_iterations
    if isequal(x, prev_x)
      steps=steps-1;
      return
    end
    prev_x = x;
    x = next_generation(x);
  end
  steps = -1;  % did not reach a stable state within max_iterations
end

function y = next_generation(x)
  [m, n] = size(x);
  y = zeros(m, n);
  for i = 1:m
    for j = 1:n
      % count the number of live neighbors, taking into account the torus shape
      neighbors = x(mod(i-2:i, m)+1, mod(j-2:j, n)+1);
      num_live_neighbors = sum(neighbors(:)) - x(i, j);
      if x(i, j) == 1  % if the cell is alive
        y(i, j) = num_live_neighbors == 2 || num_live_neighbors == 3;
      else  % if the cell is dead
        y(i, j) = num_live_neighbors == 3;
      end
    end
  end
end

disp(f([0 0 0;0 1 1;0 1 0]))
disp(f([0 0 1 1;0 1 1 1;0 1 0 0;0 1 1 1]))
disp(f([0 1 0 0;0 1 0 0;0 1 0 0;0 0 0 0]))
disp(f([0 0 0 0;0 0 0 1;0 1 1 1;0 0 1 0]))
disp(f([0 0 0 0;0 1 1 0;0 1 1 0;0 0 0 0]))
disp(f([0 0 0 0 1 1 0 1 0 0 0 0 1 0 0;0 1 1 0 1 1 1 1 1 1 1 0 0 0 0;0 1 1 1 0 1 0 1 0 0 0 0 1 0 0;0 0 1 0 1 1 1 0 0 1 1 1 0 1 1;1 1 0 0 1 1 1 0 1 1 0 0 0 1 0;0 0 0 0 1 1 0 1 0 0 0 0 1 0 0;0 1 1 0 1 1 1 1 1 1 1 0 0 0 0;0 1 1 1 0 1 0 1 0 0 0 0 1 0 0;0 0 1 0 1 1 1 0 0 1 1 1 0 1 1;1 1 0 0 1 1 1 0 1 1 0 0 0 1 0;0 0 1 0 1 1 1 0 0 1 1 1 0 1 1;1 1 0 0 1 1 1 0 1 1 0 0 0 1 0;0 0 0 0 1 1 0 1 0 0 0 0 1 0 0;0 0 0 0 1 1 0 1 0 0 0 0 1 0 0;0 1 1 0 1 1 1 1 1 1 1 0 0 0 0]))
disp(f([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 0 1 0 0 0 0 0 0 0 0 0 0;0 0 0 0 0 1 0 0 0 0 0 0 0 0 0;0 0 0 1 1 1 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 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 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;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 0 0 0 0 0 0 0 0 0 0 0 0]))

```
> 1 votes

---
Tags: code-golf, grid, cellular-automata, game-of-life
---


title: Generate the Abacaba sequence

text:
# Question
Title: Generate the Abacaba sequence
This challenge is about printing the abacaba sequence of a specific depth.

Here is a diagram of the first 5 sequences (`a(N)` is the abacaba sequence of depth N, upper/lowercase is just to show the pattern, this is not needed in the output of your program):

```
a(0) = A
a(1) = aBa
a(2) = abaCaba
a(3) = abacabaDabacaba
a(4) = abacabadabacabaEabacabadabacaba
...
a(25) = abacabadabacabaeabacabadabacabafabacabadabacabaeabacabadabacabagabacabadabacabaeabacabadabacabafabacabadabacabaeabacabadabacabahabacabadabacabaeabacabadabacabafabacabadabacabaeabacabadabacabagabacabadabacabaeabacabadabacabafabacabadabacabaeabacabadabacabaiabacabadabacabaeabacabadabacabafabacabadabacabaeabacabadabacabagabacabadabacabaeabacabadabacabafabacabadabacabaeabacabadabacabahabacabadabacabaeabacabadabacabafabacabadabacabaeabacabadabacabagabacabadabacabaeabacabadabacabafabacabadabacabaeabacabadabacabajabacabadabacabaeabacabadabacabafabacabadabacabaeabacabadabacabagabacabadabacabaeabacabadabacabafabacabadabacabaeabacabadabacabahabacabadabacabaeabacabadabacabafabacabadabacabaeabacabadabacabagabacabadabacabaeabacabadabacabafabacabadabacabaeabacabadabacabaia...

```

As you can probably tell, the n'th abacaba sequence is the last one with the n'th letter and itself again added to it. (`a(n) = a(n - 1) + letter(n) + a(n - 1)`)

Your task is to make a program or function that takes an integer and prints the abacaba sequence of that depth. The output has to be correct at least for values up to and including 15.

# Answer
# Pyth, 11 bytes

```
u++GHG<GhQk

```

Simple reduction.
> 9 votes

# Answer
## Python, 44 bytes

```
f=lambda n:"a"[n:]or f(n-1)+chr(97+n)+f(n-1)

```

Looks suspiciously might-be-golfable.
> 7 votes

# Answer
## Haskell, ~~39~~ 37 bytes

```
a 0="a"
a n=a(n-1)++['a'..]!!n:a(n-1)

```

Usage example: `a 3` -\> `"abacabadabacaba"`.

Edit: @Angs found two bytes to save. Thanks!
> 7 votes

# Answer
# Pyth, ~~14~~ 13 bytes

Thanks to Jakube for saving a byte!

```
VhQ=+k+@GNk;k

```

A solution with 14 bytes: `VhQ=ks[k@GNk;k`.

Explanation:

```
VhQ=+k+@GNk;k

               # Implicit: k = empty string
VhQ            # For N in range input + 1
   =           # Assign k
      +@GNk    # Position N at alphabet + k
    +k         # k + above
           ;   # End loop
            k  # Print k

```

Try it here!
> 6 votes

# Answer
# Brainfuck, 157 bytes

```
,+>-[>++<-----]>----->>+<<<<[->>[[->>[>>>]<+<+<[<<<]>>[>>>]<]>>[>>>]<[-<<[<<<]>>[>>>]<+>>[>>>]<]+>+<<<[<<<]>>[>>>]+[>>>]<]<<<+>>[<-<<]<]>>>>[>>>]<<<<<<[<<.<]

```

Input is given in binary.

The basic idea is to repeatedly duplicate the current sequence (starting with "a") and to increment the last element after each iteration:

1. a → aa → ab
2. ab → abab → abac
3. abac → abacabac → abacabac
4. ...

When all of this has been done the specified amount of times, the result gets printed excluding the last element.

## In-depth explanation

The memory is arranged in the following way:

```
.---------.-.-----.----.---.-----.----.---.---
|Countdown|0|Value|Copy|End|Value|Copy|End|...
'---------'-'-----'----'---'-----'----'---'---

            |--Element 1---|--Element 2---|

```

**Countdown** holds the number of copy cycles that are yet to be executed. The ABACABA sequence is stored in adjecent blocks, each made up of 3 cells. **Value** holds the character of the element (i.e. "A","B","C"...). The **Copy** flag indicates whether or not the corresponding element needs to be copied within the current copying cycle (0=copy, 1=don't). The **End** flag is set to 0 for the last element while it is being copied (it's 1 in all other cases).

Now to the actual (slightly ungolfed) program:

```
,                       read Countdown from input
+                       add 1 to avoid off-by-one error
>-[>++<-----]>-----     initialize value cell of first element to 97 ("a")
>>+                     set End flag of first element to 1
<<<<                    move to Countdown
[                       loop until Countdown hits 0 (main loop)
    -                   decrement Countdown
    >>                  move to Value cell of first element
    [                   copying loop
        [               duplication sub-loop
            -           decrement Value cell of the element to copy
            >>          move to End flag
            [>>>]       move to End flag of the last element
            <+<+        increment Copy and Value cell of last element (Copy cell is temporarily abused)
            <           move to End flag of second to last element
            [<<<]>>     move back to Copy cell of first element
            [>>>]<      move to Value cell of the first element where the Copy flag is 0
        ]
        >>[>>>]<        move to (abused) Copy flag of the last element
        [               "copy back" sub-loop
            -           decrement Copy flag
            <<          move to End flag of second to last element
            [<<<]>>     move back to Copy cell of first element
            [>>>]<      move to Value cell of the first element where the Copy flag is 0
            +           increment Value cell
            >>[>>>]<    move back to Copy flag of the last element
        ]
        +>+             set Copy and End flag to 1
        <<<             move to End flag of second to last element
        [<<<]>>         move back to Copy cell of first element
        [>>>]<          move to Value cell of the first element where the Copy flag is 0
        >+<             set Copy flag to 1
        >[>>>]<         move to Value cell of the next element to copy
    ]                   loop ends three cells behind the last "valid" Value cell
    <<<+                increment Value cell of last element
    >>                  move to End flag
    [<-<<]              reset all Copy flag
    <                   move to Countdown
]
>>>>                    move to End flag of first element
[>>>]<<<                move to End flag of last element
<<<                     skip the last element
[<<.<]                  output Value cells (in reverse order, but that doesn't matter)

```
> 6 votes

# Answer
## Retina, ~~37~~ 32 bytes

```
$
aa
(T`_l`l`.$
)`1(a.*)
$1$1
z

```

The trailing linefeed is significant. Input is taken in unary.

Try it online!
> 5 votes

# Answer
# Haskell, 36 bytes

```
tail.(iterate((:"a").succ=<<)"_a"!!)

```

Try it online!

This uses a different recursive method from most of the other answers. To get the next string in the sequence, we don't join two copies in the previous string with a new letter in between, but instead increment every letter and intersperse `a`'s.

```
aba -> bcb -> abacaba

```
> 5 votes

# Answer
# JavaScript (ES6), ~~43~~ 42 bytes

```
a=n=>n?a(--n)+(n+11).toString(36)+a(n):"a"

```

*A byte saved thanks to @Neil!*

Yet another simple recursive solution...
> 4 votes

# Answer
# 05AB1E, 12 bytes (non-competitive)

Code:

```
'aIGDN>.bsJl

```

I'll be damned. I fixed a lot of bugs thanks to this challenge haha.

Explanation:

```
'aIGDN>.bsJl

'a             # Push the character 'a'
  I            # User input
   G           # For N in range(1, input)
    D          # Duplicate the stack
     N         # Push N
      >        # Increment
       .b      # Convert to alphabetic character (1 = A, 2 = B, etc.)
         s     # Swap the last two elements
          J    # push ''.join(stack)
           l   # Convert to lowercase
               # Implicit: print the last item of the stack

```
> 4 votes

# Answer
# jq `-r`, 43 bytes

```
def f:.-1|[[97]][.+1]//f+[.+98]+f;f|implode

```

Try it online!

---

With the capitalization pattern from the example outputs, 58 bytes:

```
def f:[[65]][.]//([.-1|f[]%32+96,.+66]|.+.)[:-1];f|implode

```

Try it online!

```
def f:    ...       ;  define a filter named f
      [[65]][.]        base case, if the argument . is 0, return [65]
      //               otherwise
         .-1|f         call the filter recursively
         []%32+96      convert each codepoint to lower case
          ,.+66        append .+66 (. is now the filter argument -1)
         [ ... ]       collect all codepoints in an array
         |.+.          and repeat that array twice
         [:-1]         remove the last integer
f|implode              call the filter on the input and convert the result to a string

```
> 4 votes

# Answer
## CJam (14 bytes)

```
'aqi{'b+1$++}/

```

Online demo
> 3 votes

# Answer
# Ruby (1.9 and up), 38 bytes

`?a` is a golfier way to write `"a"` but looks weird when mixed with ternary `?:`

```
a=->n{n<1??a:a[n-1]+(97+n).chr+a[n-1]}

```
> 3 votes

# Answer
# , 48 bytes

```
f=function(n)if(n)paste0(a<-f(n-1),letters[n],a)

```

Try it online!

Simple recursion.
> 3 votes

# Answer
# jq, 51 bytes

```
[range(.)+97|[.]|implode]|reduce.[]as$i("a";.+$i+.)

```

Try it online!

My life has improved significantly since I found `reduce` in this language.

-16 bytes from ovs.
> 3 votes

# Answer
# Labyrinth, 31 bytes

```
_-)"(;;
(. ?  {_
@  +}989
   1_

```

Try it online!

I feel like this can be rearranged to be golfier, but a better layout eludes me. I also have a cleaner 1-indexed version which has a higher ratio of walls. This uses xnor's method of repeatedly incrementing the string and interspersing with `a`s.
> 3 votes

# Answer
# Python, ~~62~~ ~~54~~ ~~46~~ 45 bytes

I would like to think that this code can still be golfed down somehow.

Edit: Bug fix thanks to Lynn. -1 byte thanks to squid.

```
a=lambda n:n and a(n-1)+chr(97+n)+a(n-1)or'a'

```

Try it online!
> 2 votes

# Answer
# C#, 59 bytes

```
string a(int n){return n<1?"a":a(n-1)+(char)(97+n)+a(n-1);}

```

Just another C# solution...
> 2 votes

# Answer
# Perl, 33 bytes

```
map$\.=chr(97+$_).$\,0..pop;print

```

No real need for un-golfing. Builds the string up by iteratively appending the next character in sequence plus the reverse of the string so far, using the ASCII value of 'a' as its starting point. Uses `$\` to save a few strokes, but that's about as tricky as it gets.

Works for `a(0)` through `a(25)` and even beyond. Although you get into extended ASCII after `a(29)`, you'll run out of memory long before you run out of character codes:

`a(25)` is ~64MiB. `a(29)` is ~1GiB.

To store the result of `a(255)` (untested!), one would need 2^256 - 1 = 1.15x10^77 bytes, or roughly **1.15x10^65 1-terabyte drives.**
> 2 votes

# Answer
# MATL, 14 bytes

```
0i:"t@whh]97+c

```

This uses version 8.0.0 of the language/compiler, which is earlier than the challenge.

### Example

```
>> matl
 > 0i:"t@whh]97+c
 >
> 3
abacabadabacaba

```

### Explanation

The secuence is created first with numbers `0`, `1`, `2`, ... These are converted to letters `'a'`, `'b'`, `'c'` at the end.

```
0         % initiallize: a(0)
i:        % input "N" and create vector [1, 2, ... N]
"         % for each element of that vector
  t       % duplicate current sequence
  @       % push new value of the sequence
  whh     % build new sequence from two copies of old sequence and new value
]         % end for
97+c      % convert 0, 1, 2, ... to 'a', 'b', 'c'. Implicitly print

```

### Edit

**Try it online!**
> 2 votes

# Answer
# Mathematica, ~~36~~ 32 bytes

```
##<>#&~Fold~Alphabet[][[;;#+1]]&

```

Have you ever watched TWOW 11B?
> 2 votes

# Answer
# Java 7, 158 bytes

```
class B{public static void main(String[]a){a('a',Byte.valueOf(a[0]));}static void a(char a,int c){if(c>=0){a(a,c-1);System.out.print((char)(a+c));a(a,c-1);}}}

```

I like to lurk around PPCG and I would enjoy being able to vote/comment on other answers.

Input is given as program parameters. This follows the same format as many other answers here in that it's a straight forward recursive implementation. I would have commented on the other answer but I don't have the rep to comment yet. It's also slightly different in that the recursive call is done twice rather than building a string and passing it along.
> 2 votes

# Answer
# Husk, 12 bytes

```
!¡S+oṠ:o→▲"a

```

Try it online!

Uses 1-based indexing, which I hope is OK.

## Explanation

```
!             (                                          !!)
 ¡             iterate(                              )
  S                        <*>
   +                   (++)
    o                         (                     )
     Ṡ                         join$   .
      :                             (:)
       o                                    .
        →                               succ
         ▲                                   maximum
          "a                                          "a"

              (iterate((++)<*>(join$(:).succ.maximum))"a"!!)

```
> 2 votes

# Answer
# Vim, 35 bytes

```
:h<_
jjYZZpqqv|yPyl/<c-r>"
xq{Dddl@-@qD

```

Try it online!

### Explanation

The buffer starts with a single line containing the input integer.

```
:h<_
jjYZZp

```

Yank the lowercase alphabet from the help file. Paste it on a new line below the integer, leaving the cursor on the first character of the second line.

```
qq

```

Start recording macro `q`. This will be our "loop."

```
v|y

```

Using visual mode, select everything from the current character to the beginning of the line, inclusive, and yank it. This leaves the cursor on the first character of the line.

```
P

```

Paste the yanked text to the left of the cursor. The cursor is now on the last of the pasted characters.

```
yl

```

Yank that character.

```
/<c-r>"
x

```

Find the next occurrence of the just-yanked character. Delete it.

```
q

```

Stop recording the macro. Conveniently, this first time through the macro has left the alphabet unchanged. The only effect is that the cursor has moved from the `a` to the `b`.

```
{Dddl

```

Go to the beginning of the buffer. Delete the contents of the first line (the input number). Then delete the (now-empty) first line. Move the cursor one character to the right so as to start on `b`.

```
@-@q

```

Execute the macro *N* times, where *N* is the number we just deleted.

```
D

```

Delete the unused remainder of the alphabet.

---

Normally, the `@-@q` idiom is fraught with peril if the number has a chance of being zero, because `0` is not a valid count in Vim; instead, it is treated as a separate command that move the cursor to the beginning of the line. However, in this particular case, an input of `0` is no problem at all:

```
@-

```

Move the cursor to the beginning of the line.

```
@q

```

Execute the macro once. Recall that executing the macro with the cursor on the `a` leaves the alphabet unchanged and the cursor on the `b`.

```
D

```

Delete everything to the end of the line--which leaves only the `a`, exactly the output we want.
> 2 votes

# Answer
# Knight (v2.0-alpha), 37 bytes

```
;=q+96=n+1P;=x"";W=n-nT=x++xA-q n xOx

```

Try it online!

Expanded

```
; = q (+ 96 (= n (+ 1 PROMPT)))
; = x ""
; WHILE (= n (- n TRUE))
    = x (+ (+ x (ASCII (- q n))) x)
: OUTPUT x

```
> 2 votes

# Answer
# Thunno 2 `J`, 9 bytes

```
Oėıf2c;⁺Ä

```

Attempt This Online!

Port of emanresu A's Vyxal answer.

#### Explanation

```
Oėıf2c;⁺Ä  # Implicit input
O          # Push 2 ** input
 ė         # Push [1..that)
  ı   ;    # Map:
   f       #  Prime factors
    2c     #  Count 2s
       ⁺Ä  # Letter of alphabet
           # Implicit output

```
> 2 votes

# Answer
# Vyxal, 61 bitsv2, 7.625 bytes

```
¤$(nøAȮW∑

```

Try it Online!

Uses 1-indexing.

## Explained

Generated using Luminespire

```
¤$(nøAȮW∑
¤$         # Push an empty string under the input
  (        # For each n in the range [1, input]:
   nøA     #   Get the nth letter of the alphabet
      Ȯ    #   Push a copy of the item under the top of the stack. This leaves the stack as [already generated, new letter, already generated]
       W∑  #   Wrap and sum the stack

```
> 2 votes

# Answer
## JavaScript, ~~65~~ 571 bytes

```
n=>eval('s="a";for(i=0;i<n;i++)s+=(i+11).toString(36)+s')

```

Demo:

```
function a(n){
  return eval('s="a";for(i=0;i<n;i++)s+=(i+11).toString(36)+s')
}
alert(a(3))
```

 1 - thanks Neil for saving 8 bytes
> 1 votes

# Answer
# Mathematica, 46 bytes

```
If[#<1,"a",(a=#0[#-1])<>Alphabet[][[#+1]]<>a]&

```

Simple recursive function. Another solution:

```
a@0="a";a@n_:=(b=a[n-1])<>Alphabet[][[n+1]]<>b

```
> 1 votes

# Answer
# K5, 18 bytes

```
"A"{x,y,x}/`c$66+!

```

Repeatedly apply a function to a carried value (`"A"`) and each element of a sequence. The sequence is the alphabetic characters from B up to some number N (``c$66+!`). The function joins the left argument on either side of the right argument (`{x,y,x}`).

In action:

```
 ("A"{x,y,x}/`c$66+!)'!6
("A"
 "ABA"
 "ABACABA"
 "ABACABADABACABA"
 "ABACABADABACABAEABACABADABACABA"
 "ABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABA")

```
> 1 votes

# Answer
# Japt, ~~20~~ 17 bytes

```
97oU+98 r@X+Yd +X

```

Test it online!

### How it works

```
         // Implicit: U = input integer
65oU+66  // Generate a range from 65 to U+66.
r@       // Reduce each item Y and previous value X in this range with this function:
X+Yd     // return X, plus the character with char code Y,
+X       // plus X.

         // Implicit: output last expression

```

## Non-competing version, 14 bytes

```
97ôU r@X+Yd +X

```

The `ô` function is like `o`, but creates the range `[X..X+Y]` instead of `[X..Y)`. Test it online!

I much prefer changing the 97 to 94, in which case the output for `5` looks like so:

```
^_^`^_^a^_^`^_^b^_^`^_^a^_^`^_^c^_^`^_^a^_^`^_^b^_^`^_^a^_^`^_^

```
> 1 votes

# Answer
## Java, 219 bytes

My first code golf attempt. Probably can be golf'd further, but I'm hungry and going out to lunch.

```
public class a{public static void main(String[]a){String b=j("a",Integer.parseInt(a[0]),1);System.out.println(b);}public static String j(String c,int d,int e){if(d>=e){c+=(char)(97+e)+c;int f=e+1;c=j(c,d,f);}return c;}}

```

Ungolfed:

```
public class a {
    public static void main(String[] a) {
        String string = addLetter("a", Integer.parseInt(a[0]), 1);
        System.out.println(string);
    }

    public static String addLetter(String string, int count, int counter) {
        if (count >= counter) {
            string += (char) (97 + counter) + string;
            int f = counter + 1;
            string = addLetter(string, count, f);
        }
        return string;
    }
}

```

Pretty straightforward brute force recursive algorithm, uses `char` manipulation.
> 1 votes

# Answer
# Powershell, ~~53~~,~~46~~,~~44~~,41 Bytes

```
1..$args[0]|%{}{$d+=[char]($_+96)+$d}{$d}

```

Pasting into console will generate erronous output on the second run since `$d` is not re-initialized.

Save 2 bytes by using += Save 3 bytes thanks to @TimmyD
> 1 votes

# Answer
# Gaia, 14 bytes

```
₵aØ@⟪¤ṇ3ṁ¤+ṫ⟫ₓ

```

Try it online!

```
₵a		| Push lowercase alphabet
  Ø		| push lowercase string
   @         ₓ	| push the input and do everything between ⟪⟫ that many times
    ⟪¤		| swap
      ṇ		| take the last (first) character
       3ṁ	| push the 3rd item on the stack
         ¤+	| swap and concatenate
           ṫ⟫	| and palindromize
```
> 1 votes

# Answer
# Japt, 8 bytes

```
;gCåÈ+iY

```

Try it

```
;gCåÈ+iY     :Implicit input of integer
 g           :Index into
; C          :  Lowercase alphabet
   å         :  Cumulatively reduce, with an initial value of an empty string
    +        :    Append a copy of the current value
     i       :    Prepended with
      Y      :    The current letter

```
> 1 votes

# Answer
# PowerShell, 54 bytes

```
param($n)for(;$n+1){$d+=[char]($i+++97-32*!$n--)+$d}$d

```

Try it online!
> 1 votes

# Answer
# APL(NARS), 24 chars, 48 bytes

```
{⍵<0:⍬⋄k,⎕A[⍵+1],k←∇⍵-1}

```

test:

```
  f←{⍵<0:⍬⋄k,⎕A[⍵+1],k←∇⍵-1}
  f 0
A
  f 1
ABA
  f 2
ABACABA
  f 3
ABACABADABACABA
  f 4
ABACABADABACABAEABACABADABACABA

```
> 1 votes

# Answer
# APL (Dyalog Classic), ~~20 19~~ 17 bytes

```
⎕a[¯1↓⊥¨⍨,⍳2,⎕⍴2]

```

Try it online!

yet another apl answer
> 1 votes

# Answer
# PHP `-r`, 43 bytes

`register_argc_argv` must be enabled for this to work.

```
for($a=$b=a;$argv[1]--;$a.=++$b.$a);echo$a;

```

Try it online!

# PHP, 51 bytes

An anonymous function that prints the output directly.

```
function($n){for($a=$b=a;$n--;$a.=++$b.$a);echo$a;}

```

Try it online!
> 1 votes

# Answer
# Befunge-93, 41 bytes

```
1-011v $<
v::+&_:#^!_:1+v
>:0\:^,+"`"$%:<

```

Try it online!

Probably some room for improvement here.

### Explanation

The sequence is generated using its recursive definition. First, we initialize the stack with the 4 values `(1, input+2), (0, -1)`. Each pair `(a, b)` on the stack is an "instruction" used in generating the sequence, which, when executed, gets popped and does the following:

* if `a == 0`:
    + if `b == -1`, terminate
    + if `b == 0`, do nothing
    + if `b != -1 and b != 0`, print `b+96` as an ASCII character
* if `a != 0`, push `(b-1, b-1), (0, b-1), (b-1, b-1)`

The top two items on the stack are continuously run as a sequence-building instruction until the program terminates.

Worth noting that `&+` is used the first time around to get the input, as well as every subsequent time as a decrement (because when there is no more input, `&` returns -1)
> 1 votes

# Answer
# Lua, 69 bytes

```
f=function(n)return n<1 and"a"or f(n-1)..string.char(97+n)..f(n-1)end

```

Try it online!

# C++ (gcc), ~~58~~ 53 bytes

```
string f(int n){return n--?f(n)+char(98+n)+f(n):"a";}

```

\- 5 bytes saved by `ceilingcat`

Try it online!
> 1 votes

# Answer
# 05AB1E (legacy), 9 bytes

```
AćsI£vDyý

```

Try it online!

Also runs with the new 05AB1E version.

code:

```
A       push the lowercase alphabet
ć       extract first character of that ["bcdefg....", "a"]
s       swap both strings ["a", "bcdefg...."]
I£      drop all letters of the alphabet after the index defined by input
v       for each character
  D     duplicate last stack entry
  yý    join by current letter
        implicitly close for-loop and print top of stack

```
> 1 votes

# Answer
# k4, 23 bytes

```
{.Q.a x{x,(1+|/x),x}/0}

```

---

```
      x{           }/0  / do {func} x times, passing output of last iteration as input (first input is 0)
          (1+|\x)       / 1 + max x
        x,       ,x     / join x either side
 .Q.a                   / index into alphabet

```

executed with inputs \[0,4) we get:

```
  {.Q.a x{x,(1+|/x),x}/0}'[0 1 2 3]
("a";"aba";"abacaba";"abacabadabacaba")

```
> 1 votes

# Answer
# Vyxal `s`, 11 bytes

```
Eɽƛǐ2O;97+C

```

Try it Online!

```
Eɽ          # 0...2**n
  ƛ   ;     # Mapped to...
   ǐ2O      # Count of 2 in prime factorisation
       97+C # Add 97 and get charcodes

```
> 1 votes

# Answer
# Pip, 14 bytes

```
a?z@aWRREa-1'a

```

Takes the integer as a command-line argument. Try it here! Or, here's a 15-byte equivalent in Pip Classic: Try it online!

### Explanation

A recursive full program.

```
a?              ; Is the argument truthy (non-zero)?
                ; If so:
  z@a           ;  Get the letter of the lowercase alphabet at index a
     WR         ;  and wrap it in two copies of
       RE       ;  the result of a recursive call
         a-1    ;  with argument a-1
                ; Otherwise:
            'a  ;  Return the letter a

```
> 1 votes

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

```
a=lambda n:'a'[n:]or(b:=a(n-1))+chr(97+n)+b

```

Try it online!
> 1 votes

# Answer
# Arturo, 48 bytes

```
f:$->x[(0=x)?->"a"->++++f x-1to :char x+97f x-1]

```

Try it!

```
f:$->x[               ; a function named f taking an argument x
    (0=x)?            ; is x zero?
    ->"a"             ; then return "a"
    ->                ; otherwise,
        ++++          ; append three things together
        f x-1         ; f(x-1)
        to :char x+97 ; x converted to character
        f x-1         ; f(x-1)
]                     ; end function

```
> 1 votes

# Answer
# Rockstar, 80 bytes

1-indexed

```
listen to N
X's 0
O's ""
while N-X
cast X+97 in C
let O be+C+O
let X be+1

say O

```

Try it (Code will need to be pasted in)
> 1 votes

# Answer
# Matlab, 54 bytes

Just a straight forward recursive implementation.

```
function s=f(n);s='';if n>-1;k=f(n-1);s=[k,n+97,k];end

```

I first thought I could do better by using anonymous functions, but it turned out to be way longer, but I thougt I still share it:

```
i=@(b,c)c{2-b}();
a=@(n,f)i(n<0,{@()'',@()[f(n-1,f)),n+97,f(n-1,f)]});
ba=@(n)a(n,a);

```
> 0 votes

# Answer
# J, ~~30~~ 28 bytes (Try it online!)

I just found out that `a(0) = "a"`, which chopped of 2 bytes.

```
u:97+(0:`($:@<:,],$:@<:)@.*)

```

Usage:

```
   u:97+(0:`($:@<:,],$:@<:)@.*) 2
abacaba

```

How it works:

```
u:97+(0:`($:@<:,],$:@<:)@.*) n NB. pseudocode:
                               NB. input as n
                               NB. function as generate_tree
u:                             NB.   convert_to_ASCII(
  97+                          NB.     add_to_all(97,
     (xx`yyyyyyyyyyyyyyy@.z)   NB.       if z then y or x:
                          *    NB.         z: n>0?
      0:                       NB.         x: 0
         ($:@<:,],$:@<:)       NB.         y:
          ppppp,q,rrrrr        NB.           concat(p,q,r):
          $:@<:                NB.             p:
          $:@                  NB.               generate_tree(
             <:                NB.                 n-1)
                ]              NB.             q: n
                  $:@<:        NB.             r: generate_tree(n-1)

```
> 0 votes

# Answer
## Pyke, 11 bytes (noncompeting)

```
G@QVk?tQG@:

```

Try it here!

```
G@          - s = alphabet[input]
  QV        - repeat input times:
     ?tQ    -   input -= 1
        G@  -  alphabet[^]
    k     : - s = s.replace("", ^)

```
> 0 votes

# Answer
# Canvas, 8 bytes

```
ø⁸╵ｚｍ｛＋│

```

Try it here!

7 bytes taking the index starting with 1, or hacky 6 bytes by taking input "with a trailing newline" (which together can sum up to 5 bytes)
> 0 votes

# Answer
# Perl 6, 35 bytes

```
{('a',{$_~chr(++$+97)~$_}...*)[$_]}

```

Try it online!
> 0 votes

# Answer
# Jelly, 9 bytes

```
‘R;ṭ¥/ịØa

```

Try it online!

It would be 8 were it not for the requirement for the sequence to start with zero = a.
> 0 votes

# Answer
# JavaScript, 169 bytes

```
x=function(n){var r="";for(var i=1;i<=Math.pow(2,n)-1;i++){for(var j=i;j>=0;j--){if(!(i%Math.pow(2,j))){r+="ABCDEFGHIJKLMNOPQRSTUVWXYZ".slice(0,n)[j];break;}}}return r;}

```

### Try it online!

### Live demo:

```
x=function(n){var r="";for(var i=1;i<=Math.pow(2,n)-1;i++){for(var j=i;j>=0;j--){if(!(i%Math.pow(2,j))){r+="ABCDEFGHIJKLMNOPQRSTUVWXYZ".slice(0,n)[j];break;}}}return r;}

console.log(x(prompt("Input depth of ABACABA Pattern")))
```

### Explanation:

> ```
> x = function(n){ // created function, and yes, I omitted var
>   var r = ""; // declaring variable to be returned
>   for (var i = 1; i <= Math.pow(2, n) - 1; i++){ // this loop creates each letter in the pattern; "Math.pow(2, n) - 1" is the length of the pattern at depth n
>     for (var j = i; j >= 0; j--){ // this loop finds the greatest power of 2 that i is divisible by, since that can be used to find the correct character for that index
>       if (! (i % Math.pow(2, j) ) ){ // the modulo part checks the divisibility of 2^j; the "!" replaces "=== 0"
>         r += "ABCDEFGHIJKLMNOPQRSTUVWXYZ".slice(0,n)[j]; // appending character to r
>         break; // exits loop once greatest power of 2 i is divisible by is found
>       }
>     }
>   }
>   return r;
> }
>
> ```
> 0 votes

# Answer
## Clojure, 63 bytes

```
#(loop[r""i 0](if(= i %)r(recur(str r(char(+ i 97))r)(inc i))))

```
> 0 votes

# Answer
## Mumps (InterSystems), 46 bytes

```
S Q="",A=65 R N F I=0:1:N{S Q=Q_$C(A+I)_Q} W Q

```

InterSystems' version of Mumps (some say M, InterSystems likes to call it "Cache Object Script") allows delineating loops with braces which helps keep things on a single line; GT.M would be a few characters longer.
> 0 votes

# Answer
# Stax, 7 bytes

```
ö▬⌐ç╗à╢

```

Run and debug it

This uses 1-based indexing.

0-based indexing costs another byte
> 0 votes

---
Tags: code-golf, string, sequence
---


title: Is it a completely even number?

text:
# Question
Title: Is it a completely even number?
A completely even number is a positive even integer whose divisors (not including 1) are all even.

Some completely even numbers are:

* 2 (divisors: 2, 1)
* 4 (divisors: 4, 2, 1)
* 16 (divisors: 16, 8, 4, 2, 1)
* 128 (divisors: 128, 64, 32, 16, 8, 4, 2, 1).

Some *non*-completely even numbers are:

* 10 (divisors: 10, 5, 2, 1)
* 12 (divisors: 12, 6, 4, 3, 2, 1)
* 14 (divisors: 14, 7, 2, 1)
* 18 (divisors: 18, 9, 6, 3, 2, 1)
* 1, being odd, is not completely even.

0 is not completely even (it's divisible by all positive integers, including odd numbers) but you **do not** need to handle this.

Your challenge is to take a positive integer as input and output a truthy value if it is completely even and a falsy value if it is not. These outputs do not need to be consistent.

If your solution doesn't return a falsy value for 0, it's encouraged to show what changes would be necessary to make it do so. Especially encouraged is to **show how your solution differs from checking if the input is a power of 2**; in some languages it may be shorter, and in some longer.

Input may be taken via any allowed method, and output may be given via any allowed method.

The shortest code in bytes wins!

# Answer
> 8 votes
# 05AB1E, 2 bytes

```
Óg

```

Try it online!

In 05AB1E only `1` is truthy. Input-`1`-and-input-`0`-verified.

# Answer
> 13 votes
# MATL, 2 bytes

```
qB

```

Try it online!

### How it works

This takes advantage of MATL's convenient interpretation of truthy and falsy. `q` decrements the input and `B` gets the binary representation of the result. This yields a non-empty array of **1**'s (truthy) for even powers of two, an array that is either empty of contains a **0** (falsy) otherwise.

# Answer
> 7 votes
# Jelly, 3 bytes

```
^’>

```

Try it online!

### How it works

```
^’>  Main link. Argument: n

 ’   Decrement; yield n-1.
^    Compute the bitwise XOR of n and n-1.
     This will conserve the highest set bit of n only if n is a power of two.
     If n is even, n-1 will be positive and the result will be different from n.
  >  Test if the result is larger than n.

```

# Answer
> 7 votes
# Python 3, 16 bytes

```
lambda n:n^n-1>n

```

Returns *True* or *False*.

Try it online!

### How it works

* If **n = 0**, then **n ⊕ (n - 1) = 0 ⊕ -1 = -1 \< 0 = n**, so the function returns *False*.
* If **n = 1**, then **n ⊕ (n - 1) = 1 ⊕ 0 = 1 = n**, so the function returns *False*.
* If **2k \< n \< 2k+1**, then **2k ≤ n - 1 \< 2k+1**, so **n** and **n - 1** have the **2k** bit in common,
**n ⊕ (n - 1) \< 2k \< n**, and the function returns *False*.
* Finally, if **n = 2k** with **k \> 0**, then **n = 2k** and **n - 1 = 2k \- 1** have no bits in common, so
**n ⊕ (n - 1) = n + (n - 1) \> n + 0 = n** and the function returns *True*.

# Answer
> 6 votes
# Regex (ECMAScript or better), 17 bytes

`^((x+)(?=\2$))+x$` \- Completely even

Takes its input in unary, as a string of `x` characters whose length represents the number.

**Try it online! \- ECMAScript
Try it online! \- ECMAScript 2018**
Try it online! \- Java
Try it online! \- Perl
Try it online! \- PCRE
Try it online! \- Boost
**Try it online! \- Python**
Try it online! \- Ruby
Try it online! \- .NET

Remarkably, there are *three* completely different 17 byte solutions for Powers of 2, which blew my mind even when I thought there were two. For this challenge, only one is 17 bytes, but for plain Powers of 2 they all are.

---

`^(?!(x(xx)+)\1*$)` \- **17 bytes** \- Powers of 2
`^(?!(x(xx)+)\1*$)x` \- **18 bytes** \- Powers of 2, correct at zero
`^(?!(x(xx)+)\1*$)xx` \- **19 bytes** \- Completely even

| Regex engine | Powers of 2 | Completely even |
| --- | --- | --- |
| ECMAScript | Try it online! | Try it online! |
| Python | Try it online! | Try it online! |
| Ruby | Try it online! | Try it online! |

This is what I came up to solve a level of Regex Golf on 2014-02-21, and was also independently discovered by several others, including earlier than 2013-12-20. It's the one most similar to the well-known primality test, which is probably why most people came up with this one instead of the others.

It asserts that \\$n\\$ has no odd divisors of \\$3\\$ or greater yielding a positive quotient. It has a false positive for zero, since although zero can be divided by any odd number, the quotient is zero, not positive. This can be fixed at the cost of an extra byte: `^(?!(x(xx)+|)\1*$)` or `^(?!(x(xx)+)\1*$)x`.

Since the entire test is inside a (negative) lookahead, it can be adapted to answer this challenge by adding `xx` at the end, which enforces that only \\$n≥2\\$ can match.

---

`^(?!(x*)(\1\1)+$)` \- **17 bytes** \- Powers of 2
`^(?!(x*)(\1\1)+$)xx` \- **19 bytes** \- Completely even

| Regex engine | Powers of 2 | Completely even |
| --- | --- | --- |
| ECMAScript | Try it online! | Try it online! |
| Python | Try it online! | Try it online! |
| Ruby | Try it online! | Try it online! |

This was discovered by Grimmy in 2019-02-05, without fanfare. I on the other hand was amazed, as this has no such flaw as the other negative assertion – it does not match zero.

It asserts that \\$n\\$ has no divisors yielding an odd quotient of \\$3\\$ or greater. As a negative assertion, it does not consume the power of 2 that it matches, and thus is great for use in larger regexes where it doesn't need to be wrapped in a lookahead to allow other tests to be done on the same value of \\$tail\\$.

The downside is that in standard regex engines, it's significantly slower than `^(?!(x(xx)+|)\1*$)`. In my regex engine though, they're both statically optimized into a bitwise power of 2 test unless optimizations are disabled.

---

`^((x+)(?=\2$))*x$` \- **17 bytes** \- Powers of 2
`^((x+)(?=\2$))+x$` \- **17 bytes** \- Completely even

| Regex engine | Powers of 2 | Completely even |
| --- | --- | --- |
| ECMAScript | Try it online! | Try it online! |
| Python | Try it online! | Try it online! |
| Ruby | Try it online! | Try it online! |

I discovered this one in 2014-02-21, after being mentally primed by solving teukon's Dominoes 2 puzzle (which is now included in Regex Golf); teukon independently came up with it later that same day. It was the very first problem in unary that we solved by repeatedly decreasing \\$tail\\$ in a loop while retaining an invariant property at every step, and is probably the simplest function that is best golfed by being solved that way.

It repeatedly divides \\$tail\\$ by \\$2\\$ (asserting each time that there is no remainder) as many times as possible, and then asserts that the end result is \\$1\\$. This one is useful in larger regexes when it is desirable to consume the identified power of 2.

It is the most suitable for solving this challenge, “Is it a completely even number?”, as the only change necessary is upping the minimum iteration count of the loop from `0` to `1` by changing the `*` quantifier to a `+`, at a cost of 0 bytes. This enforces that \\$n\\$ must be evenly divided by \\$2\\$ at least once before yielding an end result of \\$1\\$.

# Answer
> 5 votes
# Python 2, 18 bytes

```
lambda x:~-x&x<1<x

```

Try it online!

-3 thanks to Rod.

# Answer
> 5 votes
## JavaScript (ES6), 14 bytes

```
f=
n=>n>1>(n&n-1)
```

```
<input type=number min=0 oninput=o.textContent=f(this.value)><pre id=o>
```

Python doesn't have the monopoly on chained comparisons!

# Answer
> 3 votes
# Japt, 6 bytes

```
õ!² øU

```

Test it

---

## Explanation

Generate an array of integers (`õ`) from `1` to input `U`. Raise 2 to the power of each (). Check if the array includes (`ø`) `U`.

# Answer
> 3 votes
# Husk, 3 bytes

Returns `log₂(x)` if True `0` otherwise

```
£İ2

```

### Explanation

```
£       Is it an element of the increasing sequence
 İ2     powers of two (starting at 2)

```

Try it online!

# Answer
> 3 votes
# Python 2, 33 bytes

```
lambda n:bin(n).count('1')==1-n%2

```

Try it online!

## Recusive approach, ~~38~~ 36 bytes

-2 bytes thanks to Leaky Nun

```
f=lambda n:n>1if n<3else f(~n%2*n/2)

```

Try it online!

# Answer
> 3 votes
# Implicit, ~~7~~ ~~2~~ 3 bytes

```
½?ö

```

Try it online! Explanation:

```
     implicit float input
½    calculate log2(input)
 ?   if truthy
  ö   push 1 if top-of-stack is whole, 0 if non-whole
     implicit int output

```

`½` pushes log2(input). If the input is `0` or `1` it will push `0.000000`. 0 is a whole number so performing `ö` on 0 will yield 1, giving the incorrect result for the input 1. `?` only performs the next command if the top of stack is truthy. So if the input was 1 or 0, it will skip the `ö` and print 0 as it's supposed to. Otherwise it will push 1 if `log2(input)` is whole and 0 if it's not.

# Answer
> 3 votes
# Regex (Tcl ARE), ~~24~~ 22 bytes

`^((x((xx)*))\2*$)\3` \- **19 bytes** \- Powers of 2 - Try it online!
`^(x$|(x((xx)*))\2*$)\3` \- **22 bytes** \- Completely even - Try it online!

Tcl ARE has both positive and negative lookaheads, but neither backreferences nor captures can be done inside one. So seemingly, it would be impossible to match powers of 2 instead of non-powers, because all of the ECMAScript regexes use backreferences inside a lookahead. This challenge states "output a truthy value if it is completely even and a falsy value if it is not", so an inverted-logic regex, such as `^(x*)(\1\1)+$|^x$`, would not satisfy the rules.

But as it so happens, in Tcl ARE it seems that any group anchored on both sides (`^` at the beginning and `$` at the end, either inside or outside the group as long as it's adjacent to the parentheses) in all its alternatives will be treated as atomic (preventing the engine from doing the equivalent of backtracking into that expression if the pattern fails to match at a later point). This does not appear to be documented, but it can be exploited to emulate a negative match. The equivalent in engines that support atomic groups would be:

`^(?>(x((xx)*))\1*$)\2` \- **21 bytes** \- Powers of 2 - Try it online!
`^(?>(x\B((xx)*))\1*$)\2` \- **23 bytes** \- Completely even - Try it online!

These in turn are based on the 17 byte ECMAScript regex `^(?!(x(xx)+)\1*$)`. The logic of the Tcl ARE version is to assert that the largest odd factor of \\$n\\$ is \\$1\\$. The "completely even" version additionally asserts than \\$n\ne 1\\$.

Even more strangely than the atomic grouping behavior, Tcl ARE apparently records the positions where word-boundary-match operators (`\m`, `\M`, `\y`, `\Y`) were used inside a capture group, and repeats them if that group is repeated via a backreference. So `^((x\Y((xx)*))\2*$)\3` (**21 bytes**) not only doesn't match \\$1\\$, but doesn't match \\$2\\$ either: Try it online! – and as a result, the 22 byte method has to be used instead.

Explanation for Powers of 2 (**19 bytes**):

```
^
(                  # Group an expression that is anchored to start at its
                   # beginning and to end at its end, thus telling the Tcl ARE
                   # regex engine to treat it as atomic, not backtracking into
                   # it if a subsequent match fails.
    (              # \2 = sum of the following, which will be the largest odd
                   #      number that results in a match for what follows:
        x          # 1; tail -= 1
        ((xx)*)    # \3 = any even number, including zero, trying the largest
                   #      values first; tail -= \3
    )
    \2*$           # Assert that \2 divides tail; anchor to end of string
)
\3                 # Now that the above match is locked in and won't backtrack,
                   # assert that \3 == 0, as no other value can match when
                   # tail == 0 (at the end of the string), thus asserting that
                   # \2 == 1, i.e. that the largest odd factor of N is 1.

```

For Completely even (**22 bytes**), an alternative of `x$` is inserted as the first choice. If \\$n=1\\$ and this alternative matches, it effectively acts like a boolean short-circuit operator – the powers of 2 test won't be done, and `\3` will not be set.

An alternative method to match powers of 2 is `^((x+?)((\2\2)*$))\3` (**20 bytes**): Try it online! \- this uses the same atomic grouping trick, but the logic is to assert that the smallest quotient from dividing \\$n\\$ by any odd number is \\$n\\$ (thus it's implied that the only odd divisor of \\$n\\$ is \\$1\\$). For "completely even" numbers this becomes `^(x$|(x+?)((\2\2)*$))\3` (**23 bytes**): Try it online! But this method is much slower than the primary one shown in this answer, and Tcl cannot even match \\$n=64\\$ within 60 seconds.

# Answer
> 2 votes
# Jelly, 5 bytes

```
Æf=2Ȧ

```

Try it online!

Does ***NOT*** fail for `1`!

# Answer
> 2 votes
# Java (OpenJDK 8), ~~18~~ 16 bytes

```
i->i>1&(i&~-i)<1

```

Try it online!

# Answer
> 2 votes
# C (gcc), ~~37~~ ~~33~~ ~~27~~ 18 bytes

Thanks to @MD XF for the idea

```
f(n){n=(n^n-1)>n;}

```

Try it online!

# Answer
> 2 votes
# Pyth, 5 bytes

```
q]2{P

```

**Verify all the test cases.**

Alternative:

```
q2s{P

```

# Explanation

```
q]2{P  ~ Full program with implicit input (Q) at the end.

    P  ~ Prime factors.
   {   ~ Deduplicated.
q      ~ Equals?
 ]2    ~ The literal [2].
       ~ Output (implicitly).

```

# Answer
> 2 votes
# MATL, 4 bytes

Saved a byte thanks to Luis Mendo!

```
Yf2=

```

**Try it here.**

Returns `1` (or an array of several `1`s) for truthy and `0` or  (the empty string) for falsy.

# How?

```
Yf2=   % Full program.

Yf     % Prime factors.
  2=   % All equal 2?
       % Output implicitly.

```

# Answer
> 2 votes
# JavaScript, ~~14~~ 11 bytes

-3 thanks to Deadcode

```
f=
n=>!(n&n-2)

// test numbers 0-16
const tests = [f(0), false, true, false, true, false, false, false, true, false, false, false, false, false, false, false, true]
const results = tests.map((res, n) => res === f(n))
document.write(
  results.every(res => res)
    ? "All tests passed "
    : [
        "Tests failed ",
        ...results.map((res, n) => !res && `f(${n}): expected ${tests[n]}`).filter(Boolean),
      ].join("<br />")
)
```

```
body{font-size:3rem;font-family:monospace}
```

Explanation - this uses this trick for checking if `n` is a power of 2, but uses `n&n-2` instead of `n&n-1` to make 1 return false

# Answer
> 2 votes
# Regex (Java / Perl / PCRE / .NET), 12 bytes

`^(\1\1|^x)*x$` \- **13 bytes** \- Powers of 2
`(\1\1|^x)+x$` \- **12 bytes** \- Completely even

| Regex engine | Powers of 2 | Completely even |
| --- | --- | --- |
| Java | Try it online! | Try it online! |
| Perl | Try it online! | Try it online! |
| PCRE | Try it online! | Try it online! |
| .NET | Try it online! | Try it online! |

Subtracts increasing powers of 2 from \\$tail\\$, starting with \\$1\\$. As such, the sum of the subtracted powers will be \\$2^a-1\\$ where \\$a\\$ is the number of iterations so far. Once the loop has matched as many iterations as it can, asserts that the remaining \\$tail=1\\$.

Unlike the ECMAScript regexes, this needs to do no backtracking, thus is orders of magnitude faster in standard regex engines.

As with the 17 byte ECMAScript regex, it is quite suitable for solving this challenge, as the only change necessary is upping the minimum iteration count of the loop from `0` to `1` by changing the `*` quantifier to a `+`, at a cost of 0 bytes. But an added bonus here is that the first iteration of the loop can only match at the beginning of the string, so we can remove the first `^` anchor to save 1 byte. This does make the regex much slower in most regex engines though.

# Regex (Java / Perl / PCRE / Python`regex` / Ruby / .NET), 22 bytes

`^((?=(\3\3|^x))(\2))*x$` \- **23 bytes** \- Powers of 2
`((?=(\3\3|^x))(\2))+x$` \- **22 bytes** \- Completely even

| Regex engine | Powers of 2 | Completely even |
| --- | --- | --- |
| Python `import regex` | Try it online! | Try it online! |
| Ruby | Try it online! | Try it online! |

This is a direct port of the 13 byte / 12 byte regex. Ruby, and Python's `regex` module, do not support nested backreferences, so they must be emulated via forward-declared backreferences. (Python's `re` module doesn't even support the latter.) The 13 byte version of this is faster than the 17 byte regexes, but golf-wise, they win.

Although this results in a fast regex that's compatible with six different engines, the recursive solutions provide the best golf for Python's `regex` module and Ruby.

### \\$\large\textit{Full programs}\\$

# Retina 0.8.2, 18 bytes

```
.+
$*
(\1\1|^.)+.$

```

Try it online!

Takes its input in decimal. Uses the Java/Perl/PCRE/.NET pure regex.

# Perl 5, 24 bytes

```
say 1x<>~~/(\1\1|^.)+.$/

```

Try it online!

# Answer
> 2 votes
# Regex (PCRE1), 11 bytes

`^(x(?1)?x|x)$` \- **13 bytes** \- Powers of 2
`^(x(?1)?x)$` \- **11 bytes** \- Completely even

| Regex engine | Powers of 2 | Completely even |
| --- | --- | --- |
| PCRE1 | Try it online! | Try it online! |

I'm not sure when this recursive regex was originally discovered. It was likely an accidental discovery, when someone tried to match palindromes and found that due to PCRE1's atomic subroutine calls, words consisting of only one distinct letter would only match when their length was a power of 2.

Explaining why this works is complicated, but I do intend to do it sometime.

This regex is absolutely phenomenal at being ported to this challenge; it loses 2 bytes in doing so.

# Regex (Perl / PCRE), 15 bytes

`^x(x(?1)?+x|x|)$` \- **16 bytes** \- Powers of 2
`^x(x(?1)?+x|x)$` \- **15 bytes** \- Completely even

This is a port of the PCRE1 regex to engines that may have non-atomic subroutine calls.

| Regex engine | Powers of 2 | Completely even |
| --- | --- | --- |
| Perl | Try it online! | Try it online! |
| PCRE1 | Try it online! | Try it online! |
| PCRE2 | Try it online! | Try it online! |

# Regex (PCRE / Ruby), 16 bytes

`^x(x\g<1>?+x|x|)$` \- **17 bytes** \- Powers of 2
`^x(x\g<1>?+x|x)$` \- **16 bytes** \- Completely even

This is a port of the PCRE1 recursive regex to Ruby's subroutine call syntax.

| Regex engine | Powers of 2 | Completely even |
| --- | --- | --- |
| PCRE1 | Try it online! | Try it online! |
| PCRE2 | Try it online! | Try it online! |
| **Ruby** | **Try it online!** | **Try it online!** |

# Regex (Perl / PCRE2 / Boost / Python`regex`), 15 bytes

`^x(x((?1))\2|)$` \- Powers of 2
`^x(x((?1)?)\2)$` \- Completely even

| Regex engine | Powers of 2 | Completely even |
| --- | --- | --- |
| Perl | Try it online! | Try it online! |
| PCRE2 | Try it online! | Try it online! |
| **Boost** | **Try it online!** | **Try it online!** |
| **Python `import regex`** | **Try it online!** | **Try it online!** |

I discovered this recursive regex on 2022-07-18 while working on Sum of Powers of 2. It relies on subroutine calls being atomic.

```
^            # tail = N = input number
x            # tail -= 1
(            # Define subroutine (?1)
    x        # match += 1; tail -= 1
    ((?1))   # \2 = match made by recursive call; match += \2; tail -= \2
    \2       # match += \2; tail -= \2
|    # or
             # Match nothing, causing a cascading pop to the top level of
             # recursion, ending the match.
)
$            # Assert that we've reached the end of the string.

```

This is similar to `^(\1\1|^x)*x$`, in that the `(?1)` subroutine call will always return \\$2^a-1\\$ where \\$a\\$ is the depth of recursion it reached. This is why an extra \\$1\\$ is subtracted at the beginning (it could just as easily be done at the end, but that would be slightly slower due to backtracking).

It is very easily ported to solving this challenge; the first iteration at which it has a choice of whether to match nothing just has to be pushed down one level, at a cost of 0 bytes.

# Regex (PCRE2 / Ruby), 16 bytes

`^x(x(\g<1>)\2|)$` \- Powers of 2
`^x(x(\g<1>?)\2)$` \- Completely even

| Regex engine | Powers of 2 | Completely even |
| --- | --- | --- |
| PCRE2 | Try it online! | Try it online! |
| **Ruby** | **Try it online!** | **Try it online!** |

This is a port of the non-atomic recursive regex to Ruby's subroutine call syntax.

# Answer
> 2 votes
# Thunno `-`, \\$ 4 \log\_{256}(96) \approx \\$ 3.29 bytes

```
bdiP

```

Attempt This Online! or verify all test cases

Port of Dennis's MATL answer.

## Thunno `DD`, \\$ 5 \log\_{256}(96) \approx \\$ 4.12 bytes

```
1-A^<

```

Attempt This Online! or verify all test cases

Port of Dennis's Jelly answer.

**Note**: a plain "power of two" answer would be 5 chars: `b1c1=` (is the count of 1s in the binary representation equal to 1?)

#### Explanation

```
bdiP  # Implicit input
      # - flag decrements
b     # Convert to a binary string
 di   # Get the list of digits
      # This is a non-empty list of ones
      # if the input is a power of two
   P  # Push the product of this list
      # Implicit output

```

```
1-A^<  # Implicit input
1-     # Subtract one
  A^   # Xor with input
       # The highest set bit will only be conserved
       # if the input is a power of two
    <  # Is more than input?
       # Implicit output

```

# Answer
> 2 votes
# Vyxal `g`, 4 bytes

```
Kḣv₂

```

Try it Online!

Can probably be golfed but it’s painful to do this on mobile.

Outputs `1` for truthy, `0` or the empty list for falsy.

```
K    # divisors of input
 ḣ   # without the first element
  v  # vectorize the following over it
   ₂ # is even?
     # (after which the `g` flag takes the minimum of the stack)

```

# Answer
> 2 votes
# PowerShell, 40 bytes

```
param($i)(($i-band(-$i))-eq$i)-and$i-ne0

```

Try it online!

# Answer
> 2 votes
# Thunno 2 `M`, 2 bytes

```
⁻ḃ

```

Attempt This Online!

Port of Dennis's MATL answer: decrement, convert to binary, take minimum.

---

A plain "power of two" answer would be **4 bytes:**

```
2BSḅ

```

Attempt This Online!

Convert to a binary list, sum equals one?

# Answer
> 1 votes
# Neim, 3 bytes

Doesn't work on TIO.

# Answer
> 1 votes
# Mathematica, 21 bytes

```
IntegerQ@Log2@#&&#>1&

```

# Answer
> 1 votes
# Jelly, 5 bytes

```
ÆEL’¬

```

Try it online!

# Answer
> 1 votes
# Retina, 25 bytes

```
.+
$*
+`^(11+)\1$
$1
^11$

```

Try it online!

# Answer
> 1 votes
# Actually, 5 bytes

```
;R♂╙c

```

Try it online!

Explanation:

```
;R♂╙c
;      duplicate n
 R     range(1, n+1)
  ♂╙   powers of 2
    c  contains n

```

# Answer
> 1 votes
# Haskell, 24 bytes

```
f n=elem n$map(2^)[1..n]

```

Try it online!

# Answer
> 1 votes
# Actually, 4 bytes

```
yN2=

```

Try it online!

# Answer
> 1 votes
# CJam, 9 bytes

```
{mf2f=:*}

```

Anonymous block that takes the input number from the stack and replaces it by either `1` or `0`.

**Try it online!**

### Explanation

```
{       e# Begin block
  mf    e# Array of (repeated) prime factors
  2f=   e# Compare each element of that array with 2
  :*    e# Fold product over the array
}       e# End block

```

# Answer
> 1 votes
# Pyke, 6 bytes

```
P}2]1q

```

Try it here!

```
P      - Prime factors.
 }     - Deduplicate.
  2]1  - Create a one-element list, [2].
     q - Is equal?

```

# Answer
> 1 votes
# Kotlin, ~~19~~ ~~17~~ 16 bytes

```
{it-1 xor it>it}

```

## Test

```
private val t: (Int) -> Boolean =
{it-1 xor it>it}

fun main(args: Array<String>) {
    println(t(0))
    println(t(1))
    println(t(999))
    println(t(1024))
    println(t(2))
}

```

TryItOnline

# Answer
> 1 votes
# Julia 0.6, 10 bytes

```
!n=n-1$n>n

```

Try it online!

# Answer
> 1 votes
# TI-Basic, 11 bytes

```
logBASE(Ans,2
Ans and not(fPart(Ans

```

Alternate solution (14 bytes):

```
max(Ans=2^seq(I²,I,2,Ans

```

# Answer
> 1 votes
# Perl 5, 28 bytes

```
$_=sprintf'%b',<>;say/^10+$/

```

Try it online!

# Answer
> 1 votes
# Cubically, 12 bytes

```
$R:7-8⊕7>7%6

```

Try it online!

Cubically's code is quite short and easily writable, if the solution does not involves too much (more than 1) temporary variables.

Explanation: I used other people's solutions, calculate `(n^(n-1)) > n`.

```
$               Input number n, store to memory index 7.
 R              Make the cube unsolved by perform a move "R" on the cube, thus the value of face 8 will be truthy (1).
  :7            Set notepad value to value of memory index 7 (number n)
    -8          Subtract by value of memory index 8, which is 1 because cube is unsolved.
      ⊕7       Calculate bit-xor of current notepad value (n-1) with value of memory index 7 (n), store to notepad.
        >7      Calculate (notepad > n), store to notepad.
          %6    Print value of notepad as number (0 for falsy, 1 for truthy).

```

# Answer
> 1 votes
# QBIC, 16 bytes

```
[:|~2^a=b\_X1}?0

```

This checks all powers of 2 from 1 to the input, to see if it matches the input. Prints 1 when it does, 0 when it doesn't.

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

```
n=>(n^n-1)>n

```

Port of my Python answer.

Try it online!

# Answer
> 1 votes
# PHP, ~~22~~ 24+1 bytes

```
<?=(($n=$argn)^$n-1)>$n;

```

Run as pipe with `-rF`. Prints `1` for truthy, empty output for falsy.

hmm ... looks like a port from Dennis´ answer.

---

Dang, @Deadcode is right: bitwise operations rank lower than comparisons.
And try as I might, I could not find a way around the parentheses.

# Answer
> 1 votes
# Perl 5, ~~20~~ 18 bytes

```
say!(($_=<>)&$_-2)

```

Try it online!

Note that this would be **17 bytes** with swapping allowed, but by my interpretation, the challenge specifies that swapping is not allowed.

This is modification of the classic bitwise formula for powers of 2, using \\$n∧(n-2)=0\\$ instead of \\$n∧(n-1)=0\\$. It appears nobody else has used this yet? This method would work for eliminating all powers of 2 less than any chosen power of 2. For example, to eliminate \\$\\{1,2,4,8\\}\\$, the formula would be \\$n∧(n-16)=0\\$.

To handle zero correctly, a port of Dennis's Jelly answer won't work, since Perl casts the result of bitwise XOR to an unsigned integer, giving the result `18446744073709551615` for `0^-1`. This can be fixed with `use integer`, but that would result in the program being **34 bytes**:

```
use integer;say((($_=<>)^$_-1)>$_)

```

Try it online!

There is, however, a way to have proper zero handling at **21 bytes**:

```
say!(($_=<>)--&$_)x$_

```

Try it online!

With both zero handling and consistent truthy values, **23 bytes**:

```
say!(($_=<>)&$_-2)>!-$_

```

Try it online!

---

Checking for a power of 2 is **18 bytes** if returning truthy for zero is acceptable:

```
say!(($_=<>)&$_-1)

```

Try it online!

With proper handling of zero, it's **21 bytes**:

```
say!(($_=<>)&$_-1)*$_

```

Try it online!

With both zero handling and consistent truthy values, **23 bytes**:

```
say!(($_=<>)&$_-1)>!-$_

```

Try it online!

# Answer
> 1 votes
# C#, ~~22~~ 17 bytes

```
x=>x!=1&&x&x-1==0

```

-5 by Steffan

# Answer
> 1 votes
# Pyt, 5 bytes

```
ĐĦ1=*

```

Try it online!

Outputs 0 if not completely even, n if completely even

```
Đ            implicit input (n); duplicate on stack
 Ħ           get Hamming weight
  1=         equal to 1?
    *        coerce boolean to integer and multiply by n; implicit print

```

# Answer
> 1 votes
# Japt `-!`, 3 bytes

```
&-Í

```

Try it or test numbers 0-16

This is `n & -(2 - n)` (simplifying to `n & n-2`), with the `!` flag negating the result (0 becomes true, everything else becomes false)

# Answer
> 1 votes
# , 7 bytes

```
<[XOR<:

```

Uses \\$n \< (n \oplus n - 1)\\$.

Attempt This Online!

```
<[XOR<:
     <:  NB. decrement
 [       NB. input
  XOR    NB. XOR
<        NB. is n less than result

```

# Answer
> 1 votes
# Nekomata \+ `-e`, 4 bytes

```
←2D≡

```

Attempt This Online!

```
←2D≡
←       Decrement
 2D     Convert to base 2
   ≡    Check if all digits are equal

```

# Answer
> 1 votes
# Sed, 117 bytes

Not the obvious language for an arithmetic code-golf, but still fun:

```
:a
s/^0*2$/T/
s/.*[,0]$/F/
t
s/[13579]/&,/g
y/123456789/011223344/
s/,0/5/g
s/,1/6/g
s/,2/7/g
s/,3/8/g
s/,4/9/g
ta
ba

```

This works using successive division by 2, terminating when we reach 2 (true) or a value that ends in zero (which must be a multiple of 5, or zero itself) or with a carry-out from having divided an odd number.

In more detail:

```
:a                   # start of loop
s/^0*2$/T/           # reached 2
s/.*[,0]$/F/         # reached an odd number
t                    # in which case, jump to end

s/[13579]/&,/g          # odd numbers cause a carry when divided
y/123456789/011223344/  # divide by two

s/,0/5/g             # add the carry
s/,1/6/g
s/,2/7/g
s/,3/8/g
s/,4/9/g

ta                   # jump, clearing the "substituted" flag
ba                   # jump anyway

```

Sample input and corresponding output:

```
0
1
2
3
4
32
64
10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376

```

```
F
F
T
F
T
T
T
T

```

(that last value is 2¹⁰⁰⁰)

# Answer
> 0 votes
### C, 31 bytes

```
f(x){return !(x&(x-1))&&!(x-1)}

```

These are the powers of 2, except 1, and thus binary arithmetics solves the problem.

# Answer
> 0 votes
# PARI/GP, 29 bytes

Try it online!

```
f(n)=hammingweight(n)==1-n%2;

```

# Answer
> 0 votes
# Python, 43 Bytes

```
import math
lambda x:math.log(x,2)%1or x==1

```

Outputs false for completely even number and outputs a truthy value for not completely even number.

Try it online (2 bytes added to allow testing)

Completely even numbers are just powers of 2 excluding 1. This programme takes the binary logarithm of the number. This only gives an integer when the argument is a power of 2. The modulo is to check if it is an integer.

# Answer
> 0 votes
# C, 21 bytes

Requirement: 2's complement arithmetic

```
f(x){return!(x&x-2);}

```

This is a minor modification of the well-known expression `x & (x-1)` which yields zero when `x` is an power of two (including 2⁰, i.e. unity). By subtracting an additional 1 from the right-hand side, we exclude the value that has that bit set.

0 results in a true value; if we wish to exclude that, we need an extra 3 bytes: `!(x&x-2)&&x`.

---

## Demo

```
#include <stdio.h>
#include <limits.h>

int main(void)
{
    for (int i = INT_MAX;  i > 0; --i) {
        if (f(i)) { printf("%d\n", i); }
    }
}

```

The demo produces this output on a 32-bit system:

```
1073741824
536870912
268435456
134217728
67108864
33554432
16777216
8388608
4194304
2097152
1048576
524288
262144
131072
65536
32768
16384
8192
4096
2048
1024
512
256
128
64
32
16
8
4
2

```

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