It's February and we'd love to help you find the right course plan!

G
Topic
First Poster
Last Poster
k a February Highlights and 2025 AoPS Online Class Information
jlacosta   0
Feb 2, 2025
We love to share what you can look forward to this month! The AIME I and AIME II competitions are happening on February 6th and 12th, respectively. Join our Math Jams the day after each competition where we will go over all the problems and the useful strategies to solve them!

2025 AIME I Math Jam: Difficulty Level: 8* (Advanced math)
February 7th (Friday), 4:30pm PT/7:30 pm ET

2025 AIME II Math Jam: Difficulty Level: 8* (Advanced math)
February 13th (Thursday), 4:30pm PT/7:30 pm ET

The F=ma exam will be held on February 12th. Check out our F=ma Problem Series course that begins February 19th if you are interested in participating next year! The course will prepare you to take the F=ma exam, the first test in a series of contests that determines the members of the US team for the International Physics Olympiad. You'll learn the classical mechanics needed for the F=ma exam as well as how to solve problems taken from past exams, strategies to succeed, and you’ll take a practice F=ma test of brand-new problems.

Mark your calendars for all our upcoming events:
[list][*]Feb 7, 4:30 pm PT/7:30pm ET, 2025 AIME I Math Jam
[*]Feb 12, 4pm PT/7pm ET, Mastering Language Arts Through Problem-Solving: The AoPS Method
[*]Feb 13, 4:30 pm PT/7:30pm ET, 2025 AIME II Math Jam
[*]Feb 20, 4pm PT/7pm ET, The Virtual Campus Spring Experience[/list]
AoPS Spring classes are open for enrollment. Get a jump on 2025 and enroll in our math, contest prep, coding, and science classes today! Need help finding the right plan for your goals? Check out our recommendations page!

Don’t forget: Highlight your AoPS Education on LinkedIn!
Many of you are beginning to build your education and achievements history on LinkedIn. Now, you can showcase your courses from Art of Problem Solving (AoPS) directly on your LinkedIn profile! Don't miss this opportunity to stand out and connect with fellow problem-solvers in the professional world and be sure to follow us at: https://www.linkedin.com/school/art-of-problem-solving/mycompany/ Check out our job postings, too, if you are interested in either full-time, part-time, or internship opportunities!

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
Monday, Feb 3 - May 19
Sunday, Mar 2 - Jun 22
Friday, Mar 28 - Jul 18
Sunday, Apr 13 - Aug 10

Prealgebra 1 Self-Paced

Prealgebra 2
Sunday, Feb 16 - Jun 8
Tuesday, Mar 25 - Jul 8
Sunday, Apr 13 - Aug 10

Prealgebra 2 Self-Paced

Introduction to Algebra A
Sunday, Feb 16 - Jun 8 (3:30 - 5:00 pm ET/12:30 - 2:00 pm PT)
Sunday, Mar 23 - Jul 20
Monday, Apr 7 - Jul 28

Introduction to Algebra A Self-Paced

Introduction to Counting & Probability
Sunday, Feb 9 - Apr 27 (3:30 - 5:00 pm ET/12:30 - 2:00 pm PT)
Sunday, Mar 16 - Jun 8
Wednesday, Apr 16 - Jul 2

Introduction to Counting & Probability Self-Paced

Introduction to Number Theory
Sunday, Feb 16 - May 4
Monday, Mar 17 - Jun 9
Thursday, Apr 17 - Jul 3

Introduction to Algebra B
Thursday, Feb 13 - May 29
Sunday, Mar 2 - Jun 22
Monday, Mar 17 - Jul 7
Wednesday, Apr 16 - Jul 30

Introduction to Algebra B Self-Paced

Introduction to Geometry
Friday, Feb 14 - Aug 1
Tuesday, Mar 4 - Aug 12
Sunday, Mar 23 - Sep 21
Wednesday, Apr 23 - Oct 1

Intermediate: Grades 8-12

Intermediate Algebra
Wednesday, Feb 12 - Jul 23
Sunday, Mar 16 - Sep 14
Tuesday, Mar 25 - Sep 2
Monday, Apr 21 - Oct 13

