Stay ahead of learning milestones! Enroll in a class over the summer!

G
Topic
First Poster
Last Poster
k a April Highlights and 2025 AoPS Online Class Information
jlacosta   0
Apr 2, 2025
Spring is in full swing and summer is right around the corner, what are your plans? At AoPS Online our schedule has new classes starting now through July, so be sure to keep your skills sharp and be prepared for the Fall school year! Check out the schedule of upcoming classes below.

WOOT early bird pricing is in effect, don’t miss out! If you took MathWOOT Level 2 last year, no worries, it is all new problems this year! Our Worldwide Online Olympiad Training program is for high school level competitors. AoPS designed these courses to help our top students get the deep focus they need to succeed in their specific competition goals. Check out the details at this link for all our WOOT programs in math, computer science, chemistry, and physics.

Looking for summer camps in math and language arts? Be sure to check out the video-based summer camps offered at the Virtual Campus that are 2- to 4-weeks in duration. There are middle and high school competition math camps as well as Math Beasts camps that review key topics coupled with fun explorations covering areas such as graph theory (Math Beasts Camp 6), cryptography (Math Beasts Camp 7-8), and topology (Math Beasts Camp 8-9)!

Be sure to mark your calendars for the following events:
[list][*]April 3rd (Webinar), 4pm PT/7:00pm ET, Learning with AoPS: Perspectives from a Parent, Math Camp Instructor, and University Professor
[*]April 8th (Math Jam), 4:30pm PT/7:30pm ET, 2025 MATHCOUNTS State Discussion
April 9th (Webinar), 4:00pm PT/7:00pm ET, Learn about Video-based Summer Camps at the Virtual Campus
[*]April 10th (Math Jam), 4:30pm PT/7:30pm ET, 2025 MathILy and MathILy-Er Math Jam: Multibackwards Numbers
[*]April 22nd (Webinar), 4:00pm PT/7:00pm ET, Competitive Programming at AoPS (USACO).[/list]
Our full course list for upcoming classes is below:
All classes run 7:30pm-8:45pm ET/4:30pm - 5:45pm PT unless otherwise noted.

Introductory: Grades 5-10

Prealgebra 1 Self-Paced

Prealgebra 1
Sunday, Apr 13 - Aug 10
Tuesday, May 13 - Aug 26
Thursday, May 29 - Sep 11
Sunday, Jun 15 - Oct 12
Monday, Jun 30 - Oct 20
Wednesday, Jul 16 - Oct 29

Prealgebra 2 Self-Paced

Prealgebra 2
Sunday, Apr 13 - Aug 10
Wednesday, May 7 - Aug 20
Monday, Jun 2 - Sep 22
Sunday, Jun 29 - Oct 26
Friday, Jul 25 - Nov 21

Introduction to Algebra A Self-Paced

Introduction to Algebra A
Monday, Apr 7 - Jul 28
Sunday, May 11 - Sep 14 (1:00 - 2:30 pm ET/10:00 - 11:30 am PT)
Wednesday, May 14 - Aug 27
Friday, May 30 - Sep 26
Monday, Jun 2 - Sep 22
Sunday, Jun 15 - Oct 12
Thursday, Jun 26 - Oct 9
Tuesday, Jul 15 - Oct 28

Introduction to Counting & Probability Self-Paced

Introduction to Counting & Probability
Wednesday, Apr 16 - Jul 2
Thursday, May 15 - Jul 31
Sunday, Jun 1 - Aug 24
Thursday, Jun 12 - Aug 28
Wednesday, Jul 9 - Sep 24
Sunday, Jul 27 - Oct 19

Introduction to Number Theory
Thursday, Apr 17 - Jul 3
Friday, May 9 - Aug 1
Wednesday, May 21 - Aug 6
Monday, Jun 9 - Aug 25
Sunday, Jun 15 - Sep 14
Tuesday, Jul 15 - Sep 30

Introduction to Algebra B Self-Paced

Introduction to Algebra B
Wednesday, Apr 16 - Jul 30
Tuesday, May 6 - Aug 19
Wednesday, Jun 4 - Sep 17
Sunday, Jun 22 - Oct 19
Friday, Jul 18 - Nov 14

Introduction to Geometry
Wednesday, Apr 23 - Oct 1
Sunday, May 11 - Nov 9
Tuesday, May 20 - Oct 28
Monday, Jun 16 - Dec 8
Friday, Jun 20 - Jan 9
Sunday, Jun 29 - Jan 11
Monday, Jul 14 - Jan 19

Intermediate: Grades 8-12

Intermediate Algebra
Monday, Apr 21 - Oct 13
Sunday, Jun 1 - Nov 23
Tuesday, Jun 10 - Nov 18
Wednesday, Jun 25 - Dec 10
Sunday, Jul 13 - Jan 18
Thursday, Jul 24 - Jan 22

Intermediate Counting & Probability
Wednesday, May 21 - Sep 17
Sunday, Jun 22 - Nov 2

Intermediate Number Theory
Friday, Apr 11 - Jun 27
Sunday, Jun 1 - Aug 24
Wednesday, Jun 18 - Sep 3

Precalculus
Wednesday, Apr 9 - Sep 3
Friday, May 16 - Oct 24
Sunday, Jun 1 - Nov 9
Monday, Jun 30 - Dec 8

Advanced: Grades 9-12

Olympiad Geometry
Tuesday, Jun 10 - Aug 26

Calculus
Tuesday, May 27 - Nov 11
Wednesday, Jun 25 - Dec 17

Group Theory
Thursday, Jun 12 - Sep 11

Contest Preparation: Grades 6-12

MATHCOUNTS/AMC 8 Basics
Wednesday, Apr 16 - Jul 2
Friday, May 23 - Aug 15
Monday, Jun 2 - Aug 18
Thursday, Jun 12 - Aug 28
Sunday, Jun 22 - Sep 21
Tues & Thurs, Jul 8 - Aug 14 (meets twice a week!)

MATHCOUNTS/AMC 8 Advanced
Friday, Apr 11 - Jun 27
Sunday, May 11 - Aug 10
Tuesday, May 27 - Aug 12
Wednesday, Jun 11 - Aug 27
Sunday, Jun 22 - Sep 21
Tues & Thurs, Jul 8 - Aug 14 (meets twice a week!)

AMC 10 Problem Series
Friday, May 9 - Aug 1
Sunday, Jun 1 - Aug 24
Thursday, Jun 12 - Aug 28
Tuesday, Jun 17 - Sep 2
Sunday, Jun 22 - Sep 21 (1:00 - 2:30 pm ET/10:00 - 11:30 am PT)
Monday, Jun 23 - Sep 15
Tues & Thurs, Jul 8 - Aug 14 (meets twice a week!)

AMC 10 Final Fives
Sunday, May 11 - Jun 8
Tuesday, May 27 - Jun 17
Monday, Jun 30 - Jul 21

AMC 12 Problem Series
Tuesday, May 27 - Aug 12
Thursday, Jun 12 - Aug 28
Sunday, Jun 22 - Sep 21
Wednesday, Aug 6 - Oct 22

AMC 12 Final Fives
Sunday, May 18 - Jun 15

F=ma Problem Series
Wednesday, Jun 11 - Aug 27

WOOT Programs
Visit the pages linked for full schedule details for each of these programs!


MathWOOT Level 1
MathWOOT Level 2
ChemWOOT
CodeWOOT
PhysicsWOOT

Programming

Introduction to Programming with Python
Thursday, May 22 - Aug 7
Sunday, Jun 15 - Sep 14 (1:00 - 2:30 pm ET/10:00 - 11:30 am PT)
Tuesday, Jun 17 - Sep 2
Monday, Jun 30 - Sep 22

Intermediate Programming with Python
Sunday, Jun 1 - Aug 24
Monday, Jun 30 - Sep 22

USACO Bronze Problem Series
Tuesday, May 13 - Jul 29
Sunday, Jun 22 - Sep 1

Physics

Introduction to Physics
Wednesday, May 21 - Aug 6
Sunday, Jun 15 - Sep 14
Monday, Jun 23 - Sep 15

Physics 1: Mechanics
Thursday, May 22 - Oct 30
Monday, Jun 23 - Dec 15

Relativity
Sat & Sun, Apr 26 - Apr 27 (4:00 - 7:00 pm ET/1:00 - 4:00pm PT)
Mon, Tue, Wed & Thurs, Jun 23 - Jun 26 (meets every day of the week!)
0 replies
jlacosta
Apr 2, 2025
0 replies
k i Peer-to-Peer Programs Forum
jwelsh   157
N Dec 11, 2023 by cw357
Many of our AoPS Community members share their knowledge with their peers in a variety of ways, ranging from creating mock contests to creating real contests to writing handouts to hosting sessions as part of our partnership with schoolhouse.world.

To facilitate students in these efforts, we have created a new Peer-to-Peer Programs forum. With the creation of this forum, we are starting a new process for those of you who want to advertise your efforts. These advertisements and ensuing discussions have been cluttering up some of the forums that were meant for other purposes, so we’re gathering these topics in one place. This also allows students to find new peer-to-peer learning opportunities without having to poke around all the other forums.

To announce your program, or to invite others to work with you on it, here’s what to do:

1) Post a new topic in the Peer-to-Peer Programs forum. This will be the discussion thread for your program.

2) Post a single brief post in this thread that links the discussion thread of your program in the Peer-to-Peer Programs forum.

Please note that we’ll move or delete any future advertisement posts that are outside the Peer-to-Peer Programs forum, as well as any posts in this topic that are not brief announcements of new opportunities. In particular, this topic should not be used to discuss specific programs; those discussions should occur in topics in the Peer-to-Peer Programs forum.

Your post in this thread should have what you're sharing (class, session, tutoring, handout, math or coding game/other program) and a link to the thread in the Peer-to-Peer Programs forum, which should have more information (like where to find what you're sharing).
157 replies
jwelsh
Mar 15, 2021
cw357
Dec 11, 2023
k i C&P posting recs by mods
v_Enhance   0
Jun 12, 2020
The purpose of this post is to lay out a few suggestions about what kind of posts work well for the C&P forum. Except in a few cases these are mostly meant to be "suggestions based on historical trends" rather than firm hard rules; we may eventually replace this with an actual list of firm rules but that requires admin approval :) That said, if you post something in the "discouraged" category, you should not be totally surprised if it gets locked; they are discouraged exactly because past experience shows they tend to go badly.
-----------------------------
1. Program discussion: Allowed
If you have questions about specific camps or programs (e.g. which classes are good at X camp?), these questions fit well here. Many camps/programs have specific sub-forums too but we understand a lot of them are not active.
-----------------------------
2. Results discussion: Allowed
You can make threads about e.g. how you did on contests (including AMC), though on AMC day when there is a lot of discussion. Moderators and administrators may do a lot of thread-merging / forum-wrangling to keep things in one place.
-----------------------------
3. Reposting solutions or questions to past AMC/AIME/USAMO problems: Allowed
This forum contains a post for nearly every problem from AMC8, AMC10, AMC12, AIME, USAJMO, USAMO (and these links give you an index of all these posts). It is always permitted to post a full solution to any problem in its own thread (linked above), regardless of how old the problem is, and even if this solution is similar to one that has already been posted. We encourage this type of posting because it is helpful for the user to explain their solution in full to an audience, and for future users who want to see multiple approaches to a problem or even just the frequency distribution of common approaches. We do ask for some explanation; if you just post "the answer is (B); ez" then you are not adding anything useful.

You are also encouraged to post questions about a specific problem in the specific thread for that problem, or about previous user's solutions. It's almost always better to use the existing thread than to start a new one, to keep all the discussion in one place easily searchable for future visitors.
-----------------------------
4. Advice posts: Allowed, but read below first
You can use this forum to ask for advice about how to prepare for math competitions in general. But you should be aware that this question has been asked many many times. Before making a post, you are encouraged to look at the following:
[list]
[*] Stop looking for the right training: A generic post about advice that keeps getting stickied :)
[*] There is an enormous list of links on the Wiki of books / problems / etc for all levels.
[/list]
When you do post, we really encourage you to be as specific as possible in your question. Tell us about your background, what you've tried already, etc.

