37
\$\begingroup\$

It frustrates me that when you say "base 16", the 16 is in base 10. We need a base neutral way of writing down numbers when favoring a specific base would be inappropriate.

How it works

We define <n> to be the nth prime. So <1>=2, <2>=3, <3>=5. Note that every positive integer can be uniquely represented by the product of some number of <> expressions. For example 6 can be written as <1>*<2>.

However, in this form we still have numbers that need to be represented in some base. So we must recurse on each term. Until we reach the number 1, which has the same value almost in any base.

Your challenge is to print positive integer in this base neutral format.

I hope the examples will make things more clear:

Test cases

base 10 base neutral Explanation
1 1 1 can't be factored
2 <1> 2 is the first prime
3 <<1>> 3 is the second prime, 2 is the first prime
4 <1> * <1> 2 times 2
5 <<<1>>> 5 is the third prime
6 <1> * <<1>> 2 times 3
10 <1> * <<<1>>>
13 <<1> * <<1>>> 6th prime
255 <<1>> * <<<1>>> * <<<1> * <1>>> 3 * 5 * 17, 17 is the 7th prime, 7 is the 4th prime

You may replace * with any symbol of you prefer. You may replace <> with {},[] or () if you prefer, as long as you don't use the symbol replacing *. The 1 must stay a 1 though. You may also add spaces or line breaks anywhere. The spaces in the examples are just for clarity and you may omit them.

For example, a valid output would be [[1], [1]] or {{1 }%{1 }} for the number 7.

This is code golf. Shortest answer in each language wins.

\$\endgroup\$
14
  • 4
    \$\begingroup\$ Can we omit the 1s? (just have <>) \$\endgroup\$
    – naffetS
    Commented Nov 24, 2022 at 18:52
  • 2
    \$\begingroup\$ No, that would mean 1 would not be representable \$\endgroup\$
    – mousetail
    Commented Nov 24, 2022 at 19:48
  • 12
    \$\begingroup\$ This is an awesome question. There is something fascinating about representing a number not only by its multiplicity, but the multiplicity of its prime factor's indices too... \$\endgroup\$ Commented Nov 25, 2022 at 5:05
  • 3
    \$\begingroup\$ Is 1*<1> a valid representation of the number 2? It obviously isn't as short as just <1>, but seems to evaluate correctly... \$\endgroup\$ Commented Nov 25, 2022 at 10:53
  • 3
    \$\begingroup\$ The question says "print" but a few answers are a function that returns a list which can create the string to print by removing the leading and trailing characters from their representation. Could you state whether or not this is allowed? (As a reference My Jelly submission would be 9 if it is acceptable and 15 if not for example.) \$\endgroup\$ Commented Nov 25, 2022 at 19:57

15 Answers 15

8
\$\begingroup\$

Vyxal, 13 bytes

λǐÞpvḟ›vx1w$∨

Try it Online! Output is an array, so there is an extra pair of brackets on the outside. 1w$∨ can be removed if we can omit the 1s.

λǐÞpvḟ›vx1w$∨
λ               # Open a lambda for recursion
 ǐ              # Get the prime factors
  Þpvḟ›         # Find the one-indexed index of each in an infinite list of primes
       vx       # Recurse over each
         1w$∨   # Logical OR with [1] (replace empty lists with [1])
\$\endgroup\$
7
\$\begingroup\$

JavaScript (ES6), 92 bytes

Borrowing an optimization from Jakque's answer, as suggested by @Mukundan314.

f=(n,k=2,p=1)=>n<2?1:n%k?f(n,k+1,p+(P=d=>k%--d?P(d):d<2)(k)):`<${f(p)}>`+(n>k?'*'+f(n/k):'')

Try it online!


JavaScript (ES6), 96 bytes

-4 thanks to @Mukundan314

f=(n,m,k=2,p=1)=>n>1?n%k?f(n,m,k+1,p+(P=d=>k%--d?P(d):d<2)(k)):[m]+`<${f(p)}>`+f(n/k,'*'):m?'':1

Try it online!

Commented

f = (             // f is a recursive function taking:
  n,              //   n = input
  m,              //   m = either undefined or '*'
  k = 2,          //   k = current divisor
  p = 1           //   p = 1-based index of the smallest prime >= k
) =>              //
n > 1 ?           // if n is greater than 1:
  n % k ?         //   if k is not a divisor of n:
    f(            //     do a recursive call:
      n,          //       leave n unchanged
      m,          //       leave m unchanged
      k + 1,      //       increment k
      p + (       //       pass either p or p + 1
        P = d =>  //       according to the result of P(k)
        k % --d ? //       where P is a recursive helper function
          P(d)    //       testing whether k is prime
        :         //
          d < 2   //
      )(k)        //
    )             //     end of recursive call
  :               //   else:
    [m] +         //     append m (force an empty string if undefined)
    `<${f(p)}>` + //     append '<', followed by f(p), followed by '>'
    f(            //     append the result of a recursive call:
      n / k,      //       divide n by k
      '*'         //       enable the multiply sign
    )             //     end of recursive call