Intermediate Counting & Probability
Monday, Feb 10 - Jun 16
Sunday, Mar 23 - Aug 3

Intermediate Number Theory
Thursday, Feb 20 - May 8
Friday, Apr 11 - Jun 27

Precalculus
Tuesday, Feb 25 - Jul 22
Sunday, Mar 16 - Aug 24
Wednesday, Apr 9 - Sep 3

Advanced: Grades 9-12

Olympiad Geometry
Wednesday, Mar 5 - May 21

Calculus
Friday, Feb 28 - Aug 22
Sunday, Mar 30 - Oct 5

Contest Preparation: Grades 6-12

MATHCOUNTS/AMC 8 Basics
Tuesday, Feb 4 - Apr 22
Sunday, Mar 23 - Jun 15
Wednesday, Apr 16 - Jul 2

MATHCOUNTS/AMC 8 Advanced
Sunday, Feb 16 - May 4
Friday, Apr 11 - Jun 27

AMC 10 Problem Series
Sunday, Feb 9 - Apr 27
Tuesday, Mar 4 - May 20
Monday, Mar 31 - Jun 23

AMC 10 Final Fives
Sunday, Feb 9 - Mar 2 (3:30 - 5:00 pm ET/12:30 - 2:00 pm PT)

AMC 12 Problem Series
Sunday, Feb 23 - May 11

AMC 12 Final Fives
Sunday, Feb 9 - Mar 2 (3:30 - 5:00 pm ET/12:30 - 2:00 pm PT)

Special AIME Problem Seminar B
Sat & Sun, Feb 1 - Feb 2 (4:00 - 7:00 pm ET/1:00 - 4:00 pm PT)

F=ma Problem Series
Wednesday, Feb 19 - May 7

Programming

Introduction to Programming with Python
Sunday, Feb 16 - May 4
Monday, Mar 24 - Jun 16

Intermediate Programming with Python
Tuesday, Feb 25 - May 13

USACO Bronze Problem Series
Thursday, Feb 6 - Apr 24

Physics

Introduction to Physics
Friday, Feb 7 - Apr 25
Sunday, Mar 30 - Jun 22

Physics 1: Mechanics
Sunday, Feb 9 - Aug 3
Tuesday, Mar 25 - Sep 2

Relativity
Sat & Sun, Apr 26 - Apr 27 (4:00 - 7:00 pm ET/1:00 - 4:00pm PT)
0 replies
jlacosta
Feb 2, 2025
0 replies
P6 Geo Finale
math_comb01   7
N 2 minutes ago by GuvercinciHoca
Source: XOOK 2025/6
Let $ABC$ be a triangle with incenter $I$ and excenters $I_A$, $I_B$, $I_C$ opposite to $A,B,C$ respectively. Suppose $BC$ meets the circumcircle of $I_AI_BI_C$ at points $D$ and $E$. $X$ and $Y$ lie on the incircle of $\triangle ABC$ so that $DX$ and $EY$ are tangents to the incircle (different from $BC$). Prove that the circumcircles of $\triangle AXY$ and $\triangle ABC$ are tangent.

Proposed by Anmol Tiwari
7 replies
math_comb01
Feb 10, 2025
GuvercinciHoca
2 minutes ago
A functional equation
super1978   1
N 14 minutes ago by pco
Source: Somewhere
Find all functions $f: \mathbb R \to \mathbb R$ such that:$$ f(f(y-x)-xf(y))+f(x)=y(1-f(x)) $$for all $x,y \in \mathbb R$
1 reply
super1978
an hour ago
pco
14 minutes ago
Sequences Handout
M11100111001Y1R   4
N 18 minutes ago by MR.1
Source: Own
Hi everyone, I wrote this handout about sequences in NT.
Hope you enjoy!
4 replies
+2 w
M11100111001Y1R
Oct 19, 2022
MR.1
18 minutes ago
[Handout] 50 non-traditional functional equations
gghx   2
N 44 minutes ago by GreekIdiot
Sup guys,

I'm retired. I love FEs. So here's 50 of them. Yea...

Functional equations have been one of the least enjoyed topics of math olympiads in recent times, mostly because so many techniques have been developed to just bulldoze through them. These chosen problems do not fall in that category - they require some combi-flavoured creativity to solve (to varying degrees).

