AMC 10 · 2010 · #25

Grade 8 number-theory

Archetype Small-Domain Constrained Search └ Sub-archetype Factor / Divisibility Constraint

prime-factorizationp-adic-valuationprime-numbersmultiples identify-subproblemsextreme-principle ↑ Prerequisites: prime-factorizationp-adic-valuation

📏 Long solution 💡 4 insights

Problem

Each number contributes the power of its own largest prime, and all of them are multiplied together. Find the highest power of a given number that divides it.

Pick an answer.

(A)

(B)

(C)

(D)

(E)

How to solve

Strategy Identify Subproblems

The product is astronomically large, so nobody computes it. Tool #7 (Identify Subproblems) is the whole game: since 2010=2 · 3 · 5 · 67 is squarefree, the single question "what is the largest m?" splits into four completely separate counting questions — how many 2s, 3s, 5s, and 67s does the product contain — and m is the smallest of the four answers. Tool #14 (Extreme Principle) appears twice: pow is defined by the largest prime of n, and the final answer is a minimum over primes. Tool #15 (Organize Information in More Ways) turns the intimidating product into a sorted tally: instead of walking n from 2 to 5300, group the n by which prime is their largest. Tool #2 (Make a Systematic List) and Tool #3 (Eliminate Possibilities) then count the 67-contributors exactly, layer by layer, throwing out the ones that secretly contain a bigger prime. Tool #9 (Solve an Easier Related Problem) handles the three small primes: we do not need their exact tallies, only proof that each clears the 67 tally — but the margin turns out to be thin enough that the check is mandatory, not decorative.

1STEP 1

Split into four prime counts

The divisor splits into four separate primes.

2010=2 · 3 · 5 · 67 ⟹ m=min(v₂(X), v₃(X), v₅(X), v₆₇(X))

2STEP 2

Sort the terms by top prime

Each number feeds only its own largest prime.

v_p(X)=Σ_{2 ≤ n ≤ 5300 ; largest prime of n = p} v_p(n)

3STEP 3

Describe every 67-contributor

The contributors form a describable family.

n=67^a b, a ≥ 1, 67 ∤ b, every prime of b ＜ 67, 67^ab ≤ 5300 → contributes a

4STEP 4

Count the a = 1 layer

The first layer gives 75.

b ≤ ⌊ 5300/67 ⌋=79; delete b∈{67,71,73,79}; 79-4=75 values, contributing 75

5STEP 5

Count the a = 2 layer

The second layer adds 2 more.

67²=4489 ≤ 5300 ＜ 8978=2 · 67² → only n=4489, contributing 2; v₆₇(X)=75+2=77

6STEP 6

Check the 2s — the tight one

The count of twos is the close rival.

v₂(X)=Σ_k=1¹² k=(12 · 13)/2=78, 2¹²=4096 ≤ 5300 ＜ 8192=2¹³

7STEP 7

Check the 3s and the 5s

The other two primes are comfortably larger.

v₃(X)=11+20+24+28+25+18+14=140; v₅(X) ≥ 41 · 1+25 · 2=91

8STEP 8

Take the minimum

The smallest count is 77, choice (D).

m=min(78, 140, ≥ 91, 77)=77 → (D)

Answer

Two independent sanity checks. First, the size estimate: the 67s essentially come from multiples of 67 up to 5300, of which there are ⌊ 5300/67⌋=79, and we removed three big-prime cases and added one for the square — landing at 77, inside the answer range 74 to 78 as the choices promise. Second, and more important, the sufficiency check has real teeth: v₂(X)=78 beats 77 by a single copy. If the problem had run n up to 5500 instead of 5300, the 67 tally would climb to 80 while the 2 tally would sit unchanged at 78 (the next power of two, 8192, is still far out of range), and the answer would be 78, set by the 2s rather than the 67s. The upper limit 5300 sits just below that switchover. This is exactly why "there are surely enough small primes" is not an argument here; the numbers had to be computed. Small boundary cases also check out: n=5293=67 · 79 is inside the range but excluded because 79 ＞ 67 is its true largest prime, and n=4489=67² is the only term contributing two 67s.

💡Key takeaway

Since 2010=2 · 3 · 5 · 67, count each prime separately and take the smallest count: the 67s run out first at 77, and the 2s survive with exactly one to spare.

Split into four prime counts
Sort the terms by top prime
Describe every 67-contributor
Count the a = 1 layer
Count the a = 2 layer
Check the 2s — the tight one
Check the 3s and the 5s
Take the minimum