:                 // else:
  m ? '' : 1      //   stop the recursion; append '1' if m is undefined
\$\endgroup\$
3
  • \$\begingroup\$ 88 bytes by outputting nested lists. \$\endgroup\$ Commented Nov 25, 2022 at 7:39
  • 1
    \$\begingroup\$ 92 bytes by implicitly determining m based on n>k (inspired by @Jakque answer) \$\endgroup\$ Commented Nov 25, 2022 at 13:38
  • \$\begingroup\$ 86 bytes by applying same trick to the nested lists version \$\endgroup\$ Commented Nov 25, 2022 at 13:40
7
\$\begingroup\$

Python 3, 90 89 bytes

f=lambda n,i=2,p=1:1//n or n%i and f(n,i+1,p+(f(i)>"."))or(n>i)*f" {f(n/i)}*"+f"<{f(p)}>"

Try it online!

"You may also add spaces or line breaks anywhere"

Wait a minute, I can totally (ab)use that!

Explanation :

f=lambda n,i=2,p=1:
# f: recursive function
## n: input
## i: increment to have a prime that divide n
## p: prime index of i

1//n          # if n == 1: return 1
or              # else 
n%i and f(      # if i is not a divisor of n recurse
  n,              # with same input
  i+1,            # increment i
  p+(f(i)>"."))   # increment p if i is prime (no leading space)
or              # then (assuming that i is prime and divide n and p the index of i)
(n>i)*          # if n//i > 1 
  f" {f(n/i)}*"   # recurse adding a space before and a "*" after
+f"<{f(p)}>"    # add to the representation of i

-1 byte thanks to @Dominic van Essen

Python 3, 99 83 77 bytes, cheaty (but totally legit) version

This version abuse of list representation and the fact that <...> * 1 is "equal" to <...> to produce non canonic expressions. But the author authorised it so ¯\_(ツ)_/¯

<...> * <...> representation is [...], [...] with total result enclosed with []

f=lambda n,i=2,p=1:1//n*[1]or n%i and f(n,i+1,p+2//len(f(i)))or[f(p)]+f(n//i)

Try it online!

the process is the same but we check the length of f(i) do detect if it is prime.

\$\endgroup\$
10
  • 2
    \$\begingroup\$ I'm all in favour of being creative with the rules, but removing a pair of brackets outside the function proper crosses the line IMO. \$\endgroup\$
    – loopy walt
    Commented Nov 26, 2022 at 13:41
  • 1
    \$\begingroup\$ I agree with @loopywalt, althouth I notice that the Vyxal & 05ab1e answers are also essentially doing this. Is it really so uncompetitive to actually include the code to generate the correct output? \$\endgroup\$ Commented Nov 26, 2022 at 13:48
  • 1
    \$\begingroup\$ @loopywalt Dominic_van_Essen You're right. I added a non cheaty solution \$\endgroup\$
    – Jakque
    Commented Nov 26, 2022 at 15:39
  • \$\begingroup\$ @Jakque - Well done. I like it. \$\endgroup\$ Commented Nov 26, 2022 at 20:06
  • 1
    \$\begingroup\$ I don't think you need // since n%i is already zero at that point, so you can save a byte using /... \$\endgroup\$ Commented Nov 26, 2022 at 21:57
7
\$\begingroup\$

Jelly, 9 bytes

ÆfÆC߀;¹?

Try it online!

A monadic Link that accepts a positive integer and yields a ragged list of ones - that is, a list of 1s where inner nesting is the prime counting and adjacency is multiplication.


A full program that prints that without the outer [] is \$15\$ bytes:

ÆfÆC߀;¹?
ÇŒṘṖḊ

Try it online!

How?

ÆfÆC߀;¹? - Helper Link: positive integer, I
Æf        - prime factors
  ÆC      - number of primes up to (vectorises across that)
        ? - if...
       ¹  - ...condition: no-op
    ߀    - ...then: call this Link for each
      ;   - ...else: concatenate (I) - N.B. Only 1 has no prime factors, so concatenate 1.

ÇŒṘṖḊ - Main Link: positive integer, I
Ç     - call the Helper Link (with I)
 ŒṘ   - get the Python representation (of that)
   Ṗ  - pop
    Ḋ - dequeue
      - implicit print