For this reason, this handout is aimed at more advanced problem solvers who are bored of traditional FEs and are up for a little challenge!

In some sense, this is dedicated to the "covid FE community" on AoPS who got me addicted to FEs, people like EmilXM, hyay, IndoMathXdZ, Functional_equation, GorgonMathDota, BlazingMuddy, dangerousliri, Mr.C, TLP.39, among many others: thanks guys :). Lastly, thank you to rama1728 for suggestions and proofreading.

Anyways...
2 replies
gghx
Sep 23, 2023
GreekIdiot
44 minutes ago
No more topics!
Only consecutive terms are coprime
socrates   34
N Feb 3, 2025 by L13832
Source: 7th RMM 2015, Problem 1
Does there exist an infinite sequence of positive integers $a_1, a_2, a_3, . . .$ such that $a_m$ and $a_n$ are coprime if and only if $|m - n| = 1$?
34 replies
socrates
Feb 28, 2015
L13832
Feb 3, 2025
Only consecutive terms are coprime
G H J
G H BBookmark kLocked kLocked NReply
Source: 7th RMM 2015, Problem 1
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
socrates
2104 posts
#1 • 6 Y
Y by Davi-8191, tenplusten, Centralorbit, megarnie, Adventure10, Mango247
Does there exist an infinite sequence of positive integers $a_1, a_2, a_3, . . .$ such that $a_m$ and $a_n$ are coprime if and only if $|m - n| = 1$?
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
mikeshadow
55 posts
#2 • 2 Y
Y by Adventure10, Mango247
Yes, there exists.
Let us partition the set of prime numbers into pairs of $(p_i,q_i)$, take $a_{2n+1}=p_{2n+1}q_{2n+1}\prod_{k=0}^{n-1}  p_{2k+1} \prod_{k=1}^{n-1} q_{2k}$ and $a_{2n}=p_{2n}q_{2n}\prod_{k=0}^{n-2}  q_{2k+1} \prod_{k=1}^{n-1} p_{2k}$, notice that any two non-consecutive terms have a prime divisor in common, while any consecutive don't have one.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
dibyo_99
487 posts
#3 • 2 Y
Y by Adventure10, Mango247
Err.. with the same basic idea, we can make the above form a little less complicated. Construct $a_i$'s inductively. Take $2$ distinct primes not chosen at some previous step $p_{i,0}, p_{i,1}$ and let \[a_i = p_{i,0}p_{i,1} \prod_{j=1}^{i-2}p_{j,i\pmod{2}} \]Then, clearly, $a_i$ shares factors with all $a_j$'s $\forall$ $j \in [1,i-2]$. However, $p_i$ and $p_{i-1}$ are coprime because primes chosen in $a_i$ and $a_{i-1}$ have opposite pairity indices and are therefore distinct.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
v_Enhance
6853 posts
#4 • 7 Y
Y by utkarshgupta, xdiegolazarox, Wizard_32, Centralorbit, sa2001, Adventure10, Mango247
Yeah, I found this surprisingly easy for an RMM1: Enumerate the primes $p_1$, $q_1$, $p_2$, $q_2$, ... and define
\[
	a_{n}
	= 
	p_nq_n \cdot 
	\begin{cases}
		\prod_{k=1}^{n-2} p_k & n \text{ even} \\
		\prod_{k=1}^{n-2} q_k & n \text{ odd}.
	\end{cases}
\]
The idea is that you just take every pair $i < j$ you want to not be relatively prime (meaning $\left\lvert i-j \right\rvert \ge 2$) and throw in a prime. You can't do this by using a different prime for every pair (since each $a_i$ must be finite) and you can't use the same prime for a fixed $i$, so you do the next best thing and alternate using even and odd and you're done.

Hope to see actual number theory tomorrow :)
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Konigsberg
2205 posts
#5 • 2 Y
Y by Adventure10, Mango247
This is remarkably similar to USAMTS round 3 problem 4
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Konigsberg
2205 posts
#6 • 2 Y
Y by Adventure10, Mango247
Nice intuitive thinking: think of the darn a1. Oh hey it can't be a prime! How about a product of 2 primes, and just alternate stuff. Then just repeat and repeat. QED

