# Encode an integer

## Husk, ~~35~~ ~~31~~ ~~30~~ ~~29~~ ~~26~~ ~~25~~ ~~24~~ ~~22~~ ~~20~~ ~~19~~ 15 bytes

-7 bytes thanks to @Zgarb!

Saved an extra 4 bytes, indirectly, thanks to Zgarb

```
ḋhΣhgφṁȯ`Jḋ2⁰ṗp
```

Try it online!

### Explaination

```
φ -- Define a recursive function which calls itself ⁰ and is applied to an Integer
ṁ p -- map then concatenate over its prime factors
ṗ -- return their indices into the primes
⁰ -- and then recur, applying ⁰ to that number
ȯ`Jḋ2 -- then surround it between the list [1,0] (binary 2)
g -- group adjacent equal elements
h -- drop last element (trailing 0s)
Σ -- concatenate
h -- drop the last element
ḋ -- interpret as base 2
```

## Jelly, ~~ 22 20 ~~ 19 bytes

-1 thanks to Erik the Outgolfer (tail zeros from both sides, `t`

, rather than from the right `œr`

)

```
ÆfÆC$ÐLŒṘO%3ḟ2Ḋt0ṖḄ
```

A monadic link taking an integer greater than 2 and returning an integer greater than 0 (2 would return 0 as per the original spec too).

**Try it online!**

### How?

This almost exactly replicates the description given, just with some ordinal manipulation for the creation of the binary array...

```
ÆfÆC$ÐLŒṘO%3ḟ2Ḋt0ṖḄ - Link: number n (>=2)
ÐL - loop until no more changes occur:
$ - last two links as a monad:
Æf - prime factorisation (includes duplicates & vectorises)
ÆC - count primes less than or equal (vectorises)
- ...note for entries of 2 this yields [1]
- then for entries of 1 it yields [], as required
ŒṘ - get a Python representation - just like in the OP,
- something like: "[[], [[[]], [[]]]]" (for an input of 46)
O - convert to ordinals e.g. [91,91,93,44,32,91,91,91,93,93,44,32,91,91,93,93,93,93]
%3 - modulo by 3 e.g. [ 1, 1, 0, 2, 2, 1, 1, 1, 0, 0, 2, 2, 1, 1, 0, 0, 0, 0]
ḟ2 - filter discard twos e.g. [ 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0]
Ḋ - dequeue e.g. [ 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0]
t0 - strip zeros e.g. [ 1, 0, 1, 1, 1, 0, 0, 1, 1]
Ṗ - pop e.g. [ 1, 0, 1, 1, 1, 0, 0, 1]
Ḅ - binary to decimal e.g. 185
```

## Python 2, ~~212~~ 177 bytes

```
lambda n:int(g(n).rstrip("0")[1:-1],2)
g=lambda n:"1%s0"%"".join(map(g,p(n)))
def p(n,i=0,j=1):
while n>1:
j+=1;P=q=1;exec"P*=q*q;q+=1;"*~-j;i+=P%q
while n%j<1:yield i;n/=j
```

Try it online!

The lack of prime builtins really hurts the byte count, and it times out on TIO with larger primes. Uses xnor's primality check.

## Python 2 + gmpy2, 175 bytes

```
lambda n:int(g(n).rstrip("0")[1:-1],2)
g=lambda n:"1%s0"%"".join(map(g,p(n)))
def p(n,i=0,j=1):
while n>1:
j+=1;i+=is_prime(j)
while n%j<1:yield i;n/=j
from gmpy2 import*
```

Try it online!

This version does not time out on the larger test cases (i.e. 10000 - 10008).