Encode an integer

Question

Given positive integer n > 2. We convert it to an array as follows:

1. If it is equal to 2 return an empty array
2. 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 9th 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.

Input

Positive integer n greater than 2.

Output

Encoded integer n.

Rules and IO format

• 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!

Test cases

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

Sandbox

Answer 1

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

Answer 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

Answer 3

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

Answer 4

Mathematica, 125 119 bytes

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

Try it on Wolfram Sandbox

Usage:

f = Flatten[ ...

f[10008]

1402478

Answer 5

Jelly, 35 bytes

ÆfẎW€ÆC2,“”y¹ß€Ṇ?
ÇŒṘḊ⁾][iЀḟ0t1Ṗ’Ḅ

Try it online!

Answer 6

J, 74 73 66 bytes

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

Try it online!

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

Explanation (ungolfed)

Preamble

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

Encode

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

Convert

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)

Drop

(}.~ >:@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

Decode is the built-in function #. which takes a list of 1s and 0s and converts it to a binary number.

Answer 7

Retina, 244 227 225 bytes

+%(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

Try it online!

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

Explanation:

+%(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

Answer 8

Haskell, 162 160 155 bytes

sum.zipWith((*).(2^))[0..].tail.snd.span(<1).(r%)
r=zip[1..][x|x<-[2..],all((>0).mod x)[2..x-1]]
_%1=[]
((i,q):p)%n|mod n q<1=r%div n q++0:r%i++[1]|1<3=p%n

Try it online!

Explanation:

r=zip[1..][x|x<-[2..],all((>0).mod x)[2..x-1]] defines an infinite list of tuples of primes and their indices: [(1,2),(2,3),(3,5),(4,7),(5,11),(6,13), ...].

The function (%) takes this list r and a number n and converts the number into the reversed factor-array representation. This is done by stepping through r until we find a prime which divides n. We then recursively determine the representation of the index of this prime and enclose it in 0 and 1 and prepend the representation of n divided by that prime.

For n=46, this yields the list [0,0,0,1,1,0,0,1,1,1,0,1] from which then the leading zeros (snd.span(<1)) and the next 1 (tail) are dropped. Afterwards the list is converted to a decimal number by element-wise multiplying with a list of powers of two and summing up the resulting list: sum.zipWith((*).(2^))[0..].

Answer 9

JavaScript, 289 bytes

The bytes are the sum of the JavaScript code without linebreaks after the commas (which are inserted only for better formatting and readability) (256 bytes) and the additional characters for the command line switch, which is required when using Chrome (33 bytes).

'use strict'
var f=(n,i=2,r=[])=>n>1?n%i?f(n,i+1,r):f(n/i,i,r.concat(i)):r,
c=(p,r=1,i=2)=>i<p?f(i)[1]?c(p,r,i+1):c(p,r+1,i+1):r-1?f(r).map(h):[],
h=a=>c(a),
s=a=>a.reduce((r,e)=>r+s(e),'1')+' ',
o=i=>+('0b'+s(f(i).map(h)).trim().replace(/ /g,'0').slice(1,-1))

And a longer, better readable version:

'use strict';
const f = (n,i=2,r=[]) => n>1 ? n%i ? f(n,i+1,r) : f(n/i,i,r.concat(i)) : r;
const c = (p,r=1,i=2) => i<p ? f(i)[1] ? c(p,r,i+1) : c(p,r+1,i+1) : r-1 ? f(r).map(h) : [];
const h = i => c(i);
const s = a => a.reduce((r,e) => r+s(e),'1')+' ';
const o = i => +('0b'+s(f(i).map(h)).trim().replace(/ /g,'0').slice(1,-1));

Some brief explanations:

f is a purely functional tail-recursive factorization algorithm.

c counts at which place r the prime number p occurs in the sequence of prime numbers and returns either [] (if p=2 and r=1) or factorizes and further processes r by means of recursion.

h is a small helper function which unfortunately is necessary as map calls the supplied function with numberOfCurrentElement as the second and wholeArray as the third argument, thus overriding the default values provided in c if we would pass this function directly (it took me some time to get after this pitfall; replacing h by its definition would be a few bytes longer).

s transforms the generated array to a string. We use blank instead of 0 so that we can use trim() in o.

o is the function to be called with the input value i which returns the output. It generates the binary string representation required by the specification and converts it to a (decimal) number.

Edit: Chrome must be started with chrome --js-flags="--harmony-tailcalls" to enable optimization of tail-recursion (see https://v8project.blogspot.de/2016/04/es6-es7-and-beyond.html). This also requires using strict mode.

The following test shows that the computation is a bit slow for some values (the longest is more than six seconds for 10007on my computer). Interestingly, without optimization of tail-recursion the computation is much faster (about factor 5) when there is no stack overflow.

for (let i=3; i<=10008; i==10 ? i=10000 : ++i) {
    let time = new Date().getTime();
    let val = o(i);
    time = new Date().getTime() - time;
    document.write(i + ': ' + o(i) + ' (computed in ' + time + ' ms)<br>');
}

Answer 10

tinylisp, 209 bytes

(load library
(d [(q((N)(map(q((P)([(length(filter prime?(1to P))))))(reverse(prime-factors N
(d B(q((L)(c 1(insert-end 0(foldl concat(map B L
(d T(q((N)(if(mod N 2)(/ N 2)(T(/ N 2
(q((N)(T(from-base 2(t(B([ N

The last line is an unnamed function that computes the specified encoding. Try it online!

Pre-golfing version

This is the code I had before I started golfing it down:

(load library)

(def prime-index
 (lambda (P)
  (length (filter prime? (1to P)))))

(def to-list
 (lambda (N)
  (map to-list
   (map prime-index
    (reverse (prime-factors N))))))

(def to-bits
 (lambda (L)
  (cons 1
   (insert-end 0
    (foldl concat
     (map to-bits L))))))

(def trim
 (lambda (N)
  (if (mod N 2)
   (div2 N 2)
   (trim (div2 N 2)))))

(def encode
 (lambda (N)
  (trim
   (from-base 2
    (tail (to-bits (to-list N)))))))

Answer 11

05AB1E, 18 bytes

ΔÒ.Ø>}¸»Ç3%2K0ܨ2β

Try it online!

Explanation:

Δ    }       # loop until a fixed point
 Ò           # replace each number with its prime factorization
  .Ø>        # replace each prime with its 1-based index
¸»           # after the loop: join to a string
  Ç          # get ASCII value of each character
   3%        # modulo 3 (maps '[' to 1, ']' to 0, ' ' to 2, ',' to 2)
     2K      # remove 2s
       0Ü    # trim trailing 0s
         ¨   # remove the last 1
          2β # parse as base 2