Could someone make a totally different construction as this?
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
MathPanda1
1135 posts
#7 • 2 Y
Y by Adventure10, Mango247
When will the other problems of today's RMM be posted?
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
AnonymousBunny
339 posts
#8 • 4 Y
Y by biomathematics, Zoom, adityaguharoy, Adventure10
This looks pretty silly; can someone verify this please?

Solution
This post has been edited 1 time. Last edited by AnonymousBunny, Mar 1, 2015, 9:11 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Konigsberg
2205 posts
#9 • 2 Y
Y by Adventure10, Mango247
Oh yeah, that's another possible, but very similar construction. Do you know of a TOTALLY DIFFERENT construction? (obviously not just jumbling around the primes), or just multiplying a prime to everything... or is it possible to prove that all possible constructions will follow a similar form?

Also, it is really really similar to usamts round 3 problem 4
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Emerson_Soriano
14 posts
#10 • 3 Y
Y by vinayak-kumar, codyj, Adventure10
La respuesta es sí. En efecto, sea $a_1=2 \times 3, a_2=5 \times 7$ y $a_3=2 \times 11$ y sea $a_4=3 \times 5 \times 13$. Luego, para $n \geq 4$, $a_n= \frac{a_{n-2}}{p_{n-2}} \times p_{n-3} \times q_n$, donde $p_i$ representa el mayor primo que aparece en $a_i$ ($i \geq 1$), y $q_i$ representa el menor primo que no divide a ninguno de los siguientes términos: $a_1, a_2, ... , a_{i-1}$, para $i \geq 2$, por ejemplo, $a_5=2 \times 7 \times 17$. Probaremos que esta secuencia funciona. Si demuestro que para cualquier $i \geq 5$, se cumple que $a_i$ y $a_{i-1}$ son coprimos, y $a_i$ con $a_j$ no son coprimos, para todo $1 \leq j \leq i-2$, ya quedaría listo. En efecto, probaremos que para $n \geq 5$, cumple, notemos que la base ya la construimos, pues los $5$ primeros términos ya satisfacen, luego supongamos que todos los términos $a_1, a_2, ... , a_{i-1}$ cumplen lo pedido, entonces como $a_i= \frac{a_{i-2}}{p_{i-2}} \times p_{i-3} \times q_n$. Notemos que $a_{i-1}$ es coprimo con $a_{i-2}$, con $p_{i-3}$, y con $q_i$. Por lo tanto, $a_i$ y $a_{i-1}$ son coprimos. Luego, es fácil ver que $a_i$ y $a_{i-3}$ no son coprimos, también vemos que como $p_{i-2}$ es el mayor de los primos en $a_{i-2}$, entonces no aparece atrás, y por tanto, $\frac{a_{i-2}}{p_{i-2}}$ no es coprimos con $a_j$, para$j \leq i-4$. Por lo tanto, $a_i$ no es coprimo con $a_j$, para todo $j \leq i-2$. Lo cual completa la inducción.

Observación: $q_i$ tambíen es igual a $p_i$, solo que usé otro sentido en la fórmula para que se vea la construcción.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Stens
49 posts
#11 • 1 Y
Y by Adventure10
Quite similar to the other solutions, but does this work as well?

Let $a_1=2$, and define the other $a_i$´s recursively:
$a_n=p_{n}\cdot\prod_{i=1}^{n-2}a_i$
where $p_n$ denotes the nth prime.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
newton123
1 post
#12 • 2 Y
Y by Adventure10, Mango247
Stens wrote:
Quite similar to the other solutions, but does this work as well?

Let $a_1=2$, and define the other $a_i$´s recursively:
$a_n=p_{n}\cdot\prod_{i=1}^{n-2}a_i$
where $p_n$ denotes the nth prime.

