Do the bare minimum

Computer Science Level 5

Any number can be represented as a sum of square of numbers, for example $9$ can be represented as $3^{2}$ or $2^{2}+2^{2}+1^{2}$ or even $\underset { 9\quad times }{ \underbrace { { 1 }^{ 2 }+{ 1 }^{ 2 }+\cdots +{ 1 }^{ 2 } } }$ .

Let $\varsigma (n)$ be the minimum squares of numbers needed in the representation of $n$ . What is the value of.. $\large \sum _{ i=2 }^{ 2015 }{ \varsigma (i) }$

Details and assumptions

As explicit examples:

$\varsigma (100)=1 \longrightarrow 10^{2}$

$\varsigma (120)=3 \longrightarrow 10^{2}+4^{2}+2^{2}$

The answer is 5714.

5 solutions

Arjen Vreugdenhil
Sep 26, 2015

The answer is 5714.

Here is a dynamic-programming approach. In an array a[i] we keep track of the number of ways in which a number can be written as the sum of squares. Starting with "1" for the perfect squares, we then combine each number with subsequent numbers to generate further possibilities.

        final int N = 2015;
        int a[] = new int[N+1];

        for (int i = 1; i <= N; i++) a[i] = 0;     // 0 = undefined
        for (int sq = 1, i = 1; sq <= N; sq+=i,i++,sq+=i) a[sq] = 1;

        for (int i = 1; i <= N; i++) if (a[i] > 0) {
            for (int j = 1, s = i+1; s <= N; j++, s++) if (a[j] > 0) {
                int newa = a[i] + a[j];
                if (a[s] == 0 || newa < a[s]) a[s] = newa;
            }
        }

        int sum = 0;
        for (int i = 2 ; i <= N; i++) sum += a[i];

        out.println(sum);

A number-theoretical approach:

Only perfect squares can be written as the sum of one square (obvious).
A number is the sum of two squares iff it is of the form $n^2\cdot 2^a\cdot p_1\cdot p_2\cdots$ , where $p_i$ are prime numbers of the form $p_i = 4q_i + 1$ .
Almost all other number can be written as the sum of three squares...
... except numbers of the form $4^n\cdot(8k+7)$ , which can be written as the sum of four squares.

    private static int get_prime_factor(int i) {
        for (int d = 2; d*d <= i; d += (d==2?1:2))
            if (i % d == 0) return d;
        return i;
    }

    private static int count_squares(int x) {
        int factors_2 = 0;
        int odd_part = x;
        boolean has_nonsq_factor = false;
        boolean has_3mod4_factor = false;

        int factor = get_prime_factor(x), new_factor;
        while (x > 1) {
            int exponent = 0;
            do { 
                x /= factor; exponent++;
                new_factor = get_prime_factor(x);
            }
            while (new_factor == factor);

            if (factor == 2) { factors_2 = exponent; odd_part = x; }
            if (exponent % 2 == 1) {
                has_nonsq_factor = true;
                if (factor % 4 == 3) has_3mod4_factor = true;
            }

            factor = new_factor;
        }

        if (!has_nonsq_factor) return 1;
        if (!has_3mod4_factor) return 2;
        if (factors_2 % 2 == 1 || odd_part % 8 != 7) return 3; 
        return 4;
    }

    public static void main(String[] args) {
        final int N = 1025;

        int sum = 0;
        for (int i = 2; i <= N; i++)
            sum += count_squares[i];

        out.println(sum);
    }

What is the time complexity for your number-theoretical approach? I based only on Lagrange's four-square theorem without any optimization and I think the time complexity is $O(N\sqrt{N})$ .

    // default
    for (int i = 0; i < 2016; i++)
        cnt[i] = 4;

    for (int i = 1; i * i < 2016; i++) {
        if (cnt[i * i] > 1)
            cnt[i * i] = 1;
        for (int j = 1; j * j + i * i < 2016; j++) {
            if (cnt[i * i + j * j] > 2)
                cnt[i * i + j * j] = 2;
            for (int k = 1; k * k + j * j + i * i < 2016; k++) {
                if (cnt[i * i + j * j + k * k] > 3)
                    cnt[i * i + j * j + k * k] = 3;
            }
        }
    }

    int sum = 0;
    for (int i = 2; i < 2016; i++)
        sum += cnt[i];

    cout << sum << endl;

