OFFSET
1,1
COMMENTS
Contains A070003 as a subsequence (because single-element intervals are permitted); the two sequences are conjectured by Erdős and Graham to have the same asymptotic growth (Erdős problem #380). The complement of that subsequence in this sequence is A387054.
Intervals with this property were called "bad" by Erdős and Graham. Using Bertrand's postulate, one can show that a bad interval [N, N+H] must obey H <= N.
LINKS
Pontus von Brömssen, Table of n, a(n) for n = 1..10000
Thomas Bloom, Problem 380, Erdős Problems.
P. Erdős and R. L. Graham, On products of factorials, Bull. Inst. Math. Acad. Sinica 4 (1976), pp. 337-355.
P. Erdős and R. L. Graham, Old and new problems and results in combinatorial number theory, Monographies de L'Enseignement Mathématique (1980).
Peter Luschny, Python implementation.
EXAMPLE
24 and 25 are in the sequence, because the interval [24, 25] is bad: 24*25 is divisible by the square of the largest prime factor, which in this case is 5.
27 is in the sequence because the singleton interval [27,27] is bad: 27 is divisible by the square of the largest prime factor 3.
MATHEMATICA
nn = 500; s = Array[FactorInteger[#][[-1, 1]] &, nn + Floor@ Log2[nn]]; k = 1; Rest@ Union@ Flatten@ Reap[While[Set[t, Select[Partition[Range[nn], k, 1], Divisible[#2, Max[s[[#1 ;; #1 + k - 1] ]]^2] & @@ {First[#], Times @@ #} &]]; Length[t] > 0, Sow[t] k++]][[-1, 1]] (* Michael De Vlieger, Sep 22 2025 *)
PROG
(Python)
from collections import defaultdict
from math import isqrt
def spf_sieve(n):
spf = list(range(n+1))
for i in range(2, isqrt(n)+1):
if spf[i] == i: # prime
step = i
start = i*i
for j in range(start, n+1, step):
if spf[j] == j:
spf[j] = i
return spf
def factorize(x, spf):
fac = defaultdict(int)
while x > 1:
p = spf[x]
fac[p] += 1
x //= p
return fac
def bad_numbers_and_intervals(limit):
"""Return (bad_numbers_sorted, bad_intervals, spf) up to `limit`."""
spf = spf_sieve(2*limit)
bad_nums = set()
bad_intervals = []
for N in range(1, limit+1):
counts = defaultdict(int)
maxp = 0
for H in range(0, N+1):
k = N + H
if k > 1:
for p, e in factorize(k, spf).items():
counts[p] += e
if p > maxp:
maxp = p
is_bad = (maxp > 0 and counts[maxp] >= 2)
if is_bad:
for m in range(N, N+H+1):
if m <= limit:
bad_nums.add(m)
bad_intervals.append((N, N+H))
return sorted(bad_nums), bad_intervals, spf
CROSSREFS
KEYWORD
nonn,changed
AUTHOR
Terence Tao, Sep 19 2025
STATUS
approved