18
\$\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 where . Then:

For example:

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\$
  • \$\begingroup\$ Is the same output, without the commas, still recognisable as a sequence? \$\endgroup\$ – Dennis Nov 23 '15 at 13:44
  • \$\begingroup\$ @Dennis Yes, you can tell by the brackets. \$\endgroup\$ – LegionMammal978 Nov 23 '15 at 13:44
  • \$\begingroup\$ How about the number 1 \$\endgroup\$ – Akangka Nov 23 '15 at 13:56
  • \$\begingroup\$ Ooh, that is {}. \$\endgroup\$ – Akangka Nov 23 '15 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 '15 at 16:10
1
\$\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\$
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\$
  • \$\begingroup\$ Blame Pastebin :P \$\endgroup\$ – LegionMammal978 Nov 23 '15 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\$ – Peter Taylor Nov 23 '15 at 14:36
  • \$\begingroup\$ @PeterTaylor Thanks for the golf and the hint. \$\endgroup\$ – Dennis Nov 23 '15 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\$ – Peter Taylor Nov 23 '15 at 18:59
  • \$\begingroup\$ @PeterTaylor That one magical 1|. Thanks again! \$\endgroup\$ – Dennis Nov 23 '15 at 19:10
2
\$\begingroup\$

Mathematica, 88 bytes

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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