It won't work if $a_1$ is prime. since if $a_1$ is prime, $a_3$ and $a_4$ must have a common factor, $a_1$. Such that they cannot be coprime.
This post has been edited 2 times. Last edited by newton123, Sep 29, 2015, 1:42 AM
Reason: Adjust spaces
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
k.vasilev
66 posts
#13 • 2 Y
Y by Adventure10, Mango247
We will prove that for each $n$ there exist a sequence $a_1,a_2,\ldots,a_n,$ satisfying the condition in the promp by induction on $n.$ The base case is trivial. For the step let the statement be true for some $n.$ Now we will construct our new sequence with $n+1$ members as follows:
Let $p_1,p_2,\ldots,p_{n-1}$ be distinct primes greater than $a_i$ for each $i=1,2,\ldots,n.$ The sequence with $n+1$ members is $a_1p_1, a_2p_2,\ldots,a_{n-1}p_{n-1},a_n,p_1p_2\cdots p_{n-1}.$ Now it is easy to notice, that $(a_kp_k,a_lp_l)=1$ iff $|k-l|=1$ for $k,l<n$ and $(a_n,p_i)=1$ for all $i.$ Therefore $(a_n,a_kp_k)=1$ iff $(a_n,a_k)=1$ iff $|n-k|=1$(By the induction hypothesis), we also have that $(a_n,p_1p_2\cdots p_{n-1})=1$ and for all $i\leq n-1$ $(p_1p_2\cdots p_{n-1}, a_ip_i)=p_i>1.$ Thus, the problem is solved.
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
#15 • 2 Y
Y by Adventure10, Mango247
The answer is yes. Let the primes be $p_1,p_2,p_3,\ldots$. Now, let $b_n$ be the product of the primes $p_{2k-1}$ where $k\equiv n\pmod{2}$ and $k\le n-2$ and $p_{2\ell}$ where $\ell\not\equiv n\pmod{2}$ and $\ell\le n-3$. Let $a_n=p_{2n}p_{2n-1}b_n$. It is easy to see that this works.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
pad
1671 posts
#16 • 1 Y
Y by Adventure10
Yes. The following construction works: $a_1=p_1p_3, a_2=p_2p_4, a_3=p_1p_5, a_4=p_2p_3p_6$, and
\[ a_n = \begin{cases} p_1(p_4p_6p_8p_{10} \cdots p_{n-3}p_{n-1})p_{n+2} \text{ for } n \text{ odd} \\ p_2(p_3p_5p_7p_9 \cdots p_{n-3}p_{n-1})p_{n+2} \text{ for } n \text{ even}. \end{cases}\]It is not hard to see that this works.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Wizard_32
1566 posts
#17 • 5 Y
Y by amar_04, Adventure10, Mango247, Aopamy, Funcshun840
Here's a solution which I think is not new, but written in a different way.
socrates wrote:
Does there exist an infinite sequence of positive integers $a_1, a_2, a_3, . . .$ such that $a_m$ and $a_n$ are coprime if and only if $|m - n| = 1$?
The answer is yes. By looking at the prime factors, we only need to find an infinite number of sets so that $S_i \cap S_J=\phi$ if and only if $|i-j|=1.$ Here's the construction:

Let $p_i$ denote the $i$th prime. Consider the sets $A_1=\{p_1,p_2\},A_2=\{p_3,p_4\},\dots.$ Then, add alternating elements from previous sets, as shown:
$$\begin{array}{c | c | c | c | c | c | c | c | c | c}
    A_i & \{2,3\} & \{5,7\} & \{11,13\}  & \{17,19\} & \{23,29\} & \{31,37\} & \{41,43\} & \{47,53\} & \\
    \text{From } A_1 &  &  & 2 & 3 & 2 & 3 & 2 & 3 & \\
    \text{From } A_2 &  &  &   & 5 & 7 & 5 & 7 & 5 & \\
    \text{From } A_3 &  &  &   &   & 11 & 13 & 11 & 13 &  \dots \\
    \text{From } A_4 &  &  & & & & 17 & 19 & 17 & \\
    \text{From } A_5 &  &  & & & & & 23 & 29 &\\
    \text{From } A_6 &  &  & & & & &  & 31 &\\
    % &  &  & & \vdots & & &  &  &\\
\end{array}$$Then the sets $S_i$ to be $A_i$ $\cup$ the $i$th column works, for instance $S_1=\{2,3\}$ and $S_4=\{17,19,3,5\}.$ $\blacksquare$

