/*! This file is auto-generated */ .wp-block-button__link{color:#fff;background-color:#32373c;border-radius:9999px;box-shadow:none;text-decoration:none;padding:calc(.667em + 2px) calc(1.333em + 2px);font-size:1.125em}.wp-block-file__button{background:#32373c;color:#fff;text-decoration:none} Problem 10 Find the number of positive inte... [FREE SOLUTION] | 91影视

91影视

Log out

Learning Materials

Features

Discover

Chapter 8: Problem 10

Find the number of positive integers not exceeding 100 that are not divisible by 5 or by 7 .

Short Answer

Expert verified
68

Step by step solution

01

Identify Total Numbers

The first step is to identify the total number of positive integers not exceeding 100. This is simply 100, as we are considering the numbers from 1 to 100.
02

Count Numbers Divisible by 5

Next, count the numbers that are divisible by 5. The sequence of numbers divisible by 5 up to 100 is 5, 10, 15, ..., 100. This forms an arithmetic sequence with the first term (a) as 5 and the common difference (d) as 5. The number of terms (n) in this sequence can be found using the formula for the nth term of an arithmetic sequence: \[ an = a + (n-1)d \] Set the nth term (an) to 100 and solve for n: \[ 100 = 5 + (n-1) \times 5 \] \[ 100 = 5 + 5n - 5 \] \[ 100 = 5n \] \[ n = 20 \] There are 20 numbers divisible by 5.
03

Count Numbers Divisible by 7

Count the numbers that are divisible by 7 up to 100. The sequence of numbers divisible by 7 is 7, 14, 21, ..., 98. This forms an arithmetic sequence with the first term (a) as 7 and the common difference (d) as 7. Using the nth term formula: \[ an = a + (n-1)d \] Set the nth term (an) to the largest number not exceeding 100 and solve for n: \[ 98 = 7 + (n-1) \times 7 \] \[ 98 = 7 + 7n - 7 \] \[ 98 = 7n \] \[ n = 14 \] There are 14 numbers divisible by 7.
04

Count Numbers Divisible by Both 5 and 7

Find the numbers that are divisible by both 5 and 7. Any such number must be divisible by their least common multiple (LCM). The LCM of 5 and 7 is 35. The sequence of numbers up to 100 that are divisible by 35 is 35, 70. This forms an arithmetic sequence with the first term (a) as 35 and the common difference (d) as 35: \[ an = a + (n-1)d \] Set the nth term (an) to the largest number not exceeding 100 and solve for n: \[ 70 = 35 + (n-1) \times 35 \] \[ 70 = 35 + 35n - 35 \] \[ 70 = 35n \] \[ n = 2 \] There are 2 numbers divisible by both 5 and 7.
05

Apply Inclusion-Exclusion Principle

Use the Inclusion-Exclusion Principle to find the total number of positive integers not divisible by 5 or by 7. Count the numbers divisible by 5 (20) and 7 (14), subtract the numbers divisible by both (2): \[ 20 + 14 - 2 = 32 \] There are 32 numbers divisible by 5 or by 7.
06

Calculate the Result

Subtract the number of integers divisible by 5 or 7 from the total integers not exceeding 100 to get the result: \[ 100 - 32 = 68 \] Thus, there are 68 numbers not exceeding 100 that are not divisible by 5 or by 7.

Unlock Step-by-Step Solutions & Ace Your Exams!

  • Full Textbook Solutions

    Get detailed explanations and key concepts

  • Unlimited Al creation

    Al flashcards, explanations, exams and more...

  • Ads-free access

    To over 500 millions flashcards

  • Money-back guarantee

    We refund you if you fail your exam.

Over 30 million students worldwide already upgrade their learning with 91影视!

Key Concepts

These are the key concepts you need to understand to accurately answer the question.

Inclusion-Exclusion Principle
The Inclusion-Exclusion Principle is a fundamental concept in combinatorics. It helps us count the number of elements in the union of multiple sets by including the sizes of individual sets and excluding the sizes of overlapping sets.
In this problem, we want to find numbers up to 100 that are not divisible by 5 or 7. Using the Inclusion-Exclusion Principle, we first count the numbers divisible by 5 and those divisible by 7.
Then, we subtract the count of numbers divisible by both to avoid double-counting.
  • Count divisible by 5: 20
  • Count divisible by 7: 14
  • Count divisible by both 5 and 7: 2
Applying the principle:
\[ 20 + 14 - 2 = 32 \] Subtract this from the total (100):
\[ 100 - 32 = 68 \] We get 68 numbers that are not divisible by either.
Arithmetic Sequence
An arithmetic sequence is a sequence of numbers with a constant difference between consecutive terms.
For example, if we want to count numbers divisible by 5 up to 100, these form an arithmetic sequence: 5, 10, 15, ..., 100. Here, the first term (a) is 5, and the common difference (d) is also 5.
To find the number of such terms, we use the formula for the nth term:
\[ a_n = a + (n-1)d \] Setting the nth term (a_n) to 100 and solving for n:
\[ 100 = 5 + (n-1) \times 5 \] \[ 95 = 5n \] \[ n = 20 \] So, there are 20 terms divisible by 5. Similarly, we count numbers divisible by 7 and those divisible by 35, which are also arithmetic sequences.
Divisibility
Divisibility is a key concept in number theory and arithmetic. A number is divisible by another if it can be divided without leaving a remainder.
In our problem, we identify numbers up to 100 which are divisible by 5 or 7. By understanding divisibility, we can list numbers that meet these criteria.
  • Numbers divisible by 5: Divisibility rules tell us that if a number ends in 0 or 5, it is divisible by 5.
  • Numbers divisible by 7: This is less straightforward and often involves checking individual terms.
To see if a number is divisible by both 5 and 7, we find its Least Common Multiple (LCM). The LCM of 5 and 7 is 35. So, numbers like 35 and 70 are divisible by both.
These concepts help break down the task of counting specific groups of numbers efficiently.

One App. One Place for Learning.

All the tools & learning materials you need for study success - in one app.

Get started for free

Most popular questions from this chapter

Show that the Fibonacci numbers satisfy the recurrence relation \(f_{n}=5 f_{n-4}+3 f_{n-5}\) for \(n=5,6,7, \ldots,\) together with the initial conditions \(f_{0}=0, f_{1}=1, f_{2}=1, f_{3}=2\) and \(f_{4}=3 .\) Use this recurrence relation to show that \(f_{5 n}\) is divisible by \(5,\) for \(n=1,2,3, \ldots\)

Use generating functions to solve the recurrence relation \(a_{k}=5 a_{k-1}-6 a_{k-2}\) with initial conditions \(a_{0}=6\) and \(a_{1}=30\)

a) Find a recurrence relation for the number of bit strings of length \(n\) that contain the string \(01 .\) b) What are the initial conditions? c) How many bit strings of length seven contain the string 01\(?\)

