# Generalised Taxicab Numbers


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 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}$$

• Sandbox. Imaginary brownies for beating my 14 byte Jelly answer Dec 28 '20 at 20:34
• I was wondering why you used $i$ and $x$... but now I realise it spells "taxi" ha Dec 28 '20 at 20:40
• @pxeger Thank Adám for that :P Dec 28 '20 at 20:42

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

• I replaced the second $n$ with $k$ as it's clearer that way. Dec 29 '20 at 2:24

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

# Wolfram Language (Mathematica), 79 bytes

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


Try it online!

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

• Nice! I had this for my 14 bytes Dec 30 '20 at 0:09

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


# 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


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