Edit: Oh yeah, this is the same as v_Enhance's solution at #4. Oops.
This post has been edited 2 times. Last edited by Wizard_32, May 2, 2020, 9:51 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Idio-logy
206 posts
#18 • 1 Y
Y by Nathanisme
The answer is yes. Let the prime numbers be $p_1,p_2,p_3,\dots$ since there are infinitely many of them. Let $a_1=p_1p_2$, $a_2=p_3p_4$, $a_3=p_1p_5$, and
\begin{align*}
    a_{2n} &= p_2p_3p_5p_7\dots p_{2n-1}p_{2n+2}\\
    a_{2n+1} &= p_1p_4p_6p_8\dots p_{2n}p_{2n+3}.\\
\end{align*}
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
#19 • 1 Y
Y by Nathanisme
Remark: Do RMM 1 when you can't do RMM 2.

The answer is yes. Let the primes be $p_1 < q_1 < p_2 < q_2 < \ldots $ and suppose we let\[a_n = (p_nq_n)\cdot (p_1p_2\ldots p_{n-2})\]if $n$ is even and\[a_n = (p_nq_n) \cdot (q_1q_2\ldots q_{n-2})\]if $n$ is odd.

It is easy to check that this works.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
lazizbek42
548 posts
#20
Y by
Very nice problem
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
MathsLover04
95 posts
#22
Y by
The answer is yes. We will build our sequence so that it only contains square-free integers. Now lets do some notations:


Consider $p_1,p_2,\ldots $ the prime numbers.

For any $a_m=p_{b_1}p_{b_2}\ldots p_{b_k}$ with $b_1<b_2<\ldots <b_k$ denote $deg(a_m)=p_{b_k}$.

For any $a_m=p_{b_1}p_{b_2}\ldots p_{b_k}$ with $b_1<b_2<\ldots <b_k$ denote $\overline{a_m}=\frac{p_1p_2\ldots p_{b_k}}{a_m}$.


Build the sequence as following:


$a_1=p_1p_2$ and $a_2=p_3p_4$

$a_n=\frac{\overline{a_{n-1}}}{deg(\overline{a_{n-1}})}\cdot p_{n+2}$


This construction satisfies the given condition, so 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.
HoRI_DA_GRe8
584 posts
#23 • 2 Y
Y by Mango247, lelouchvigeo
Construction
This post has been edited 2 times. Last edited by HoRI_DA_GRe8, May 21, 2022, 5:50 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
laikhanhhoang_3011
637 posts
#24 • 1 Y
Y by David-Vieta
not sure
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
IAmTheHazard
4998 posts
#25
Y by
laikhanhhoang_3011 wrote:
not sure

I had the same idea at first but I don't think this works. In particular, if we pick, say, $p_1$ for $a_1$, and then down the line we are forced to pick $p_3$ for some $a_i$, then $a_1 \mid a_{n+1}$. Then $a_{n+2}$ should be coprime to $a_{n+1}$, but also not coprime with $a_1$, which is impossible.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
IAmTheHazard
4998 posts
#26
Y by
Yes.
Let the primes be $p_1,\ldots,$ in some order. Let
$$a_n=p_{2n-1}p_{2n}\cdot \prod_{i=1}^{n-2} p_{2i-(n\%2)}$$where $n\%2=1$ if $n$ is odd and $0$ otherwise. It is easy to check that this works, since $\gcd(a_n,a_{n+1})=1$ and $\gcd(a_m,a_n)=p_{2m-(n\%2)}$ for $m\leq n-2$. $\blacksquare$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
asdf334
7572 posts
#27
Y by
hmmm it feels like this should work

essentially, if we have $a_1$ to $a_n$ chosen, we just need to pick suitable $a_{n+1}$, which essentially just means that the sets of primes $S_i$ dividing $a_i$ satisfy $S_1, S_2, \dots, S_{n-1}$ are not subsets of $S_n$. at this point we can just realize that if we selected $S_1$ to $S_{n-1}$ to contain really large arbitrary sets of primes (think of them as buffers) then this basically works, 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.
GrantStar
807 posts
#28
Y by
Yes.
Denote the primes by $p_1$, $p_2$, $\dots$. The construction is as follows
  • Put $p_{2i}$ in $a_i$, $a_{i+2}$, $a_{i+4}$, $\dots$ where by putting it in we simply mean $p_{2i}$ divides these numbers
  • Put $p_{2i+1}$ in $a_i$, $a_{i+3}$, $a_{i+5}, a_{i+7}, a_{i+9}, \dots$
