Descending dungeons of positional systems

Question

The sequence discussed in this challenge is a variant of the Descending Dungeons sequence family. Specifically, the sequence generation rules:

(A_b = A's base 10 representation read as a base b number, A = A_10)
A(0) = 10
A(n) = 10_(11_(12_(...(n+9)_(n+10))))

Your goal is to make a program which accepts a nonnegative integer n and returns A(n) of the descending dungeons sequence, using 0-indexing.

Base conversion built-ins are allowed.

Return the result itself in base 10.

Test cases: (A = B means input A returns B)

0 = 10
1 = 11
2 = 13
3 = 16
4 = 20
5 = 25
6 = 31
7 = 38
8 = 46
9 = 55
10 = 65
11 = 87
12 = 135
13 = 239
14 = 463
15 = 943
16 = 1967
17 = 4143
18 = 8751
19 = 18479
20 = 38959

Use OEIS A121263 for further test cases.

This is code golf, so the shortest program wins. Have fun.

Final sidenote: This sequence came to my attention through a recent Numberphile video discussing descending dungeon sequences.

Answer 1

Jelly, 9 bytes

Ż+⁵ṚDḅ¥@/

A monadic Link accepting a non-negative integer which yields a non-negative integer.

Try it online! Or see the test-suite.

How?

Ż+⁵ṚDḅ¥@/                  e.g. 5
Ż         - zero-range          [0,1,2,3,4,5]
  ⁵       - ten                 10
 +        - add                 [10,11,12,13,14,15]
   Ṛ      - reverse             [15,14,13,12,11,10]
        / - reduce by:          f(f(f(f(f(15,14),13),12),11),10)
       @  -   using swapped arguments:         e.g. f(y=15,x=14)
      ɗ   -     last two links as a dyad
    D     -       decimal (x)                       [1,4]            
     ḅ    -       convert (that) from base (y)      19
                           i.e. f(f(f(f(f(15,14),13),12),11),10)
                              = f(f(f(f(19,13),12),11),10)
                              = f(f(f(22,12),11),10)
                              = f(f(24,11),10)
                              = f(25,10)
                              = 25

Answer 2

Python 3, 75 72 bytes

f,g=lambda n:n and f(n-1)+n*g(n)or 10,lambda n:n and(n+9)//10*g(n-1)or 1

Try it online!

Explanation: On observing the terms, I came across this recursive relation

f(n) = f(n-1) + n*g(n) where g(n) is the product of first n terms of the sequence

1^1, 1^2, ... 1^10, 2^1, 2^2, 2^3, ... 2^10, 3^1, 3^2, 3^3 ...

---

Python 3, 69 65 bytes

f=lambda n:n<2and n+10or(f(n-1)-f(n-2))*n//~-n*((n+9)//10)+f(n-1)

Try it online!

Explanation: This is an even more recursive approach of the above solution, with the g function completely removed. However note that this one is highly inefficient.

f(n) = f(n-1) + n*g(n) implies g(n-1) = (f(n-1) - f(n-2))/(n-1)

---

Special thanks to Jo King for -4 bytes.

Answer 3

05AB1E, 6 bytes

ÝT+.«ö

Basically a golfed version of @hi.'s 05AB1E answer, which I suggested as a golf in the comments of his/her answer. Since I got no response, I figured I'd just post it myself instead.

Try it online or verify all test cases.

Explanation:

Ý       # Push a list in the range [0, (implicit) input-integer]
 T+     # Add 10 to each value in this list
   .«   # Right-reduce this list by:
     ö  #  Base-conversion
        # (after which the result is output implicitly)

You can replace the . with Å to see each step of the reduction (from right to left).

Answer 4

JavaScript (ES6), 54 bytes

n=>(F=i=>(g=k=>i>n?k:k&&k%10+F(i)*g(k/10|0))(++i+9))``

Try it online!

Commented

n => (                // n = input
  F = i => (          // F is a recursive function taking a counter i
    g = k =>          //   g is a recursive function taking a number k
                      //   and returning either k if i > n or k converted
                      //   from base F(i) to decimal otherwise
      i > n ?         //     if i is greater than n:
        k             //       just return k
      :               //     else:
        k &&          //       return 0 if k = 0
        k % 10 +      //       otherwise extract the last digit of k
        F(i) *        //       and add F(i) multiplied by the result of
        g(k / 10 | 0) //       a recursive call with floor(k / 10)
  )(++i + 9)          //   increment i; initial call to g with k = i + 9
)``                   // initial call to F with i zero'ish

Answer 5

Python 3, 110 107 87 85 90 bytes

f=lambda n,b=10:f(n-1,sum((int(v)*b**i)for i,v in enumerate(str(10+n)[::-1])))if n+1else b

Try it online!

Uses recursion to compute the solution.

Answer 6

Charcoal, 21 bytes

Ｎθ≔⁺θχηＦθ≔⍘Ｉ⁻⁺θ⁹ιηηＩη

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

Ｎθ

Input n.

≔⁺θχη

Start with n+10.

Ｆθ

Loop n times.

≔⍘Ｉ⁻⁺θ⁹ιηη

Cast the previous integer to string and interpret it using the current base.

Ｉη

Print the final value as a string.

Answer 7

Retina 0.8.2, 88 bytes

.+
10$*@$&$*;
(?!@)
$.`
\d+$
$*#
{`#(?=#*\d*;(#+)$)
$1
(\d)(\d*;#+)$
$1$*#$2
}`#;#+$
#
#

Try it online! Link includes some test cases (code gets too slow for TIO with larger numbers). Explanation:

.+
10$*@$&$*;

Convert the input to n ;s, and prepend with 10 @s.

(?!@)
$.`

Insert the decimal numbers 10..n+10 around the ;s.

\d+$
$*#

Convert the last number to unary using #s.

{`
}`

Reduce right-to-left over the list of numbers and left-to-right over the digits of each number.

#(?=#*\d*;(#+)$)
$1

Multiply the partial result so far by the base.

(\d)(\d*;#+)$
$1$*#$2

Add the next digit of the number to convert.

#;#+$
#

Once the number has been converted, delete the previous base, so that this result can serve as the base for the next conversion.

#

Once all of the numbers have been converted, convert the result to decimal.

Answer 8

Scala, 105...57 50 bytes

n=>((10 to n+10):\10)((i,r)=>(0/:s"$i")(_*r+_-48))

Scastie

Well, this has been a fun problem.

Explanation:

n =>
    ((10 to n+10) //A range from 10 to n+10
      :\10) (     //Fold it right with the initial value of 10
      (i, r) =>      //r is the current base, i is the counter
        (0 /: s"$i") //Make i a string/iterable of chars, and fold it left with an initial value of 0
           (_*r + _-48) //Multiply the previous value by r and add the current value to that (-48 because it's a Char and not a proper Int)
      )

Answer 9

Pyth, 12 bytes

.UijZTb}+TQT

Try it online!

Explanation

.UijZTb}+TQT
       }+TQT  # inclusive range [10 + input, 10]