\$\endgroup\$
4
\$\begingroup\$

Retina 0.8.2, 70 bytes

.+
$*
{+`\b(11+)(\1)+\b
$1*1$#2$*
\b1(1((?<!\b\3+(11+)))?)+\b
<$#2$*1>

Try it online! Link includes test cases. Explanation:

.+
$*

Convert to unary.

{`

Repeat until no more numbers can be decomposed.

+`\b(11+)(\1)+\b
$1*1$#2$*

Decompose numbers into their prime factors. (Note that this outputs the factors in descending order as that's golfier.)

\b1(1((?<!\b\3+(11+)))?)+\b
<$#3$*1>

Decompose primes into their index.

\$\endgroup\$
4
\$\begingroup\$

Charcoal, 50 bytes

≔⟦⟧θF²⊞υ1FE…·²NΦ…²ι¬﹪ιλ⊞υ⎇ι⁺⁺§υ⌊ι*§υ⌈ι⪫<>§υL⊞Oθω⊟υ

Try it online! Link is to verbose version of code. Explanation:

≔⟦⟧θ

Start with no prime numbers discovered.

F²⊞υ1

Start with a dummy entry for 0 and an entry of 1 for 1.

FE…·²N

Loop from 2 to the input...

Φ…²ι¬﹪ιλ

... finding the factors of each number, ...

⊞υ⎇ι

... if the number has nontrivial proper factors, then push...

⁺⁺§υ⌊ι*§υ⌈ι

... the concatenation of the representations for the lowest and highest factor with an intermediate *, otherwise push...

⪫<>§υL⊞Oθω

... the representation of the incremented count of primes found so far, wrapped in <>.

⊟υ

Output the final value.

\$\endgroup\$
4
\$\begingroup\$

Python 3, 108 bytes

f=lambda n,k=2,p=1,m=1:n>1and(n%k and f(n,k+1,p+all(k%i for i in range(2,k)),m)or[f(p)]+f(n/k,k,p,0))or[1]*m

Try it online!

Suggested by Mukundan314. Outputs nested lists.

Python 3, 140 139 136 135 bytes

f=lambda n,k=2,p=1,m='':(f(n,k+1,p+all(k%i for i in range(2,k)),m)if n%k else m+f'<{f(p)}>'+f(n/k,k,p,'*'))if n>1 else'1'if m==''else''

Try it online!

  • -1 thanks to Arnauld
  • -3 thanks to Seb

Port of Arnauld's JavaScript answer. Outputs the string shown in the test cases.

\$\endgroup\$
7
  • \$\begingroup\$ Do you really need the parentheses in (m+'1'if m==''else'')? \$\endgroup\$
    – Arnauld
    Commented Nov 24, 2022 at 21:25
  • 1
    \$\begingroup\$ @Arnauld Yes, because if/else precedence in python would mean that x if y else c if d else e parses as (x if y else c) if d else e. However, this could be rewritten with and/or to save bytes. \$\endgroup\$
    – naffetS
    Commented Nov 25, 2022 at 3:41
  • \$\begingroup\$ 108 bytes, by returning nested lists and using and/or \$\endgroup\$ Commented Nov 25, 2022 at 4:07
  • \$\begingroup\$ @Steffan Are you sure? In this example, f0 behaves like f1, not like f2. \$\endgroup\$
    – Arnauld
    Commented Nov 25, 2022 at 8:24
  • 1
    \$\begingroup\$ @Arnauld I think you're right. Thanks for that! \$\endgroup\$
    – The Thonnu
    Commented Nov 25, 2022 at 17:20
4
\$\begingroup\$

Wolfram Language (Mathematica), 58 bytes

#0/@(Join@@Table@@@FactorInteger@#/.#->PrimePi@#/.{0}->1)&

Try it online!

Uses { } to represent both operations, depending on the number of elements. Test output converts lists with >1 element into NonCommutativeMultiply (**) for clarity.

    Join@@Table@@@FactorInteger@#                       prime factorize
#0/@                                                    recurse on factors
                                 /.#->PrimePi@#         prime input: recurse on #prime instead
                                               /.{0}->1 1=input: return 1
\$\endgroup\$
3
\$\begingroup\$

sclin, 43 bytes

P/"*`"mapf"$P rev.= find:1+ @"map""Q1.,, |#

Try it here! Outputs as [[[1]] [[[1]]] [[[1] [1]]]] where each space replaces *.

For testing purposes:

[1 2 3 4 5 6 10 13 255] ( ; f>o ) map
P/"*`"mapf"$P rev.= find:1+ @"map""Q1.,, |#

Explanation

Prettified code:

P/ \*` mapf ( $P rev.= find: 1+ @ ) map dup 1.,, |#
  • P/ \*` mapf prime factors converted from frequency map to list
  • (...) map for each prime factor...
    • $P rev.= find: 1+ get its index (1-indexed)
    • @ execute this line (i.e. recurse)
    • since 1's list of prime factor is empty, map doesn't trigger recursion on 1s
  • dup 1.,, |# replace empty list with [1]
    • boolean check works here because empty lists are falsy in sclin
\$\endgroup\$
3
\$\begingroup\$

05AB1E, 17 bytes

"Di¸ëÒεÅPg®.V"©.V

Recursion isn't exactly 05AB1E's strong suit.. As in, I have to use strings and evals to mimic recursive behavior.

Outputs just like some of the other answers as a nested list, including additional wrapped list around the entire output (e.g. [[[1],[1]]] for \$n=7\$).

Try it online or verify all test cases.

Explanation:

"..."      # Push the recursive string explained below
     ©     # Store it in variable `®` (without popping)
      .V   # Evaluate and execute it as 05AB1E code,
           # using the (implicit) input-integer as argument
           # (after which the result is output implicitly)

D          # Duplicate the current integer
 i         # If it's exactly 1:
  ¸        #  Wrap this 1 inside a list: [1]
 ë         # Else:
  Ò        #  Get the prime factors (including duplicates) of the integer
   ε       #  Map over each prime factor:
    ÅP     #   Convert it to a list of primes <= this prime factor
      g    #   Pop and push the length to get the amount of primes in this list
       ®.V #   Do a recursive call by evaluating and executing string `®`
\$\endgroup\$
3
\$\begingroup\$

C++, 156 bytes

(+40 bytes of header includes) Try it online!

Header:

#include <string>
#include <iostream>

My attempt at code. I find this exercise horrible, yet fascinating :)

