9
\$\begingroup\$

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.

\$\endgroup\$

14 Answers 14

7
\$\begingroup\$

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
\$\endgroup\$
1
  • 1
    \$\begingroup\$ @Arnauld thanks, was just the final evaluation that had an error at f(22,12)=24 (where I gave 26 :/) \$\endgroup\$ Aug 8, 2020 at 16:54
4
\$\begingroup\$

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.

\$\endgroup\$
0
2
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
2
  • 2
    \$\begingroup\$ JS lambdas are terse, huh! \$\endgroup\$ Aug 8, 2020 at 16:58
  • 1
    \$\begingroup\$ When I saw your answer, I thought that Markdown in this answer wasn't working... \$\endgroup\$
    – user96495
    Aug 9, 2020 at 8:13
2
\$\begingroup\$

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.

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

Charcoal, 21 bytes

Nθ≔⁺θχηFθ≔⍘I⁻⁺θ⁹ιηηIη

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

Nθ

Input n.

≔⁺θχη

Start with n+10.

Fθ

Loop n times.

≔⍘I⁻⁺θ⁹ιηη

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

Iη

Print the final value as a string.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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)
      )
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
2
  • \$\begingroup\$ @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! \$\endgroup\$
    – user96495
    Aug 9, 2020 at 13:43
  • \$\begingroup\$ Ah, makes sense. I got that Range does not respond to 'to' exception and thought I must be doing something wrong with the parentheses. \$\endgroup\$
    – DLosc
    Aug 9, 2020 at 13:48
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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)
\$\endgroup\$
5
  • 1
    \$\begingroup\$ 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/… \$\endgroup\$
    – ovs
    Nov 24, 2020 at 15:20
  • \$\begingroup\$ @ovs That's really nice, thanks! \$\endgroup\$
    – user
    Nov 24, 2020 at 15:41
  • \$\begingroup\$ Full program, 18: (⊢⊥10⊥⍣¯1⊣)/9+⍳⎕+1 Try it online! \$\endgroup\$
    – Adám
    Dec 6, 2020 at 13:58
  • \$\begingroup\$ Any reason you only requested 50 rep for this? \$\endgroup\$
    – Adám
    Dec 6, 2020 at 14:04
  • \$\begingroup\$ @Adám Thanks! (Sorry, I didn't notice your first comment earlier) \$\endgroup\$
    – user
    Dec 6, 2020 at 19:21
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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