[fortenforge]

The author mentions at one point that he was unable to solve a problem because he didn't memorize the formula for the Euler totient function in order to count the number of numbers relatively prime to 9999.

...but its actually an interesting (and not super difficult) exercise in its own right to figure this out even if you don't know the formula. Encourage you all to give it a shot.

SPOILERS: 9999 = 3^2 * 11 * 101, so first subtract out the multiples of 3 (3333 of them), the multiples of 11 (909 of them), the multiples of 101 (99 of them). Note that we've now double-subtracted multiples of 33 (303 of them), multiples of 303 (33 of them), multiples of 1111 (9 of them) so add these back. Finally subtract 1 to not count 9999 itself.

phi(9999) = 9999 - 3333 - 909 - 101 + 33 + 303 + 9 - 1 = 6000

I guess my point is that the purpose of these problems is not to separate out people who know specific tricks from people who don't—its to separate out people who can reason their way through difficult mathematical problems and people who can't.

[chongli]

The difference for you is that you're doing it as a fun exercise. With contest math, you're drilling these formulas and tricks so you can reproduce them quickly on a timed exam. If you know both of the facts listed in the essay then you can knock off this question in a minute or two.

Trying to come up with everything from scratch could take a lot longer and be very frustrating when you've got other problems waiting for you to solve.

[Jensson]

> Trying to come up with everything from scratch could take a lot longer and be very frustrating

If that is frustrating instead of thrilling to you then you probably shouldn't do these competitions.

[gowld]

The problem (and linked solution is here)

https://artofproblemsolving.com/wiki/index.php/2022_AIME_I_P...

The totient formula isn't the hard part of the problem.

The test has a very short time limit (for the difficulty of the problems), and has many gruelingly complicated problems,so if you dont have the formulas down cold, you'll burn out during the contest.

Of course, if you don't care about silly speed-mathing contests, you can enjot the problems at a leisurely pace.

[junar]

Agree, and to add a bit more context:

* The contest has 15 problems and a time limit of 3 hours, giving only an average of 12 minutes per problem.

* The average score is 4.83/15, from the official statistics [1].

* The statistics noted that only 5.17% of test takers answered this problem correctly, making it the second-hardest problem out of the 15 on the exam.

[1] "AIME 02/08/2022" https://amc-reg.maa.org/reports/generalreports.aspx

[lupire]

What's especially fascinating is that the core of the problem is a generalization of the totient computation, so understanding the inclusion-exclusion construction of totient is very helpful to the problem, while simply memorizing the formula is a misdirection.

OP missing this point shows that he really was doing this for all the wrong reasons. He should have done FIRST or science bowl instead.

[lupire]

More direct calculation:

For every distinct prime factor p (so, of 9 is a factor, use 3 not 9), only (p-1)/p of the natural numbers ≤ n are relatively prime to it. Pime. This overcpunts nothing, since prime factors are relatively prime to each other. (Proving this requires some analysis of remaimders / modular arithmetic. But working an example shows the pattern).

This gives a formula, phi(n = Sum (p_i ^ e^i)) = n • Product ((p_i -1)/p))

This also shows how OP (and maybe the coach) missed the point of math team.