Hardy–Ramanujan number generalization

$$\1729\$$, known as the Hardy–Ramanujan number, is the smallest positive integer that can be expressed as the sum of two cubes of positive integers in two ways ($$\12^3+1^3=10^3+9^3=1729\$$). Given an integer $$\n\$$ (as input in whatever form is natural to your language of choice) find the smallest positive integer that can be expressed as the sum of two positive integers raised to the $$\n\$$th power in two unique ways. No use of external sources. Fewest characters wins.

Note that this is actually an unsolved problem for $$\n>4\$$. For those numbers, let your program run forever in search, or die trying! Make it so that if given infinite time and resources, the program would solve the problem.

• You may (?) want to specify "the sum of two positive integers raised to the nth power". Otherwise, 91 (not 1729) is the solution for n=3, since 6^3+(−5)^3=4^3+3^3=91. I learned this from your Wikipedia link so maybe your H-M reference makes this unnecessary by convention. Cheers! Dec 30, 2013 at 6:23
• actually, 1 is the first solution: 1 = cbrt(0.5)^3 + cbrt(0.5)^3 = ... Dec 30, 2013 at 6:53
• Thanks for the suggestions and edit - I meant 2 positive integers! Dec 30, 2013 at 14:07
• @JanDvorak, ha, yes. Keeping it Real! Dec 30, 2013 at 18:51
• You say "find the smallest positive integer that" ..., as though there is one -- but for any n > 4, the existence of such numbers is an unsolved problem. Maybe you should say "find the smallest positive integer (if there is one) that" ... It's possible that the "answers" are nonterminating loops that find nothing. Dec 31, 2013 at 13:27

APL  45  41

{⍺←1⋄2≤+/,⍺=(v∘.≤v)×∘.+⍨⍵*⍨v←⍳⌊⍺*.5:⍺⋄⍵∇⍨⍺+1}


Shorter but slower version of 41 chars:

{⍺←1⋄2≤+/,⍺=(v∘.≤v)×∘.+⍨⍵*⍨v←⍳⍺:⍺⋄⍵∇⍨⍺+1}


You can try it online, just paste the function and invoke it with a number:

      {⍺←1⋄2≤+/,⍺=(v∘.≤v)×∘.+⍨⍵*⍨v←⍳⌊⍺*.5:⍺⋄⍵∇⍨⍺+1} 2
50
{⍺←1⋄2≤+/,⍺=(v∘.≤v)×∘.+⍨⍵*⍨v←⍳⌊⍺*.5:⍺⋄⍵∇⍨⍺+1} 3
1729


(The algorithm is quite dumb though, don't expect the online interpreter to compute n=4)

The answer for n=2 is 50 = 5² + 5² = 7² + 1² because its a number that "can be expressed as the sum of two squares of positive integers—doesn't say different—in two ways."

If you want to add the distinct clause, just change (v∘.≤v) into (v∘.<v), same number of chars, and n=2 becomes 65:

      {⍺←1⋄2≤+/,⍺=(v∘.<v)×∘.+⍨⍵*⍨v←⍳⌊⍺*.5:⍺⋄⍵∇⍨⍺+1} 2
65


I'm beating GolfScript? Can't be!!

• nice! And I did mean distinct integers, but I didn't specify, so more power to ya! Back to the drawing board for the GolfScript... Dec 30, 2013 at 22:32

n=$*[r=0].to_i;while r+=1 r.times{|a|r.times{|b|next if a**n+b**n!=r;r.times{|c|r.times{|d|puts(r)if c**n+d**n==r&&a!=c&&a!=d}}}}end  Pass n as command line argument. First line to stdout is the solution. Optimized for code-golf, not performance. (Runs correctly. But slow. Does more work than needed.) Here is a longer, slightly faster C program. Same correct but horrible algorithm. (I really need to study more theory!) Tested for n=2, n=3. C, 234 #include<stdio.h>#include<math.h> r,a,b,c,d;main(n){scanf("%d",&n);while(++r){for(a=0;a<r;++a){for(b=a;b<r;++b){if(pow(a,n)+pow(b,n)!=r)continue;for(c=a+1;c<r;++c){for(d=0;d<r;++d){if(pow(c,n)+pow(d,n)==r&&a!=d)printf("%d\n",r);}}}}}}  The C version takes n on stdin. As above, first line to stdout is the solution. GolfScript 53 1\.{;\).,{}@.@\{?}+%.{\{+}+%~}+%$.{\{=}+,,4=}+,.!}do)


Input is the initial number on the stack. The number on top of the stack at the end is the answer. I'll explain this in more detail when I get a chance.

E.g.

{1\.{;\).,@.@\{?}+%.{\{+}+%~}+%$.{\{=}+,,4=}+,.!}do)}:f 2 f -> 25 3 f -> 1729  This is pretty slow right now. It also counts 0 (so that 25 is the answer for n=2, since 25=5^2+0^2=3^2+4^2. In order to not count 0, add the 2 characters (; after the first , 1\.{;\).,(;{}@.@\{?}+%.{\{+}+%~}+%$.{\{=}+,,4=}+,.!}do)


To find that 2 f=65, since 65=8^2+1^2=5^2+6^2

GolfScript (30 chars)

:N{).,{)N?}%:P{1\$\-P?)},,3<}do


Note: this is quite slow, because it does a brute-force search rather than something elegant like a priority queue. The most elegant thing about it is reusing N as a lower bound from which to search: this is valid because 1^N + 2^N > N for all N.

Takes N on the stack, leaves the corresponding taxicab number on the stack. To take N from stdin, prepend ~.

The version above allows x^N + x^N (so for N=2 it gives 50). To require adding distinct numbers (giving 65 instead), change the 3 to 4. To allow 0^N + x^N (giving 25), remove the ) immediately before N?.

Mathematica, 58 chars

A very very slow solution using generating function:

0//.i_/;(D[Sum[x^(n^#),{n,1,i}]^2,{x,i}]/.x->0)/i!<4:>i+1&


Jelly, 13 bytes

Œċ*§ċ⁸=2
1ç1#


Try it online!

This is very inefficient for $$\n = 3\$$ and doesn't complete within 60s. However, this can be fixed for an additional 4 bytes

How it works

Œċ*§ċ⁸=2 - Helper link. Takes an integer i on the left and a power n on the right
Œċ       - Yield all pairs, choosing with replacement
*      - Raise each to the power n
§     - Take the sum of each
ċ⁸   - Count the occurrences of i in this list
=2 - Is this equal to 2?

1ç1# - Main link. Takes a power n on the left
1    - Set the return value to 1
ç1# - Return the first positive integer, i,
where running the helper link with
i on the left and n on the right is True