Actually, the absolute best way to get a helpful response is to take a few examples of problems that you tried to solve but couldn't, and explain what you tried on them / why you couldn't solve them. Here is a great example of a specific question.
-----------------------------
5. Publicity: use P2P forum instead
See https://artofproblemsolving.com/community/c5h2489297_peertopeer_programs_forum.
Some exceptions have been allowed in the past, but these require approval from administrators. (I am not totally sure what the criteria is. I am not an administrator.)
-----------------------------
6. Mock contests: use Mock Contests forum instead
Mock contests should be posted in the dedicated forum instead:
https://artofproblemsolving.com/community/c594864_aops_mock_contests
-----------------------------
7. AMC procedural questions: suggest to contact the AMC HQ instead
If you have a question like "how do I submit a change of venue form for the AIME" or "why is my name not on the qualifiers list even though I have a 300 index", you would be better off calling or emailing the AMC program to ask, they are the ones who can help you :)
-----------------------------
8. Discussion of random math problems: suggest to use MSM/HSM/HSO instead
If you are discussing a specific math problem that isn't from the AMC/AIME/USAMO, it's better to post these in Middle School Math, High School Math, High School Olympiads instead.
-----------------------------
9. Politics: suggest to use Round Table instead
There are important conversations to be had about things like gender diversity in math contests, etc., for sure. However, from experience we think that C&P is historically not a good place to have these conversations, as they go off the rails very quickly. We encourage you to use the Round Table instead, where it is much more clear that all posts need to be serious.
-----------------------------
10. MAA complaints: discouraged
We don't want to pretend that the MAA is perfect or that we agree with everything they do. However, we chose to discourage this sort of behavior because in practice most of the comments we see are not useful and some are frankly offensive.
[list] [*] If you just want to blow off steam, do it on your blog instead.
[*] When you have criticism, it should be reasoned, well-thought and constructive. What we mean by this is, for example, when the AOIME was announced, there was great outrage about potential cheating. Well, do you really think that this is something the organizers didn't think about too? Simply posting that "people will cheat and steal my USAMOO qualification, the MAA are idiots!" is not helpful as it is not bringing any new information to the table.
[*] Even if you do have reasoned, well-thought, constructive criticism, we think it is actually better to email it the MAA instead, rather than post it here. Experience shows that even polite, well-meaning suggestions posted in C&P are often derailed by less mature users who insist on complaining about everything.
[/list]
-----------------------------
11. Memes and joke posts: discouraged
It's fine to make jokes or lighthearted posts every so often. But it should be done with discretion. Ideally, jokes should be done within a longer post that has other content. For example, in my response to one user's question about olympiad combinatorics, I used a silly picture of Sogiita Gunha, but it was done within a context of a much longer post where it was meant to actually make a point.

On the other hand, there are many threads which consist largely of posts whose only content is an attached meme with the word "MAA" in it. When done in excess like this, the jokes reflect poorly on the community, so we explicitly discourage them.
-----------------------------
12. Questions that no one can answer: discouraged
Examples of this: "will MIT ask for AOIME scores?", "what will the AIME 2021 cutoffs be (asked in 2020)", etc. Basically, if you ask a question on this forum, it's better if the question is something that a user can plausibly answer :)
-----------------------------
13. Blind speculation: discouraged
Along these lines, if you do see a question that you don't have an answer to, we discourage "blindly guessing" as it leads to spreading of baseless rumors. For example, if you see some user posting "why are there fewer qualifiers than usual this year?", you should not reply "the MAA must have been worried about online cheating so they took fewer people!!". Was sich überhaupt sagen lässt, lässt sich klar sagen; und wovon man nicht reden kann, darüber muss man schweigen.
-----------------------------
14. Discussion of cheating: strongly discouraged
If you have evidence or reasonable suspicion of cheating, please report this to your Competition Manager or to the AMC HQ; these forums cannot help you.
Otherwise, please avoid public discussion of cheating. That is: no discussion of methods of cheating, no speculation about how cheating affects cutoffs, and so on --- it is not helpful to anyone, and it creates a sour atmosphere. A longer explanation is given in Seriously, please stop discussing how to cheat.
-----------------------------
15. Cutoff jokes: never allowed
Whenever the cutoffs for any major contest are released, it is very obvious when they are official. In the past, this has been achieved by the numbers being posted on the official AMC website (here) or through a post from the AMCDirector account.

You must never post fake cutoffs, even as a joke. You should also refrain from posting cutoffs that you've heard of via email, etc., because it is better to wait for the obvious official announcement. A longer explanation is given in A Treatise on Cutoff Trolling.
-----------------------------
16. Meanness: never allowed
Being mean is worse than being immature and unproductive. If another user does something which you think is inappropriate, use the Report button to bring the post to moderator attention, or if you really must reply, do so in a way that is tactful and constructive rather than inflammatory.
-----------------------------

Finally, we remind you all to sit back and enjoy the problems. :D

-----------------------------
(EDIT 2024-09-13: AoPS has asked to me to add the following item.)

Advertising paid program or service: never allowed

Per the AoPS Terms of Service (rule 5h), general advertisements are not allowed.

While we do allow advertisements of official contests (at the MAA and MATHCOUNTS level) and those run by college students with at least one successful year, any and all advertisements of a paid service or program is not allowed and will be deleted.
0 replies
v_Enhance
Jun 12, 2020
0 replies
k i Stop looking for the "right" training
v_Enhance   50
N Oct 16, 2017 by blawho12
Source: Contest advice
EDIT 2019-02-01: https://blog.evanchen.cc/2019/01/31/math-contest-platitudes-v3/ is the updated version of this.

EDIT 2021-06-09: see also https://web.evanchen.cc/faq-contest.html.

Original 2013 post
50 replies
v_Enhance
Feb 15, 2013
blawho12
Oct 16, 2017
No More than √㏑x㏑㏑x Digits
EthanWYX2009   3
N 36 minutes ago by MathisWow
Source: 2024 April 谜之竞赛-3
Let $f(x)\in\mathbb Z[x]$ have positive integer leading coefficient. Show that there exists infinte positive integer $x,$ such that the number of digit that doesn'r equal to $9$ is no more than $\mathcal O(\sqrt{\ln x\ln\ln x}).$

Created by Chunji Wang, Zhenyu Dong
3 replies
EthanWYX2009
Mar 24, 2025
MathisWow
36 minutes ago
Sum of points' powers
Suntafayato   2
N an hour ago by fadhool
Given 2 circles $\omega_1, \omega_2$, find the locus of all points $P$ such that $\mathcal{P}ow(P, \omega_1) + \mathcal{P}ow(P, \omega_2) = 0$ (i.e: sum of powers of point $P$ with respect to the two circles $\omega_1, \omega_2$ is zero).
2 replies
Suntafayato
Mar 24, 2020
fadhool
an hour ago
IMO ShortList 2001, number theory problem 3
orl   10
N an hour ago by OronSH
Source: IMO ShortList 2001, number theory problem 3
Let $ a_1 = 11^{11}, \, a_2 = 12^{12}, \, a_3 = 13^{13}$, and $ a_n = |a_{n - 1} - a_{n - 2}| + |a_{n - 2} - a_{n - 3}|, n \geq 4.$ Determine $ a_{14^{14}}$.
10 replies
orl
Sep 30, 2004
OronSH
an hour ago
Existence of a solution of a diophantine equation
syk0526   4
N an hour ago by ihategeo_1969
Source: North Korea Team Selection Test 2013 #6
Show that $ x^3 + x+ a^2 = y^2 $ has at least one pair of positive integer solution $ (x,y) $ for each positive integer $ a $.
4 replies
syk0526
May 17, 2014
ihategeo_1969
an hour ago
Please support!
warriorsin7   0
2 hours ago
warriorsin7
2 hours ago
0 replies
9 Did I make the right choice?
Martin2001   27
N 4 hours ago by ninjaforce
If you were in 8th grade, would you rather go to MOP or mc nats? I chose to study the former more and got in so was wondering if that was valid given that I'll never make mc nats.
27 replies
Martin2001
Apr 29, 2025
ninjaforce
4 hours ago
I'm trying to find a good math comp...
ysn613   5
N 5 hours ago by MathPerson12321
Okay, so I'm in sixth grade. I have been doing AMC 8 since fourth grade, but not anything else. I was wondering what other "good" math competitions there are that I am the right age for.

I'm also looking for prep tips for math competitions, because when I (mock)ace 2000-2010 AMC 8 and then get a 19 on the real thing when I was definitely able to solve everything, I feel like what I'm doing isn't really working. Anyone got any ideas? Thanks!
5 replies
ysn613
Yesterday at 4:12 PM
MathPerson12321
5 hours ago
2025 Math and AI 4 Girls Competition: Win Up To $1,000!!!
audio-on   64
N Today at 2:59 PM by WhitePhoenix
Join the 2025 Math and AI 4 Girls Competition for a chance to win up to $1,000!

Hey Everyone, I'm pleased to announce the dates for the 2025 MA4G Competition are set!
Applications will open on March 22nd, 2025, and they will close on April 26th, 2025 (@ 11:59pm PST).

Applicants will have one month to fill out an application with prizes for the top 50 contestants & cash prizes for the top 20 contestants (including $1,000 for the winner!). More details below!

Eligibility:
The competition is free to enter, and open to middle school female students living in the US (5th-8th grade).
Award recipients are selected based on their aptitude, activities and aspirations in STEM.

Event dates:
Applications will open on March 22nd, 2025, and they will close on April 26th, 2025 (by 11:59pm PST)
Winners will be announced on June 28, 2025 during an online award ceremony.

Application requirements:
Complete a 12 question problem set on math and computer science/AI related topics
Write 2 short essays

Prizes:
1st place: $1,000 Cash prize
2nd place: $500 Cash prize
3rd place: $300 Cash prize
4th-10th: $100 Cash prize each
11th-20th: $50 Cash prize each
Top 50 contestants: Over $50 worth of gadgets and stationary


Many thanks to our current and past sponsors and partners: Hudson River Trading, MATHCOUNTS, Hewlett Packard Enterprise, Automation Anywhere, JP Morgan Chase, D.E. Shaw, and AI4ALL.

Math and AI 4 Girls is a nonprofit organization aiming to encourage young girls to develop an interest in math and AI by taking part in STEM competitions and activities at an early age. The organization will be hosting an inaugural Math and AI 4 Girls competition to identify talent and encourage long-term planning of academic and career goals in STEM.

Contact:
mathandAI4girls@yahoo.com

For more information on the competition:
https://www.mathandai4girls.org/math-and-ai-4-girls-competition

More information on how to register will be posted on the website. If you have any questions, please ask here!


64 replies
audio-on
Jan 26, 2025
WhitePhoenix
Today at 2:59 PM
MOP Emails Out! (not clickbait)
Mathandski   101
N Today at 1:01 PM by pingpongmerrily
What an emotional roller coaster the past 34 days have been.

Congrats to all that qualified!
101 replies
Mathandski
Apr 22, 2025
pingpongmerrily
Today at 1:01 PM
How many approaches you got? (A lot)
IAmTheHazard   86
N Today at 8:27 AM by User141208
Source: USAMO 2023/2
Let $\mathbb{R}^+$ be the set of positive real numbers. Find all functions $f \colon \mathbb{R}^+ \to \mathbb{R}^+$ such that, for all $x,y \in \mathbb{R}^+$,
$$f(xy+f(x))=xf(y)+2.$$
86 replies
IAmTheHazard
Mar 23, 2023
User141208
Today at 8:27 AM
Berkeley mini Math Tournament Online 2025 - June 7
BerkeleyMathTournament   0
Today at 7:38 AM
Berkeley mini Math Tournament is a math competition hosted for middle school students once a year. Students compete in multiple rounds: individual round, team round, puzzle round, and relay round.

BmMT 2025 Online will be held on June 7th, and registration is OPEN! Registration is $8 per student. Our website https://berkeley.mt/events/bmmt-2025-online/ has more details about the event, past tests to practice with, and frequently asked questions. We look forward to building community and inspiring students as they explore the world of math!

3 out of 4 of the rounds are completed with a team, so it’s a great opportunity for students to work together. Beyond getting more comfortable with math and becoming better problem solvers, our team is preparing some fun post-competition activities!

Registration is open to students in grades 8 or below. You do not have to be local to the Bay Area or California to register for BmMT Online. Students may register as a team of 1, but it is beneficial to compete on a team of at least 3 due to our scoring guideline and for the experience.

We hope you consider attending, or if you are a parent or teacher, that you encourage your students to think about attending BmMT. Thank you, and once again find more details/register at our website,https://berkeley.mt.
0 replies
BerkeleyMathTournament
Today at 7:38 AM
0 replies
How to get good at comp math
fossasor   28
N Today at 6:27 AM by Konigsberg
I'm a rising ninth grader who wasn't in the school math league this year, and basically put aside comp math for a year. Unfortunately, that means that now that I'm in high school and having the epiphany about how important comp math actually is, and how much it would help my chances of getting involved in other math-related programs. In addition, I do enjoy math in general, and suspect that things like the AMCs are probably going to be some of the best practice I can get. What this all means is that I'm trying to go from mediocre to orz, 2 years after I probably should have started if I wanted to be any good.

So my question is: how do I get good at comp math?

This year, my scores on AMC 10 (and these are the highest I've ever gotten) were a 73.5 and an 82.5 (AMC 8 was 21/25, but that doesn't matter much). This is not good enough to qualify for AIME, and I probably need to raise my performance on each by at least 10 points. I've been decently good in the past at Number Theory, but I need to work on Geo and Combinatorics, and I'm trying to find the best resources to do that. My biggest flaw is probably not knowing many algorithms like Stars and Bars, and the path is clear here (learn them) but I'm still not sure which ones I need to know.

