# Reconstruct a recursively prime-encoded integer

Recursively prime-encoded integers

Consider $$\11681169775023850 = 2 \times 5 \times 5 \times 42239 \times 5530987843\$$. This isn't a nice prime factorisation, as $$\42239\$$ and $$\5530987843\$$ make it difficult to store this factorisation in a small manner. Being primes, we can't then factorise them, but we can factorise $$\p - 1\$$, which is guaranteed to not be prime (ignoring $$\p = 3\$$). by doing this we get:

• $$\42239 \to 42238 = 2 \times 7 \times 7 \times 431\$$
• $$\5530987843 \to 5530987842 = 2 \times 3 \times 17 \times 54225371\$$

This helps, but $$\431\$$ and $$\54225371\$$ are still pesky, so we run the same procedure (prime factorising their decrement). Just to be safe, we'll also do it with $$\17\$$ so that we can only have single digit primes ($$\2,3,5,7\$$) in the final result. This eventually results in:

[2, 5, 5, [2, 7, 7, [2, 5, [2, 3, 7]]], [2, 3, [2, 2, 2, 2], [2, 5, [2, 2, 2, 5], [2, 2, 2, 2, 2, [2, 2, [2, 2, 2, 3, [2, 3, 7]]]]]]]


representing $$\11681169775023850\$$. This is a program that shows the steps of decomposition of the input, and this is a program which decomposes a given integer.

The representations for the integers from 2 to 25 are:

 2 [2]
3 [3]
4 [2, 2]
5 [5]
6 [2, 3]
7 [7]
8 [2, 2, 2]
9 [3, 3]
10 [2, 5]
11 [[2, 5]]
12 [2, 2, 3]
13 [[2, 2, 3]]
14 [2, 7]
15 [3, 5]
16 [2, 2, 2, 2]
17 [[2, 2, 2, 2]]
18 [2, 3, 3]
19 [[2, 3, 3]]
20 [2, 2, 5]
21 [3, 7]
22 [2, [2, 5]]
23 [[2, [2, 5]]]
24 [2, 2, 2, 3]
25 [5, 5]


For example, for [2, [2, 5]], we first multiply the inner list and increment to get [2, 11]. From here, we just multiply, resulting in the final output of 22

You are to take the representation of a recursively prime-encoded integer and output the original integer.

The input will be a jagged list, where each element is either a single digit prime ($$\2,3,5,7\$$) or a list where the same rule applies. The input will never contain empty lists, and will never be empty.

This is , so the shortest code in bytes wins

## Test cases

[2, 2, 2, 5] -> 40
[[2, 2, 3]] -> 13
[[2, 3, 5]] -> 31
[3] -> 3
[2, 3, 3, 5] -> 90
[2, [2, [2, 5]]] -> 46
[[2, 5]] -> 11
[[2, 2, 7, [2, 2, 2, 2, 3, 7]]] -> 9437
[2, 2, 2, 2, 2, 3, 5] -> 480
[2, 2, 2, 7, [2, 2, 2, 2]] -> 952
[2, [2, 2, 3, 7, [2, 3, 3]]] -> 3194
[2, 3, 3, [2, 2, 2, 2, 2, 2, 7]] -> 8082
[5, [2, 2, 7], [2, [2, [2, 5]]]] -> 6815
[5, [2, [2, 2, [2, 2, 2, 5], [2, [2, 5, 5, 5]]]]] -> 824935
[3, 3, [2, 2, 3, 3], [2, 7, [2, [2, 2, 2, 5]]]] -> 387279
[7, [2, 2, 5, 5], [2, 3, 5, [2, 3, 7]]] -> 912737
[[2, [2, [2, 5, [2, 2, 3]], [2, 2, 2, 2, 3, 3, 7]]]] -> 528719
[2, 2, 2, 2, 7, [2, 5], [2, 2, [2, 2, 2, 2, 2, 2, 3]]] -> 952336
[2, 3, 3, [2, 3, 5], [2, 5, 5, [2, 2, 7]]] -> 809658
[[2, 2, 2, 3, [2, 2, [2, 3, 7]]], [2, 2, 2, 2, 2, 2, 3, [2, 2, 3], [2, 2, 7, [2, 3, 3, 7]], [2, 5, [2, 2, 2, [2, 5]], [2, [2, 2, [2, 2, 3]]]]]] -> 3511306351619449
[5, 7, 7, [2, 3, [2, 5], [2, [2, 2, 2, 5]]], [2, 2, 2, 7, [2, [2, [2, 2, 2, [2, 5]]]], [2, 2, 2, 2, 2, 3, 3, [2, 5, [2, 3, [2, 2, 2, 2]]]]]] -> 8013135306533035
[2, 3, 3, [2, 2, 2, 3, 3], [2, 3, [2, [2, 5]]], [2, 3, [2, 2, 3, [2, 2, 2, 2, 2, 3], [2, [2, 5, 7, 7]], [2, 2, [2, 5], [2, 2, [2, 2, 3]]]]]] -> 2925382459116618


