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
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ @Arnauld thanks, was just the final evaluation that had an error at f(22,12)=24 (where I gave 26 :/) \$\endgroup\$ – Jonathan Allan Aug 8 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.

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

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ I'm not sure that the default rules allow you to have a second parameter. \$\endgroup\$ – Neil Aug 8 at 20:25
  • 2
    \$\begingroup\$ @Neil thanks, fixed. \$\endgroup\$ – Manish Kundu Aug 9 at 6:27
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).

| improve this answer | |
\$\endgroup\$
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.

| improve this answer | |
\$\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.

| improve this answer | |
\$\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)
      )
| improve this answer | |
\$\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
| improve this answer | |
\$\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
| improve this answer | |
\$\endgroup\$
  • \$\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 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 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
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

APL (Dyalog Unicode), 25 21 bytes

Saved 4 bytes thanks to @ovs

{⍵⊥10(⊥⍣¯1)⍺}/9+∘⍳1+⊢

Try it online!

{⍵⊥10(⊥⍣¯1)⍺}/9+∘⍳1+⊢
               9+∘⍳1+⊢  ⍝ Create a range from 10 to n+10
              /        ⍝ Then fold over it
    10(⊥⍣¯1)⍺          ⍝ Get the digits of A
 ⍵⊥                   ⍝ Interpret in base b
| improve this answer | |
\$\endgroup\$
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.

| improve this answer | |
\$\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
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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