finding numbers not sumsble by others

GLneo · Post by **GLneo** » Sat Sep 22, 2007 12:46 pm

I do not care what the solution is, but how to find it with a simple c program. What I want to find is "what football scores are not possible", in football it is possible to to get a 2, 3, 6, and 7 points and any combination of these, so what scores can not be gotten by summing these; ( like I said I don't care about the solution, just how to find it) also the code should have portability so any string of #'s. Here is what I have so far:

Code: Select all

#include <stdio.h>
#include <stdlib.h>

#define MAX_SEARCH 500

int main( void )
{
    int num_testing = 0, sum = 0, work = 0;
    for( work = 0 ; num_testing <= MAX_SEARCH ; num_testing++ )
    {
        for( ; sum <= MAX_SEARCH; sum + 2 )
        {
            if( num_testing % sum )
            {
                printf( "%d, ", num_testing );
                break;
            }
            for( ; sum <= MAX_SEARCH; sum + 3 )
            {
                if( num_testing % sum )
                {
                    printf( "%d, ", num_testing );
                    break;
                }
                for( ; sum <= MAX_SEARCH; sum + 6 )
                {
                    if( num_testing % sum )
                    {
                        printf( "%d, ", num_testing );
                        break;
                    }
                    for( ; sum <= MAX_SEARCH; sum + 7 )
                    {
                        if( num_testing % sum )
                        {
                            printf( "%d, ", num_testing );
                            break;
                        }
                    }
                }
            }
        }
    }
    puts("DONE!");
    system("pause");
    return 0;
}

dont ask me what i'm doing because i don't even know

Alboin · Post by **Alboin** » Sat Sep 22, 2007 1:24 pm

Are there any scores that can't be added with 2, 3, 6, and 7? (Besides 1.)

GLneo · Post by **GLneo** » Sat Sep 22, 2007 1:32 pm

no, but i want to know how to find out how it can be calculated for other #'s

bluecode · Post by **bluecode** » Sat Sep 22, 2007 1:36 pm

First of all I would say that you can just forget about the 6 and the 7 here, because 6 is 2 + 2 + 2 or 3 + 3 and 7 is 2 + 2 + 3. So all score values (Let's call the y) must fulfill the following equation:

Code: Select all

y = x1 * 2 + x2 * 3

Yet I am not sure which numbers do (not) fulfill this equation (exept the trivial 1).

edit: I am missing the point of this, I guess? Could you clarify what you want?

jnc100 · Post by **jnc100** » Sat Sep 22, 2007 2:05 pm

Alboin is correct. For the numbers 2, 3, 6 and 7, the 6 and 7 are irrelevant because 6 = 3 + 3 and 7 = 2 + 2 + 3. So for the numbers 2 and 3, the 2 implies you can get any even number, and the 3 implies you can get to 3, as well as 3 + any even number i.e. all odd numbers >= 3.

For a more general case, you should start with the numbers you have. Now, to test if a number can be summed from these, you should start with a collection containing only these numbers (let's call them a, b and c). Then, start from the smallest number in the sequence + 1, call it d.

Test if d - a is in the collection, if it is, then d can be summed from those original numbers, and then add d to the collection.
Similarly, test d - b and d - c.

Then move on to the next number, call it e. Test e - a, e - b, e - c similarly to above. Also, if you added 'd' to the collection, test e - d. If any of them result in a number in the collection, then e can be made from the original numbers to, so you can add it to the collection.

Work through this way, and you can produce a list of those numbers which cannot be calculated.

There probably is an easier way though, but this seems complete.

Regards,
John.

GLneo · Post by **GLneo** » Sat Sep 22, 2007 2:09 pm

@bluecode: I want code that can calculate numbers that can not be summed by any combining numbers like (2, 3) or (24, 43, 58)

@Alboin: 11 is not modable by 2 or 3, but can be found with 3 + 3 + 3 + 2

I presume the code would need a lot of loops and recursion.

Alboin · Post by **Alboin** » Sat Sep 22, 2007 2:19 pm

GLneo wrote:@Alboin: 11 is not modable by 2 or 3, but can be found with 3 + 3 + 3 + 2

Ah, but:

11 % 3 = 2
2 % 2 = 0

So, there you have it.

bluecode · Post by **bluecode** » Sat Sep 22, 2007 2:21 pm

jnc100 wrote:Alboin is correct. For the numbers 2, 3, 6 and 7, the 6 and 7 are irrelevant because 6 = 3 + 3 and 7 = 2 + 2 + 3.

Actually that was me

But nevermind.

@GLneo: As jnc100 pointed out, there are no numbers that can not be represented as a sum of 2s and 3s (except for the number 1). So there is no point in seeking them

Or is it about a random tuple/tripple/whatever of summands?

GLneo · Post by **GLneo** » Sat Sep 22, 2007 2:59 pm

no, it's more that I'm bored and want to see code that can find unsumable numbers...

@Alboin: when you said: "11 % 3 = 2 \ 2 % 2 = 0 \\ So, there you have it.", I think i know what you mean, so i wrote this:

Code: Select all

#include <stdio.h>
#include <stdlib.h>

#define MAX_SEARCH 500

int numbers[]= { 10 , 11 };

int main( void )
{
    int num_testing = 0, index = 0, sum = 0;
    for( ; num_testing <= MAX_SEARCH ; num_testing++ )
    {
        for ( sum = num_testing, index = 0; index < sizeof( numbers ); index++ )
        {
            sum = ( sum % numbers[ index ] );
            if( sum = 0 )
            {
                printf( "%d, ", num_testing );
                break;
            }
        }
    }
    puts("DONE!");
    system("pause");
    return 0;
}

which just Inf Loops, and i cant figure out what is wrong...

jnc100 · Post by **jnc100** » Sat Sep 22, 2007 3:06 pm

bluecode wrote:
jnc100 wrote:Alboin is correct. For the numbers 2, 3, 6 and 7, the 6 and 7 are irrelevant because 6 = 3 + 3 and 7 = 2 + 2 + 3.
Actually that was me But nevermind.

Actually only Alboin had replied when I started posting...

GLneo wrote:
Code: Select all
if( sum = 0 )

Please tell me your compiler emits a warning about this line

Regards,
John.

GLneo · Post by **GLneo** » Sat Sep 22, 2007 3:13 pm

nope it doesn't, but i just fixed it and now it finds that 0 in not summable then crashes

Alboin · Post by **Alboin** » Sat Sep 22, 2007 4:45 pm

Meow...

Code: Select all

char isin(int n, int a, int b) {
	while(n != 0) {			
		int table[] = {
			n % (a * b),
			n % (a + b) * a,
			n % (a + b) * b,
			n % (a + b),
			n % a,
			n % b,
		};
		
		int i;
		char set = 'f';
		for(i = 5; i != -1; i--) {
			if(table[i] == 0 || table[i] == a || table[i] == b) 
				return 't';
			else if(table[i] >= a || table[i] >= b) {
				if((table[i] % a) == 0 || (table[i] % b) == 0) 
					n = table[i];
				return 'f';
			}
		}
	}
	return 'f';
}

GLneo · Post by **GLneo** » Sun Sep 23, 2007 10:40 am

... comments ...

what does that function do, and how do i use it ...

Alboin · Post by **Alboin** » Sun Sep 23, 2007 12:31 pm

GLneo wrote:... comments ...

what does that function do, and how do i use it ...

It determines if n is able to be added up by any combination of a and b. So,

Code: Select all

isin(x, 2, 3);

Should yield 't' for any value greater than one for x.

GLneo · Post by **GLneo** » Sun Sep 23, 2007 6:10 pm

but what if I want to test 3, 4, 5+ numbers?