# Python 2, 42 bytes

Thanks to @tsh for suggesting a 2-byte improvement

f=lambda x=1,*a:x<2or-(x*-1or~f(*x))*f(*a)


Try it online!

-(x*-1or~f(*x)) computes for a given element, its decoded value. If x is an integer, the or will short circuit, resulting in x as the value. If it is a list, x*-1 will return an empty list, and the result becomes a recursive call on x: -~f(*x).

This result is then multiplied by the rest of the elements through recursion: f(*a). Finally, the default x=1 argument assists in the terminating condition of x<2.

• Python 3, 43 bytes: f=lambda x=1,*a:x==1or-(x*-1or~f(*x))*f(*a)
– tsh
Jun 22 '21 at 2:57
• In case anybody is wondering about @tsh's modification: The original code relies on the < operator allowing comparisons between list and int. This is allowed in Python 2, but not in Python 3. Jun 23 '21 at 23:50

# APL (Dyalog Extended), 13 bytes

¯1+(≡+×/)⍥1⍣≡


Try it online!

Takes a nested APL array (which can be obtained from JSON-converting the test cases) and returns the original number.

### How it works

This uses the Depth operator f⍥n, which hasn't made into mainstream yet. A depth-1 value in a mixed array can be a vector or a scalar (if one of its siblings is nested). ≡+×/ is an expression that keeps scalar intact (product is itself and its depth ≡ is 0), and evaluates product + 1 for vectors. Now, we can simply repeat this at depth 1 until the entire value becomes a single number, and subtract 1 at the end (to negate the +1 applied at the very last layer).

• I don't think this answer can be ported to J, but I'd appreciate any ideas you have on improving my answer. It felt like it should be much simpler, but given the way J's L: and L. verbs work, and the requirements for cases like [ x x ] and [[ x x ]], things got ugly. Jun 22 '21 at 13:56

# yuno, 5 bytes

ᴘ’)υ‘


Try it online!

(ᴘ’)υ‘    Main Link
(  )υ     Deep Recurse; on each sub-list and recursively, call
ᴘ        - Product
’       - Increment
‘   Decrement


I've had the idea for υ from ever since I first started drafting yuno, but this adverb was implemented after this challenge.

Old version

# yuno, 7 bytes

ɫ’)ᴅ?Ͼᴘ


Try it online!

Expect this to get shorter later once I implement more adverbs.

For now, this is the same approach as my Jelly solution.

(ɫ’)ᴅ?Ͼᴘ    Main Link
Ͼ     For each item
?      - If
ᴅ         - It has depth (it is a list and not just a single number)
’           - And increment
ᴘ    Take the product

• I'm looking forward to yuno becoming more usable! Jul 9 '21 at 9:34

# Wolfram Language (Mathematica), 22 bytes

