MHB Solving Integer Equations for Integers Not Hit By Any Expression

[lukem]

Hello

I am trying to simplify a set of equations to something easier to work with. For example

11x+4
13x+11
31x+17
19x+2
14x+9

Over integer values for x, I need to find numbers that won't be hit by these equations. The first one hits 4,15,26,37,48,59 for x=0,1,2,3,4,5. Is there a way to find a number that won't be in any set, for any range of x values? I know for a single equation, 11x+5 wouldn't ever be the same as 11x + 4, but is there a way to find an equation that won't be in any of the sets, or even a reliable way to find one number that won't be in those sets (without comparing results manually). I don't care about lines crossing on a graph of these if they were y(x) functions, I just need to know which integers don't get picked by anyone of the expressions for integer values of x. I'm trying to combine 50 of these "rules" and find numbers that never get hit.

Sorry about the wording, I really have no idea how to present this question.

Thanks!

 

[I like Serena]

Hello

I am trying to simplify a set of equations to something easier to work with. For example

11x+4
13x+11
31x+17
19x+2
14x+9

Over integer values for x, I need to find numbers that won't be hit by these equations. The first one hits 4,15,26,37,48,59 for x=0,1,2,3,4,5. Is there a way to find a number that won't be in any set, for any range of x values? I know for a single equation, 11x+5 wouldn't ever be the same as 11x + 4, but is there a way to find an equation that won't be in any of the sets, or even a reliable way to find one number that won't be in those sets (without comparing results manually). I don't care about lines crossing on a graph of these if they were y(x) functions, I just need to know which integers don't get picked by anyone of the expressions for integer values of x. I'm trying to combine 50 of these "rules" and find numbers that never get hit.

Sorry about the wording, I really have no idea how to present this question.

Thanks!

Hi lukem! Welcome to MHB! (Smile)

For starters, the numbers 1, 3, 5, 7, 8 are not hit by any of these expressions are they?

To formulate it more properly, let's call the set with numbers that are hit $H$, and the set of numbers that won't get hit $W$.
Then we have:
$$H=\{11x+4, 13x+11, 31x+17, 19x+2, 14x+9 : x \in \mathbb N\}$$
I think we're looking for its complement, $W=\mathbb N \setminus H$ yes?

We will have a sequence of numbers that won't get hit, and after $N=11 \times 13\times 31\times 19\times 14$ numbers this sequence will repeat itself, since that's the common multiple of the factors in those expressions.
For example, we already know that $1$ won't get hit.
That means that $N+1$ won't get hit either.
That's because for $x=\frac N{11}$, the first expression is $11\cdot \frac N{11} + 4=N+4$.
The number before is $N+4-11$, and $N+1$ is between those two.
The same reasoning applies to all other expressions.

To find the numbers, we can apply a sieve.
That is, we keep track of the set of numbers 1 up to some $n$, and we cross out every number that gets hit by each of the expressions.

For the numbers up to $n=100$, these are:

1, 3, 5, 6, 7, 8, 10, 12, 13, 14, 16, 18, 19, 20, 22, 25, 27, 28, 29, 30,  31, 32, 33, 34, 35, 36, 38, 39, 41, 42, 43, 44, 45, 46, 47, 49, 52, 53, 54, 55, 56, 57, 58, 60, 61, 62, 64, 66, 67, 68, 69, 71, 72, 73, 74, 75, 77, 80, 82, 83, 84, 85, 86, 87, 88, 90, 91, 94, 95, 96, 98, 99, 100

 

[HallsofIvy]

These can be expressed as "Diophantine" equations, equation in which all variables have to be integers. I would turn the question around: the first asks for values of y that are NOT of the form 11x+ 4 so I would look for y the does satisfy 11x+ 4= y. That can be written in the linear "Diophantine" equation form of y- 11x= 4. The first thing I would see is that an obvious answer is x= 1, y= 15: 15- 11= 4. The next thing, slightly harder to see, is that any number of the form x= 1+ k, y= 15+ 11k is also a solution, (15+ 11k)- 11(x+ k)= 15+ 11k- 11- 11k= 15- 11= 4, and that any solution must be of that form. So any value of y for which 11x+ 4= y must be of the form 15+ 11k. Reversing that, 11x+ 4 takes on all values except those that are NOT of the form 15+ 11k.

 

[lukem]

Hi lukem! Welcome to MHB! (Smile)

