Given positive integer `n > 1`

. We convert it to an array as follows:

- If it is equal to
`2`

return an empty array - Otherwise create array of all
`n`

's prime factors sorted ascending, then each element replace with its index in prime numbers sequence and finally convert each element to array

For example, lets convert number `46`

to array. Firstly, convert it to array of its prime factors:

`[2, 23]`

Number `23`

is `9`

th prime, so replace `2`

with empty array and `23`

with `[9]`

. Array now becomes:

`[[], [9]]`

Prime factors of `9`

are `3`

and `3`

, so:

`[[], [3, 3]]`

Do the same for both `3`

:

`[[], [[2], [2]]]`

And finally:

`[[], [[[]], [[]]]]`

Now, to encode it, we simply replace each open bracket with `1`

and each closing bracket with `0`

, then remove all ending zeros and drop one `1`

from the end. This is our binary number. Using the above example:

```
[ ] [ [ [ ] ] [ [ ] ] ]
| | | | | | | | | | | |
| | | | | | | | | | | |
V V V V V V V V V V V V
1 0 1 1 1 0 0 1 1 0 0 0
```

Now simply drop the last three zeros and the last `1`

. The number becomes `10111001`

which is `185`

in decimal. That is the expected output. Notice that in array to binary conversion brackets of the main array are not included.

Positive integer `n`

greater than `2`

.

Encoded integer `n`

.

- Standard rules apply.
- Input can be string or number (but in case of string it must be in base 10).
- Output can be string or number (but in case of string it must be in base 10).
- This is code-golf, the shortest answer in bytes wins!

More test cases upon request.

```
3 ---> 1
4 ---> 2
5 ---> 3
6 ---> 5
7 ---> 6
8 ---> 10
9 ---> 25
10 ---> 11
10000 ---> 179189987
10001 ---> 944359
10002 ---> 183722
10003 ---> 216499
10004 ---> 2863321
10005 ---> 27030299
10006 ---> 93754
10007 ---> 223005
10008 ---> 1402478
```

H.PWiz 08/15/2017.

-7 bytes thanks to @Zgarb!

`ḋh↔↓¬↔φṁ?ḋö`Jḋ2⁰#ṗḣ=2p`

(Of older version of code, 24 bytes)

