An algorithm for discovering prime numbers?

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

w

29 users

TOPICS

No tags match your search

M

No tags match your search

M

An algorithm for discovering prime numbers?

G H J

Reveal topic tags

infinite sequence

L

G H BBookmark kLocked kLocked NReply

Source: 2025 Junior Macedonian Mathematical Olympiad P3

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

286 posts

#1 h May 18, 2025, 3:31 PM

Y by

Is there an infinite sequence of prime numbers $p_1, p_2, ..., p_n, ...,$ such that for every $i \in \mathbb{N}, p_{i + 1} \in \{2p_i - 1, 2p_i + 1\}$ is satisfied? Explain the answer.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1448 posts

#2 h May 18, 2025, 6:31 PM

Y by

We first show that there is an $n_0$ and $\epsilon\in\{-1,1\}$ such that for every $n\ge n_0$ , $p_{n+1} = 2p_n+\epsilon$ .

To see this, suppose $p_1>3$ . If $p_1\equiv 1\pmod{3}$ then $p_{n+1}=2p_n-1$ must hold necessarily (otherwise $3\mid 2p_n+1$ but $p_n>3$ ). Likewise if $p_1\equiv -1\pmod{3}$ then $p_{n+1}\equiv 2p_n+1$ must hold. If $p_1\le 3$ , then $p_j>3$ for some $j>1$ , so the same argument carries through. Shifting if necessary, we will analyze the sequence $p_{n+1} =2p_n-1$ and $p_{n+1}=2p_n+1$ for $p_1>3$ .

Case 1. Let $p_{n+1} = 2p_n-1$ for $n\ge 1$ . Set $b_n:=p_n-1$ to obtain $b_{n+1} = 2b_n$ . Iterating, we find $b_n = 2^{n-1}b_1$ . Consequently, $p_n = 2^{n-1}(p_1-1)+1$ . Taking $n=k(p_1-1)+1$ for suitably large $k$ , Fermat's theorem asserts $2^{n-1}\equiv 1\pmod{p_1}$ . So, $p_1\mid p_n$ but $p_n>p_1$ , hence $p_n$ cannot be a prime.

Case 2. Let $p_{n+1}=2p_n+1$ for $n\ge 1$ . Set $b_n:=p_n+1$ to obtain $p_n = 2^{n-1}(p_1+1)-1$ . The same choice of $n$ ensures $p_1\mid p_n$ , a contradiction.

So, no such infinite sequence exists.

Remark. This is an old Bulgarian problem (between 2003-2010 I think), though I don't remember the exact year.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1481 posts

#3 h May 29, 2025, 4:17 PM

Y by

@above Hm, haven't seen this in Bulgaria, but it is popular from Baltic Way 2004.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

24 posts

#4 h May 29, 2025, 5:15 PM • 1 Y

Y by alexanderhamilton124

hahaha I was in the comp,after i got out I told everyone that nobody could solve this after the results came it was only me :-D

:-D

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

alexanderhamilton124

404 posts

alexanderhamilton124

#5 h May 30, 2025, 2:47 PM

Y by

TopGbulliedU wrote:

hahaha I was in the comp,after i got out I told everyone that nobody could solve this after the results came it was only me :-D

:-D

orz gj man

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a