mathematics

Problems involving arithmetic progressions

Problems involving arithmetic progressions is a mathematics topic covered in the lgStudy science library. This page brings together a partial reference excerpt, illustrations, worked examples, real-world applications and a short study plan, so you can understand Problems involving arithmetic progressions rather than just read about it. In short: Problems involving arithmetic progressions are of interest in number theory, combinatorics, and computer science, both from theoretical and applied points of view. Largest progression-free subsets Find the cardinality (denoted by Ak(m)) of the largest subset of {1, 2, ..., m} which contains no progression of k distinct terms.

Key takeaways

Problems involving arithmetic progressions belongs to mathematics; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Problems involving arithmetic progressions to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Problems involving arithmetic progressions from memory before moving on to harder problems.

Reference excerpt

Problems involving arithmetic progressions are of interest in number theory, combinatorics, and computer science, both from theoretical and applied points of view.

Largest progression-free subsets Find the cardinality (denoted by Ak(m)) of the largest subset of {1, 2, ..., m} which contains no progression of k distinct terms. The elements of the forbidden progressions are not required to be consecutive. For example, A4(10) = 8, because {1, 2, 3, 5, 6, 8, 9, 10} has no arithmetic progressions of length 4, while all 9-element subsets of {1, 2, ..., 10} have one. In 1936, Paul Erdős and Pál Turán posed a question related to this number and Erdős set a $1000 prize for an answer to it. The prize was collected by Endre Szemerédi for a solution published in 1975, what has become known as Szemerédi's theorem.

Arithmetic progressions from prime numbers

Szemerédi's theorem states that a set of natural numbers of non-zero upper asymptotic density contains finite arithmetic progressions, of any arbitrary length k. Erdős made a more general conjecture from which it would follow that

The sequence of primes numbers contains arithmetic progressions of any length. This result was proven by Ben Green and Terence Tao in 2004 and is now known as the Green–Tao theorem. See also Dirichlet's theorem on arithmetic progressions. As of 2020, the longest known arithmetic progression of primes has length 27:

224584605939537911 + 81292139·23#·n, for n = 0 to 26. (23# = 223092870) As of 2011, the longest known arithmetic progression of consecutive primes has length 10. It was found in 1998. The progression starts with a 93-digit number

100 99697 24697 14247 63778 66555 87969 84032 95093 24689 19004 18036 03417 75890 43417 03348 88215 90672 29719 and has the common difference 210.

Primes in arithmetic progressions The prime number theorem for arithmetic progressions deals with the asymptotic distribution of prime numbers in an arithmetic progression.

Covering by and partitioning into arithmetic progressions Find minimal ln such that any set of n residues modulo p can be covered by an arithmetic progression of the length ln. For a given set S of integers find the minimal number of arithmetic progressions that cover S For a given set S of integers find the minimal number of nonoverlapping arithmetic progressions that cover S Find the number of ways to partition {1, ..., n} into arithmetic progressions. Find the number of ways to partition {1, ..., n} into arithmetic progressions of length at least 2 with the same period. See also Covering system

See also Arithmetic combinatorics PrimeGrid

Notes

Worked examples

Example 1 — a first encounter with Problems involving arithmetic progressions

Start with the simplest possible case. Write down what Problems involving arithmetic progressions claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In mathematics, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Problems involving arithmetic progressions before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Problems involving arithmetic progressions ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Problems involving arithmetic progressions

In research: Problems involving arithmetic progressions appears in mathematics research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Problems involving arithmetic progressions in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Problems involving arithmetic progressions is common in secondary-school and first-year university syllabi. It links to neighbouring topics Series (mathematics), Unsolved problems in number theory, so understanding it makes those chapters shorter.
In everyday life: Look for Problems involving arithmetic progressions outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

Affiliate

Preply — study more efficiently by working with a personal tutor. 50% off.

How to study Problems involving arithmetic progressions in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Problems involving arithmetic progressions means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Problems involving arithmetic progressions out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Problems involving arithmetic progressions in simple terms?

Problems involving arithmetic progressions are of interest in number theory, combinatorics, and computer science, both from theoretical and applied points of view. Largest progression-free subsets Find the cardinality (denoted by Ak(m)) of the largest subset of {1, 2, ..., m} which contains no prog…

Why does Problems involving arithmetic progressions matter?

Because it connects several mathematics ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Problems involving arithmetic progressions?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Problems involving arithmetic progressions.