Lighthouse numbers: the least missing prime is more useful than factoring N

greirat_gang·Apr 21, 2026(edited)

I tested a few examples and found 1260 works. Is there a clean upper bound? Listing all integers coprime to N is getting nowhere. Problem: A positive integer

N

is called a *lighthouse number* if it has the following property. Any positive integer not exceeding

N

which is relatively prime to it has at most two prime factors (possibly equal). Determine whether the lighthouse numbers are infinitely or finitely many and, in the latter case, find the greatest among them. Source: Baltic Way 2019 · MNET-01G6

Open MNET-01G6 in the question bank →

5 replies

pixelated_toast·Apr 21, 2026(edited)

Let q be the least prime not dividing N. The smallest integer coprime to N with at least three prime factors, counted with multiplicity, is

q^3

. Hence the condition is precisely

N<q^3

greirat_gang·Apr 23, 2026(edited)

Why must a bad integer be at least

q^3

if N has some larger prime factors as well?

pixelated_toast·Apr 23, 2026(edited)

Every prime factor of an integer coprime to N is at least q. Three such factors already give

q^3

, and

q^3

itself is coprime to N. Larger prime factors of N don't affect this argument.

snorlax_afk·Apr 23, 2026

Write q as the (r+1)-st prime. Then

N\ge p_1\cdots p_r

. For r≥5 this product is at least

p_{r+1}^3

: check r=5,6; for r≥7 Bertrand gives

p_{r+1}^3<64p_rp_{r-1}p_{r-2}\le p_1\cdots p_r

greirat_gang·Apr 23, 2026

So r≤4. If r≤3, N<343. If r=4, N is a multiple of 210 below

11^3=1331

, hence at most 1260. And 1260's least missing prime is 11, so it works.

Join the discussion

A hint, a different approach, or a thoughtful question can help.

Loading discussion…