22
\$\begingroup\$

Recently, I have found a bijective mapping \$f\$ from positive integers to finite, nested sequences. The purpose of this challenge is to implement it in the language of your choice.

The Mapping

Consider a number \$n\$ with the factors \$2^{a_1}3^{a_2}5^{a_3}\cdots p^{a_i}\$ where \$a_i > 0\$

$$f(n) = \{f(a_2+1),f(a_3+1),\cdots,f(a_i+1),\underbrace{\{\},\{\},\cdots,\{\}}_{a_1}\}$$

For example:

$$\begin{align} f(22308) & = \{f(2),f(1),f(1),f(2),f(3),\{\},\{\}\} \\ & = \{\{\{\}\},\{\},\{\},\{\{\}\},\{f(2)\},\{\},\{\}\} \\ & = \{\{\{\}\},\{\},\{\},\{\{\}\},\{\{\{\}\}\},\{\},\{\}\} \end{align}$$

Rules

  • You may write a full program or a function to do this task.
  • Output can be in any format recognisable as a sequence.
  • Built-ins for prime factorization, primality testing, etc. are allowed.
  • Standard loopholes are disallowed.
  • Your program must complete the last test case in under 10 minutes on my machine.
  • This is code-golf, so the shortest code wins!

Test Cases

  • 10: {{},{{}},{}}
  • 21: {{{}},{},{{}}}
  • 42: {{{}},{},{{}},{}}
  • 30030: {{{}},{{}},{{}},{{}},{{}},{}}
  • 44100: {{{{}}},{{{}}},{{{}}},{},{}}
  • 16777215: {{{{}}},{{}},{{}},{},{{}},{{}},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{{}}}
  • 16777213: pastebin
\$\endgroup\$
6
  • \$\begingroup\$ Is the same output, without the commas, still recognisable as a sequence? \$\endgroup\$
    – Dennis
    Nov 23, 2015 at 13:44
  • \$\begingroup\$ @Dennis Yes, you can tell by the brackets. \$\endgroup\$ Nov 23, 2015 at 13:44
  • \$\begingroup\$ How about the number 1 \$\endgroup\$
    – Xwtek
    Nov 23, 2015 at 13:56
  • \$\begingroup\$ Ooh, that is {}. \$\endgroup\$
    – Xwtek
    Nov 23, 2015 at 13:56
  • 1
    \$\begingroup\$ Would this be an acceptable output format? CJam doesn't distinguish between empty lists and empty strings, so this is the natural way of representing a nested array. \$\endgroup\$
    – Dennis
    Nov 23, 2015 at 16:10

6 Answers 6

5
\$\begingroup\$

CJam, 51 48 44 42 41 39 34 33 31 bytes

{mf_W=)1|{mp},\fe=(0a*+{)J}%}:J

Try it online in the CJam interpreter.

Thanks to @MartinBüttner for golfing off 3 bytes!

Thanks to @PeterTaylor for golfing off 3 bytes and paving the way for 1 more!

At least on my computer, downloading the file takes longer than running the program...

I/O

This is a named function that pops and integer from STDIN and pushes an array in return.

Since CJam does not distinguish between empty arrays and empty strings – a string is simply a list that contains only characters –, the string representation will look like this:

[[""] "" [""] ""]

referring to the following, nested array

[[[]] [] [[]] []]

Verification

$ wget -q pastebin.com/raw.php?i=28MmezyT -O test.ver
$ cat prime-mapping.cjam
ri
  {mf_W=)1|{mp},\fe=(0a*+{)J}%}:J