To show that this works, we just notice the following
  • Proving that consectutive terms are relatively prime is trivial by construction of the sequence.
  • Proving that consecutive terms are not relatively prime is also easy. This is done as fixing a term $a_N$, all terms $a_k$ with $k$ and $N$ having the same parity clearly share a common factor, namely $2$ or $5$. Accesing the odd terms is also easy by the delay of some terms by $3$ indices instead of $2$.
This completes the problem.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
megarnie
5488 posts
#29
Y by
Yes there does.

Order the set of prime numbers as $2 = p_1, p_2, \ldots,$. Let $(g_i)$ denote a sequence of ordered pairs, such that $g_i = (p_{2i-1}, p_{2i})$ for each positive integer $i$ (so $g_1 = (2,3), g_2 = (5,7)$, and so on). Define $a_1 = p_1 p_2 = 2\cdot 3$ and $a_2 = p_3 p_4 = 5\cdot 7$. For odd $n$, we let $a_n$ be the product of all the first elements in each of $g_1, g_2, \ldots, g_{n-2}$ multiplied by the product of both elements in $g_n$. For even $n$, we let $a_n$ be the product of all the second elements in each of $g_1, g_2, \ldots, g_{n-2}$ multiplied by the product of both elements in $g_n$. The first few numbers of this sequence we \[2\cdot 3, 5\cdot 7, 2\cdot 11\cdot 13, 3\cdot 7\cdot 17 \cdot 19, \ldots,  2\cdot 5\cdot 11\cdot 23\cdot 29\]
If $m > n + 1$, then $g_n$ divides both $a_n$ and $a_m$, so they aren't relatively prime. If $m = n + 1$, then we can see the prime factors of $a_m$ and $a_n$ are disjoint ($m$ and $n$ have different parity). Therefore, $\gcd(a_m, a_n) = 1 \iff |m-n| = 1$.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
lelouchvigeo
171 posts
#30
Y by
Answer
My solution is same as (23)
Hint
This post has been edited 2 times. Last edited by lelouchvigeo, Jan 7, 2024, 5:26 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
cursed_tangent1434
523 posts
#31 • 1 Y
Y by GeoKing
Really easy just that it's annoying to write out like a decent proof. The answer is yes, and we construct such a sequence recursively as follows. First we let $\mathcal{P}={p_1,p_2,\dots}$ be the set of all prime numbers. Then, we define a sequence of sets $(S_i)$ which are subsets of $\mathcal{P}$ and let $a_i$ be the product of all the primes in $S_i$.

In the first two rounds, let $S_1=\{p_1,p_2\}$ and $S_2=\{p_3,p_4\}$. Then, we add $p_1$ to all sets $S_i$ where $i \equiv 1 \pmod{2}$ and $p_2$ to all sets $S_j$ where $j\equiv 0 \pmod{2}$ for all $i\geq 3$. Next, in the third round we add $p_5$ and $p_6$ to $S_3$. Then, we add $p_3$ to all sets $S_i$ where $i \equiv 3 \pmod {2}$ ($i>3$) and $p_4$ to all sets $S_j$ where $j \not \equiv 3 \pmod{2}$ ($j>4$). Similarly, we keep continuing, where in the $k^{\text{th}}$ round we add $p_{2k-1}$ and $p_{2k}$ to $S_k$. Then, we add $p_{2k-1}$ to all sets $S_i$ where $i\equiv 2k-1 \pmod{2}$ ($i>2k-1$) and $p_{2k}$ to all sets $S_j$ where $j \not \equiv 2k-1 \pmod{2}$ ($j>2k$).

