Middle number square

[catee]

Hello I'm new here and I need to do this task:


Find all 5-digit integers whose middle square is equal to the sum of the digits and how many are they? Make a function. :)


My bad code is:

  #include <vcl.h>
#pragma hdrstop
#pragma argsused
#include <iostream.h>
int main(int argc, char* argv[])
{
int a,b,c,i,k,x;
int suma;
int kvad;
int kiek=0;
for (x=10000;x<=99999;x++)
{
b=x;
suma=0;
while (b>0)
{
a=b%10;
k=0;
for(i=1;i<=a;i++)
{
if (a%i==0) k++;
}
if (k==2) suma=suma+a;
b=b/10;
}
if (kvad=c^2) ;
{
kiek++;
cout<<x<<" Number middle square -"<<suma<<" \n";
}
}
cout<<"Sum of digits: "<<kiek<<" \n";
system ("PAUSE");
        return 0;
}

[Thomas1965]

I would even make 2 functions: one for the middle square and one for the sum of the digits.
In this way you can break down the problem into 2 smaller problems.
Then you call theses 2 functions inside the for loop and when the results are equal then you increment a counter.

[jonnin]

welcome!
your code is a little hard to read, so I will simply offer that ^ is XOR, NOT A POWER. For a square, just use x*x (whatever variable). For powers > 3 or so, use pow(x,power).

[catee]

Could you help me? its very difficult for me, edit my code if you can.

[dhayden]

This code will loop through the 5 digit numbers and extract the digits.

Once you've extracted the digits, it should be pretty easy to add code to check whether the sum of the digits equals the square of the middle digit.

int main()
{
    unsigned digits[5];
    for (unsigned num = 10000; num <= 99999; ++num) {
	// extract the digits
	unsigned tmp = num;
	for (unsigned i=0; i<5; ++i) {
	    digits[i] = tmp % 10;
	    tmp /= 10;		// same as num = num / 10;
	}
    }
}

[icy1]

Confused on your term "middle square" -- do you mean "third digit, squared" ?

e.g.
21312 seems to be a possibility.

Third digit is "3". 3² is 9.
Sum of everything is 2+1+3+1+2 , also 9.

To get third digit without using strings, you can do 21312/100 % 10. The result of this is 3.

How does this work? Typically to remove last digit you can do an integer divide by 10, so to remove two digits we can integer divide by 100. (21312/100 == 213). Then from this result, last digit is obtained with modulus operator on 10.

Edit: nevermind; don't even need this. Just naive brute force of 90000 numbers without early exits, which I'm sure are plentiful, is fast enough:

#include <iostream>

using namespace std;

// Find all 5-digit numbers whose third digit, squared, 
//  equals the sum of all digits
int main() 
{
    // Naive approach seems fast enough...
    for (int a=1; a<=9; ++a)
    {
        for (int b=0; b<=9; ++b)
        {
            for (int c=0; c<=9; ++c)
            {
                for (int d=0; d<=9; ++d)
                {
                    for (int e=0; e<=9; ++e)
                    {
                        if (c*c == a+b+c+d+e)
                            cout << a << b << c << d << e << endl;
                    }
                }
            }
        }
    }

    return 0;
}

[tpb]

I've only heard the term "middle square" in association with an old-fashioned (and terrible) PRNG technique: https://en.wikipedia.org/wiki/Middle-square_method

[icy1]

for the lulz, I wrote a method with some early exits, so less iterations at the cost of more conditional checks:

#include <iostream>

using namespace std;

