Consider N positive integers which are not necessarily distinct such that their sum of cubes is equal to 2011 (base ten) and their sum of squares is a perfect square.

Determine the smallest value of N for which this is possible. What is the next smallest value of N?

The smallest workable value of N is 10 and the next is 11.

As shown in the below first few lines of the sorted output of the program, N = 10 can be exemplified with three 3's, four 4's, a 6 and two 9's; as well as a 2, three 3's, three 4's, a 12 and two 1's; and by four 3's, two 4's, two 6's, a 7 and a 10.

The rows exemplifying N = 11 can be read in the same manner:

   10          3  3  3  4  4  4  4  6  9  9 + 0 1's
   10          2  3  3  3  4  4  4  12 + 2 1's
   10          3  3  3  3  4  4  6  6  7  10 + 0 1's

   11          2  2  2  3  3  3  3  7  8  8  8 + 0 1's
   11          3  3  3  4  6  6  6  6  10 + 2 1's
   11          2  4  4  4  5  5  6  7  10 + 2 1's
   11          2  2  2  2  3  3  5  6  7  8  9 + 0 1's
  
Note that the program uses 1's as an afterthought and so appears as a count rather than as a 1 for each 1 making up the set, and that this count of ones is zero in a few instances.  

Extended beyond these values:

   10          2  3  3  3  4  4  4  12 + 2 1's
   10          3  3  3  3  4  4  6  6  7  10 + 0 1's
   10          3  3  3  4  4  4  4  6  9  9 + 0 1's
  
   11          3  3  3  4  6  6  6  6  10 + 2 1's
   11          2  2  2  2  3  3  5  6  7  8  9 + 0 1's
   11          2  4  4  4  5  5  6  7  10 + 2 1's
   11          2  2  2  3  3  3  3  7  8  8  8 + 0 1's
  
   12          2  2  4  4  4  6  7  8  9 + 3 1's
  
   13          3  3  5  5  5  5  5  5  6  6  6  6  7 + 0 1's
   13          3  4  4  4  4  6  6  6  6  6  6  6  6 + 0 1's
  
   14          3  3  3  3  4  4  4  4  4  5  5  11 + 2 1's
  
   15          2  2  2  2  2  2  2  2  3  4  4  4  6  8  10 + 0 1's
   15          2  2  2  2  2  2  3  3  3  3  3  3  7  9  9 + 0 1's

DECLARE SUB addOn ()
CLEAR , , 25000
DEFDBL A-Z

DIM SHARED cube(2 TO 12), square(2 TO 12)
DIM SHARED cuTot, sqTot, hist(260), numCt

FOR i = 2 TO 12
  cube(i) = i * i * i
  square(i) = i * i
NEXT

OPEN "sumcusq.txt" FOR OUTPUT AS #2

addOn

CLOSE

SUB addOn
  IF numCt = 0 THEN stNum = 2:  ELSE stNum = hist(numCt)
  FOR addNum = stNum TO 12
    cu = cube(addNum): sq = square(addNum)
    cuTot = cuTot + cu: sqTot = sqTot + sq
    IF cuTot <= 2011 THEN
      numCt = numCt + 1
      oneCt = 2011 - cuTot
      sqTst = sqTot + oneCt
      sr = INT(SQR(sqTst) + .5)
      hist(numCt) = addNum
      IF sr * sr = sqTst AND numCt + oneCt < 16 THEN
        PRINT USING "#####"; numCt + oneCt;
        PRINT ,
        FOR i = 1 TO numCt
          PRINT hist(i);
        NEXT
        PRINT "+"; oneCt; "1's"
        PRINT #2, USING "#####"; numCt + oneCt;
        PRINT #2, ,
        FOR i = 1 TO numCt
          PRINT #2, hist(i);
        NEXT
        PRINT #2, "+"; oneCt; "1's"
      END IF
      IF cuTot < 2011 THEN IF numCt < 16 THEN addOn
      numCt = numCt - 1
    END IF
    cuTot = cuTot - cu: sqTot = sqTot - sq
  NEXT addNum
END SUB

 

Posted by Charlie on 2011-08-28 21:24:16