Squares and Reciprocals

You can approach a solution easily without code by multiplying the original sum by $1/2$ to get:

$1/2=1/4+1/6+1/12$

Then we can add $1/2$ to our new sum to get:

$1=1/2+1/4+1/6+1/12$

Finally, we add the squares of the denominators to get:

$2^2+4^2+6^2+12^2=200$

Notice it is easy to deduce that 200 is the next smallest square-partitionable integer involving a 2, since the remaining terms of the reciprocal sum must add to $1/2$ , and by dividing the reciprocal sum of the smallest solution by 2, we end up with the best reciprocal sum to add to $1/2$ . However, it is not known for sure if this is the next smallest square-partitionable integer, since there could be a smaller one that does not involve a 2, but fortunately, this is not the case.

Thus the answer must be $\boxed{200}$ .

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

#include<stdio.h>

#define MAX_N 999
#define MAX_T 99

long N;
int term[MAX_T];

void split_squares(long M, int ct, long num, long den) {
    int i, min_i;

    if (num == den) {
        if (M == 0 && ct >= 2) {
            printf("%ld: ", N);
            for (i = 1; i <= ct; i++) printf("%d ",term[i]);
            printf("\n");
        }
    } else {
        min_i = den / (den-num);
        if (term[ct] >= min_i) min_i = term[ct] + 1;
        ct++;

        for (i = min_i; i*i <= M; i++) {
            term[ct] = i;
            split_squares(M - i*i, ct, num*i+den, den*i);
        }
    }
}

int main() {
    term[0] = 0;
    for (N = 1; N < MAX_N; N++) {
        split_squares(N,0,0,1);
    }
    return 0;
}

Output:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

49: 2 3 6 
200: 2 4 6 12 
338: 2 3 10 15 
418: 2 3 9 18 
445: 2 4 5 20 
486: 3 4 5 6 20 
489: 2 4 10 12 15 
530: 3 4 6 10 12 15 
569: 2 4 9 12 18 
609: 2 5 6 12 20 
610: 3 4 6 9 12 18 
653: 2 3 8 24 
770: 2 6 9 10 15 18 
775: 3 4 5 10 15 20 
804: 2 4 8 12 24 
845: 3 4 6 8 12 24 
855: 3 4 5 9 18 20 
898: 2 5 10 12 15 20 
899: 3 4 9 10 12 15 18 
939: 3 5 6 10 12 15 20 
978: 2 5 9 12 18 20 

We see that the example solution of 49 is the smallest; the second-smallest is $\boxed{200} = 2^2 + 4^2 + 6^2 + 12^2,$ and indeed $\frac 1 2 + \frac 1 4 + \frac 1 6 + \frac 1 {12} = \frac{6 + 3 + 2 + 1}{12} = 1.$

Explanation: The work is done by the recursive function split_squares . At any point in the calculation, we have $N = t_0^2 + t_1^2 + \cdots + t_{c-1}^2 + M;\ \ \ \ \frac 1{t_0} + \frac1{t_1} + \cdots + \frac1{t_{c-1}} = \frac{n}{d}.$ The process ends successfully if $M = 0$ and $n = d$ . It fails if $M = 0$ but $n < d$ ; or if $n = d$ but $M > 0$ ; or if $M < 0$ or $n > d$ .

