login
a(1) = 1, a(2) = 2; a(n) = least k != a(m), m < n, such that omega(a(n-1)) >= omega(k) requires rad(k) | a(n-1), where omega = A001221 and rad = A007947.
1

%I #24 Aug 11 2024 23:39:15

%S 1,2,4,6,3,9,10,5,12,8,14,7,15,25,18,16,20,30,24,27,21,42,28,32,22,11,

%T 26,13,33,60,36,48,54,64,34,17,35,49,38,19,39,66,44,70,40,50,78,52,84,

%U 56,90,45,75,81,46,23,51,102,68,105,63,110,55,114,57,120,72

%N a(1) = 1, a(2) = 2; a(n) = least k != a(m), m < n, such that omega(a(n-1)) >= omega(k) requires rad(k) | a(n-1), where omega = A001221 and rad = A007947.

%C A greedy algorithm selects the smallest candidate k new to the sequence if either omega(k) > omega(a(n-1)) or if omega(k) <= omega(a(n-1)) and rad(k) | a(n-1).

%C Primes enter the sequence late.

%C For a(n) = p odd and prime and n <= 587, a(n-1) = 2*p. It seems for n > 1278, primes are not preceded by 2*p.

%C a(718) = 167 is followed by a(719) = 2*167. There are 13 primes that are followed by 2*p, with a(1364) = 293 apparently the largest. Normally, aside from p = 2 or 3, a(n) = p is such that a(n) and a(n+1) are coprime.

%C Prime powers a(n) = p^j follow a(n-1) = m*p, m >= 1. a(2, 3) = {2, 4}, a(5, 6) = {3, 9}, and these are the only primes immediately followed by their squares, since there are smaller candidates for a(n+1) for larger primes p. Only rarely is a(n+1) a multiple of p.

%C Let r be squarefree and let S_r = { k : rad(k) = r } = { m*r : rad(m) | r }. As consequence of the greedy algorithm and definition, k in S_r enter in order of magnitude. There are chains of consecutive terms in A033845 (e.g., a(31..33) = {36, 48, 54}) and A143207 (e.g., a(496..499) = {720, 750, 810, 900}).

%C Squarefree numbers k appear in trajectories according to omega(k).

%C Composite prime powers p^j, j > 1, appear relatively early, since rad(p^j) = p, and thus prime powers are minimally restricted after a(n-1) such that p | a(n-1).

%C Conjecture: this sequence is a permutation of natural numbers.

%H Michael De Vlieger, <a href="/A374284/b374284.txt">Table of n, a(n) for n = 1..16384</a>

%H Michael De Vlieger, <a href="/A374284/a374284.png">Log log scatterplot of a(n)</a>, n = 1..2^14, showing primes in red, perfect prime powers in gold, squarefree composites in green, and numbers neither squarefree nor prime powers in blue and purple, where purple additionally represents powerful numbers that are not prime powers.

%H Michael De Vlieger, <a href="/A374284/a374284_1.png">Log log scatterplot of a(n)</a>, n = 1..2^14 with a color function showing primes in red, a(n) with omega(a(n)) = 2 in yellow, a(n) with omega(a(n)) = 3 in green, etc.

%H Michael De Vlieger, <a href="/A374284/a374284_2.png">Log log scatterplot of a(n)/n</a>, n = 1..360000, showing fine striation detail associated with numbers that have a given prime signature. The sequence features a phase change near n = 9740.

%e a(3) = 4 since omega(2) = omega(3) = 1, but rad(3) does not divide 2, but omega(4) = omega(2) = 1 and rad(4) = 2.

%e a(4) = 6 since though both 3 and 5 have the same number of distinct prime factors but are pairwise coprime to 4, omega(6) > omega(4).

%e a(5) = 3 since omega(3) < omega(6) and 3 | 6.

%e a(6) = 9 since though 5, 7, and 8 have 1 distinct prime factor like 3, these are pairwise coprime to 3, while omega(9) = omega(3) = 1 and rad(9) = 3.

%e a(7) = 10 since though 5, 7, and 8 have 1 distinct prime factor like 9, these are pairwise coprime to 9, but omega(10) > omega(9).

%e a(8) = 5 since omega(5) < omega(10) and 5 | 10.

%e a(9) = 12 since though 7, 8, and 11 have 1 distinct prime factor like 5, these are pairwise coprime to 5, but omega(12) > omega(5), etc.

%t nn = 120; c[_] := False; a[1] = 1; j = r = a[2] = 2; c[1] = c[2] = True; u = 3;

%t rad[x_] := Times @@ FactorInteger[x][[All, 1]];

%t Do[k = u;

%t While[Set[s, PrimeNu[k]];

%t Or[c[k], If[s <= r, ! Divisible[j, rad[k]] ] ], k++];

%t Set[{a[n], c[k], j, r}, {k, True, k, s}];

%t If[k == u, While[c[u], u++]], {n, 3, nn}];

%t Array[a, nn]

%Y Cf. A001221, A007947.

%K nonn

%O 1,2

%A _Michael De Vlieger_, Jul 31 2024