Christopher Boo - 5 years ago

Since you use three nested loops that count up to $\sqrt{N}$ , I would think that the complexity of $O(N\sqrt N)$ is correct.

My first approach has complexity $O(N^2)$ , although for the given value $N = 2016$ it is not significantly slower. For much higher values of $N$ , I would maintain a list of squares, which requires slightly more coding and reduces the complexity to $O(N\sqrt N)$ .

The complexity of my second approach depends on the complexity of finding a prime factorization for a given number between 1 and $N$ .

Arjen Vreugdenhil - 5 years ago

Here is my solution with complexity $O(N\sqrt N)$ :

final int N = 2015;
int s[] = new int[N+1];
s[0] = 0;

int sum = 0;

for (int n = 1; n <= N; n++) {
    int ss = s[n-1];
    for (int k = 2, nk = n-4; nk >= 0; nk-= k, k++, nk-= k)
        if (s[nk] < ss) ss = s[nk];
    s[n] = ss+1;

    if (n >= 2) sum += s[n];
}

If $n-1$ can be written as the sum of $ss$ squares, then $n$ can be written as the sum of $ss+1$ squares. That is the initial guess.

Next we loop through all squares $k^2 \leq n$ to see if $nk = n - k^2$ is a better starting point. Note the trick I used to reduce the arithmetic to additions and subtractions only.

Arjen Vreugdenhil - 5 years ago

@Arjen Vreugdenhil – This is a much better $O(N\sqrt{N})$ , and nk-= k, k++, nk-= k is a very neat trick! For those who are wondering, it's due to the fact that $n^2-(n-1)^2=2n-1$

Christopher Boo - 5 years ago

