13
\$\begingroup\$

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

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

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ I replaced the second \$n\$ with \$k\$ as it's clearer that way. \$\endgroup\$ – Jonathan Allan Dec 29 '20 at 2:24
4
\$\begingroup\$

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

\$\endgroup\$
3
\$\begingroup\$

Wolfram Language (Mathematica), 79 bytes

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

Try it online!

\$\endgroup\$
3
\$\begingroup\$

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

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

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

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

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