# Descending dungeons of positional systems

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.

# 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
Ṛ      - 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)
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

• @Arnauld thanks, was just the final evaluation that had an error at f(22,12)=24 (where I gave 26 :/) Aug 8, 2020 at 16:54

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

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

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

# 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

• JS lambdas are terse, huh! Aug 8, 2020 at 16:58
– user96495
Aug 9, 2020 at 8:13

# Python 3, 1101078785 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.

• I'm not sure that the default rules allow you to have a second parameter.
– Neil
Aug 8, 2020 at 20:25
• @Neil thanks, fixed. Aug 9, 2020 at 6:27

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

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

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


# 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


# 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

• @DLosc No, you can't do that. The starting value of a range has to be a constant integer, you can't afford to have variables in them. Try it!
– user96495
Aug 9, 2020 at 13:43
• Ah, makes sense. I got that Range does not respond to 'to' exception and thought I must be doing something wrong with the parentheses. Aug 9, 2020 at 13:48

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

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


# APL (Dyalog Unicode), 2521 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)

• Based on the APLcart entry for Digits of N, the inner dfn can be shortened to {⍵⊥10(⊥⍣¯1)⍺}. And by converting the outer dfn to a train another byte can be saved: tio.run/##SyzI0U2pTMzJT///v/pR79ZHXUsNDTSA5KPexYfWG2o@6t1Vq2@p/…
– ovs
Nov 24, 2020 at 15:20
• @ovs That's really nice, thanks!
– user
Nov 24, 2020 at 15:41
• Full program, 18: (⊢⊥10⊥⍣¯1⊣)/9+⍳⎕+1 Try it online!
Dec 6, 2020 at 13:58
• Any reason you only requested 50 rep for this?
Dec 6, 2020 at 14:04
– user
Dec 6, 2020 at 19:21

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

# 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