void F(int v,std::string&o){if(v<2)o+=49;int c=1,i=1,p,j;for(;++i<=v;){p=j=1;for(;++j<i;)p&=i%j;while(v%i==0){v/=i;o+=60;F(c,o);o+=62;if(v!=1)o+=42;}c+=p;}}

Footer (calling the function):

int main() {
    auto numbers = { 1,2,3,4,5,6,10,13,255 };
    for (int number : numbers) {
        std::string result;
        F(number, result);
        std::cout << "base 10: " << number << "\tbase neutral: " << result << "\n";
    }
}

Output:

base 10: 1   base neutral: 1
base 10: 2   base neutral: <1>
base 10: 3   base neutral: <<1>>
base 10: 4   base neutral: <1>*<1>
base 10: 5   base neutral: <<<1>>>
base 10: 6   base neutral: <1>*<<1>>
base 10: 10  base neutral: <1>*<<<1>>>
base 10: 13  base neutral: <<<1>>>
base 10: 255 base neutral: <<1>>*<<<1>>>*<<<1>>>
\$\endgroup\$
2
  • \$\begingroup\$ Welcome to Code Golf, and nice answer! \$\endgroup\$ Commented Nov 28, 2022 at 4:43
  • \$\begingroup\$ "Horrible but facinating" is a good summary of code golf \$\endgroup\$
    – mousetail
    Commented Nov 28, 2022 at 7:07
2
\$\begingroup\$

R, 94 92 bytes

Edit: -2 bytes thanks to pajonk

f=\(n,i=2,p=1)`if`(n<2,1,`if`(n%%i,f(n,i+1,p+(sum(!i%%2:i)<2)),paste(f(n/i),"*<",f(p),">")))

Attempt This Online!Outputs non-minimal base-neutral representations, as allowed, including quite a lot of 1*s, but all expressions should evaluate correctly.

Based initially on Jakque's Python answer (upvote it) and golfed from there.

\$\endgroup\$
1
  • \$\begingroup\$ : has higher precedence than %%, so -2 bytes. \$\endgroup\$
    – pajonk
    Commented Nov 28, 2022 at 12:53
1
\$\begingroup\$

Python 3, 483 bytes

