Generalised Taxicab Numbers

Question

\$\newcommand{T}[1]{\text{Ta}(#1)} \newcommand{Ta}[3]{\text{Ta}_{#2}^{#3}(#1)} \T n\$ is a function which returns the smallest positive integer which can be expressed as the sum of 2 positive integer cubes in \$n\$ different ways. For example, \$\T 1 = 2 = 1^3 + 1^3\$ and \$\T 2 = 1729 = 1^3 + 12^3 = 9^3 + 10^3\$ (the Hardy-Ramanujan number).

Let's generalise this by defining a related function: \$\Ta n x i\$ which returns the smallest positive integer which can be expressed as the sum of \$x\$ \$i\$th powers of positive integers in \$n\$ different ways. In this case, \$\T n = \Ta n 2 3\$ (note: this is the same function here, \$\Ta n x i = \text{Taxicab}(i, x, n)\$)

Your task is to take 3 positive integers \$n, x\$ and \$i\$ and return \$\Ta n x i\$. This is code-golf so the shortest code in bytes wins.

In case \$x = 1 \$ and \$ n > 1\$, your program can do anything short of summoning Cthulhu, and for other cases where \$\Ta n x i\$ is not known to exist (e.g. \$\Ta n 2 5\$), the same applies.

Test cases

n, x, i -> out
1, 1, 2 -> 1
1, 2, 3 -> 2
2, 2, 2 -> 50
2, 2, 3 -> 1729
3, 3, 2 -> 54
3, 3, 3 -> 5104
2, 6, 6 -> 570947
2, 4, 4 -> 259
6, 4, 4 -> 3847554
2, 5, 2 -> 20
2, 7, 3 -> 131
2, 5, 7 -> 1229250016
5, 8, 4 -> 4228

---

Properties of \$\Ta n x i\$

• \$\forall i : \Ta 1 x i = x\$ as \$x = \underbrace{1^i + \cdots + 1^i}_{x \text{ times}}\$
• \$\Ta n 1 i\$ does not exist for all \$n > 1\$
• \$\Ta n 2 5\$ is not known to exist for any \$n \ge 2\$

This is a table of results \$\{\Ta n x i \:|\: 1 \le n,x,i \le 3 \}\$, ignoring \$\Ta 2 1 i\$ and \$\Ta 3 1 i\$:

$$\begin{array}{ccc|c} n & x & i & \Ta n x i \\ \hline 1 & 1 & 1 & 1 \\ 1 & 1 & 2 & 1 \\ 1 & 1 & 3 & 1 \\ 1 & 2 & 1 & 2 \\ 1 & 2 & 2 & 2 \\ 1 & 2 & 3 & 2 \\ 1 & 3 & 1 & 3 \\ 1 & 3 & 2 & 3 \\ 1 & 3 & 3 & 3 \\ 2 & 2 & 1 & 4 \\ 2 & 2 & 2 & 50 \\ 2 & 2 & 3 & 1729 \\ 2 & 3 & 1 & 5 \\ 2 & 3 & 2 & 27 \\ 2 & 3 & 3 & 251 \\ 3 & 2 & 1 & 6 \\ 3 & 2 & 2 & 325 \\ 3 & 2 & 3 & 87539319 \\ 3 & 3 & 1 & 6 \\ 3 & 3 & 2 & 54 \\ 3 & 3 & 3 & 5104 \\ \end{array}$$

Answer 1

05AB1E, 15 bytes

∞.ΔL¹m²ã€{ÙOy¢Q

Try it online!

This is really slow, inserting ¹zmï after .Δ limits the search space significantly: Try it online!

Commented:

                # Inputs ¹=i, ²=x, ³=n
∞.Δ             # find the first natural number k that satisfies:
   L            #   each of the range [1..k]
    ¹m          #   raised to the i-th power
      ²ã        #   take the list to the x-th cartesian power
        €{      #   sort each x-tuple
          Ù     #   deduplicate the tuples
           O    #   sum each x-tuple
            y¢  #   count the number of k's
              Q #   is this equal to the last input?

ã€{Ù does the same as Python's itertools.combinations_with_replacement, but there doesn't seem to be a builtin for this in 05AB1E.

Answer 2

R + gtools, 84 bytes

function(n,x,i){while(sum(rowSums(gtools::combinations(+T,x,re=1)^i)==T)<n)T=T+1;+T}

Try it online!

Counts T up from 1, calculating the number of combinations of x numbers ≤T whose ith powers sum to T. Stops at the first number that gives (at least) n combinations.

function(n,x,i){    
                    # variable T (TRUE) initialized by default to 1
 while( ... )T=T+1  # while the condition (see below) is met, keep incrementing T
                    # 
 a=gtools::combinations(+T,x,re=1)  # all combinations of x numbers from 1..T (as rows of matrix)
 b=a^i              # raised to the i-th power
 c=rowSums(b)       # the row sums are the sums of each combination
 d=sum(c==T)        # when the row sums equal T, we have a combination of x i-th powers that equals T
 d<n                # the condition: we didn't get n combinations yet
                    #
 +T                 # finally, the condition fails, so we've got n combinations: return this value of T
}

---

For a base-R solution (without the gtools library), swap gtools::combinations(+T,x,re=1) for unique(t(apply(expand.grid(rep(list(1:T),x)),1,sort))) (+23 bytes).

Answer 3

Wolfram Language (Mathematica), 79 bytes

(n=1;While[Length@Select[PowersRepresentations[n++,#2,#3],#~FreeQ~0&]!=#];n-1)&

Try it online!

Answer 4

Jelly, 12 bytes

œċ³*⁴§ċ⁼⁵µ1#

A full program which (given enough time!) prints the result if it exists. Inputs are \$x\$, \$i\$, \$n\$.

Try it online! (Too slow for most of the test cases.)

How?

Brute-force (and an inefficient one at that):

œċ³*⁴§ċ⁼⁵µ1# - Main Link: x
         µ1# - Count up starting with k=x until 1 truthy result, then yield k, using:
  ³          -   1st program argument, x
œċ           -   all combinations (of x elements from [1..k]), allowing repeats
    ⁴        -   2nd program argument, i
   *         -   exponentiate (vectorises)
     §       -   sums
      ċ      -   count occurrences (of k)
        ⁵    -   3rd program argument, n
       ⁼     -   equal?

Note œċ does not give unordered repeats, for example 2œċ3 yields:
[[1, 1, 1], [1, 1, 2], [1, 2, 2], [2, 2, 2]]

Answer 5

Wolfram Language, 110 108 bytes

Try it online!

(i=0;While[Length@FindInstance[i++==Tr[(v=Unique[]~Table~#2)^#3]&&LessEqual@@v,v,PositiveIntegers,#]!=#];i)&

Answer 6

JavaScript (ES7), 89 bytes

(n,x,i)=>(F=q=>(g=(k,p,j)=>j?p**i>k?0:g(k-p**i,p,j-1)+g(k,p+1,j):!k)(++q,1,x)-n?F(q):q)``

Try it online!

Commented

We recursively look for the smallest \$q\$ such that there exists exactly \$n\$ sums of the form:

$${p_1}^i+{p_2}^i+\ldots+{p_x}^i=q,\:p_{k+1}\ge p_k \ge 1$$

(n, x, i) => (        // input variables, as described in the challenge
  F = q =>            // F is a recursive function taking a candidate solution q
  ( g = (             //   g is a recursive function taking:
      k,              //     k = current sum
      p,              //     p = number to be raised to the power of i
      j               //     j = remaining number of terms in the sum
    ) =>              //   
    j ?               //     if there's at least one more term to compute:
      p ** i > k ?    //       if p ** i is greater than k:
        0             //         abort
      :               //       else:
        g(            //         do a 1st recursive call with:
          k - p ** i, //           k = k - p ** i
          p,          //           p unchanged
          j - 1       //           one less term to compute
        ) +           //
        g(            //         do a 2nd recursive call with:
          k,          //           k unchanged
          p + 1,      //           p incremented
          j           //           j unchanged
        )             //
    :                 //     else:
      !k              //       increment the final result if k = 0
  )(++q, 1, x)        //   initial call to g with k = ++q, p = 1 and j = x
  - n ?               //   if the result is not equal to n:
    F(q)              //     try again
  :                   //   else:
    q                 //     success: return q
)``                   // initial call to F with q zero'ish

Answer 7

Scala, 125 bytes

(n,x,i)=>1 to 1<<30 find(c=>Seq.fill(x)(1 to c map(Math.pow(_,i))takeWhile(_<=c)).flatten.combinations(x).count(_.sum==c)==n)

Try it online!

Approach: for each candidate integer c, generate a list of x copies of i-powered integers lower than c, and count whether n (distinct!) combinations of length x sum up to c.

Performance: the trade-off between performance and code length is made such that most test cases finish within some seconds. The following variant would save 14 bytes, but would be much less performant:

(n,x,i)=>0 to 1<<30 find(c=>Seq.fill(x)(1 to c).flatten.combinations(x).count(_.map(Math.pow(_, i)).sum==c)==n)