For starters, the numbers 1, 3, 5, 7, 8 are not hit by any of these expressions are they?

To formulate it more properly, let's call the set with numbers that are hit $H$, and the set of numbers that won't get hit $W$.
Then we have:
$$H=\{11x+4, 13x+11, 31x+17, 19x+2, 14x+9 : x \in \mathbb N\}$$
I think we're looking for its complement, $W=\mathbb N \setminus H$ yes?

We will have a sequence of numbers that won't get hit, and after $N=11 \times 13\times 11\times 31\times 19\times 14$ numbers this sequence will repeat itself, since that's the common multiple of the factors in those expressions.
For example, we already know that $1$ won't get hit.
That means that $N+1$ won't get hit either.
That's because for $x=\frac N{11}$, the first expression is $11\cdot \frac N{11} + 4=N+4$.
The number before is $N+4-11$, and $N+1$ is between those two.
The same reasoning applies to all other expressions.

To find the numbers, we can apply a sieve.
That is, we keep track of the set of numbers 1 up to some $n$, and we cross out every number that gets hit by each of the expressions.

For the numbers up to $n=100$, these are:

1, 3, 5, 6, 7, 8, 10, 12, 13, 14, 16, 18, 19, 20, 22, 25, 27, 28, 29, 30,  31, 32, 33, 34, 35, 36, 38, 39, 41, 42, 43, 44, 45, 46, 47, 49, 52, 53, 54, 55, 56, 57, 58, 60, 61, 62, 64, 66, 67, 68, 69, 71, 72, 73, 74, 75, 77, 80, 82, 83, 84, 85, 86, 87, 88, 90, 91, 94, 95, 96, 98, 99, 100

Thank you very much I-like-Serena. This is very useful . I can see my set size will grow very quickly as I add more expressions. Is there any way to calculate what size the sieve set will be before generating it? Or even more ambitiously, calculate the size of the set below 100, or below 1000?

- - - Updated - - -

These can be expressed as "Diophantine" equations, equation in which all variables have to be integers. I would turn the question around: the first asks for values of y that are NOT of the form 11x+ 4 so I would look for y the does satisfy 11x+ 4= y. That can be written in the linear "Diophantine" equation form of y- 11x= 4. The first thing I would see is that an obvious answer is x= 1, y= 15: 15- 11= 4. The next thing, slightly harder to see, is that any number of the form x= 1+ k, y= 15+ 11k is also a solution, (15+ 11k)- 11(x+ k)= 15+ 11k- 11- 11k= 15- 11= 4, and that any solution must be of that form. So any value of y for which 11x+ 4= y must be of the form 15+ 11k. Reversing that, 11x+ 4 takes on all values except those that are NOT of the form 15+ 11k.

Is there any way I could combine these Diophantine equations?

 

[I like Serena]

Thank you very much I-like-Serena. This is very useful . I can see my set size will grow very quickly as I add more expressions. Is there any way to calculate what size the sieve set will be before generating it? Or even more ambitiously, calculate the size of the set below 100, or below 1000?

The size of a sieve that finds unique numbers is the least common multiple of the factors in your expressions. After that they repeat.
I wouldn't know of a way to find how many numbers won't be hit in that sieve size though, other than working through it, possibly assisted by a computer program.
As it is, I wrote a python program to do the sieving for me:

Spoiler

n=101
s=[0] * n

def sieve(factor, base):
	k=base
	while k < n:
		s[k]=1
		k+=factor

sieve(11,4)
sieve(13,11)
sieve(31,17)
sieve(19,2)
sieve(14,9)

result = ""
for k in range(0, n):
	if s[k]==0:
		result += str(k) + ", "
print result

We can use it to count how many numbers there are as well.

 

[lukem]

The size of a sieve that finds unique numbers is the least common multiple of the factors in your expressions. After that they repeat.
I wouldn't know of a way to find how many numbers won't be hit in that sieve size though, other than working through it, possibly assisted by a computer program.
As it is, I wrote a python program to do the sieving for me:

Spoiler

n=101
s=[0] * n

def sieve(factor, base):
	k=base
	while k < n:
		s[k]=1
		k+=factor

sieve(11,4)
sieve(13,11)
sieve(31,17)
sieve(19,2)
sieve(14,9)

result = ""
for k in range(0, n):
	if s[k]==0:
		result += str(k) + ", "
print result

We can use it to count how many numbers there are as well.

Thanks! :)