f=lambda n,p=2:[]if n==1 else [p]+f(n//p,p=p)if n%p==0 else f(n,p=list(filter(lambda x:all(x%i!=0for i in range(2,(x//2)+1,2)),range(p+1,2*p)))[0])
g=lambda p,t=2,c=1:c if p in list(filter(lambda x:all(x%i!=0 for i in range(2,x)),range(2,t+1)))else g(p,t=list(filter(lambda x:all(x%i!=0 for i in range(2,x)),range(t+1,2*t)))[0],c=c+1)
r=lambda n:[[i]if i==1 else r(i)for i in[g(i)for i in f(n)]]
s=lambda n:str((lambda n:[[i]if i==1 else r(i)for i in [g(i)for i in f(n)]])(n))[1:-1]

Try online!

More cleaner version:

f = lambda n, p=2: [] if n==1 else [p] + f(n//p, p=p) if n%p == 0 else f(n, p=list(filter(lambda x: all(x%i != 0 for i in range(2, (x//2)+1, 2)), range(p+1, 2*p)))[0])
g = lambda p, t=2, c=1: c if p in list(filter(lambda x: all(x%i != 0 for i in range(2, x)), range(2, t+1))) else g(p, t=list(filter(lambda x: all(x%i != 0 for i in range(2, x)), range(t+1, 2*t)))[0], c=c+1)
r = lambda n: [[i] if i == 1 else r(i) for i in [g(i) for i in f(n)]]
s = lambda n: str((lambda n: [[i] if i == 1 else r(i) for i in [g(i) for i in f(n)]])(n))[1:-1]

Explanation:

f will factor the input numbers and return the factorization result in a list.

>>> f(12)
[2, 2, 3]

g's input is a prime and return the index of that prime. In other words n = g(p) means that p is the nth prime number.

>>> g(2)
1
>>> g(3)
2
>>> g(13)
6
\$\endgroup\$
1
\$\begingroup\$

JavaScript(ES2021)

Nested list output version, 86 80 bytes

f=(n,a=[1,[1]],m=1)=>a[n]??=n%++m?f(n,a,m,f(m,a)):[f(n>m?a[0]:a[0]++),...f(n/m)]

Attempt This Online!

String output version, 89 85 82 bytes

f=(n,a=[1,1],m=1)=>a[n]??=n%++m?f(n,a,m,f(m,a)):'<'+f(n>m?a[0]:a[0]++)+'>*'+f(n/m)

Attempt This Online!


The output contains extraneous *1s.

This "string version" actually returns a number for input 1 and a string for other input numbers. This can be changed for +2 bytes.


Explanation

Algorithm

The gist of the algorithm is to find the smallest factor m≥2 of n by brute-force trial division. Note that such an m must exist because n itself fits the criteria. Also note that m must be prime. Let m be the kth prime

During each iteration of the brute-force loop, we call f on the current divisor and cache the results in an array a. This ensures each prime < m is processed exactly once before we find m.

That way, we can use a simple counter to determine k, by making f(x) increment the counter if and only if x is prime. Since 0 is not valid input, we can just use a[0] as the counter.

Once m is found, we recurse using the fact n = m * (n/m) = <k> * (n/m). I.e.

f(n) =  '<' + f(k) + '>*' + f(n/m)

with the base case being f(1) = '1'.

Ungolfed code

Changed the brute-force division from recursion to loop. Also changed the initial loop variable to make the code more idiomatic.

function f(n, a = [1,[1]]) {
    if (a[n] !== undefined) {
        return a[n];
    }

    for (let m = 2;; m++) {
        if (n % m !== 0) {
            // This increments a[0] exactly once if m is prime
            f(m, a);
        } else {
            // Found a factor m, which is the a[0]-th prime

            // Increment the counter if m==n (i.e. n is prime)
            const k = n > m ? a[0] : a[0]++;

            // Recurse (discard cache to save keystrokes)
            return a[n] = '<' + f(k) + '>*' + f(n/m)
        }
    }
}
\$\endgroup\$
1
\$\begingroup\$

Retina, 61 bytes

{+`\b(11+)(\1)+\b
1$#2*1,$.1*1
11+
<$&>
(?=(11+)\1+\b|\b11)1

Attempt This Online!

Input is in unary. Output is same as OP except using , instead of *

Explanation

+`\b(11+)(\1)+\b
1$#2*1,$.1*1

Completely factorize each composite number, using a loop that extract one factor per iteration.

So, we are left with only ones and primes in the working string


11+
<$&>

Wrap each prime in <>


(?=(11+)\1+\b|\b11)1

Now we need to convert each prime into its "prime index". We do so by removing 1s:

  • whose position from the end of the number is composite, or
  • that is the first 1 in the number and is follow by at least another 1

For example, take 5 as an example

1 1 1 1 1
↑ ↑ ↑ ↑ ↑
| | └-┴-┴------- Keep these
| └------------- Remove, because it is 4th 1 from the right, and 4 is composite 
└--------------- Remove, because it is the first 1 and is followed by another 1

Finally, we loop all of the above ({) until fixpoint

\$\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.