login
Lexicographically earliest sequence of distinct positive terms such that a(1) = 1, a(2) = 2, and for any n > 2, the greatest prime factor of a(n) does not exceed the prime next to the greatest prime factor of a(n-1).
3

%I #20 Oct 18 2018 14:54:04

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

%T 36,40,35,33,26,17,19,23,29,31,34,38,39,42,44,45,48,50,49,54,60,56,55,

%U 52,51,57,46,58,62,37,41,43,47,53,59,61,63,64,72,75,70

%N Lexicographically earliest sequence of distinct positive terms such that a(1) = 1, a(2) = 2, and for any n > 2, the greatest prime factor of a(n) does not exceed the prime next to the greatest prime factor of a(n-1).

%C More formally, for any n > 0, A061395(a(n+1)) <= A061395(a(n)) + 1.

%C This sequence is a permutation of the natural numbers, with inverse A320455:

%C - by induction: for any k > 0, every number with greatest prime factor prime(k) (where prime(k) denotes the k-th prime number) appear in the sequence:

%C - for k = 1: we can always choose a number with greatest prime factor 2, so eventually every number with greatest prime factor 2 will appear in the sequence,

%C - for any k > 1: provided every number with greatest prime factor prime(k) appear in the sequence: after a number with greatest prime factor prime(k), say w, we can always choose a number < w with greatest prime factor prime(k+1), so eventually every number with greatest prime factor prime(k+1) will appear in the sequence, QED.

%C The prime numbers appear in ascending order as clusters in the sequence; the first prime clusters are:

%C - 2 terms: a(2) = 2, a(3) = 3,

%C - 2 terms: a(6) = 5, a(7) = 7,

%C - 2 terms: a(14) = 11, a(15) = 13,

%C - 5 terms: a(32) = 17, ..., a(36) = 31,

%C - 7 terms: a(56) = 37, ..., a(62) = 61,

%C - 14 terms: a(139) = 67, ..., a(152) = 131,

%C - 26 terms: a(343) = 137, ..., a(368) = 271,

%C - 43 terms: a(745) = 277, ..., a(787) = 547,

%C - 85 terms: a(1893) = 557, ..., a(1977) = 1109,

%C - 145 terms: a(3963) = 1117, ..., a(4107) = 2221,

%C - 276 terms: a(10047) = 2237, ..., a(10322) = 4463,

%C - 506 terms: a(24973) = 4481, ..., a(25478) = 8951,

%C - 942 terms: a(44952) = 8963, ..., a(45893) = 17923.

%C See A320503 for a similar sequence.

%H Rémy Sigrist, <a href="/A320454/b320454.txt">Table of n, a(n) for n = 1..10000</a>

%H Rémy Sigrist, <a href="/A320454/a320454.png">Scatterplot of the first 50000 terms</a> (with prime terms highlighted)

%H Rémy Sigrist, <a href="/A320454/a320454.gp.txt">PARI program for A320454</a>

%H <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>

%e The first terms, alongside the greatest prime factor of a(n) and A061395(a(n)), are:

%e n a(n) gpf(a(n)) A320454(a(n))

%e -- ---- --------- -------------

%e 1 1 N/A 0

%e 2 2 2 1

%e 3 3 3 2

%e 4 4 2 1

%e 5 6 3 2

%e 6 5 5 3

%e 7 7 7 4

%e 8 8 2 1

%e 9 9 3 2

%e 10 10 5 3

%e 11 12 3 2

%e 12 15 5 3

%e 13 14 7 4

%e 14 11 11 5

%e 15 13 13 6

%t Nest[Append[#, Block[{k = 3, p}, While[Nand[Set[p, FactorInteger[k][[-1, 1]]] <= NextPrime[#[[-1, -1]] ], FreeQ[#[[All, 1]], k ]], k++]; {k, p}]] &, {{1, 1}, {2, 2}}, 65][[All, 1]] (* _Michael De Vlieger_, Oct 17 2018 *)

%o (PARI) See Links section.

%Y Cf. A061395, A320455 (inverse), A320503.

%K nonn,look

%O 1,2

%A _Rémy Sigrist_, Oct 13 2018