[seqfan] Prime factor tour

[Peter Munn]

Hello seqfans,

I'm visualising a tour of the positive integers with prime factor steps.
Whatever the name, let's start at 1, walk through the positive integers,
multiplying or dividing exactly by a prime with each step, and visit each
positive integer exactly once.

Such tours are of course permutations of the positive integers, and
special cases of the divisor-or-multiple permutations that Michel Marcus,
Antti Karttunen, and I have been looking at; but we have as yet found none
in OEIS.

As a possible route to generate such a permutation from other mathematics,
Antti has been considering the natural mapping between N^N (where N is the
natural numbers) and the exponents of canonical prime factorizations. Any
ideas in this respect would be very welcome.

I have considered the usual route of picking out the lexicographically
earliest such sequence, but this looks very unpromising - I suspect that
there is a qualifying sequence that starts with the first k terms of
A000079 (the powers of 2) for all k > 0, thereby giving an infinite list
of progressively earlier sequences.

Looking much more promising, is asking which such sequence has the
lexicographically earliest inverse. So, we need to find the sequence in
which 1 appears as early as possible, then 2 as early as possible etc.

It's easy to see that the sequence starts 1,2,6,3,... but the first
glimpse of the complexity of calculating this sequence comes with the
intermediate terms before the appearance of 4. To get from 3 to 4 we must
remove a factor of 3 and add two factors of 2, but we cannot start by
doing either of these, as both 1 and 6 have occurred earlier. So another
factor must be added and removed en route, meaning there must be at least
four intervening terms.

... 3,9,18,36,12,4,... achieves this, but the sequence actually continues
... 3,15,5,10,20,4,... since it is the only "tour route" with the minimum
of four intervening terms that has 5 occurring before 4, thus in the
earliest position possible.

Next, notice how the early appearance of 6 and its subsequent
unavailability "delays" the appearance of 4. I put "delays" in quotes, as
the presence of 6 is unavoidable to achieve the earliest appearance of 3.
But later in the sequence, when 19 appears and the next as-yet-to-appear
number is 21, the candidates for intervening terms are "57, 399" and "133,
399". 57 looks like the best bet, so that - when we have placed all lower
numbers - it appears as early as possible. But its use immediately after
19 and consequent later unavailability might cause delay to the appearance
of a lower number than 57, such as 38. In that case, we would need to
consider if 133 is a better successor to 19. So 57 should be only
"pencilled in" until we are sure its use doesn't block the earliest
possible occurrence of any lower number.

What this means is that - at any stage of calculation - we can expect to
have many terms, for which we have only guesses, that precede terms which
we know for sure. I suspect we should still go ahead with both this
sequence and its inverse, and help would be welcome to define both
sequences clearly.

My hand-calculated terms (with pencilled-in guesses in brackets) are:
1,2, 6,3, 15,5,10,20,4, 28,14,7, 77,11, 22,44,88,8, 24,12,36,18,9,
117,39,13, 26,52,104,208,16, 272,136,68,34,17, 323,19, (57),399,21,
483,23, 115,575,25, 75,225,(45),135,27, 783,261,87,29, (58),(174),870,30,
930,(186),(93),31, 62,124,248,496,992,32, ...

The inverse sequence could perhaps be called "Lexicographically earliest
sequence of {positive | nonnegative} integers such that the indices of
neighboring-valued integers differ by a prime factor."

The choice of positive or nonnegative means we can pick from
 1,2,4,9,6,3,12,18,23,7,14,20,26,11,5,...
or:
 0,1,3,8,5,2,11,17,22,6,13,19,25,10,4,...

Best Regards,

Peter