12
\$\begingroup\$

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

\$\endgroup\$
  • 2
    \$\begingroup\$ 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! \$\endgroup\$ – Darren Stone Dec 30 '13 at 6:23
  • \$\begingroup\$ actually, 1 is the first solution: 1 = cbrt(0.5)^3 + cbrt(0.5)^3 = ... \$\endgroup\$ – John Dvorak Dec 30 '13 at 6:53
  • \$\begingroup\$ Thanks for the suggestions and edit - I meant 2 positive integers! \$\endgroup\$ – Ben Reich Dec 30 '13 at 14:07
  • 1
    \$\begingroup\$ @JanDvorak, ha, yes. Keeping it Real! \$\endgroup\$ – Darren Stone Dec 30 '13 at 18:51
  • \$\begingroup\$ 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. \$\endgroup\$ – r.e.s. Dec 31 '13 at 13:27
3
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ 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... \$\endgroup\$ – Ben Reich Dec 30 '13 at 22:32
2
\$\begingroup\$

Ruby, 132

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.

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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