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

Author

SiYang Hu, May 25 2025

Keywords

• nonn

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)

Examples

			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.
		

Links

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

Crossrefs

Similar to A064413 and A257218.

Programs

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 *)

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