What about this approach: `

import math


 Min=[1,2,3]

 def MIN(n):

kmins=[]

if math.floor(n**0.5) == math.ceil(n**0.5) and (n not in Min):

    Min.append(1)

else:

    for i in range(int(math.floor(n**0.5)),1,-1):

        m=n-(i**2)

        kmins.append(Min[m-1]+1)

if len(kmins)!=0:

    Min.append(min(kmins))



   for n in range(4,2015):

MIN(n)

  print sum(Min) -1

Sorry for the bad formatting .But can anyone explain why my code is incorrect? I keep getting 5710 instead of 5714?
Thanks!!!

Arkin Dharawat - 5 years, 8 months ago

The condition 'and (n not in Min)' is meaningless. It appears that it does not harm. Likewise, if the condition 'if len(kmins)!=0' is ever false (which won't happen), your program will no longer work, since the number of squares needed for $m$ is no longer at position Min[m-1]. Still, that does not explain why you get 5710...

Arjen Vreugdenhil - 5 years, 8 months ago

Thank you!!!,I agree a very stupid error on my part concerning the limit to which the loop had to be run,I guess I was too tired to notice it,I put the limit as 2016 and it worked! And also yeah the 'and (n not in Min)' is useless .Also the condition for len(kmins) is needed because when the number is a perfect square kmins is of zero length. Thanks again appreciate the help.

Arkin Dharawat - 5 years, 8 months ago

@Arkin Dharawat – If you keep the append command within the 'else' block, the condition is not needed, because perfect squares are not dealt with in the 'else' block.

Arjen Vreugdenhil - 5 years, 8 months ago

If I remember correctly, the range function in Python counts up to but not including the second number.

The "for i in range(...)" is affected by this only if n <= 3, and you pre-programmed those into your Min list.

But the "for n in range(4, 2015)" now only runs up to 2014. And 2015 is the sum of four squares, since it yields a remainder of 7 modulo 8. This explains the discrepancy!

Arjen Vreugdenhil - 5 years, 8 months ago

Hello Sir. I'm sorry to disturb you Sir, but I've run into a problem with the program I wrote which seems impossible for me to understand. I would be really grateful if you could kindly tell me what is wrong with the code.

Sir, I've tried to solve this first without using Dynamic Programming and had devised the following code. However, the code keeps returning the answer as 7609.

#include<iostream.h>
#include<conio.h>
#include<math.h>

void main()
{ int s,i,m,count,sc=0; 
  int issquare(int);

   for(s=2;s<=2015;++s)
      {i=s;
       m=s; /*This is so that the largest square numbers less than the tested number are subtracted from the tested number. */
       do{if(issquare(m)==0)
             {while(i>=m)
                     {i-=m;
                      count+=1;
                     }
             }
             m-=1;
          } while(i!=0);
        cout<<s<<"    "<<count<<endl;
        cout<<sc;

     getch();
}

 int issquare(int n)
{  int q=sqrt(n);
     if(pow(q,2)==n)
        return (0);
     else
        return (1);
}

cout<<s<<" "<<count<<endl;

This is to display the number and show the minimum number of squares which need to be added. I added this line to check if the code was working for some randomly selected numbers (eg 120 did indeed return a value of 3).

cout<<sc;

This is the sum of the individual count(s).

  if(issquare(m)==0)
             {while(i>=m)
                     {i-=m;
                      count+=1;
             }

I created this fragment of code primarily for the numbers $2$ and $3$ . In my original code,the moment any square number $m$ was used, m was decreased immediately by 1. However, this didn't work for 2 or 3. Thus (considering 2) because initially $m$ was equal to 2. Since 2 is not a perfect square, I reduced the value of m by 1 ie $m=1$ after the decrement.

Now, in the original code, the new value of $m$ (=1) was used, the value of $m$ was decreased by 1. To counter this, I modified the code so that while the maximum square number $m$ was smaller than or equal to $i$ (and its subsequent modified values), it would keep getting subtracted from $i$ . Only once this condition was violated would the value of $,$ be decreased.

Many many thanks in anticipation!

PS. The original code was almost identical except that the value of $m$ was reduced by 1 after each use. The part of the code referred top was as follows:

for(s=2;s<=2015;++s)
      {i=s;
       m=s;
         if(issquare(m)==0)
            {i-=m;
              count+=1;
            }         
         m-=1;
        } while(i!=0);

User 123 - 5 years, 8 months ago

If I understand your approach correctly, you start by subtracting the largest square possible. Your algorithm is too "greedy". For instance, if $s = 18$ , your program will think of it as $18 = 4^2 + 1^2 + 1^2,$ and fails to see that it may be written as $18 = 3^2 + 3^2.$

Arjen Vreugdenhil - 5 years, 8 months ago

Thank you Sir. Sir, I realized this just now considering the case of $23$ (my algorithm return a value of 5 whereas the answer seems to be 4). Sir, please could you show me how to modify my algorithm?

User 123 - 5 years, 8 months ago

@User 123 – Using the ideas of dynamic programming, you want to maintain an array of the results for smaller numbers.

Then, for each number $n$ you consider every square $m^2 \leq n$ , look up the number of squares needed for $n - m^2$ and add one. Of all these numbers, you choose the lowest.

For instance, for $n = 18$ , your table will look like this (starting at 1): $1, \boxed{2}, 3, 1, 2, 3, 4, 2, \boxed{1}, 2, 3, 3, 2, \boxed{3}, 4, 1, \boxed{2}.$ Now we try $\begin{array}{llll} m^2 = 16 & n-m^2 = 2 & 2 + 1 = 3 & 18 = 4^2 + (1^2 + 1^2) \\ m^2 = 9 & n-m^2 = 7 & 1 + 1 = 2 & 18 = 3^2 + (3^2)\\ m^2 = 4 & n-m^2 = 12 & 3 + 1 = 4 & 18 = 2^2 + (2^2 + 2^2 + 2^2) \\ m^2 = 1 & n-m^2 = 17 & 2 + 1 = 3 & 18 = 1^2 + (16^2 + 1^2) \end{array}$

To speed up your algorithm, here are some suggestions:

You need only check squares up to and including $m^2 = n/2$ .
Instead of using the square as the loop variable and checking if it is indeed a square, simply generate the squares:

sum = 0;
s[0] = 1;   // Starting point: there is one way to write 0 as a sum of squares.
for (int n = 1; n < 2015; n++)
{
   m = 1; best = -1;
   do {
      sq = m*m;
      nsq = s[n - sq] + 1;     // Look up number of squares needed for smaller number.
      if (nsq < best) best = nsq;  // Remember the smallest value
      m++;
   } while (m2 <= n/2);
   s[n] =best;   // Store the result in an array for later use.
   if (n >= 2) sum += s[n];  // Keep total for n >= 2.
}

Arjen Vreugdenhil - 5 years, 8 months ago

@Arjen Vreugdenhil Sir, please could you help me?

User 123 - 5 years, 8 months ago

Samarpit Swain
Sep 24, 2015

Here's a C++ solution using Dynamic Programming:

#include<iostream>
#define INT_MAX 999999999
using namespace std;
int MinimaSquare(int n)
{
  int dp[n+1];

  dp[0]=0;
  for(int x=1;x<=n;x++)
  {
    dp[x]=INT_MAX;
    for(int j=1;j*j<=x;j++)
    {
      int count=j*j;
        dp[x]=min(dp[x],dp[x-count]+1);
    }
  }
  return dp[n];
}
int main()
{
    long int sum=0;

  for(int i=2;i<=2015;i++)

      sum+=MinimaSquare(i);

      cout<<sum;

    return 0;
}

Output:

Thaddeus Abiy
Aug 27, 2015

Notice that $\varsigma(n) = min \{1 + \varsigma(n-i^2) \} \ for \ i \leq \lfloor n^{0.5} \rfloor$ . This recurrence can then be used to build a bottom up Dynamic Programming approach.

Python 2.7

DP = {0:0}
n = 1
while n <= 2015:
    s , sqrt = 'infinity' , n**.5
    if sqrt%1==0:
        DP[n] = 1
    else:
        for i in range(1,int(sqrt)+1):
            s = min( 1 + DP[n-i*i] , s )
        DP[n] = s
    n += 1

print sum(DP.values()[2:2015+1])

Moderator note:

Nice usage of dynamic programming here to simplify the calculations slightly. It is naturally motivated from the way in which we want to find the value as a sum of (smaller) squares.

Abdelhamid Saadi
Sep 13, 2015

A variant of the solution in python 3.4:

varsigma_ ={0: 0}

def sqrange(a):
    k = 1
    while k*k <= a:
        yield k
        k = k + 1

def varsigma(n):
    if not n in varsigma_:
        varsigma_[n] = min(1+ varsigma(n - k*k) for k in sqrange(n))
    return varsigma_[n]

def solve(n):
    "Do the bare minimum"
    return sum (varsigma(k) for k in range(2,n+1))

print(solve(2015))

Abhishek Sinha
Aug 29, 2015

First of all, observe that by Lagrange's Four Square Theorem , $\varsigma(n)\leq 4, \forall n$ . Hence we have to just check up to $3$ combinations of squares of all numbers in the list $\{1,2,\ldots, \lfloor{\sqrt{N}\rfloor}\}$ where $N=2015$ . Computational complexity $\Theta(N^{1.5})$ .

Yay to number theoretic approaches! Let's continue in this vein.

In fact, we can easily classify the numbers which need 1 square (perfect squares), those which need (at most) 2 square (via Fermat's two square theorem) and those which need (at most) 3 squares (via Legendre 3 square theorem).

Calvin Lin Staff - 5 years, 9 months ago

Number-theoretical approach added to my original solution.

Arjen Vreugdenhil - 5 years, 8 months ago

Could you add that to your solution? Thanks!!

Calvin Lin Staff - 5 years, 8 months ago

I do not get this solution. How would you check up to three combinations?

Agnishom Chattopadhyay - 5 years, 7 months ago

Do the bare minimum

The answer is 5714.

5 solutions

Moderator note:

0 pending reports