# Solving Integer Equations for Integers Not Hit By Any Expression

• MHB
• lukem
In summary: 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 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! lukem said: 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: Code: 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 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. I like Serena said: 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:
Code:
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 - - -

HallsofIvy said:
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?

lukem said:
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:
Code:
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.

I like Serena said:
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:
Code:
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! :)

## What is an integer equation?

An integer equation is an equation where all the variables and constants are integers. This means that the solution can only be a whole number.

## What does it mean for an integer to not be hit by any expression?

In an integer equation, an integer not being hit by any expression means that it is not used as a variable or a constant in any of the expressions in the equation. This integer is usually the solution to the equation.

## How do you solve integer equations for integers not hit by any expression?

To solve integer equations for integers not hit by any expression, you can use basic algebraic techniques such as combining like terms, isolating the variable, and using inverse operations. It is important to remember that the solution must be a whole number.

## Why is it important to specify that the integers should not be hit by any expression in the equation?

This specification is important because it limits the possible solutions to the equation. By not allowing any expressions to hit the integers, we can ensure that the solution will be a whole number and not a decimal or fraction.

## Can you give an example of solving an integer equation for integers not hit by any expression?

Yes, for example, if we have the equation 2x + 1 = 9, we can solve for x by isolating the variable. First, we subtract 1 from both sides to get 2x = 8. Then, we divide both sides by 2 to get x = 4. In this case, the integer not hit by any expression is 4, which is the solution to the equation.

Replies
4
Views
2K
Replies
4
Views
1K
Replies
1
Views
1K
Replies
1
Views
2K
Replies
7
Views
1K
Replies
2
Views
1K
Replies
1
Views
919
Replies
2
Views
1K
Replies
5
Views
1K
Replies
4
Views
889