If $M > 0$ and $n < d$ , we add a term $t_c$ . It must be greater than the preceding term; we generate the terms in increasing order. Then the new values for recursion are $M' = M - t_c^2;\ \ \ \frac{n'}{d'} = \frac{n}{d} + \frac 1{t_c} = \frac{nt_c + d}{dt_c}.$ To ensure that $M' \geq 0$ we limit $t_c^2 \leq M$ . Also, to ensure that the fraction does not exceed 1, we require $nt_c + d \leq dt_c$ ; this translates to a minimum value, $t_c \geq \lceil d/(d-n) \rceil$ .

[EDIT: This comment refers to a previous wording of the problem.]

The wording should include the requirement that the integers used in the sum be positive :

"We call a positive integer $N$ square-partitionable if it can be partitioned into squares of at least 2 distinct positive integers, and if the sum of the reciprocals of these positive integers is 1."

That is how I (and most everyone else) interpreted the question. But as currently worded, you can use reciprocals of negative integers, and thus get solutions with $N$ less than 200.

$\frac{1}{1}+\frac{1}{-2}+\frac{1}{3}+\frac{1}{6} = 1$ leads to $N = 1^2+(-2)^2+3^2+6^2 = 50$

$\frac{1}{1}+\frac{1}{-3}+\frac{1}{4}+\frac{1}{12} = 1$ leads to $N = 1^2+(-3)^2+4^2+12^2 = 170$

$\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{-12} = 1$ leads to $N = 2^2+3^2+4^2+(-12)^2 = 173$

You try to partition the fraction with the smallest possible denominator into two other fractions with smallest possible denominators. Since 2 cannot be partitioned (already partitioned into 1/3 and 1/6), you partition the 1/3 into two other fractions, 1/4 and 1/3 - 1/4 = 1/12. Therefore, you add up the denominators squared: 2^2 + 4^2 + 6^2 + 12^2 = 4 + 16 + 36 + 144 = 200.

My Python code:

def rekurs(n, sand, sum, i):
    if n == 0:
        return sum == sand
    while i * i <= n:
        if rekurs(n - i * i, sand * i, sum * i + sand, i + 1):
            return True
        i += 1
    return False

def check(n):
    return rekurs(n, 1, 0, 2)

i = 50
while not check(i):
    i += 1

print(i)

C#:

void Main()
{
  for (int n = 0; n < 1100; n++) {
    var partitions = PartitionIntoAscendingSquares(1,n)
              .Where( part => part.Count() > 1)   // at least 2 squares
              .Where( part => {            // reciprocals add to 1
                  var prod = part.Aggregate(1, (p,x) => p*x);   // denominator
                  var sums = part.Aggregate(0, (s,x) => (prod/x) + s);  // numerators
                  return sums == prod;
              });

    if (partitions.Count() > 0) 
      foreach (var part in partitions) 
        Console.WriteLine($"{n}: {String.Join(",", part.OrderBy(x=>x))}");
  }
}

IEnumerable<IEnumerable<int>> PartitionIntoAscendingSquares(int from, int n) {
  if (n == 0) 
    yield return new int [] {} ;
  else 
    for (int i = from; i * i <= n; i++) 
      foreach (var part in PartitionIntoAscendingSquares(i + 1, n - i * i)) 
        yield return part.Concat(new int[] {i});
} 

49: 2,3,6
200: 2,4,6,12
338: 2,3,10,15
418: 2,3,9,18
445: 2,4,5,20
486: 3,4,5,6,20
489: 2,4,10,12,15
530: 3,4,6,10,12,15
569: 2,4,9,12,18
609: 2,5,6,12,20
610: 3,4,6,9,12,18
653: 2,3,8,24
770: 2,6,9,10,15,18
775: 3,4,5,10,15,20
804: 2,4,8,12,24
845: 3,4,6,8,12,24
855: 3,4,5,9,18,20
898: 2,5,10,12,15,20
899: 3,4,9,10,12,15,18
939: 3,5,6,10,12,15,20
978: 2,5,9,12,18,20
1005: 2,6,8,10,15,24
1019: 3,5,6,9,12,18,20
1049: 2,4,7,14,28
1065: 2,5,6,10,30
1085: 2,6,8,9,18,24
1090: 3,4,5,8,20,24
1090: 3,4,6,7,14,28

200 is the second smallest integer. 1090 is the first with 2 distinct solutions.

Not a proof but I did get the answer by constructing a few such numbers backward:

In the example, the factors of 6 are 1,2,3,6 and the subset 1+2+3=6. 6/1=6, 6/2=3, 6/3=2 and 6^2+3^2+2^2=49

The key is to find a number whose factors contain a subset that sums to the number.

The next such number is 12. Factors are 1,2,3,4,6,12 (2,4,6 will give the example) and the subset is 1,2,3,6. 12^2+6^2+4^2+2^2= 200

The next number is 18 which gives 418 and 20 gives 445

I stopped there and got lucky. As Arjen's table shows, 30 gives a somewhat small 338 (by avoiding the factor 1)

if look at the 2nd part

$\frac{1}{2}+\frac{1}{3}+\frac{1}{6} = 1$

which is $3+2+1 = 6$

we can see only integers for whom a subset of factors can add to themselves can satisfy this criteria like in this case 1, 2, 3 factors of 6 add upto 6

the next integer after 6, this is possible for is 12. 1,2,3,6 and 2,4,6 add upto 12.

2,4,6 is same as first case.

for 1,2,3,6 we have,

$\frac{1}{12}+\frac{2}{12}+\frac{3}{12}+\frac{6}{12}$

$= \frac{1}{12}+\frac{1}{6}+\frac{1}{4}+\frac{1}{2}$

which gives

$12^2+6^2+4^2+2^2=200$