Encode an integer

ThePirateBay 08/16/2017. 7 answers, 1.407 views
code-golf number primes

Given positive integer n > 1. 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 , 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

5 Comments
Mr. Xcoder 08/14/2017
You should remove the test case with 2 since the submissions are not required to handle it.
Step Hen 08/14/2017
Or just say n >= 3 if 2 is not in the input domain
3 Mr. Xcoder 08/14/2017
Rip languages that do not have prime built-ins.
3 ThePirateBay 08/14/2017
@Paul. "[...] create array of all n's prime factors sorted ascending"
1 ThePirateBay 08/15/2017
@Quelklef. I was working on implementing ATP (just for fun, nothing serious) and I tried to somehow represent every number using nested arrays. So, this encoding is the first idea I came up with.

7 Answers


H.PWiz 08/15/2017.

Husk, 35 31 30 29 26 25 24 22 bytes

-7 bytes thanks to @Zgarb!

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

Try it online!

Explaination

(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
5 comments
Zgarb 08/14/2017
I think this should work for 27 bytes, but TIO times out during type inference...
1 Zgarb 08/14/2017
Never mind, 25 bytes and working. Finally a use case for φ, the fixpoint lambda!
H.PWiz 08/14/2017
Wow, I've never really understood its use cases, until now
Zgarb 08/14/2017
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.
Zgarb 08/14/2017
`:0:1 can be `Jḋ2.

notjagan 08/15/2017.

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


JungHwan Min 08/14/2017.

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

2 comments
Kelly Lowder 08/14/2017
Original answer works on 10008, but this one fails
1 JungHwan Min 08/14/2017
@KellyLowder Fixed!

Jonathan Allan 08/15/2017.

Jelly,  22  20 bytes

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

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Ḋœ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

Erik the Outgolfer 08/14/2017.

Jelly, 35 bytes

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

Try it online!


cole 08/14/2017.

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.


PunPun1000 08/15/2017.

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

Related questions

Hot questions

Language

Popular Tags