```
φ -- Define a recursive function which calls itself ⁰
ṁ -- map then concatenate
? =2 -- if the element equals 2
Kø -- return the empty list
#ṗḣ -- else, count the the number of primes upto it
ȯ⁰ -- and then recur, applying ⁰ to that number
ȯ`J -- put the result between the elements of the next list
ḋ2 -- binary 2 [1,0]
p -- over its prime factorisation
↔ -- reverse
↓¬ -- dropwhile false
↔ -- reverse, back to normal
h -- drop the last element
ḋ -- interpret as base 2
```

We added fixpoint lambdas to Husk very early, before multi-line programs were implemented. I guess we thought they would be the best way to handle recursion. But they are pretty obscure apart from saving one byte in special cases like this.

notjagan 08/15/2017.

```
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
```

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

```
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*
```

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

JungHwan Min 08/14/2017.

`Flatten[#//.{{1}->{1,0},a_/;a>1:>{1,List/@PrimePi[Join@@Table@@@FactorInteger@a],0}}]/.{1,d__,1,0..}:>{d}~FromDigits~2&`

Uses a slightly different approach; converts prime indices to `{1, index, 0}`

, and 2 to `{1, 0}`

.

**Usage:**

```
f = Flatten[ ...
f[10008]
```

`1402478`

Jonathan Allan 08/15/2017.

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

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).

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Ḋœr0ṖḄ - 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: "[[], [[[]], [[]]]]"
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, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0]
Ḋ - dequeue e.g. [ 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0]
œr0 - right-strip zeros e.g. [ 1, 1, 1, 1, 0, 0, 1, 1]
Ṗ - pop e.g. [ 1, 1, 1, 1, 0, 0, 1]
Ḅ - binary to decimal e.g. 185
```

cole 08/14/2017.

`3 :'#.(}.~ >:@i.&1)&.|.2+}.;<@(_2,~_1,[:>:[:_1&p:q:) ::<"0@;^:_ y'`

This is a real mess that certainly is in need of further golfing (e.g. removal of the explicit function definition). I think that the boxing I've been doing is especially what's bringing up the bytecount since I really don't know what I'm doing there (it's been a lot of trial and error). Also, I'm *pretty* sure that there are some built-ins I'm forgetting about (e.g. I feel like `_2,~_1,`

probably has a built-in).

Sit back tight, because this is not going to be a short explanation. Ironically, a terse language has been paired with a verbose person.

I'll be splitting this into a few functions

```
encode =. 3 : '<@(_2,~_1, [: >: [: _1&p: q:) ::<"0@;^:_ y'
convert =. 3 : '2 + }. ; y'
drop =. (}.~ >:@i.&1)&.|.
decode =. #.
```

`encode`

encodes the integer using _1 and _2 instead of [ and ]`convert`

converts a list of _1 and _2 into a list of 1 and 0`drop`

drops the last 1 and trailing zeroes`decode`

converts from a binary list to a number

I'll be walking through a sample call for 46, which expressed in the ungolfed format is done

```
decode drop convert encode 46
185
```

There's a lot to explain here.

```
3 : '<@(_2,~_1, [: >: [: _1&p: q:) ::< "0@;^:_ y'
^:_ Do until result converges
; Raze (remove all boxing)
"0 For each
q: Factorize
_1&p: Get index of prime
>: Add 1 (J zero-indexes)
_1, Prepend -1
_2,~ Append -2
< Box resulting array
:: If there is an error
< Box the element
```

Note that the explicit function definition `3 : '[function]'`

evaluates the function as if it were on the REPL with the right argument replacing every instance of `y`

(this means that I can avoid having to use caps (`[:`

), atops (`@`

), and ats (`@:`

) at the cost of a few bytes).

Here's what it looks like for each successive iteration on the input of 46

```
┌─────────┐ ┌──┬─────┬─────────┬──┐ ┌──┬──┬──┬──┬───────┬───────┬──┬──┐
│_1 1 9 _2│ => │_1│_1 _2│_1 2 2 _2│_2│ => │_1│_1│_2│_1│_1 1 _2│_1 1 _2│_2│_2│ =>
└─────────┘ └──┴─────┴─────────┴──┘ └──┴──┴──┴──┴───────┴───────┴──┴──┘
┌──┬──┬──┬──┬──┬─────┬──┬──┬─────┬──┬──┬──┐
│_1│_1│_2│_1│_1│_1 _2│_2│_1│_1 _2│_2│_2│_2│ => the final iteration is just every
└──┴──┴──┴──┴──┴─────┴──┴──┴─────┴──┴──┴──┘ value in its own box
```

This function makes use of adverse (`::`

) in order to nest the values in "brackets" (the brackets used here are -1 and -2). Basically, every time we factorize and convert to prime number indices, _1 is prepended and _2 is appended, which act as brackets. When the function is called on those elements, it just returns them as-is since `q:`

will error on trying to factorize a negative number. It's also fortunate that `q:`

does *not* error on trying to factorize 1 and instead returns the empty array (as desired).

```
3 : '2 + }. ; y'
; Raze (remove boxing)
}. Behead (remove head)
2 + Add 2
```

Convert is a lot simpler. It just removes all the boxing, as well as the first element, and then converts everything to 1s and 0s (simply by adding 2)

```
(}.~ >:@i.&1)&.|.
&.|. Reverse, apply the left function, and then undo
}.~ >:@i.&1 Drop the leading zeroes and first 1
i.&1 Index of first one
>: Add 1
}.~ Drop
```

This reverses the list, finds the first one and then drops all the values up to that one, then reverses the list again.

Decode is the built-in function `#.`