To explicitly state the sets,
\[S_i= \{p_1,p_4,p_5, \dots ,p_{2i-6},p_{2i-5},p_{2i-1},p_{2i}\} \text{ for all } i \equiv 1 \pmod{2} \text{ and } i>1\]and
\[S_i = \{p_2,p_3,p_6,p_7, \dots ,p_{2i-6},p_{2i-5},p_{2i-1},p_{2i}\} \text{ for all } i \equiv 0 \pmod{2} \text{ and } i>2\]
Now, it is immediately clear that $S_i$ and $S_j$ do not have any common factor for consecutive $i,j$ (since $i\not \equiv j \pmod{2}$, $p_r \nmid \gcd(a_i,a_j)$ for any $r < 2i-1$ and $p_{2i-1}$ and $p_{2i}$ don't divide $a_j$ since they are added only to sets $S_t$ where $t>i+1$ by the nature of our construction). For all $i,j$ where $j>i+1$, $S_i$ and $S_j$ must have one of $p_{2i-1}$ or $p_{2i}$ as a common factor depending on the parity of $j$. Thus, this construction must work and 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.
RedFireTruck
4184 posts
#32
Y by
Yes. Construction below.

Define $S_n$ as a set of positive integers such that $a_n=\prod_{i\in S_n}p_i$ where $p_i$ represents the $i$th prime.

Then, let $S_1=\{1,2\}$ and $S_2=\{3,4\}$.

For $n>2$, let $S_n=\{2,4,\dots, n-2, n, n+1\}$ for even $n$ and let $S_n=\{1,3,\dots, n-4, n-2, n+3\}$ for odd $n$.

This satisfies the assertion, as desired.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Mr.Sharkman
476 posts
#33
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.
InterLoop
226 posts
#34
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.
ezpotd
1241 posts
#35
Y by
this is so abd to writeup

Consider an infinite list of primes $p_i$, and split the primes into groups of $4$. Then for $n = 4i  +1$, have $p_n$ divide $a_k$ if and only if $k$ is odd and at least $2i + 1$. For $n = 4i + 2$, have $p_n$ divide $a_k$ if and only if $k$ is even and at least $2i + 3$ or $k$ is $2i +1$. For $n = 4i + 3$, have $p_n$ divide $a_k$ if and only if $k$ is even and at least $2i + 2$. For $n = 4i + 4$, have $p_{n}$ divide $a_k$ if and only if $k$ is odd and at least $2i + 4$ or $k$ is $2i + 2$. For simplicity, call $p_{2i + 1}, p_{2i + 2}$ the associated primes of $a_{i + 1}$.

Inspecting each individual prime makes it obvious that no two consecutive numbers share a prime divisor. We can also observe any two non consecutive numbers share a prime divisor by considering the one that comes first in the sequence, clearly every number after its successor divides one of its associated primes (in alternating fashion), so 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.
HamstPan38825
8794 posts
#36
Y by
The answer is yes. The construction is a tad bit underwhelming.

Let $p_1 < p_2 < p_3 < \cdots$ be the primes in increasing order. Then for term $a_i$ of the sequence, we let
  • primes $p_{2i-1}$ and $p_{2i}$ divide $a_i$ immediately;
  • for each $j < i - 1$, $p_{2j-1}$ divides $a_i$ if $i \equiv j \pmod 2$, and $p_{2j}$ divides $a_i$ otherwise.
To check that this sequence works, notice that:
  • for any $k \leq n-2$, one of $p_{2k-1}$ and $p_{2k}$ divides both $a_k$ and $a_n$ by construction;
  • neither of $p_{2n-3}$ and $p_{2n-2}$ divide $a_n$, and for each $k \leq n-3$, if $p_{2k-1}$ divides $a_{n-1}$ and not $p_{2k}$,
    then $p_{2k}$ divides $a_n$ and not $p_{2k-1}$, and vice versa.
So $\gcd(a_k, a_n) > 1$ when $k \leq n-2$ and $\gcd(a_{n-1}, a_n) = 1$. This is all we need to prove.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
L13832
225 posts
#37
Y by
I'll tell the motivation I had, this problem sure did take time to solve.

solution
This post has been edited 1 time. Last edited by L13832, Feb 3, 2025, 8:22 AM
Z K Y
N Quick Reply
G
H
=
a