// Find all 5-digit numbers whose third digit, squared, 
//  equals the sum of all digits
int main()
{    
    int sq;  // Third digit, squared
    int count = 0;
    int iterations = 0;
    for (int c=2; c<=6; ++c)
    {
        sq = c*c;
        for (int a=1; a<=9 && c+a<=sq; ++a)
        {
            for (int b=0; b<=9 && c+a+b<=sq; ++b)
            {
                for (int d=0; d<=9 && c+a+b+d<=sq; ++d)
                {
                    for (int e=0; e<=9; ++e)
                    {
                        iterations++;
                        if (c+a+b+d+e == sq)
                        {
                            count++;
                            break;
                        }
                    }
                }
            }
        }
    }
    cout << count << endl;
    cout << "total iterations: "<< iterations << endl;
    return 0;
}

1083
total iterations: 16052

Searched around for an online benchmarker and found Quick-Bench, where I hopefully I added both methods correctly. With no optimization, the Naive approach takes a lot more CPU time, but as you turn optimization on, the compiler greatly prefers the extra int iterations over the comparisons and appears to optimize the hell out of it:

[Lower is better]

No optimization http://quick-bench.com/mgfZ1UGQIWywSjdGmjiTWSEZ_6g
Naive: ~50950
EarlyExits: ~10154

optim=O1 http://quick-bench.com/l-kwrtblGOVCzaqzje6njGvIGo4
Naive: ~113959
EarlyExits: ~38685

optim=O2 http://quick-bench.com/K8BxVBDdW7N8G8VQpKn0oujLpQc
Naive: ~12
EarlyExits: ~669

optim=O3 http://quick-bench.com/kMOSkMBUNEOX0mYda7KC5dOE-JA
Naive: ~1
EarlyExits: ~363


;D

[jonnin]

yes ... conditions are very expensive for such a simple operation; they cost the same time as a LOT of simple operations combined.

It seems like there would be a very predictable pattern to the numbers that satisfy the condition, and that they could be generated (there is going to be some mirroring going on).
222 is the first one?
then what are the possible sums of 9? 1 8, 2 7, 3 6, 4 5, mirror out
so 3 generates
138 and 831
237 and 732,
etc...
so the first set (3 digits) are easy enough to just generate.
5 digits are going to be the above numbers with the first and last digits broken down into THEIR possible sums:
237 can become 11316, 11325, ... and all the permutations where 3 is in the middle...

until eventually you get 'almost' only 1s on the left and right for the largest possible values:
211131111 (largest non zero filled)
..
900030000 (largest is a variation of this one, eg 90000003000000 you can keep adding a left and right 0 out to infinity) ... any previously generated number can be zero padded this way so you need a cutoff (or stop a N bits worth).

[dhayden]

Icy1, that's a nice solution.

One more optimization: instead of iterating through e, just compute what it needs to be and see if it's a valid digit. i.e.

++iterations;
e = sq-a-b-c-d;
if (0<=e && e < 10) {
    ++count;
}

[lastchance]

#include <iostream>
using namespace std;

// Tut, tut - global variables;
const int mid = 2;
const int N = 2 * mid + 1;
int arr[N];
int counter = 0;


void loop( int sum, int pos )
{
   if ( sum < 0 ) return;

   if ( pos == N - 1 )                // last digit
   {
      if ( sum <= 9 )
      {
         arr[pos] = sum;
         counter++;
//       for ( int i = 0; i < N; i++ ) cout << arr[i];   cout << '\n';
      }
   }
   else
   {
      int next = pos + 1;   if ( next == mid ) next++;
      int mina = 0;         if ( pos  == 0   ) mina = 1;
      int maxa = sum;       if ( maxa  > 9   ) maxa = 9;
      for ( int a = mina; a <= maxa; a++ )
      {
         arr[pos] = a;
         loop( sum - a, next );        // recursion
      }
   }
}


int main()
{    
   for ( int midVal = 2; midVal * midVal <= 9 * N; midVal++ )
   {
      arr[mid] = midVal;
      loop( midVal * midVal - midVal, 0 );
   }
   cout << "Number of possibilities for N = " << N << " is " << counter << '\n';
}

Number of possibilities for N = 5 is 1083

Also:

Number of possibilities for N = 7 is 87729
Number of possibilities for N = 3 is 15