which takes a list of 1s and 0s and converts it to a binary number.

PunPun1000 08/15/2017.

```
+%(G`
\d+
$*0¶$&$*
+`^00(0+)
0$1¶$0
A`^(00+?)\1+$
^0+
$0;1
+`(1+)¶0+(?=¶)
$0;1$1
+`¶(11+?)(\1)*$
¶$1¶1$#2$*1
1$
m`^11$
[]
m`^1+
[¶$.0$*0¶]
+s`(0+);(1+)(.+¶)\1¶
$1;$2$3$2¶
0+;1+¶
)`1+
$.0
T`[]¶`10_
10+$
1
01
+`10
011
^0+
1
```

This is a straight forward approach following the algorithm demonstrated in the question. The prime index generation is exponential complexity so it will time out for larger inputs

```
+%(G` Repeatedly apply on each line:
\d+ If the line is a number, convert it to unary 0s and 1s
$*0¶$&$*
+`^00(0+) Generate all prefixes of the zeros greater than 1
0$1¶$0
A`^(00+?)\1+$ Remove non-prime strings of zeros
^0+ Index the first zero set (00) as 1
$0;1
+`(1+)¶0+(?=¶) Index the rest of the zeroes as their prime index
$0;1$1
+`¶(11+?)(\1)*$ Compute prime factors of input value
¶$1¶1$#2$*1
1$ Remove the 1 factor (not really prime)
m`^11$ Turn all 2 prime factors to []
[]
m`^1+ Surround all non-2 prime factors in brackets
[¶$.0$*0¶]
+s`(0+);(1+)(.+¶)\1¶ Convert non-2 prime factors to their index
$1;$2$3$2¶
0+;1+¶ Remove the list of primes
)`1+ Return all primes back to decimal ready to be repeated
$.0
T`[]¶`10_ Then convert all [ to 1 and ] to 0, and remove linefeeds
10+$ Remove the final 1 and trailing zeroes
1 Convert from binary to unary
01
+`10
011
^0+
1 Convert from unary to decimal
```

- Manchester encode a data stream
- Detect the character encoding of the input
- Tic Tac Toe encoder/decoder
- Write a GIF encoder
- Expand an encoded string
- Implement bzip2's run-length encoding
- Cycles in run-length encoding
- Sort a number's divisors by prime factorization
- Write a VIC cipher encoder
- Negative XOR primes
- Is this number a prime?

- What kind of creature is Pac-Man?
- Finding your partner
- Quoting a typo: Do I really have to do "sic", or can I just fix the sentence?
- Can running yes > /dev/null harm a Mac?
- How to use a method reference on a static import?
- Isn't Ubuntu's system prompt for my password spoofable?
- What is Voldemort's Boggart?
- Mathematica Syntax Coloring in GitHub README
- Reasons for confusion over tenses in a story
- Dealing with Resisting Students
- How can I ask my manager if he is upset at me
- Currently sole owner of a property. My girlfriend is looking to move in with me and is offering to pay 'rent'. Am I at risk here?
- How to poison a creature that measures more than a dozen meters?
- How do I deal with other people's screaming children in restaurants?
- What early tools might be devised on a planet where diamonds were abundant?
- Why are the French and Indian Wars / Seven Years' War not considered WW 1?
- Fold the integer to save space!
- Why "Integrieren bis Unendlich" but not "bis Unendlichkeit"?
- I know what a bad photo is, so why do I keep taking them?
- Can I write (200 MB - 150 min) music to a (700 MB - 80 min) CD?
- The word for discrimination against people from other regions within a country?
- How can I temporarily close an arched interior passageway?
- Determine your language's version
- Quote from mathematician-poet

`2`

since the submissions are not required to handle it.`n >= 3`

if`2`

is not in the input domain"[...] create array of all n's prime factors sorted ascending"