~`
$ time cjam prime-mapping.cjam <<< 16777213 > test.out

real    0m25.116s
user    0m23.217s
sys     0m4.922s
$ diff -s <(sed 's/ //g;s/""/{}/g;y/[]/{}/' < test.out) <(tr -d , < test.ver)
Files /dev/fd/63 and /dev/fd/62 are identical

How it works

{                           }:J  Define a function (named block) J.
 mf                              Push the array of prime factors, with repeats.
   _W=                           Push a copy and extract the last, highest prime.
      )1|                        Increment and OR with 1.
         {mp},                   Push the array of primes below that integer.

                                 If 1 is the highest prime factor, this pushes
                                 [2], since (1 + 1) | 1 = 2 | 1 = 3.
                                 If 2 is the highest prime factor, this pushes
                                 [2], since (2 + 1) | 1 = 3 | 1 = 3.
                                 If p > 2 is the highest prime factor, it pushes
                                 [2 ... p], since (p + 1) | 1 = p + 2, where p + 1
                                 is even and, therefor, not a prime.

              \fe=               Count the number of occurrences of each prime
                                 in the factorization.

                                 This pushes [0] for input 1.

                  (              Shift out the first count.
                   0a*           Push a array of that many 0's.
                      +          Append it to the exponents.

                                 This pushes [] for input 1.

                       {  }%     Map; for each element in the resulting array:
                                   Increment and call J.
\$\endgroup\$
5
  • \$\begingroup\$ Blame Pastebin :P \$\endgroup\$ Nov 23, 2015 at 14:22
  • \$\begingroup\$ mf e= is much better than what I'd found when I knocked up a sanity test while the question was in the sandbox, but one improvement I found which you haven't used is to do the mapping for the twos as (0a*+ - i.e. ri{}sa2*{mf_W=){mp},\fe=(0a*+0j\{)j}%*}j. And there's a much bigger improvement as well which I'll give you a few hours' headstart on... \$\endgroup\$ Nov 23, 2015 at 14:36
  • \$\begingroup\$ @PeterTaylor Thanks for the golf and the hint. \$\endgroup\$
    – Dennis
    Nov 23, 2015 at 15:04
  • \$\begingroup\$ Yep, changing the output representation was indeed the bigger improvement. There's a better way of handling the base case too, which I've only just found, but to beat your solution I have to use two of your ideas so: {mf_W=)1|{mp},\fe=(0a*+{)J}%}:J \$\endgroup\$ Nov 23, 2015 at 18:59
  • \$\begingroup\$ @PeterTaylor That one magical 1|. Thanks again! \$\endgroup\$
    – Dennis
    Nov 23, 2015 at 19:10
3
\$\begingroup\$

Mathematica, 88 bytes

f@1={};f@n_:=f/@Join[1+{##2},1&~Array~#]&@@SparseArray[PrimePi@#->#2&@@@FactorInteger@n]
\$\endgroup\$
1
  • \$\begingroup\$ The magic of undocumented internals... \$\endgroup\$ Nov 23, 2015 at 20:48
3
\$\begingroup\$

Jelly, 14 bytes

ÆEµ“”WẋḢ;@‘߀$

Try it online!

The last test case times out on TIO. The Footer runs the program over the inputs, gets their raw form (Jelly doesn't display empty lists well) and replaces the [] with {}

How it works

ÆEµ“”WẋḢ;@‘߀$ - Main link. Takes n on the left
ÆE             - Compute the prime exponents of n
  µ            - Begin a new link with the exponents E as the argument
   “”          - []
     W         - [[]]
       Ḣ       - Take the first exponent, a
      ẋ        - Repeat each element of [[]] a times
             $ - Group the previous 2 links as a monad f(E):
          ‘    -   Increment each exponent
            €  -   Over each:
           ß   -     Recursively run the main link
        ;@     - Append the [[]] to the recursive call result
\$\endgroup\$
2
\$\begingroup\$

Pyth, 29 bytes

L+'MhMtbmYhbL&JPby/LJf}TPTSeJ

Demonstration

This defines a function, ', which performs the desired mapping.

A helper function, y, performs the mapping recursively given a prime decomposition. The base case and the prime decomposition are performed in '.

\$\endgroup\$
1
\$\begingroup\$

05AB1E, 10 bytes

ÓćÅ0«ε¯sF¸

Output with [] instead of {}.

Try it online or verify all test cases, where test case 16777213 is replaced with 1009 (another prime number) - the output for 16777213 would be similar, just with a lot more leading [], ..

Explanation:

Ó           # Get the exponents of the prime factorization of the (implicit) input
            #  ([a,b,c,d,...] in 2^a*3^b*5^c*7^d*...=input)
 ć          # Extract head; pop and push remainder-list and first item separated
  Å0        # Get a list of 0s with a length equal to the `a` exponent
    «       # Merge that as trailing items to the remainder-list
     ε      # Map over each integer in the list:
      ¯     #  Push an empty list
       s    #  Swap so the current number is at the top of the stack
        F   #  Loop that many times
         ¸  #   And wrap the list into a list every iteration
            # (after which the result is output implicitly)
\$\endgroup\$
1
  • \$\begingroup\$ wow, that is really short. \$\endgroup\$
    – Razetime
    Nov 16, 2020 at 16:01
0
\$\begingroup\$

Stax, 34 bytes

ÑE│♂█ⁿt2N╔₧Ñ↓Ls&ûΦ}eóâÇΔ-ë╖»8Kq+╔r

Run and debug it

There's very likely a better way to do this with recursion, but I just can't seem to find anything related to it in the builtin docs. So, this is a manually built implementation.

Takes very, very long after the third test case.

Explanation (Unpacked)

z]Yx{c2>{|nBs{y@msz]s|*+c]ys+Yd}{vy@}?F|u
z]                                        array [[]]
  Y                                       write that to register Y
   x{                                 F   for i in [1..input]
     c2>                                  if i < 2,
                                {vy@}     increment and take element at that index from y
        {|n                               otherwise take prime exponents
           Bs                             push the first element and the rest of the array separately
             {  m                         map the rest of the array to:
              y@                          elements in y at those indices
                 sz]s                     push [[]] and first element
                     |*                   repeat it's elements that many times
                       +                  add those together
                        c]ys+Y            and append that to register Y
                              d}          then delete it
                                       |u convert the last element on stack to string
                                          implicit output                                            
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.