Reconstruct a recursively prime-encoded integer

Question

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 code-golf, 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

This is very similar to jan Misali's proposed way of naming bases: youtube.com/watch?v=7OEF3JD-jYo — xigoi, Jul 9, 2021 at 9:29

dingledooper · Accepted Answer · 2021-06-22 05:57:20Z

11

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.

edited Jun 22, 2021 at 5:57

answered Jun 22, 2021 at 0:53

dingledooper

20.4k1 gold badge30 silver badges113 bronze badges

1

\$\begingroup\$ Python 3, 43 bytes: f=lambda x=1,*a:x==1or-(x*-1or~f(*x))*f(*a) \$\endgroup\$
– tsh
Jun 22, 2021 at 2:57
\$\begingroup\$ 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. \$\endgroup\$
– dan04
Jun 23, 2021 at 23:50

Add a comment |

Bubbler · Accepted Answer · 2021-06-22 06:39:33Z

8

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

answered Jun 22, 2021 at 6:39

Bubbler

70.3k5 gold badges139 silver badges428 bronze badges

\$\begingroup\$ 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. \$\endgroup\$
– Jonah
Jun 22, 2021 at 13:56

Add a comment |

hyper-neutrino · Accepted Answer · 2021-06-22 14:33:30Z

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)
(ɫ’)        - Monadic function:
 ɫ            - Call this link as a monad
  ’           - And increment
       ᴘ    Take the product

\$\begingroup\$ I'm looking forward to yuno becoming more usable! \$\endgroup\$
– xigoi
Jul 9, 2021 at 9:34 — xigoi, Jul 9, 2021 at 9:34

tsh · Accepted Answer · 2021-06-22 02:04:42Z

6

JavaScript (ES6), 35 bytes

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

Try it online!

answered Jun 22, 2021 at 2:04

tsh

33.1k2 gold badges32 silver badges122 bronze badges

\$\begingroup\$ You can save 1 byte by using | instead of &&. \$\endgroup\$
– HK boy
Jun 22, 2021 at 2:12
3

\$\begingroup\$ @HKboy but it failed on last 3 test cases. \$\endgroup\$
– tsh
Jun 22, 2021 at 2:19

Add a comment |

att · Accepted Answer · 2022-01-20 03:31:42Z

6

Wolfram Language (Mathematica), 22 17 bytes

1+1##&@@#&//@#-1&

Try it online!

1+1##&@@#&//@#      expressions become the product of their arguments plus 1
              -1&   subtract 1 (outermost list doesn't increment)

edited Jan 20, 2022 at 3:31

answered Jun 22, 2021 at 1:53

att

18.7k2 gold badges13 silver badges54 bronze badges

1

\$\begingroup\$ so beautiful! +1 \$\endgroup\$
– Greg Martin
Jun 23, 2021 at 4:22

Add a comment |

Nahuel Fouilleul · Accepted Answer · 2021-06-22 11:32:06Z

4

Perl 5 (`-p`), 30 bytes

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!

answered Jun 22, 2021 at 11:32

Nahuel Fouilleul

8,0891 gold badge8 silver badges17 bronze badges

Add a comment |

Jonah · Accepted Answer · 2021-06-22 02:17:42Z

3

J, ⁴⁶ 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...

edited Jun 22, 2021 at 2:17

answered Jun 22, 2021 at 2:06

Jonah

31.5k4 gold badges35 silver badges88 bronze badges

\$\begingroup\$ maybe Bubbler's solution would help with shortening this. \$\endgroup\$
– Razetime
Jun 22, 2021 at 6:44
\$\begingroup\$ @Razetime I don't see a way, but I asked him for ideas. \$\endgroup\$
– Jonah
Jun 22, 2021 at 13:57

Add a comment |

hyper-neutrino · Accepted Answer · 2021-06-22 00:46:31Z

2

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

edited Jun 22, 2021 at 0:46

answered Jun 22, 2021 at 0:28

hyper-neutrino♦

40.8k5 gold badges65 silver badges219 bronze badges

Add a comment |

Razetime · Accepted Answer · 2021-06-22 06:45:47Z

2

Stax, 13 bytes

â╥¡░Ω↕¬∟oqFµ+

Run and debug it

recursion's a bit clunky here, but thankfully it works.

answered Jun 22, 2021 at 6:45

Razetime

26.6k3 gold badges26 silver badges71 bronze badges

Add a comment |

G B · Accepted Answer · 2021-06-22 06:49:37Z

2

Ruby, 41 bytes

f=->n{n.map{|x|x*0==0?x:f[x]+1}.reduce:*}

Try it online!

answered Jun 22, 2021 at 6:49

G B

19.9k1 gold badge19 silver badges50 bronze badges

\$\begingroup\$ 40 bytes \$\endgroup\$
– dingledooper
Jun 22, 2021 at 8:12

Add a comment |

Neil · Accepted Answer · 2021-06-22 08:10:48Z

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.

Shaggy · Accepted Answer · 2021-06-22 08:53:26Z

Japt, 9 bytes

ËÉªßD)ÄÃ×

