Base Neutral Numbering System

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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.

Answer 4

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

Answer 5

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.

Answer 6

Charcoal, 50 bytes

≔⟦⟧θＦ²⊞υ1ＦＥ…·²ＮΦ…²ι¬﹪ιλ⊞υ⎇ι⁺⁺§υ⌊ι*§υ⌈ι⪫<>§υＬ⊞Ｏθω⊟υ

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

≔⟦⟧θ

Start with no prime numbers discovered.

Ｆ²⊞υ1

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

ＦＥ…·²Ｎ

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

⪫<>§υＬ⊞Ｏθω

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

⊟υ

Output the final value.

Answer 7

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.

Answer 8

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

Answer 9

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

Answer 10

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 `®`

Answer 11

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

Answer 12

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.

Answer 13

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

Answer 14

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