(#/.List->(1+1##&))-1&


Try it online!

 #/.List->(1+1##&)      Lists become the product of their arguments plus 1
(                 )-1&  subtract 1 (outermost list doesn't increment)

• so beautiful! +1 Jun 23 '21 at 4:22

# JavaScript (ES6), 35 bytes

f=a=>a.map(n=>p*=+n||f(n)+1,p=1)&&p


Try it online!

• You can save 1 byte by using | instead of &&. Jun 22 '21 at 2:12
• @HKboy but it failed on last 3 test cases.
– tsh
Jun 22 '21 at 2:19

y/,]/*)/;s/\[/(1+/g;$_=-1+eval  replacing [ , ,, ] with (1+, *, ) resp., and evaluating. Try it online! # Perl 5, 42 bytes sub f{my$r=1;map$r*=@$_?1+f(@$_):$_,@_;$r}  with a recursive function Try it online! # J, 46 45 bytes [:(*>:)/[:;L:1^:_[:*/L:0;~&1^:((1=#)*1<L.)L:2  Try it online! I thought this was going to be like 10 chars... • maybe Bubbler's solution would help with shortening this. Jun 22 '21 at 6:44 • @Razetime I don't see a way, but I asked him for ideas. Jun 22 '21 at 13:57 # Jelly, 9 bytes ß‘µ¹ŒḊ?€P  Try it online! ß‘µPŒḊ?€P Main Link € For each element: ? - If ŒḊ - It has depth (isn't a number) ß‘µ - Call this link on the sub-list, take the product, and increment it P - Otherwise, take the product (or first element, or sum, w/e) P Take the product  # Stax, 13 bytes â╥¡░Ω↕¬∟oqFµ+  Run and debug it recursion's a bit clunky here, but thankfully it works. # Ruby, 41 bytes f=->n{n.map{|x|x*0==0?x:f[x]+1}.reduce:*}  Try it online! • 40 bytes Jun 22 '21 at 8:12 # Retina, 34 bytes ~(,$*
^.
.+¶$$.( \[$$.(_
]
$*)  Try it online! Link includes test cases. Explanation: ,$*


Change all separators into multiplication operators.

^.
.+¶$$.(  Change the opening [ into code to replace the input with the product of the values. \[$$.(_


Change the remaining [s into code to increment the product of the values.

]
$*)  Change the ]s into code to terminate the product expressions. ~(  Evaluate the resulting program on the original input. For example, the input [2, 2, 2, 7, [2, 2, 2, 2]] is transformed into the following Retina program: .+$.(2*2*2*7*$.(_2*2*2*2*))  The 2*2*2*2* evaluates to ________________, so the $.(_) results in 17, and the outer multiplication then produces the final result of 952.

# Japt, 9 bytes

ËÉªßD)ÄÃ×


Takes advantage of the fact that the sub-arrays are never singletons.

ËÉªßD)ÄÃ×     :Implicit input of array
Ë             :Map each D
É            :  Subtract 1 (resulting in NaN if it's an array)
ª           :  Logical OR with
ßD         :  A recursive call with argument D
)        :  Group that together
Ä       :  Add 1 to the result
Ã      :End map
×     :Reduce by multiplication


# R, 65 57 bytes

r=function(l,z=0)if(is.list(l),prod(sapply(l,r,1))+z,l)


Try it online!

Recursively adds 1 to the product of all list elements.

This would end-up one-too-many, so we skip adding 1 for the outermost loop.

# MMIX, 56 bytes (14 instrs)

typedef union _rpe {
struct {
uint64_t flag : 1; // must be 1
uint64_t val : 63;
};
union _rpe *list;
} rpe;

uint64_t __mmixware rpd(rpe encoded);


Lists terminate on a union _rpe that isn't a list (flag is on) whose val is 0. (MMIX pointers must be positive for user programs, or a trap occurs.)

00000000: 48000003 ec008000 f8010000 fe010004  H¡¡¤ġ¡⁰¡ẏ¢¡¡“¢¡¥
00000010: e3020001 8f040000 e7000008 f303fff9  ẉ£¡¢Ɓ¥¡¡ḃ¡¡®ṙ¤”ż
00000020: 42030003 1a020203 f1fffffb f6040001  B¤¡¤ȷ££¤ȯ””»ẇ¥¡¢
00000030: 23000201 f8010000                    #¡£¢ẏ¢¡¡

rpd     BNN   $0,0F // if(encoded.flag) ANDNH$0,#8000
POP   1,0       // return encoded.val;
0H      GET   $1,rJ SET$2,1      // uint64_t i = 1;
0H      LDOU  $4,$0     // loop: rpe n = *encoded.list;
INCL  $0,8 // encoded++; PUSHJ$3,rpd    // uint64_t j = rpd(n);
BZ    $3,0F // if(!j) goto end; MULU$2,$2,$3  // i *= j;
JMP   0B        // goto loop;
0H      PUT   rJ,$1 ADDU$0,\$2,1
POP   1,0       // return i + 1;


# Charcoal, 33 bytes

ＦＳ≡ι[⊞υ¹]¿⊖Ｌυ⊞υ×⊕⊟υ⊟υＩυ¿Σι⊞υ×⊟υΣι


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

ＦＳ≡ι


Loop over and switch on the input characters.

[⊞υ¹


For [ push a 1 to the predefined empty list.

]¿⊖Ｌυ


For ] if the list has more than one element, then...

⊞υ×⊕⊟υ⊟υ


... increment the top element and multiply the second element by it, otherwise...

Ｉυ


... print the result.

¿Σι⊞υ×⊟υΣι


Otherwise for digits multiply the top element by the value of the digits.

• "if the list has more than one element" - could you save anything there with the knowledge that sub-lists will always have more than one element? Or does that statement apply to the top-level list, too? Jun 22 '21 at 9:30
• @Shaggy I'm referring to the predefined empty list that I'm using as a stack to know how deep in [s I am, rather than the input "list" between the [ and ].
– Neil
Jun 22 '21 at 9:37
• Ah, I get it now :) Jun 22 '21 at 9:43

# Gaia, 14 12 bytes

Defines a function which takes a nested list and returns an integer.

⟨::C⟨←)⟩¿⟩¦Π


Try it online!

⟨        ⟩¦     # map over each element in the input
::             # two copies of the TOS
C            # compare for two ints (0), count occurences for two lists (1)
⟨  ⟩¿       # if the TOS is truthy:
←)         #   recursively call the function and add 1
Π    # after the map: take the product


# Pari/GP, 37 bytes

f(a)=vecprod([if(#b',f(b)+1,b)|b<-a])


Try it online!