.U            # reduce left to right by: f(b, Z)
   jZT        #   list of Z  (e.g. 123 -> [1, 2, 3])
  i   b       #   convert that from base b

Answer 10

Io, 101 bytes

method(x,Range 10 to(x+10)asList reverseReduce(i,j,j asString asList map(asNumber)reduce(x,y,x*i+y)))

Try it online!

Explanation

method(x,                // Take an argument x
    Range 10 to(x+10)    // [10..x+10]
    asList               // Reduce doesn't work on ranges
    reverseReduce(i,j,   // Reverse the list. Reduce (arguments i & j):

                         //     tl;dr base conversion from j (base 10) to base i
        j asString       //     Convert to string,
        asList           //     Convert to list,   (splits string into individual chars)
        map(asNumber)    //     (Map) Convert to number.
        reduce(x,y,      //     Reduce the digit list by (arguments x & y):
            x*i+y)))     //          x*i+y

Answer 11

R, 71 62 bytes

Edits: +3 bytes to fix output for edge-case of n=0, but then -12 bytes by skipping calculation of number of digits each step and simply calculating over an excessively large number of digits)

n=i=scan()+10;while((i=i-1)>10)n=sum(i%/%10^(m=i:0)%%10*n^m);n

Try it online!

Readable (un-golfed) version:

n=i=scan()+10               # get n and add 10; set i to same value as n
'%_%'=function(a,b)         # Define infix _ function 
                            # (this is incorporated directly inline in golfed code):
    m=rev(0:log10(a))       #   m = exponents-of-ten for each digit of a
                            #   (in golfed code we use m=a:0 which is much shorter
                            #   but uselessly includes exponentially more digits, 
                            #   which will all contribute zero to the final sum)    
    sum(                    #   get sum of... 
        a %/% 10^m %% 10    #   each base-10 digit of a...
        * b^m )             #   multiplied by corresponding exponent-of-b.
while((i=i-1)>10)           # Main loop from (n-1)..10:
    n = i %_% n             #   n = i _ n
n                           # Output n

Answer 12

APL (Dyalog Unicode), 25 21 18 bytes

• Saved 4 bytes thanks to @ovs
• Saved 3 bytes thanks to @Adám

(⊢⊥10⊥⍣¯1⊣)/9+⍳⎕+1

Try it online!

Accepts input through STDIN.

(⊢⊥10⊥⍣¯1⊣)/9+⍳⎕+1
             9+⍳⎕+1  ⍝ Create a range from 10 to n+10
            /        ⍝ Then fold over it with the train on the left:
   10(⊥⍣¯1)          ⍝ Get the digits of (inverse of interpreting in base 10)
           ⊣         ⍝ A (the number on the left).
 ⊥                   ⍝ Interpret in base
⊢                    ⍝ b (the accumulated value on the right)

Answer 13

Retina, 72 bytes

.+
*
L$`
0;$.($`10*
$
¶10
{+`\d+;(\d)(\d*¶(\d+))$
$.(*$3*_$1*);$2
;¶.+$

Try it online! Link includes test cases. Explanation:

.+
*

Convert the input to unary.

L$`
0;$.($`10*

For each integer in the range [0..n], output 0; followed by 10 more than the integer, in decimal. The decimal is the value to be converted to the appropriate base, and the 0; represents the initial value of the conversion.

$
¶10

Append an extra base 10 to simplify the algorithm.

{

Reduce (right-to-left) over the list of numbers.

+`

Reduce (left-to-right) over the second last number.

\d+;(\d)(\d*¶(\d+))$
$.(*$3*_$1*);$2

Multiply the result so far (implicitly the first number in the match) by the base ($3) and add the next digit of the second last number ($1).

;¶.+$

Delete the base.

Answer 14

Japt, 10 bytes

Port of Jonathan's Jelly solution.

AôU ÔrÏììX

Try it

AôU ÔrÏììX     :Implicit input of integer U
A              :10
 ôU            :Range [A,A+U]
    Ô          :Reverse
     r         :Reduce
      Ï        :X=current total (initially first element) Y=current element (initially the second)
       ì       :Convert Y to base-10 digit array
        ìX     :Convert from base-X digit array