I'm aware that some of this advice is going to be something like "Practice 5 hours a day and start hardgrinding" or something along those lines. Unfortunately, I have other extracurriculars I need to balance, and for me, time is a limiting resource. My parents are somewhat frowning upon me doing a lot of comp math, which limits my time as well. I have neither the time nor motivation to do more than an hour a day, and in practice, I don't think I can be doing that consistently. As such, I would need to make that time count.

I know this is a very general question, and that aops is chock-full of detailed advice for math competitions. However, I'd appreciate it if anyone here could help me out, or show me the best resources I should use to get started. What mocks are any good, or what textbooks should I use? Where do I get the best practice with the shortest time? Is there some place I can find a list of useful formulas that have appeared in math comps before?

All advice is welcome!

28 replies
fossasor
Apr 10, 2025
Konigsberg
Today at 6:27 AM
MasterScholar North Carolina Math Camp
Ruegerbyrd   17
N Today at 4:51 AM by fake123
Is this legit? Worth the cost ($6500)? Program Fees Cover: Tuition, course materials, field trip costs, and housing and meals at Saint Mary's School.

"Themes:

1. From Number Theory and Special Relativity to Game Theory
2. Applications to Economics

Subjects Covered:

Number Theory - Group Theory - RSA Encryption - Game Theory - Estimating Pi - Complex Numbers - Quaternions - Topology of Surfaces - Introduction to Differential Geometry - Collective Decision Making - Survey of Calculus - Applications to Economics - Statistics and the Central Limit Theorem - Special Relativity"

website(?): https://www.teenlife.com/l/summer/masterscholar-north-carolina-math-camp/
17 replies
Ruegerbyrd
Yesterday at 3:15 AM
fake123
Today at 4:51 AM
Segment Product
worthawholebean   25
N Today at 4:37 AM by deduck
Source: AIME 2009II Problem 13
Let $ A$ and $ B$ be the endpoints of a semicircular arc of radius $ 2$. The arc is divided into seven congruent arcs by six equally spaced points $ C_1,C_2,\ldots,C_6$. All chords of the form $ \overline{AC_i}$ or $ \overline{BC_i}$ are drawn. Let $ n$ be the product of the lengths of these twelve chords. Find the remainder when $ n$ is divided by $ 1000$.
25 replies
worthawholebean
Apr 2, 2009
deduck
Today at 4:37 AM
Unique NT Function
IndoMathXdZ   33
N Apr 10, 2025 by N3bula
Source: IMO SL 2018 N6
Let $f : \{ 1, 2, 3, \dots \} \to \{ 2, 3, \dots \}$ be a function such that $f(m + n) | f(m) + f(n) $ for all pairs $m,n$ of positive integers. Prove that there exists a positive integer $c > 1$ which divides all values of $f$.
33 replies
IndoMathXdZ
Jul 17, 2019
N3bula
Apr 10, 2025
Unique NT Function
G H J
G H BBookmark kLocked kLocked NReply
Source: IMO SL 2018 N6
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
IndoMathXdZ
691 posts
#1 • 3 Y
Y by megarnie, Kingsbane2139, Adventure10
Let $f : \{ 1, 2, 3, \dots \} \to \{ 2, 3, \dots \}$ be a function such that $f(m + n) | f(m) + f(n) $ for all pairs $m,n$ of positive integers. Prove that there exists a positive integer $c > 1$ which divides all values of $f$.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
plagueis
157 posts
#2 • 6 Y
Y by Aryan-23, IMUKAT, megarnie, Adventure10, MS_Kekas, khina
Proposed by Ariel García, Mexico
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
tastymath75025
3223 posts
#3 • 10 Y
Y by cjquines0, smurfcc, mijail, Mop2018, MiraclesINmaths, Zyz1010, hakN, Adventure10, bhan2025, pokpokben
Great problem :) We’ll split into two cases.
Case 1: $f$ is unbounded. In that case, let $n_1<n_2<...$ be an infinite sequence of integers such that $f(n_i) > f(n_i-1), f(n_i-2), \dots, f(1)$ for each $i$.

For any positive integer $k$ take large $i$ so that $f(n_i-k) \mid f(n_i-k-1) + f(1)$. Note that $f(n_i)\mid  f(n_i-k) + f(k) < 2f(n_i)\implies f(n_i-k)=f(n_i)-f(k)$ and similarly $f(n_i-k-1) = f(n_i) - f(k+1)$. Therefore we have that $f(n_i) - f(k) \mid f(n_i)-f(k+1) + f(1)$, hence $f(n_i)-f(k) \mid f(1)+f(k)-f(k+1)$. As $i$ increases $f(n_i)-f(k)$ gets arbitrarily large, implying $f(k+1)=f(k)+f(1)$ for all $k$, so $f(n)=nf(1)$ and $f(1)>1$ divides each $f(n)$, and we’re done.

Case 2: $f$ is bounded by some $M$. For any $p$ and $n>m$, note that $p\mid f(n),f(m)$ implies $p\mid f(n-m)$ because $f(n)\mid f(m)+f(n-m)$. Consider primes $p$ that divide infinitely many $f(n)$ and let $S$ be the set of all such primes. Let $u$ be the smallest positive integer with $p\mid f(u)$; it follows that for any $n$ with $p\mid f(n)$, we have $p\mid f(n-u), f(n-2u), \dots, f(n \pmod u)$, which contradicts the minimality of $u$ unless $u\mid n$. Notice this allows us to associate each prime $p$ with an “order” $u_p=u$ such that $p\mid f(n)\implies u_p\mid n$. Suppose for contradiction that $u_p\neq 1$ for each $p\in S$.

Now clearly $S$ is finite, and if $m_k= k\text{lcm}_{p\in S} u_p + 1$, then $u_p\nmid m_k$ for each $p\in S$ and each $k$, so no $p\in S$ can divide $f(m_k)$. But the sequence $f(m_1), f(m_2), \dots$ is bounded and infinite, so it takes some value greater than one infinitely many times, meaning there is a prime $q$ which divides infinitely many of the $f(m_i)$. But this would imply $q\in S$, contradiction. Therefore it follows that some $p\in S$ has $u_p=1$. But now by definition there are arbitrarily large $n$ with $p\mid f(n)$, and $p\mid f(n), f(1)\implies p\mid f(n-1)$, so this implies $p\mid f(n)$ for all $n$, and we’re done.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Kayak
1298 posts
#4 • 3 Y
Y by AlastorMoody, aops29, Adventure10
This was Indian TST D2 P3. Here's my solution to this at TST:

Case-1 $\text{Im}(f)$ is bounded.
Proof: Call a prime $p$ to be Soumil if there's infinitely many integers $i$ such that $p|f(i)$. For a soumil prime $p$, define it's lavil to be the set $T_p : \overset{\text{def}}{=} \{ i \in \mathbb{N} : p | f(i) \}$. Note that if $a, b \in T_p$ then $|a-b| \in T_p$, thus (say by Euclidean algorithm), there's an integer $g_p \in \mathbb{N}$ such that $T_p = g_p \mathbb{N}$.

Let $S$ be the set of all soumil primes. Now I claim atleast one of $g_p$ where $p \in S$ will be equal to $1$ (which would imply the proof). Assume not. Then define $S : \overset{\text{def}}{=} \prod_{p \in S} g_p$, and consider the set $Q = \{ Sm+1 \}_{m \in \mathbb{N}}$ where $m$ varies over integer. Note that by definition of soumil primes, the union of all lavil sets contains all but finitely many integers. But the elements of $Q$ don't belong to any lavil set, which is a contradiction so done. $\square$
Case-2 $\text{Im}(f)$ is unbounded.

In this case I prove $f(m) = f(1)m$.

Lemma: (Growth of $f$) We say the interval $[i, j]$ is soumil $f(n+1)-f(n) = f(1)$ for each $n \in [i, j]$. For each positive integer $m$, there're infinitely many soumil intervals of the form $[mk, m(k+1)-1]$.

Proof

So pick any integer $j$, and an integer $M > \max(f(1), f(2), \cdots, f(j))+100$, and a soumil interval $[n, 2^M+n]$. Then $f(n+M+j) = f(n)+(M+j)f(1) > M + jf(1) > \max(jf(1), f(j))$, and thus \begin{align*}
f(n+M+j) & | f(n+M) + f(j) = f(n) + Mf(1)+f(j) \\
& | f(n+M+j-1) + f(1) = f(n) + (M+j)f(1) = f(n) + Mf(1) + jf(1)
\end{align*}so subtracting them gives $f(n+M+j) | f(j) - jf(1)$ which gives the conclusion $\square$.
This post has been edited 4 times. Last edited by Kayak, Jul 17, 2019, 9:22 PM
Reason: typoes
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
juckter
323 posts
#5 • 32 Y
Y by Wizard_32, Kayak, 62861, danepale, Pathological, djmathman, Nothing000, Ti-Ci, p_square, AlastorMoody, aops29, rashah76, RAMUGAUSS, amar_04, Aryan-23, khina, SnowPanda, Supercali, starchan, tigerzhang, L567, megarnie, OlympusHero, MiraclesINmaths, CyclicISLscelesTrapezoid, ZHEKSHEN, IMUKAT, Mz_T, Kingsbane2139, sabkx, Adventure10, Deadline
This was proposed by me :)

I hope you all enjoyed it/will enjoy it!
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
v_Enhance
6877 posts
#6 • 11 Y
Y by v4913, Kobayashi, SerdarBozdag, Anshul_singh, HamstPan38825, ZHEKSHEN, sabkx, Nuterrow, Adventure10, Assassino9931, khina
The following solution splices together ideas from both of the official solutions.

Claim: Let $d_n = \gcd(f(n), f(1))$. Then $d_{n+1} \mid d_n$ for all $n$.
Proof. Immediate from $f(n+1) \mid f(n) + f(1)$. $\blacksquare$

Hence, we will assume henceforth that $d_n = \gcd(f(n), f(1)) = 1$ for all $n \ge C$, for some constant $C$ (otherwise $\min_n d_n$ is the required constant).

Claim: If $\gcd(a,b) = 1$, then $\gcd(f(a), f(b)) \mid f(1)$. In particular, $\gcd(f(a), f(b)) = 1$ if $\min(a,b) \ge C$.
Proof. This follows by Euclidean algorithm: if $a > b$ then $f(a) \mid f(a-b) + f(b)$, so $\gcd( f(a), f(b) ) \mid \gcd( f(a-b), f(b) )$. $\blacksquare$

The second claim already implies $f$ is unbounded: if $f$ takes only values in $\{2, \dots, L\}$ then taking any $L+1$ primes larger than $C$ gives a contradiction.

Main induction: Assume $f$ is unbounded. Let $X$ be a local maximum, meaning $Y = f(X) \ge \max \left\{ f(1), \dots, f(X-1) \right\}$. We will assume $X$ and $Y$ are large enough such that $X > C + C f(1)$, $Y > 2 f(1) f(C)$. Then: \begin{align*} 	Y = f(X) \mid f(X-C) + f(C) &\implies f(X-C) = Y - f(C) \\ 	Y-f(C) = f(X-C) \mid f(X-2C) + f(C) &\implies f(X-2C) = Y - 2f(C) \\ 	Y-2f(C) = f(X-2C) \mid f(X-3C) + f(C) &\implies f(X-3C) = Y - 3f(C) \\ 	&\vdotswithin{\implies} \\ 	&\implies f(X-f(1)C) = Y - f(1) f(C). \end{align*}However, all the right-hand sides are supposed to not be divisible by $f(1)$, yet we assumed $\gcd(f(C), f(1)) = 1$, contradiction.
This post has been edited 1 time. Last edited by v_Enhance, Nov 25, 2022, 4:13 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
MarkBcc168
1595 posts
#7 • 11 Y
Y by hyx, rashah76, Mathasocean, Aryan-23, Kanep, Kobayashi, Adventure10, Kingsbane2139, Mango247, sabkx, Deadline
Here is a short solution by Gems98.

First, we make the following observation.

Claim: If $d\mid f(m)$ and $d\mid f(n)$ then $d\mid f(m-n)$.

Proof: Obvious from the problem's condition.

We will consider two cases.
Case 1: $f$ is bounded.

Let $p_{1}$ be a prime number. By Dirichlet's theorem, there exists a sequence of prime numbers $p_{2}, p_{3}, \cdots, $ such that
$$p_{n+1} \equiv 1 \pmod{\prod_{i=1}^{n}p_{i}}$$By pigeonhole principle, there exists a increasing sequence $a_{1}, a_{2} ,\cdots$ such that
$$c = f(p_{a_{1}}) = f(p_{a_{2}}) = \cdots$$From $p_{a_{i+1}} \equiv 1 \pmod{p_{a_{i}}}$, we get $c \mid f(1)$ by applying the Claim repeatedly. Therefore, if $c \mid f(n)$ then $c \mid f(n-1)$.

