A384308 a(1) = 3; for n > 1, a(n) is the smallest number that has not appeared before and has the same set of prime divisors as a(n-1) + 1.

3, 2, 9, 10, 11, 6, 7, 4, 5, 12, 13, 14, 15, 8, 27, 28, 29, 30, 31, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 81, 82, 83, 42, 43, 44, 45, 46, 47, 36, 37, 38, 39, 40, 41, 84, 85, 86, 87, 88, 89, 60, 61, 62, 63, 32, 33, 34, 35, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 90, 91, 92, 93, 94, 95, 72, 73, 74, 75

Offset

1,1

Comments

Theorem 1: {a(n)} is a permutation of the positive integers greater than 1.

Proof: Suppose the smallest positive integer greater than 1 that does not appear in this sequence is m, whose set of prime divisors is {p1, p2, ..., pk}. Since there are infinitely many numbers with this set of prime divisors, we know that either all of them appear or none of them appear. Since m is the smallest among them, we know that m = p1*p2*...*pk. Therefore, p1*p2*...*pk - 1 does not appear, a contradiction, implying that all integers greater than one appear in {a(n)}. Since there are no repetitions by the definition, we have proven that {a(n)} is a permutation of the positive integers greater than 1.

From Yifan Xie, May 26 2025: (Start)

Theorem 2: The parity of a(n) is the same as the parity of n.

Proof: Since a(1) is odd, we only need to prove that an odd term is immediately followed by an even term, and an even term is immediately followed by an odd term. If a(n-1) is odd, the set of prime divisors of a(n-1) + 1 contains 2, so a(n) is even; If a(n-1) and a(n) are both even, the set of prime divisors of a(n-1) + 1 does not contain 2, so a(n)/2 is a smaller candidate for a(n), a contradiction. (End)

Links

Michael S. Branicky, Table of n, a(n) for n = 1..10000

Example

For a(5) = 11, 11 + 1 = 12, its set of prime divisors is {2, 3}. The smallest number with the same set of prime divisors that has not appeared before is 6, so a(6) = 6.

Maple

N:= 1000:# for terms before the first term > N
for i from 2 to N do
  S:= numtheory:-factorset(i);
  if assigned(V[S]) then V[S]:= V[S] union {i}
  else V[S]:= {i}
  fi
od:
R:= 3: r:= 3: V[{3}]:= V[{3}] minus {3}:
while r < N do
  S:= numtheory:-factorset(r+1);
  if V[S] = {} then break fi;
  r:= min(V[S]);
  V[S]:= V[S] minus {r};
  R:= R, r;
od:
R; # Robert Israel, May 25 2025

Mathematica

s={3}; Do[i=2; While[MemberQ[s, i]||First/@FactorInteger[i]!=First/@FactorInteger[s[[-1]]+1], i++]; AppendTo[s, i], {n, 2, 81}]; s (* James C. McMahon, Jun 04 2025 *)

Prog

(Python)
import heapq
from math import prod
from sympy import factorint
from itertools import islice
def bgen(pset): # generator of terms with set of prime divisors = pset
    h = [prod(pset)]
    while True:
        v = heapq.heappop(h)
        yield v
        for p in pset:
            heapq.heappush(h, v*p)
def agen(): # generator of terms
    an, aset = 3, set()
    while True:
        yield an
        aset.add(an)
        an = next(m for m in bgen(set(factorint(an+1))) if m not in aset)
print(list(islice(agen(), 81))) # Michael S. Branicky, May 25 2025

Crossrefs

Similar to A064413 and A257218.

Sequence in context: A365278 A342802 A099887 * A366348 A274827 A038220

Adjacent sequences: A384305 A384306 A384307 * A384309 A384310 A384311

Keyword

nonn

Author

SiYang Hu, May 25 2025

Status

approved