Try it or test 2-25 or run all test cases

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

Dominic van Essen · Accepted Answer · 2021-06-22 09:25:06Z

2

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.

edited Jun 22, 2021 at 9:25

answered Jun 22, 2021 at 8:53

Dominic van Essen

31k2 gold badges16 silver badges51 bronze badges

Add a comment |

NoLongerBreathedIn · Accepted Answer · 2021-07-08 19:19:07Z

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;

Neil · Accepted Answer · 2021-06-22 08:32:32Z

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.

answered Jun 22, 2021 at 8:32

Neil

158k12 gold badges69 silver badges268 bronze badges

\$\begingroup\$ "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? \$\endgroup\$
– Shaggy
Jun 22, 2021 at 9:30
\$\begingroup\$ @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 ]. \$\endgroup\$
– Neil
Jun 22, 2021 at 9:37
\$\begingroup\$ Ah, I get it now :) \$\endgroup\$
– Shaggy
Jun 22, 2021 at 9:43

Add a comment |

ovs · Accepted Answer · 2021-06-22 10:03:10Z

1

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

edited Jun 22, 2021 at 10:03

answered Jun 22, 2021 at 9:49

ovs

56.8k3 gold badges42 silver badges150 bronze badges

Add a comment |

alephalpha · Accepted Answer · 2022-01-12 03:48:26Z

1

Pari/GP, 37 bytes

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

Try it online!

answered Jan 12, 2022 at 3:48

alephalpha

41.9k7 gold badges53 silver badges157 bronze badges

Add a comment |

Stack Exchange Network

Reconstruct a recursively prime-encoded integer

Test cases

17 Answers 17

Python 2, 42 bytes

APL (Dyalog Extended), 13 bytes

How it works

yuno, 5 bytes

yuno, 7 bytes

JavaScript (ES6), 35 bytes

Wolfram Language (Mathematica), 22 17 bytes

Perl 5 (`-p`), 30 bytes

Perl 5, 42 bytes

J, ⁴⁶ 45 bytes

Jelly, 9 bytes

Stax, 13 bytes

Ruby, 41 bytes

Retina, 34 bytes

Japt, 9 bytes

R, 65 57 bytes

MMIX, 56 bytes (14 instrs)

Charcoal, 33 bytes

Gaia, 14 12 bytes

Pari/GP, 37 bytes

Your Answer

Not the answer you're looking for? Browse other questions tagged
code-golf
math
primes
ragged-list
or ask your own question.

Hot Network Questions

Reconstruct a recursively prime-encoded integer

Test cases

17 Answers 17

Python 2, 42 bytes

APL (Dyalog Extended), 13 bytes

How it works

yuno, 5 bytes

yuno, 7 bytes

JavaScript (ES6), 35 bytes

Wolfram Language (Mathematica), 22 17 bytes

Perl 5 (-p), 30 bytes

Perl 5, 42 bytes

J, 46 45 bytes

Jelly, 9 bytes

Stax, 13 bytes

Ruby, 41 bytes

Retina, 34 bytes

Japt, 9 bytes

R, 65 57 bytes

MMIX, 56 bytes (14 instrs)

Charcoal, 33 bytes

Gaia, 14 12 bytes

Pari/GP, 37 bytes

Your Answer

Sign up or log in

Post as a guest

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

Related

Hot Network Questions

Perl 5 (`-p`), 30 bytes

J, ⁴⁶ 45 bytes

Not the answer you're looking for? Browse other questions tagged
code-golf
math
primes
ragged-list
or ask your own question.