Since the sequence $p_{a_{i}}$ is unbounded, we get $c \mid f(n)$ for every $n \in \mathbb{Z}^+$ which is the desired result.

Case 2: $f$ is unbounded.

We call the natural number $n$ $\textit{good}$ iff $f(n) > \max\{f(1), \cdots, f(n-1)\}$. Since $f$ is unbounded, there exist infinitely many $\textit{good}$ number.

It's easy to show that if $m$ is $\textit{good}$, then $f(m) = f(i) + f(m-i)$ for all $i \leq m-1$. Let $n$ be a positive integer and $m$ be a sufficiently large $\textit{good}$ number. From the condition, we get
\begin{align*}
    f(m-n+1) &\mid f(m-n)+f(1) \\
    f(m) - f(n-1) &\mid f(m) - f(n) + f(1) \\ 
    f(m) - f(n) &\mid f(n) - f(n-1) - f(1)
\end{align*}Since $m$ is sufficiently large, we get $f(n) - f(n-1) - f(1) = 0$ which implies that $f$ is linear.
Therefore, there exists positive integer $c = f(1) > 1$ such that $c\mid f(n)$ for all $n \in \mathbb{Z}^+$.
This post has been edited 1 time. Last edited by MarkBcc168, Jul 17, 2019, 2:42 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
mofumofu
179 posts
#8 • 7 Y
Y by test20, danepale, AlastorMoody, Kingsbane2139, Adventure10, Mango247, sabkx
While this problem is a really nice one, I would like to point out some similar (and difficult) problems that have appeared before, namely 2007 N5, IMO 2011, Iran 3rd round 2017, and with a different condition Romania TST 2016.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
juckter
323 posts
#9 • 3 Y
Y by starchan, Adventure10, Mango247
Yeah, there are some other pretty cool NT functional problems around. I definitely got reminded of some of those when I came up with this problem :)