a) Find the recurrence relation satisfied by \(R_{n},\) where \(R_{n}\) is the number of regions that a plane is divided into by \(n\) lines, if no two of the lines are parallel and no three of the lines go through the same point. b) Find \(R_{n}\) using iteration.

This exercise deals with the problem of finding the largest sum of consecutive terms of a sequence of n real numbers. When all terms are positive, the sum of all terms provides the answer, but the situation is more complicated when some terms are negative. For example, the maximum sum of consecutive terms of the sequence \(-2,3,-1,6,-7,4\) is \(3+(-1)+6=8 .\) (This exercise is based on \([\mathrm{Be} 86] .\) Recall that in Exercise 56 in Section 8.1 we developed a dynamic programming algorithm for solving this problem. Here, we first look at the brute-force algorithm for solving this problem; then we develop a divide- and-conquer algorithm for solving it. a) Use pseudocode to describe an algorithm that solves this problem by finding the sums of consecutive terms starting with the first term, the sums of consecutive terms starting with the second term, and so on, keeping track of the maximum sum found so far as the algorithm proceeds. b) Determine the computational complexity of the algorithm in part (a) in terms of the number of sums computed and the number of comparisons made. c) Devise a divide-and-conquer algorithm to solve this problem. [Hint: Assume that there are an even number of terms in the sequence and split the sequence into two halves. Explain how to handle the case when the maximum sum of consecutive terms includes terms in both halves.] d) Use the algorithm from part (c) to find the maximum sum of consecutive terms of each of the sequences: \(-2,4,-1,3,5,-6,1,2 ; 4,1,-3,7,-1,-5, \quad 3,-2 ;\) and \(-1,6,3,-4,-5,8,-1,7\) e) Find a recurrence relation for the number of sums and comparisons used by the divide-and-conquer algorithm from part (c). f ) Use the master theorem to estimate the computational complexity of the divide-and-conquer algorithm. How does it compare in terms of computational complexity with the algorithm from part (a)?
See all solutions

Recommended explanations on Math Textbooks

Geometry

Read Explanation

Decision Maths

Read Explanation

Theoretical and Mathematical Physics

Read Explanation

Logic and Functions

Read Explanation

Mechanics Maths

Read Explanation

Discrete Mathematics

Read Explanation
View all explanations

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Study anywhere. Anytime. Across all devices.