I learned of the existence of the Romania TST problem because I heard this one was discarded from the shortlist due to it, which was a shame :( . Had I known that problem existed beforehand I may have not sent my problem to be considered for IMO.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
yayups
1614 posts
#10 • 3 Y
Y by Adventure10, Mango247, sabkx
We split into cases based on whether $f$ is bounded or not.

First, assume $f$ is unbounded. This means that there is an infinite sequence of \textit{peaks} $1=x_0<x_1<x_2<\cdots$ such that $f(x_n)>f(x)$ for all $x<x_n$. Note that $f(x_n)\mid f(x)+f(x_n-x)$ and $f(x)+f(x_n-x)<2f(x_n)$, so in fact $f(x_n)=f(x)+f(x_n-x)$. For any given $x$, we have for large enough $n$ that $f(x_n-x)\mid f(1)+f(x_n-x-1)$, so
\[f(x_n)-f(x)\mid f(1)+f(x_n)-f(x+1),\]so $f(x_n)-f(x)\mid f(1)+f(x)-f(x+1)$ for arbitrarily large $n$. We see that $f(x_n)$ can be arbitrarily large, so we must have $f(x+1)=f(x)+f(1)$, so $f(x)=xf(1)$. Thus, $f(1)\mid f(n)$ for all $n$.

Now suppose $f$ is bounded. Note that $f(n+1)\mid f(n)+f(1)$, so $\gcd(f(n+1),f(1))\mid\gcd(f(n),f(1))$. Thus,
\[\cdots\mid\gcd(f(3),f(1))\mid\gcd(f(2),f(1))\mid\gcd(f(1),f(1)),\]so either $\gcd(f(n),f(1))=1$ for large enough $n$, or $\gcd(f(n),f(1))>1$ for all $n$, in which case we're done. So WLOG, suppose that $\gcd(f(n),f(1))$ for all $n\ge N$.

We claim that $\gcd(f(x),f(xy+1))=1$ for $x\ge N$. To see this, note that
\[f(xy+1)\mid f(x)+f(x(y-1)+1)\implies\gcd(f(xy+1),f(x))\mid\gcd(f(x(y-1)+1),f(x)).\]Iterating this gives $\gcd(f(xy+1),f(x))\mid\gcd(f(1),f(x))=1$, as desired. Thus, any two terms in
\[f(N),f(N+1),f(N(N+1)+1),f(N(N+1)(N(N+1)+1)+1),\ldots\]are relatively prime, so in particular, any two terms are distinct. But this is an infinite sequence of $f(x)$ for distinct values of $x$, so $f$ is unbounded, which is the desired contradiction.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
mathaddiction
308 posts
#11 • 5 Y
Y by amar_04, jishu2003, a_n, Mango247, ihatemath123
This is the first shortlist #6 that I solve(This is also the few ones that I have attempted), and spend a lot of time (10+ hours), so I decided to post it on the thread.
Let $a_n=f(2^n)$ for all $n\geq 0$. We distinguish two cases:
$\underline{Case I:}$For all $n\geq 0$, $a_n$ has an odd prime factor
note that by taking $m=n=2^k$ we have
$$a_k|2a_{k-1}$$Hence any prime factors of $a_n$ must also be a prime factor of $a_i$ where $i$ is any positive integer less than $i$. Since $a_1$ has only finitely many prime factors, there exists a prime p such that $p|a_n$ for all positive integers $n$. We that $p|f(n)$ for all $n\in\mathbb N$.
Indeed, we proceed by backward induction to show that every integer in the interval $[2^k,2^{k+1}]$ has this property, indeed we have $p|f(2^{k+1})$. Now note that if $p|f(n)$ then since $p|f(1)$ together with
$$f(n)|f(n-1)+f(1)$$we have $p|f(n-1)$ and therefore we complete the inductive step and therefore we're done.
$\underline{Case II:}$There exists $k\in\mathbb N$ such that for all $N\geq k$ we have the fact that $a_n$ is a power of $2$.(We assume that $k$ is the minimal choice)
Using similar arguments as in case I we have that for every number $m$ there exists a number $k$ such that for all $N\geq k$ we have $f(m\cdot 2^k)$ is a power of 2.
Note that if $p|f(m)$ and $p|f(n)$, then we have $p|f(n-m)$ therefore $p|f(gcd(m,n))$ by Euclidean algorithm. That is
$$gcd(f(m),f(n))|f(gcd(m,n))(1)$$Let $q$ be the minimal number such that $a_q$ is even. We claim that if $v_2(n)<q$ then $f(n)$ is odd. Otherwise, suppose $v_2(n)=s$, by $(1)$ we have $$2|gcd(f(n),f(2^k))|f(gcd(f(n),f(2^k))=f(2^s)$$this contradicts the minimality of $q$
We further distinguish two cases
$\underline{Case IIa:}$$q\geq1$
We prove the following
$\underline{CLAIM 1.}$The sequence $\{a_n\}$ is unbounded
$\underline{Proof.}$Suppose $\{a_n\}<M$ for all $n$, then since
$$f(2^n+1)|f(2^n)+f(1)$$We have $f(2^n+1)\leq f(2^n)+f(1)\leq M+f(1)$ hence $f(2^n+1)$ is also bounded, therefore by pigeonhole principle there exists an infinite sequence of numbers $\{b_n\}$ such that
$$f(2^{2^{b_i}}+1)=f(2^{2^{b_j}}+1)$$for all $i,j\in\mathbb N$.Let this number be $c$, then since $(2^{2^{b_i}}+1,2^{2^{b_j}}+1)=1$, from $(1)$ we have
$c|f(1)$, using the same induction method as in Case I we have $c|f(n)$ for all positive integer $n$, contradiction.
$\underline{CLAIM 2.}$ Let $a$ be an integer, denote $v_2(n)$ by $m$, then
$$v_2(f(a))=v_2(f(2^m))$$$\underline{Proof.}$Suppose $a=2^mp$, and $v_2(f(a))=x$, $v_2(f(2^m))=y$
If $x>y$, then we prove by induction that $v_2(f(an+2^m))\leq y$ for all positive integers $n$
Indeed the base cases are trivial, suppose the case n holds, then
$$v_2(f(a(n+1)+2^m))\leq v_2(f(an+2^m)+f(n))\leq y$$so we're done. In particular, let $d$ be the order of $2$ mod $p$, pick n such that $np+1=2^wd$ for all integer $w$, we obtain that $v_2(a_{wd+m})=y$, and since $v_2(a_i)+1\geq v_2(a_{i+1})$ we must have $v_2(a_n)\leq y$ that is, $a_n$ is bounded, which violates CLAIM 1.
If $y>x$, then we prove by induction that $v_2(f(a+n2^m))\leq x$ for all positive integers $n$
Indeed the base cases are trivial, suppose the case n holds, then
$$v_2(f(a+(n+1)2^m))\leq v_2(f(a+n2^m)+f(2^m))\leq x$$so we're done. pick n such that $n+p+1=2^w$ for all integer $w$, we obtain that $v_2(a_{w})=x$, that is, $a_n$ is bounded, which violates CLAIM 1.
Combining the two cases, we proves the claim.
$\underline{CLAIM 3.}$If $a\geq k$, then
$$v_2(f(2^{a+1})=v_2(f(2^a))+1$$$\underline{Proof.}$
Otherwise, since $v_2(f(2^{a+1})\leq v_2(f(2^a))+1$ either
(i)$v_2(f(2^{a+1})<v_2(f(2^a))$ or
(ii)$v_2(f(2^{a+1})=v_2(f(2^a))$
If $(i)$ holds,
$$v_2(f(2^a))>v_2(f(2^{a+1})=v_2(f(2^{a+1})+f(2^a))\geq v_2(f(2^{a+1}+2^a))$$This violates CLAIM 2 since $v_2(2^{a+1}+2^a)=v_2(2^a)$
If $(ii)$ holds, then we let $f(2^a)=2^m$. We prove by induction that
$$f(n2^a)=2^m$$for all integer $n$ not divisible by $4$. Indeed from $(ii)$ we have $f(2\cdot 2^a)=2^m$
Now suppose all smaller cases holds, we have
$$f(n2^a)| f((n-1)2^a)+f(2^a)=2^{m+1}$$From CLAIM 2 we have $v_2f(n2^k)=m$ and therefore $f(n2^k)=2^m$, this completes the inductive step. Now we have, for all integers $b$,
$$f(2^{b+m})|f(2^m)+f((2^b-1)2^m)=2^{a+1}$$that is $a_n$ is bounded, this violates CLAIM 1, so we prove CLAIM 3.
$\underline{CLAIM 4.}$
For all integer $n$ we have
$$f(n2^k)=n2^m$$$\underline{Proof.}$
We proceed by induction. In the following we denote $f(2^k)=2^m$. Note that $CLAIM 3$ implies that for all integer $b$ we have $f(2^{b+k})=2^{m+b}$
The base cases are trivial. Now suppose all smaller cases hold we consider the case $n$,suppose $2^{t-1}\leq n\leq 2^t$, we have
$$f(n2^k)|f((n-1)2^k)+f(2^k)$$$$f(2^t\cdot 2^m)|f(n2^k)+f(2^t-n)2^k)$$applying the inductive hypothesis we have
$$n2^m\leq f(n2^k)\leq n2^m$$This completes the inductive step and we hence have proof CLAIM 4.
$\underline{CLAIM 5.}$
$$f(2^{k-1})=2^{m-1}$$$\underline{Proof.}$
Now we have
$$f(n2^k+2^{k-1})|f(n2^k)+f(2^{k-1})$$$$f((n+1)2^k)|f(n2^k+2^{k-1})+f(2^{k-1})$$for all integer $n$. Let the terms on the left and right side of the first divisibility be $A$ and $B$, and the terms on the left and right side of the second divisibility be $C$ and $D$.
Note that $A\leq B$ and $C\leq D$. If $A=B$ and $C=D$, we add them up and apply $CLAIM 4$ to get
$$f(2^{k-1})=2^{m-1}$$which is what we want to prove.
Otherwise, either one of $2A\leq B$ or $2C\leq D$ must hold.
If the former holds we have
$$2^m+f(n2^k+2^{k-1})\leq f(2^{k-1})$$since $f(n2^k+2^{k-1})\geq \frac{1}{2}n2^{m+1}+2^m$
we have $f(2^{k-1})\geq (n+1)2^{m+1}$ which can't hold for large $n$.
If the latter holds we have
$$(n+1)2^m\leq 2f(2^{k-1})$$which also can't hold for large $n$. So CLAIM 5 is proved.
However, we define $k$ to be the minimal integer such that $f(2^k)$ is a power of $2$, so we obtain a contradiction, which rejects the case $q\geq 1$
$\underline{Case IIb.}$$q=0$
Now we have $f(1)$ is even, using the same reasoning as in Case I, we have that for all $n$, $f(n)$ is even, so we're done.
Hence we reject all case and the proof is thus completed.
This post has been edited 2 times. Last edited by mathaddiction, May 5, 2020, 3:07 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
niksic
81 posts
#12
Y by
Hopefully this isn't equivalent to any previous solutions :D Nowhere near as pretty as the first one tho :(

Notice that if $p|f(1)$ and $p|f(n)$, then $p|f(m)$ for all $m\leq n$. So for the sake of contradiction, assume that $(f(1),f(n))=1$ for all $n>N$, where $N$ is some integer.

Claim 1: $f(n)\leq n+C$ where $C$ is a constant

Also notice that $f(2n)|2f(n)$, so by induction we have $f(2^k)|2^kf(1)$, so $f(2^k)|2^k$ for $2^k>N$. Because $f(n+m)|f(n)+f(m)$, we also have $f(n+m)\leq f(n)+f(m)$. We will also use these two inequalities: $f(2^k)\leq 2^k$ for $k\geq \log_2(N)$ and $f(2^k)\leq 2^kf(1)$ for the smaller ones. Writing any $n$ as a sum of powers of two and using the inequality as many times as needed, we get $f(n)\leq n+(1+2+4+...+2^{\log_2(N)})f(1)\leq n+C$ where $C$ is constant.

Claim 2: Let $a_p$ be the smallest value $n$ for which $p|f(n)$. Then we have $p|f(n)\implies a_p|n$
Assume the contrary and let $k$ be the smallest value for which $p|f(k)$ and $a_p\nmid k$. Then $k>a_p$ and we have $f(k)|f(k-a_p)+f(a_p)\implies p|f(k-a_p)$, a contradiction.

We now split into two cases:

Case 1 $f(n)\leq \frac{1}{2}(f(n-1)+f(1))$ for infinitely many values of $n$
Take some big $n$ and $\varepsilon>0$ such that $n+2C\leq n(1+\varepsilon)$. Notice that by our assumption we can make $\varepsilon$ arbitrarily small

Take a big integer $m$ and write it as follows: $f(m)=f(an+b)\leq af(n)+f(b)\leq a\frac{1}{2}(f(n-1)+f(1))+f(b)\leq a\frac{1}{2}(n-1+C+1+C)+b+C$
$\leq \frac{1}{2}an(1+\varepsilon)+b\frac{1}{2}(1+\varepsilon)+n+C\leq (an+b)\frac{1}{2}(1+\varepsilon)+C+n = m\frac{1}{2}(1+\varepsilon)+n+C<\frac{3}{4}m$ for $m$ large enough, say for $m\geq N_0$. Take $M=max(N,N_0)$
(These inequalities are far from pretty but they work :D and obviously $3/4$ is arbitrary)

Now look at primes that are larger then $M$ .Say the number of primes that divide $f(1)f(2)\cdots f(k)$ for some $k$ is $g(k)$. By claim 2, you can notice that all primes larger than $M$ are $a_p$ for some $p$, which means $g(k)\geq \pi(k)-\pi(M)$. Say the largest prime dividing $f(1)f(2)\cdots f(M)$ is $P$. Notice that for $k>\frac{4}{3}P$, $\pi(\frac{3}{4}k)\geq g(k)\geq \pi{k}-\pi{M} \iff \pi(k)-\pi(\frac{3}{4}k)\leq \pi(M)$, the right-hand side is fixed, and from here there are many ways to prove that this is a contradiction.
(I won't be writing any of them because I can't think of an elementary way :( )

Case 2 $f(n)=f(n-1)+f(1)$ for $n\geq L$, where $L$ is some integer

This means $f(m)=f(L)+f(1)(m-L) = mf(1)+(f(L)-Lf(1))$ for $m\geq L$. Remember we had the property of $f(2)$ to be a power of $2$. It is trivial to see that this forces $f(L)-Lf(1)=0$ and $f(1)$ is a power of $2$, meaning $2$ divides all $f(m)$ with $m\geq L$, contradiction
This post has been edited 3 times. Last edited by niksic, Aug 13, 2020, 7:00 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Aryan-23
558 posts
#13
Y by
Nice problem !

We distinguish cases based on the boundedness of $f$.

Case 1 : $\operatorname {Im}f$ is bounded.

For all primes $p$, define the set $S_p= \{n : p\mid f(n)\}$. Call a prime $p$ strong , if $S_p$ is infinite and weak otherwise. Its easy to see that $p\vert f(a) , f(b) \implies p\mid f(a-b)$, hence $S_p=x_p \cdot \mathbb Z^{+}$ , for some $x_p$. Suppose that for all strong primes $p$, $x_p\neq 1$. Then note that since $f(n)$ is divisible by only finitely many weak primes, hence this means that the set $ \mathbb Z^+ \setminus { \bigcup_{p 
   \quad         \text{strong}} S_p } $ is finite. Consider, $X= \prod_{p  \quad \text{strong}} x_p$ and look at $X\mathbb Z^++1$. Obviously its infinite and has $f(\bullet)$ not divisible by any strong prime, contradiction. $\blacksquare$. Hence $x_p=1$ for some strong prime $p$, and the conclusion is immediate.

Case 2 : $f$ is unbounded.

The idea is to worry only about the size of $f$ and force "Cauchyness" on some intervals.

We show $f(x)=xf(1)$ for all $x\in \mathbb Z^+$

Call a $x$ to be a peak if $f(x) > \operatorname {max} \{f(1),f(2) ,\dots f(x-1)\}$. Obviously there are infinitely many such peaks due to unboundedness. Its easy to see that due to size issues, $f(x)=f(x-k)+f(k)$ holds for all $x>k$.

We show $f(n+1)-f(n)=f(1)$ for all $n$.
Pick a arbitrary $x$ and $y$ such that $x+y$ is a peak and $f(x+y)$ is huge. Spamming the equality $f(x+y)=f(x)+f(y)=f(x-1)+f(y+1)$, we get :

$$ f(y+1) \vert f(y)+f(1) $$$$\implies f(x+y)-f(x-1) \mid f(x+y)-f(x)+f(1)$$$$\implies f(x+y)-f(x-1) \mid f(x)-f(x-1)-f(1)$$
Taking $f(x+y)$ to be huge we're done. $\blacksquare$
This post has been edited 1 time. Last edited by Aryan-23, Oct 22, 2020, 5:52 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
shalomrav
330 posts
#14
Y by
For the bounded case, just take a prime $p$ for which all the values of $f(n)$ appeared before $p$. So there is some $n$ smaller than $p$ such that $f(p)=f(n)=c$ and by euclidean algorithm $c$ divides $f(1)$, and by more application of euclidean algorithm (induct down, begin with $p,1$) we get $c$ divides every guy in $f(p-1), f(p-2), f(p-3) ... $ and so. we are done since by assumption every value of $f$ is included in this sequence.
This post has been edited 6 times. Last edited by shalomrav, Feb 12, 2021, 3:54 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
SnowPanda
186 posts
#15
Y by
Solution
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
jj_ca888
2726 posts
#16 • 1 Y
Y by Mango247
Let $P(m, n)$ denote the assertion. First of all, $P(1, n)$ yields\[f(n+1) \mid f(n) + f(1) \implies \gcd(f(n+1), f(1)) \mid \gcd(f(n), f(1))\]always. Now, we only need to consider when there exists $M$ for which $\gcd(f(n), f(1)) = 1$ for all $n \geq M$ since\[\gcd(f(n), f(1)) \mid f(n) \mid \gcd(f(n-1), f(1))\]so the sequence $\gcd(f(i), f(1))_{i = 1}^{\infty}$ is in fact nonincreasing, and if it never hits $1$, then the lower bound $L$ of the sequence divides all $\gcd(f(i), f(1))$, and thus divides all $f(i)$, at which point we would be done.

Next, we will prove that in the case where $f(n), f(1)$ are relatively prime for all sufficiently large $n \geq M$, then $f$ is unbounded. First, note that $P(n, m-n)$ yields $f(n) \mid f(m-n) + f(m)$ hence $\gcd(f(n), f(m)) \mid \gcd(f(m-n), f(n))$ which is analogous to the Euclidean Algorithm, and performing this continuously yields $\gcd(f(n), f(m)) \mid f(\gcd(m, n))$. Thus, for pairs $(m, n)$ that are relatively prime, and $m, n \geq M$, it follows that $\gcd(f(m), f(n)) \mid f(1)$ but since\[\gcd(f(m), f(1)) = \gcd(f(n), f(1)) = 1\]we know $\gcd(f(m), f(n)) = 1$. It easily follows that $f$ is then unbounded; if it were upper bounded by $U$, then just pick some $N > U$ numbers $a_1, \ldots , a_N \geq M$ for which their $f$ values are all pairwise relatively prime; no two $f(a_i)$ could be the same, hence the range of $f$ needs to hit at least $N > U$ numbers, thus $U$ could not have been the upper bound, a contradiction.

Lastly, we finish by considering the case where $f$ is unbounded. Consider numbers $k$ for which $f(k) > f(1), \ldots , f(k-1)$. There are clearly infinitely many of these $k$, else $f$ is upper bounded by the largest $f(k)$. Pick arbitrarily large $K$ for which $f(K)$ is large, and greater than all $f(i)$ for $i < K$. Then for any positive $x + y = K$, note $f(x) + f(y) < 2f(K)$ but still must be a whole multiple of $K$, hence $f(x) + f(y) = K$. Note that since $f(x + 1) \mid f(x) + f(1)$,\[f(K) - f(y-1) \mid f(K) - f(y) + f(1) \implies f(K) - f(y-1) \mid f(y-1) - f(y) + f(1)\]where clearly $|f(y-1) - f(y) + f(1)| < |f(K) - f(y-1)|$ from picking $K$ such that $f(K)$ is much larger than every one of $f(y), f(y-1), f(1)$. Finally, this implies that $f(y) = f(y-1) + f(1)$ for all integers $y$, hence $f$ is linear and then induction easily shows that $f(y) = yf(1)$, so indeed $f(1) \mid f(y)$ for all $y$, finishing this case as well.

After exhausting all cases, we have shown $f(1)$ does indeed always divide all $f(n)$.
This post has been edited 11 times. Last edited by jj_ca888, Jun 29, 2021, 9:10 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
L567
1184 posts
#17
Y by
Cool problem! :D. I did the bounded case first and then died on the unbounded case for a longg time proving useless stuff like $f(n) > n$ before I realised simple stuff does work :P

Note that every value of $f$ has some prime dividing it since $f(n) > 1$. Let $p$ be an arbitrary prime dividing some value of $f$. Let $S_p$ denote the set of numbers $n$ such that $p | f(n)$. Note that $a,b \in S_p \implies |a-b| \in S_p$ as well, by the problem statement. Let $a_1 < a_2 < a_3, \cdots$ be the elements of $S_p$. Now, we must have $a_{k+1} - a_k = a_1$. This is because if $a_{k+1} - a_k = z < a_1$, then $z < a_1 \in S_p$, not possible. If $a_{k+1} - a_k = z > a_1$, then $a_{k+1} - a_1 \in S_p$ and is between $a_{k}$ and $a_{k+1}$, not possible. So, we have that $S_p$ is just multiples of $a_1$.

Let $q$ be a prime dividing $f(1)$. If the problem is false, then $S_q$ is finite, say with maximal element $M$. Pick a prime $r > M$. Note that $f(r)$ cannot contain any prime divisor that divides $f(n)$ for $n < r$ since then we would need $n | r$, not possible since $n \neq 1$ and $r$ is prime. Since this is true for infinitely many $r$, we have that there are infinitely many primes dividing some value of $f$. In particular, $f$ is unbounded.

I will in fact show that if $f$ is unbounded, then it is linear. Call a number $n$ a peak if $f(n) > f(k)$ for all $1 \le k \le n-1$. So $f(n) | f(k) + f(n-k)$ but since $f(n)$ is greater than both of them, we must have $f(n) = f(k) + f(n-k)$ for all $k < n$. Since $f$ is unbounded, there are infinitely many peaks. Let $m$ be one such peak.

Observe that $f(m) - f(k) = f(m-k) | f(m-k-1) + f(1) = f(m) - f(k+1) + f(1) \implies f(m) - f(k) | f(k) + f(1) - f(k+1)$. Since we can make $m$ sufficiently large, we must have that the RHS is $0$, so $f(k+1) = f(k) + f(1)$ which gives $f(n) = nf(1)$ and so $c = f(1)$ itself divides all values of $f$. Therefore, we are done. $\blacksquare$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
rama1728
800 posts
#18
Y by
IndoMathXdZ wrote:
Let $f : \{ 1, 2, 3, \dots \} \to \{ 2, 3, \dots \}$ be a function such that $f(m + n) | f(m) + f(n) $ for all pairs $m,n$ of positive integers. Prove that there exists a positive integer $c > 1$ which divides all values of $f$.

Solved with MathLuis :showoff:

Let \(P(m,n)\) denote the assertion of the given functional equation. We split the problem into two cases.

Case 1. \(\text{Im}(f)\) is bounded.
From the divisibility condition \[f(n+1)\mid f(n)+f(1)\]we have that \[\gcd(f(n+1),f(1))\mid\gcd(f(n)+f(1),f(1))=\gcd(f(n),f(1))\]Also, by Pigeon Hole, there exists a prime \(p\) such that \(p\mid f(n)\) for infinitely many \(n\), let the set of such \(n\) be denoted as \(\mathbb{S}_p\) and let \(k\) be their greatest common divisor. By the Euclidean algorithm, we can show that \(\mathbb{S}_p\) contains all the multiples of \(k\). Now, we choose a subset \(\mathcal{S}\) of \(\mathbb{S}_q\) (for some prime \(q\)) so that \(\mathcal{S}\) contains the least element of \(\mathbb{S}_q\) and all the images of the elements are equal. Let the least element be \(n_0\), then note that \(\gcd(f(n_0),f(1))=\gcd(f(m),f(1))\) for all \(m\geq n_0\), because of the divisibility condition we got earlier. Now, if we choose the prime \(q\) so that it divides \(f(1)\), then we get that \(q\) divides \(f(i)\) and \(f(i+1)\) for some \(i\). And since the only \(k\) that divides \(i\) and \(i+1\) is \(1\), \(q\) divides \(f(i)\) for all natural numbers \(i\) as desired.

Case 2. \(\text{Im}(f)\) is unbounded.
Call a positive integer \(n\) gawaskar, if \(f(n)>f(i)\) for all \(i<n\). Note that there are infinitely many gawaskar numbers and \(f(n)=f(i)+f(n-i)\) for all \(i<n\). Now, let \(x+y\) be a gawaskar number such that \(f(x+y+1)\) is huge. Then, by the problem's condition, \[f(x+y+1)\mid f(x+y)+f(1)=f(x)+f(y)+f(1)\]and \[f(x+y+1)\mid f(x)+f(y+1)\]implying that \[f(x+y+1)\mid f(y+1)-f(y)-f(1)\]Implying that \(f(y+1)=f(y)+1\). Since there are infinitely many gawaskar numbers, we have that \(f(x+1)-f(x)=f(1)\) for all \(x\in\mathbb{N}\). This implies that \(f(x)=xf(1)\), and since \(1\neq f(1)\mid f(x)=xf(1)\), we are done.

Remarks
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
AwesomeYRY
579 posts
#19
Y by
Solved with help from Max Lu

If $p$ divides $f(1)$, then first there's $n_p$ values of f divisible by p, then everything afterwards isn't divisible by p. Thus, there exists some $N$ s.t. for all $n\geq N$ you have $\gcd(f(1),f(n))=1$.

If $p\nmid f(1)$, then let the first time that $q$ appears in $f(i)$ be $s_q$. Then, $p\mid f(n) \Longrightarrow s_q\mid n$. Combining these two results, for $p\geq N$, $f(p)$ is relatively prime to all previous numbers.

Thus, if $f$ is bounded, you find a contradiction because you can't keep generating relatively prime numbers (finite number of prime divisors).

Otherwise, if $f$ is bounded then we claim that $f$ is linear (and therefore of the form $f(n) = n\cdot f(1)$. There must be arbitrarily long chains of $f(n+1) = f(n)+f(1)$, otherwise if all chains were of length $\leq C$, then the value would go up by $Cf(1)$ and then get halved, which cannot become unbounded. Thus, there exists a chain with arbitrarily large $k$ of the form $[b-k,b]$. Next, $f(b)\mid f(b-k) + f(k) = f(b) - kf(1) + f(k) \leq f(b)$ so $f(k) = kf(1)$ and we're done. $\blacksquare$.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Inconsistent
1455 posts
#20 • 1 Y
Y by Nuterrow
Assume otherwise.

Notice that $f(m+n) \leq f(m)+f(n)$ so we can induct to $f(a_1+a_2+\ldots+a_n) \leq f(a_1)+f(a_2)+\ldots+f(a_n)$.

We say a prime $p$ is alive if for any positive integer $N$, there exists $x \geq N$ such that $p \mid f(x)$. We say a prime is dead otherwise.

Notice that for every $p \mid f(1)$ we have $p \nmid f(k)$ for some $k$, so $p$ is dead by induction because $p \nmid f(i) \Longrightarrow p \nmid f(i+1)$ since $f(i+1) \mid f(1)+f(i)$.

We say a dead prime $p$ dies on a day $N$ if for any $x \geq N$ we have $p \nmid f(x)$ and such $N$ is minimal. By definition, every prime has a death day.

Note that $f(2n) \mid 2f(n)$ so for an odd prime $p$ if $p \nmid f(n)$ then $p \nmid f(2n)$. Therefore no new primes appear in the sequence $f(1), f(2), f(4), \ldots, f(2^i), \ldots$ and eventually after all primes that divide $f(1)$ die, $f(2^n)$ is a power of $2$ for all $n \geq C$ for some $C$, and none of them are equal to $1$. This implies $2$ is alive, so $2 \nmid f(1)$. Therefore since $v_2(f(2^{i+1}) \leq 1+v_2(f(2^{i}))$ we know $v_2(f(2^i)) \leq i$. A corollary is that $f(2^i) \leq 2^i$ for all $i \geq C$.

Assume at some integer $T$ we have $v_2(f(2^T)) < T$ then by induction $v_2(f(2^i))<i$ for all integers $i \geq T$. So for all $i \geq \max(T, C)$ we have $f(2^i) \leq \frac{2^i}{2}$

Let $S = \sum_{i = 0}^{\max(T, C)} \left(f(2^i)-2^i\right)$, which is a finite positive integer.

Then for all $i \geq \max(T, C)$ we have $f(i) \leq \sum_{2^s \text{ in binary representation of i}} f(2^s) \leq \frac{i}{2}+S$

Let $R$ be the day when all primes that divide $f(1)$ die.

Lemma: If $p \mid f(q)$ where $p, q$ are primes and $q \geq N$ for some constant $N$ then $p \nmid f(i)$ for all $i < q$.

Proof: Choose $N = R$. Then assume $p \mid f(i)$ for some $i < q$, so pick the minimal such $i$ which must be greater than $1$. Clearly $i \nmid q$ so let $s$ be $q$ reduced modulo $i$. Then $p \nmid f(s)$, and by induction on $p \nmid f(k) \Longrightarrow p \nmid f(k+i)$ using $f(k+i) \mid f(i)+f(k)$, we prove $p \nmid f(q)$ which is a contradiction, so we are done.

Therefore the set of primes between $R$ and $x$ for arbitrary $x$ has an injective mapping to the set of primes at most $\frac{x}{2}+S$. So $\pi\left(x\right) \leq \pi\left(\frac{x}{2}\right)+(R+S)$ for constant $R+S$. This is clearly false by the Prime Number Theorem, giving contradiction.

Therefore $T$ doesn't exist, so $v_2(f(2^i)) = i$ for all $i$, implying $f(2^i) = 2^i$ for all $i \geq C$.

Now let $M = \sum_{i = 0}^C \left(f(2^i)-2^i\right)$. Clearly by summing over the binary representation again, $f(i) \leq i+m$ for all $i$. By taking the smallest power of 2 greater than $i$, $2^k$, we know that $2^k \leq f(i)+f(2^k-i)$ so $f(i) \geq i-M$ since $f(2^k-i) \leq 2^k-i+M$.

For $i, j > 2M$ we must have $f(i+j) \mid f(i)+f(j)$ but if $f(i+j) \neq f(i)+f(j)$ then $i+j-M \leq f(i+j) \leq \frac{f(i)+f(j)}{2} \leq \frac{i+j}{2}+M$, which is a contradiction. So $f(i+j) = f(i)+f(j)$. So letting $j = ki$ and inducting on positive integers $k$ gives us that $f(ki) = kf(i)$ for $i > 2M$. However this means if $p$ is any prime that divides $f(1)$, then $p \mid f(pi) = pf(i)$ for arbitrarily large $i$. This means $p$ is alive, so by contradiction we are done.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
bora_olmez
277 posts
#21
Y by
I didn't like this as much as most others.
Solution
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
NoctNight
108 posts
#22 • 2 Y
Y by PRMOisTheHardestExam, Mango247
Solution
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
IAmTheHazard
5001 posts
#23
Y by
Really long solution, but this problem feels like you just keep throwing stuff at it and keep track of what you've proved and you eventually grind it down.

As with everyone else, split into cases where $f$ is bounded and unbounded.

In general, note that if $n \mid f(a),f(b)$ for $a>b$, then $n \mid f(a) \mid f(b)+f(a-b) \implies n \mid f(a-b)$. Call an integer $i$ with $n \mid f(i)$ $n$-cool. I claim that if there exist $n$-cool integers, then they are all consecutive multiples of some positive integer $k$, and $k$ is one of them (i.e. they are $\{k, 2k, \ldots\}$ or $\{k, 2k, \ldots, ak\}$ for some $a \geq 1$). I claim that setting $k$ equal to the least $n$-cool integer works, which is by induction. Suppose that the $c$ smallest $n$-cool integers are $\{k,\ldots,ck\}$, and the $c+1$-th smallest $n$-cool integer exists. Then if $x$ is this $c+1$-th smallest $n$-cool integer, $x-k$ must be $n$-cool as well, and also must be in $S$ as it's smaller than $x$, hence $x-k=ck \implies x=(c+1)k$, completing the induction.

Suppose $f$ is bounded, so there exists some maximal $M$ such that there are infinitely many $n$ with $f(n)=M$, and call such $n$ fat. The key idea is that for any fat $n$, we have $f(a)+f(b) \in \{M,2M\}$ for all $a+b=n$ with $a,b$ sufficiently large (so $f(a),f(b) \leq M$), where we only achieve $2M$ if $a$ and $b$ are fat as well.
First, we use the above idea but loosened a bit: let $m$ be the least integer such that $M \mid f(m)$ (which exists, since it's at most the smallest fat number). Then if $n$ is fat and $n-m$ is large, $M \mid f(n-m) \implies f(n-m)=M$. On the other hand, if some $n>k>n-m$ exists such that $f(k)=M$, then $M=f(n) \mid f(k)+f(n-k) \implies M \mid f(n-k)$: impossible by definition, as $n-k<m$. This is enough to imply that the gap between large enough consecutive fat numbers is constant (and equal to $m$).
Now, pick positive integers $a,b$, such that $a,b,b-a$ are large enough, and $b$ is fat, so $b+m$ is fat as well. Then $f(b-a)=f(b+m-a)=M-f(a)$. By fixing $a$ and letting $b$ vary, this means that $f$ is eventually periodic (with minimal period $m$).
Pick $x$ large and let $1<k=f(mx+1)$, which is constant for large enough $x$. Then by our "general fact", $k$ divides $mx+1,mx+m+1$, which implies that it divides $\gcd(mx+1,mx+m+1)=\gcd(mx+1,m)=1$. Then because there are infinitely many $k$-cool integers, and $1$ is one of them, every positive integer is $k$-cool, completing the proof. $\blacksquare$

Now to tackle the case where $f$ is unbounded. Let $M$ be the minimum value attained by $f$, and call an $n$ such that $f(n)=M$ skinny. Further, let $n$ be powerful if $f(n)\geq f(n-1),f(n-2),\ldots,f(1)$, and overpowered if the inequality is strict, so there are infinitely many overpowered (and thus powerful) $n$. It's easy to see that for all overpowered $n$, we have $f(a)+f(b)=f(n)$ for all $a+b=n$, and if $n$ is powerful (but not overpowered) this equality holds so long as both $a$ and $b$ aren't powerful either, and if one is, then both are.
Pick some large overpowered $n$ with $f(n)=x$ and $x>9999M$. Then we have $f(m)=x-M \iff f(n-m)=M$ for $m<n$. On the other hand, by our general claim, the set of $a$ such that $x-M \mid f(a)$ is equal to consecutive multiples of some positive integer $k$, including $k$in particular, the least $m$ with $f(m)=x-M$ is $k$ (important!). On the other hand, if $a<n$, then $2(x-M)\geq x$, so any such $a$ must have $f(a)=x-M$. Hence for $m<n$, $f(m)=x-M \iff m=ck$ where $c$ ranges from $1$ to some arbitrary positive integer (possibly $1$ as well). This means that the skinny integers less than $n$ are evenly spaced out with a gap of $k$ as well. But since $k$ must equal the least $m$ satisfying $f(m)=x-M$ (which is overpowered), we can repeat this argument with a different (larger) choice of overpowered $n$, giving us a different value of $k$, unless $c \leq 1$ always (in which case the gap isn't defined). This means that there is exactly one skinny number $K$, which in turn readily implies that if $n>K$ is overpowered, then $n-K$ is overpowered as well, and they are consecutive (i.e. there is no overpowered number between them). Thus there exists some $1 \leq r \leq K$ such that the overpowered integers which are at least $r$ are precisely those of the form $Kx+r$ for $r \geq 0$. Note that if $f(r)=C$, then $f(Kx+r)=Mx+C$.
For any $y$, pick some $x$ such that $Kx+r>y$, so $f(y)+f(Kx+r-y)=f(Kx+r)=Mx+C$. We then also have
$$f(y+K)+f(Kx+r-y)=f(K(x+1)+r)=M(x+1)+C,$$so $f(y+K)=f(y)+M$ for all $y$.
We are now ready to finish. Pick some $x,y$ and consider the equation $x+(y+cK)=(x+y+cK)$ for all $c \geq 0$. Then,
$$f(x+y+cK) \mid f(x)+f(y+cK) \implies f(x+y)+cM \mid f(x)+f(y)+cM \implies f(x+y)+cM \mid f(x)+f(y)-f(x+y).$$Since $f(x+y)+cM$ is unbounded, $f(x)+f(y)=f(x+y)$, hence $f$ satisfies Cauchy and is linear. This clearly implies that $f(1)>1$ divides all values of $f$, so we're done. $\blacksquare$
This post has been edited 3 times. Last edited by IAmTheHazard, Jan 25, 2023, 10:31 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
blackbluecar
302 posts
#24
Y by
Assume $f$ is unbounded. We have a sequence $m_1<m_2< \cdots$ where $f(m_i)>f(n)$ for all positive integers $n<m_i$. First, by size stuff, we see that $f(m_i) = f(m_i-k)+f(k)$ for every positive integer $k<m_i$. Likewise $f(m_i) = f(m_i-k-1)+f(k+1)$. So, $f(m_i)-f(k)$ divides $f(m_i)-f(k+1)+f(1)$. Thus, $f(m_i)-f(k)$ divides $f(k)-f(k+1)+f(1)$. But $f(m_i)-f(k)$ gets arbitrarily large. So, $f(k)-f(k+1)+f(1)=0$. Thus, $f(n)=n \cdot f(1)$

Assume $f$ is bounded. First, we claim that there exist positive integers $a$, $b$, and $p$ where $\gcd(a,b)=1$ and $p$ divides $f(a)$ and $f(b)$. This follows from the fact that $\text{Im}(f)$ is bounded. If there are $k$ primes dividing elements in $\text{Im}(f)$ then just consider a set of $k+1$ pairwise relatively prime positive integers, by PHP we get what we want. Now, let $A=\{a_1<a_2< \cdots \}$ be the set of positive integers where $f(a_i)$ is divisible by $p$. We claim $a_k = c \cdot k$ for some positive integer $c$. Indeed, if $m>n$ are positive integers then $f(a_m)$ divides $f(a_m-a_n)+f(a_n)$. Since $p$ divides $f(a_m)$ and $f(a_n)$, it must follow that $p$ divides $f(a_m-a_n)$. So, $a_m-a_n \in A$. Now, we will proceed by induction. Suppose $a_i = c \cdot i$ for every positive integer $i<k$, we will show $a_k = c \cdot k$. Assume $a_k < c \cdot k$. Then, $a_{k}-a_{k-1}<k = a_1$. But this contradicts minimality since $a_k-a_{k-1} \in A$. Now, assume $a_k > c \cdot k$. Then $a_k>a_k-a_1>a_{k-1}$. But because $a_k-a_1\in A$, this implies there is an element in $A$ between two consecutive elements. Contradiction.

So, we have positive integers $\gcd(a,b)=1$ where $p$ divides $f(a)$ and $f(b)$. But, this implies that $a = k \cdot A$ and $b = k \cdot B$ for some $A$ and $B$. So, $k=1$. Implying that $p$ divides $f(n)$ for all positive integers $n$.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Anzoteh
126 posts
#25
Y by
Lol I ended up turning this into an analysis problem smh (also thanks to some theorem a few have pointed out).

Sketch
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
VicKmath7
1389 posts
#26 • 1 Y
Y by Maths_Girl
Solution
This post has been edited 1 time. Last edited by VicKmath7, May 15, 2023, 2:26 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Leo.Euler
577 posts
#27
Y by
Assume for contradiction that there exists large $N$ such that for $n \ge N$, $\gcd(f(1), f(n))=1$.

Claim: $f$ is unbounded.
Proof. First, we note that $\gcd(f(1), f(n+1)) \mid \gcd(f(1), f(n))$ for all $n$, and inductively we have \[ \gcd(f(1), f(a)) \mid \gcd(f(1), f(b)) \]whenever $a > b$. Furthermore, for such $a, b$, it follows by the Euclidean algorithm that \[\gcd(f(a), f(b)) \mid \gcd(f(a-b), f(b)), \]and we can accordingly condense this to \[ \gcd(f(a), f(b)) \mid \gcd(f(1), f(n)) \mid f(1) \]for some $n$. By our assumption, when both $a$ and $b$ are larger than $N$, $\gcd(f(a), f(b)) \mid 1$, which forces $\gcd(f(a), f(b))=1$, implying that $f$ is unbounded. :yoda:

We assume the claim henceforth. Say that a positive integer $n$ is Skywalker if and only if $f(n) \ge f(k)$ for each $k < n$; clearly there is an infinitude of such numbers. By definition $f(n)=f(k)+f(n-k)$ for all $k<n$ whenever $n$ is Skywalker. Let $n$ be an arbitrarily large Skywalker, and $m<n$ be arbitrary. Fixing $m$ and variating $n$, the original functional equation implies \[ f(n-m+1) \mid f(n-m)+f(1), \]which we easily reduce to \[ f(n) - f(m) \mid f(m)-f(m-1)-f(1), \]so by size reasons we have $f(m)-f(m-1)-f(1)=0$, which rewrites as $f(m)=f(m-1)+f(1)$. Inductively we have $f(i)=if(1)$ for all $i \ge 1$, but this is a contradiction to our initial assumption that $\gcd(f(1), f(n))=1$ for sufficiently large $n$. We conclude. :starwars:

Remark: This proof consists of three main components, namely
  • showing that $f$ is unbounded by following the Euclidean algorithm,
  • defining Skywalker numbers using the unboundedness of $f$ and observing their infinitude, and
  • solving the functional equation by fixing some $m<n$ (where $n$ is a large Skywalker) and variating $n$.
In fact, the final two steps are motivated by the solution to 2019 N4, in which the functional divisibility is taken to advantage by fixing the dividend and varying the divisor enough to conclude that the dividend is 0.
This post has been edited 1 time. Last edited by Leo.Euler, Aug 14, 2023, 7:42 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
huashiliao2020
1292 posts
#28
Y by
I was suggested to solve this by Leo.Euler;
here's a long and inefficient solution, where I just threw things at the wall until it stuck:

Suppose FTSOC that there exists a number $L$ (we take the smallest) that does not share the common gcd of the numbers smaller than it; let the earlier common gcd be g. Let $d_n=\gcd(f(n),f(1))$. Note that $$d_{n+1}=\gcd(f(n+1),f(1))\mid\gcd(f(n)+f(1),f(1))=d_n\stackrel{\text{induction}}{\rightarrow}d_i\mid d_j\forall i>j\implies\forall l\ge L,d_l\mid d_L,$$and by assumption $\gcd(d_L,g)=1\implies\gcd(d_l,g)=1$. We also extract $$\forall a\equiv1\pmod b,a,b\ge L,\gcd(f(a),f(b))\mid\gcd(f(a-b)+f(b),f(b))=\gcd(f(a-b),f(b))=...=\gcd(f(1),f(k))\mid f(1)$$by iterating. By assumption, this is one (otherwise $1<\gcd(f(a),f(b),f(1))\mid\gcd(f(a),f(1))$); in particular, f is unbounded.

Since f is unbounded, there are an infinite number of times when a new largest value appears in the sequence (namely $f(n)>f(k)\forall k<n$); namely $f(n)>\max(f(k),f(n-k))>\frac{f(k)+f(n-k)}2\implies f(n)=f(k)+f(n-k)$ for infinite n. Fix $m$ and vary n with this property; we have $$f(n)-f(m)=f(n-m)\mid f(n-m-1)+f(1)=f(n)-f(m+1)+f(1)\leftrightarrow f(n)-f(m)\mid f(m)-f(m+1)+f(1),$$which for sufficiently large f(n) s.t. LHS>RHS, we must have RHS=0; in particular, $f(m+1)=f(m)+f(1)\implies f(m)=mf(1)$, contradiction since f(1)>1 and f(1) is a common gcd, so our inital FTSOC was wrong.
This post has been edited 8 times. Last edited by huashiliao2020, Sep 5, 2023, 3:53 AM
Reason: better latex
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
math_comb01
662 posts
#29
Y by
Fun problem!
Sketch:
Case 1: IM(f) is unbounded
The idea is to look at a "peak" and do some sort of downward induction to get $f(x)=xf(1)$.
Case 2:Im(f) is bounded
Here, the idea is to take the set of primes dividing $f$ infinitely many times, then prove one of them divides all by contradiction argument.
This post has been edited 3 times. Last edited by math_comb01, Mar 30, 2024, 11:17 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Iveela
116 posts
#30
Y by
We begin by solving the case where $d = f(1)$ is the minimum value attained by $f$. In particular, we prove that $d$ divides all values of $f$. Assume the contrary. Then, obviously $f$ is nonconstant. Notice that $d \mid f(x)$ implies $d \mid f(x-1)$ since $d \mid f(x) \mid f(x-1)+f(1) = f(x-1) + d$. Consequently $d$ doesn't divide $f(k)$ for all sufficiently large values of $k$.
Now suppose $x \in \mathbb{N}$ satisfies $f(x) \leq f(x+1)$. Then, the condition implies that $f(x+1) \mid f(x) + f(1) \leq 2f(x+1)$. Since equality holds only if $d=f(x)=f(x+1)$, this tells us that either $f(x+1)=f(x) + d$ or $f(x+1)=d$. Consider the smallest positive integer $k$ such that $f(k) \neq kd$. Suppose that a positive integer $x$ satisfies $d \neq f(x) \leq f(x+1) \leq \dots \leq f(x+k)$. Then, the condition implies that $f(x) + kd = f(x+k) \mid f(x) + f(k) \implies f(x + k) \mid f(k) - kd$ and hence $f(x+k) \leq |f(k)-kd|$ which is a constant number.
On the other hand, suppose that $x \in \mathbb{N}$ satisfies $f(x) > f(x+1)$. Then, we have $f(x+1) \mid f(x) + d \implies f(x+1) \leq \frac{f(x)+d}{2}$. It is clear that these observations are enough to conclude that $f$ is bounded. (Actually, this implies that if $f$ is unbounded we must have $f(x)=dx$.)
Let $\alpha$ be the largest value that appears infinitely many times in $f$. Let $\alpha_1, \alpha_2, \dots$ be the numbers mapped to $\alpha$ by $f$. Consider two sufficiently large positive integers $i > j$ such that $i-j$ is also very large. Then, we have $f(\alpha_j) \geq f(\alpha_j-1)$ and hence $f(\alpha_j-1) = \alpha - d$. The condition implies that $f(\alpha_i) \mid f(\alpha_j-1) + f(\alpha_i-\alpha_j+1)$. Since $i-j$ is very large, we have $f(\alpha_i-\alpha_j+1) \leq \alpha \implies f(\alpha_j - 1) + f(\alpha_i - \alpha_j +1 ) < 2 \alpha$. Hence, $f(\alpha_j-1) + f(\alpha_i-\alpha_j+1) = \alpha \implies f(\alpha_i-\alpha_j+1) = d$, a contradiction. (We actually dont use the fact that $f(1)$ is the minimum here.) $\square$

Now we solve the general case. Let $c$ be the smallest positive integer such that $f(c) \leq f(k)$ for all $k \in \mathbb{N}$. Consider the function $g : \mathbb{N} \to \mathbb{N}$ such that $g(x) = f(cx)$. Observe that $g(m+n) \mid g(m) + g(n)$ for all $m, n \in \mathbb{N}$ and $g(1) \leq g(k)$ for all $k \in \mathbb{N}$. It follows that $g(1) \mid g(k) \Leftrightarrow f(c) \mid f(ck)$ for all positive integers $k$.
Case 1: The sequence $f(c), f(2c), \dots$ is bounded.
It suffices to show that $f$ is bounded. Assume the contrary. Then there exists a positive integer $s$ such that the sequence $f(s), f(c+s), f(2c+s), \dots$ is unbounded. Let $f(ck+s)$ be a sufficiently large term of this sequence. Our condition implies that $f(ck+s) \mid f(ck) + f(s)$ which is bounded by a constant number, a contradiction. $\square$.
Case 2: The sequence $f(c), f(2c), \dots$ is unbounded.
Note that $f(ck)=kf(c)$. We claim that $f(x+c) = f(x) + f(c)$. Using the same logic as Case 1, we see that the sequences $f(s), f(c+s), f(2c+s), \dots$ are unbounded for all positive integers $s$. Consider positive integers $k$ such that $f(ck+s) > f(ck_0+s)$ for all $k > k_0$. Suppose that $f(ck) > f(ck+s)$. Consider the largest positive integer $\alpha \leq k$ such that $f(c\alpha) \leq f(ck+s)$. It is clear that $f(ck+s) - f(c\alpha) < f(c)$ The condition implies that $f(ck+s) \mid f(c\alpha) + f(c(k-\alpha)+s)<2f(ck+s)$. Hence, $f(c(k- \alpha)+s) < f(c)$ a contradiction. Then, $f(ck+s) \mid f(c\alpha) + f(c(k-\alpha)+s) < 2f(ck+s)$ implies that $f(c(k-\alpha)+s) + \alpha f(c) = f(ck+s)$.
Now we prove that $f(x+y)=f(x)+f(y)$. Let $x=\alpha c+ x_0$ and $y=\beta c + y_0$. Then, $f(x+y)=(\alpha+\beta)c+f(x_0+y_0) \mid f(x) + f(y) = c(\alpha+\beta) + f(x_0) + f(y_0)$ and hence $c(\alpha+\beta)c + f(x_0 + y_0) \mid f(x_0) + f(y_0) - f(x_0+y_0)$ for all positive integers $\alpha$ and $\beta$. This implies $f(x_0) + f(y_0) = f(x_0+y_0) \implies f(x) + f(y) = f(x+y)$. Hence, $f(x) \equiv kx, \ k \in \mathbb{N}$. $\blacksquare$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
idkk
118 posts
#31
Y by
Claim: if $c|f(a),c|f(b)$ then $c|f(gcd(a,b))$

Proof: Its easy to see $c|f(a),c|f(b) \implies c|f(|b-a|)$ use euclidian division algorithim to prove the claim .


Case 1: $f$ is bounded above or in other words $f$ attains finite values.


Let $f(M)=t$ be the largest value in its range which repeats infinitely often. say $a$ is the smallest natural number such that $f(a)=t$ .
we know then that $f(x)=t \implies a|x$


Claim: $f(x)=t \iff a|x$ for large $x$

assuming $n$ is large we have $f(n)|f(a)+f(n-a)$ if $f(n)=t$ we know $f(n-a)=t$ using this the claim is easy to see .


Claim: For large $x$ , $f(x)=t$ or $\frac{t}{2}$

Consider the sequence $t=f(ax_1)=f(a(x_1+1))=......$ where $x_1$ is large covering all large solutions for $f(x)=t$


Now for any large $m$ not divisible by $a$ pick some large $n$ such that $m+n=ax_1$


Now its easy to see $I=f(m)=f(m+a)=f(m+2a)=........$ we know then $|$ divides $t$.

Pick any other large $m_1$ such that $a|m+m_1$ and choose some large $n_1$ such that $a|m_1+n_1$ to similarly get $a|f(m_1)$ and repeat similarly
from here observe we are writing $t$ as a sum of its divisors only way to do is $\frac{t}{2}+\frac{t}{2}$


Now once we have the main problem proved for large $x$ , smaller $x$'s automatically follow pretty easily .


Case 2: $f$ is unbounded .






Its easy to observe

$f(2^d)|2f(2^{d-1})|4f(2^{d-2})......|2^df(1)$

now i define the function $f_2(x)=$ largest odd factor of any natural no $x$ , observe $f_2(2^{d+1})|f_2(2^{d})$

Case 1: $f_2(f(2^d)) > 1$ always .


Prove that the common odd factor divides any number of form $f(K 2^t)$ where $K$ is a odd no. By induction.

Case 2: The sequence $f(1),f(2),f(4),.....$ eventually turns into powers of 2 .


Say $f(2^d)$ is the smallest power of $2$ in the sequence .

Claim: All multiples of $f(2^d)$ come in the sequence $f(2^d),f(2^{d+1}),f(2^d*3),f^(2^{d+2}),.....$

appolozie my laziness prove alll terms basically are multiples of $f(2^d)$ and do $f^(2^d+2^dt)|f(2^d)+f(2^dt)$ , its easy prove that the sequence wont be bounded . which will give u this claim .


Now observe $f^(2^dx+r)|f(2^dx)+f(1)$ where $f(1)$ is odd

Now as $f(1)$ has to be odd[can be proved with more that if it wasent the case all terms would be even]. , we know there exist ifninitely many $x$ such that $f(2^dx)+f(1)$ is a power of $f(1)$ , by which the result isnt hard to see[ too lazy to add the details :P]
This post has been edited 5 times. Last edited by idkk, May 28, 2024, 9:20 AM
Reason: .
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Akacool
14 posts
#32 • 1 Y
Y by Titibuuu
Lets prove that $f$ is bounded. If we assume that $f$ is unbounded we can say that there are infinite amount of $N$ that $f(N)$ is the prefix max. So it becomes that for any $x < N$
$f(x) + f(N - x) = f(N)$. Now if we take large N and some x to be $f(N - x) | f(N - x - 1) + f(1)$ and it becomes that $f(N) - f(x) | f(N) - f(x + 1) + f(1)$ which in turn means that
$f(x + 1) = f(x) + f(1)$ so $f(x) = xf(1)$.
Now that $f$ is bounded we can assume that there is a set of values of $f$ lets call $A$ that they appear infinitely many times in $f$. It is clear that the $\gcd(f(n), f(1))$ divides all $f$ less than $n$.
If we use euclidean alg on $f$ we can easily see that the $\gcd(f(x), f(y) | f(\gcd(x, y))$. So it means that every occurrence of a element of $S$ is divisible by some "primitive occurrence".
And if that occurrence is $1$ we will get that that element of $S$ is divisible by $f(1)$ in turn all of $f$ will be divisible. So every "primitive" occurrence divides every occurrence of elements of $S$. Every $f(x)$ if $x$ is large will be an element of $S$ which means that every $x$ will be divisible by some "primitive" occurrence but we can take an $X$ that isn't divisible by any so thus a contradiction.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
HamstPan38825
8857 posts
#33
Y by
woah this is like the most perfect number theory FE ever made

We split into two cases.

Case 1: $f$ is bounded, say by $N$. Then there exists a nonempty set of positive integers $S$ such that for any $k \in S$, $k \mid f(n)$ for infinitely many values of $n$. Otherwise, every $k$ only divides $a_k$ values of $n$, and we can only define $f$ for less than $a_1+a_2+\cdots+a_N$ values of $n$.

For each $n \in S$, let $m_n$ be minimal such that $n \mid f(m_n)$, and let $a_1$ be the minimum among the $m_n$. Furthermore, let $a_2, a_3, \dots$ be the values with this $n \mid f(a_i)$ in increasing order.

Claim: For any $q \in \mathbb N$, $n \mid f(qa_1)$.

Proof: Observe we have
\begin{align*}
f(a_i) \mid f(a_i - a_1) + f(a_1) &\implies n \mid f(a_i - a_1) \\
f(a_i - a_1) \mid f(a_i - 2a_1) + f(a_1) &\implies n \mid f(a_i- 2a_1) \\
&\vdots
\end{align*}so we inductively have $n \mid f(a_i \bmod a_1)$. If $a_1 \nmid a_i$, this is less than $a_1$, hence we must have $a_1 \mid a_i$.

By definition, the sequence $\{a_i\}$ has infinitely many terms, so for any $q$, we can find a $a_\ell > qa_1$, and the above process implies $n \mid f(qa_i)$, as needed. $\blacksquare$

Claim: $a_1 = 1$.

Proof: Otherwise, any divisor $d$ of $f(1)$ divides only finitely many $f(n)$. In particular, for sufficiently large primes $p$, $f(p) \mid f(1) p$ implies $f(p) = p$. But this contradicts $f$ bounded. $\blacksquare$

These two claims solve the bounded case.

Case 2: $f$ is unbounded. Then by definition, there exists a sequence $n_1, n_2, n_3, \dots$ such that $f(n_i) > f(k)$ for all $k < n_i$. For these $n_i$, we must have $f(n_i) = f(k) + f(n_i-k)$ as $2f(n_i) > f(k) + f(n_i-k)$ for all $k$. In particular, we have the following claim:

Claim: $f(k+1)-f(k) = c$ for some constant $c$.

Proof. We will show that $f(k) - f(k-1) = f(k+1) - f(k)$ for each $k$. Take some $n_i > k$; by the previous property, \[f(k) + f(n_i-k) = f(n_i) = f(k+1) + f(n_i-k-1) \implies f(k+1) - f(k) = f(n_i-k) - f(n_i-k-1).\]Let $a_{k-1} = f(k) - f(k-1)$ and $a_k = f(k+1) - f(k)$. We have
\[f(n_i-1) \mid \gcd(f(k-1) + f(n_1 - k), f(k) + f(n_1-k-1)) = \gcd(f(k-1)+f(n_1-k), a_{k-1}-a_k).\]In particular, $f(n_i - 1) \mid a_{k-1} - a_k$. But $\{f(n_i)\}$ is unbounded, hence $\{f(n_i - 1)\} = \{f(n_i) - f(1)\}$ is unbounded, so $a_{k-1} = a_k$, as needed. $\blacksquare$

Therefore $f$ is linear in $n$. Let $f(1) = b$ and $f(2) = a+b$; if $a$ and $b$ are relatively prime, then $a+b \mid 2b$, which is a clear contradiction as $\gcd(a+b, 2b) = \gcd(a+b, 2)$. Hence $a$ and $b$ share a common factor $d$, and this $d$ divides $f(n)$ for every $n$.
This post has been edited 1 time. Last edited by HamstPan38825, Aug 21, 2024, 9:17 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
N3bula
269 posts
#34
Y by
Claim: If $f(n)\geq \alpha n$ for some fixed $\alpha$ we get the result.

Proof:
Let $\alpha$ be the largest value such that for all $n$ we have that $f(n)\geq \alpha n$. Clearly from the definition we can find values such that for any $\epsilon$ we get that $\frac{f(n)}{\alpha n} \leq 1+\epsilon$, now take a value of $r$ such that $\frac{f(r)}{\alpha r} < 2$. I claim that we have for that value of $r$ that $f(nr)=nf(r)$. Suppose that $f((n-1)r)=(n-1)f(r)$, we must have that $f(nr)\mid nf(r)$ if $f(nr)\neq nf(r)$ we have that $f(nr)\leq \frac{nf(r)}{2}$, thus $\frac{f(nr)}{\alpha nr} \leq \frac{f(r)}{2\alpha r} < 1$ however this is a contradiction. Thus for all $n$ we have that $f(nr)=nf(r)$. Now suppose that for some $p\mid f(1)$ that $p\nmid f(k)$. Clearly we have that $p \nmid f(k+1)$ and thus for all $m\geq k$ we get $p\nmid f(m)$. Thus we must have unless the result holds true that $f(r)$ is coprime to $f(1)$. Now let $p$ be a prime such that $p\mid f(1)$. Clearly there exists infinetly many $k$ such that $f(n) \mid p^k-1$. Thus we can choose abitrarily large $n$ such that $f(nr)=p^k-1$. Now consider $f(f(1)nr+f(1)) \mid f(1)f(nr)+f(1)$ as $f(nr)=p^k-1$, we get that $f(f(1)nr+f(1)) \mid f(1)p^k$ as we can make $n$ abitrarily large, as $f(n)\geq \alpha n$ we can get that $p \mid f(f(1)nr+f(1))$ for all sufficiently large $n$ this suffices as this means that $p\mid f(n)$ for all $n$.

Now suppose no such lower bound exists.
I will prove that such a $c$ still exists. Clearly we must have that if $gcd(a, b)=1$ that $gcd(f(a), f(b))=1$. Thus if we let the first $n$ primes be $p_1$, $p_2$, $\dots$, $p_n$. We know that for all $n$ we have $f(n)\leq f(1)n$. Now let $k$ be a value such that $\frac{f(k)}{k}< \frac{1}{10^{1000}}$. We get that above some point from that we must have for all $m>N$ that $\frac{f(m)}{m}<\frac{1}{10^{1000}}$. Let the largest prime divisor amongst $f(p_1)$, $f(p_2)$, $\dots$, $f(p_n)$, such that $p_n\leq N < p_{n+1}$ be $q$. Suppose $q$ is the $i$th prime, now let $u$ be a value such that $u \geq n, i$. Take the first $u$ primes. Clearly a prime divisor of size at least $p_u$ divides one of $f(p_{n+1}), f(p_{n+2}), \dots, f(p_u)$ which contradicts the size condition thus implying the result.
This post has been edited 2 times. Last edited by N3bula, Apr 10, 2025, 10:35 AM
Z K Y
N Quick Reply
G
H
=
a