[seqfan] Re: Prime factor tour

[Chris Thompson]

On Apr 18 2018, Peter Munn described a sequence here which seems to me
interesting, quite difficult to compute accurately, and well worthy of
inclusion in OEIS (both it and its inverse). It's strange that there
hasn't been any follow-up on Seqfan about it, and I should thank
David Seal for bringing it to my attention again.

Peter wrote:

>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.
>
[some background material snipped here]
>
>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.

Yes, that is clear. Any finite sequence conforming to the rules and
without repetitions so far can be extended to a permutation of all the
positive integers. For one can always get from any number N to any
other M by choosing a prime P that has not so far occurred as a factor
and going N -> P*N -> (via multiples of P) -> P*M -> M. You can never
run out of primes! (Due credit: Euclid.)

>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.

One should think of this as maintaining all minimal-length ways of
achieving the sequence so far, and refining them as one finalises
the location of each successive integer. This is easy in principle
if one can get from N to M (the smallest integer greater than N that
cannot be positioned before N) in the minimal numbers of steps, i.e.
Omega(N/gcd(N,M))+Omega(M/gcd(N,M)) [where Omega is as in A001222],
for in that case there are only a finite number of possibilities.

But sometimes one requires 2 more steps (never more, because we can
always multiply in a new prime and take it out at the end) and then
keeping track is harder. This occurs first at 3->4 and at 7->8 and
not again until one gets to 63->64. The fact that this last requires
11 rather than 9 steps can be deduced from the possibilities remaining
at that point for the 54->56 transition in 6 steps, which are

 54 -> 378 -> 126 -> 252  -> 84  -> 168 -> 56
 54 -> 378 -> 126 -> 252  -> 504 -> 168 -> 56
 54 -> 378 -> 756 -> 252  -> 84  -> 168 -> 56
 54 -> 378 -> 756 -> 252  -> 504 -> 168 -> 56
 54 -> 378 -> 756 -> 1512 -> 504 -> 168 -> 56
 54 -> 108 -> 756 -> 252  -> 84  -> 168 -> 56
 54 -> 108 -> 756 -> 252  -> 504 -> 168 -> 56
 54 -> 108 -> 756 -> 1512 -> 504 -> 168 -> 56
 54 -> 108 -> 216 -> 1512 -> 504 -> 168 -> 56
 54 -> 108 -> 216 -> 72   -> 504 -> 168 -> 56

(One can imagine more efficient representations than just a list
of these 10 full sequences, of course.) Now going from 63->64 in
9 steps requires starting 63 -> 126 -> 252 -> 84 -> 168, which
is impossible as 168 is now fixed just before 56, or else
63 -> 126 -> 252 -> 504. The latter is impossible because each
of the 54->56 sequences contains either 252 or 504 (or both).

So 63->64 will need 11 steps, and there are infinitely many
ways of doing that. It probably comes as no surprise that the
way finally selected is one of the those that go via the next
prime 67, so we are back to finite numbers of possibilities
again. For putting 65 in would require 13 steps, and 66 has
already been placed at this stage. But will we always be able
to find a quick argument reverting to the finite-possibilities
scenario again?

>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, ...

There is a 69 missing between 483 and 23; otherwise I can confirm
these. I have carried out my own hand calculations up to 90+, and
get the following, where the parenthesised values are just one
possibility but the positions of the others are determined.

  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,69,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,
  96,48,528,264,132,66,33,
  165,55,385,35,
  1295,(185),37,
  74,1406,38,
  76,(152),760,40,
  1640,(328,164),82,41,
  1783,43,
  86,1978,46,
  2162,94,47,
  329,2303,49,
  98,490,70,350,50,
  850,(170),85,255,51,
  2703,(159),53,
  (106,318,954),2862,54,
  108,216,72,504,168,56,
  3304,(472,236,118),59,
  (177,354,708),3540,60,
  3660,(732,244,122),61,
  (183,549),3843,63,
  4221,(603,201),67,134,268,536,1072,2144,4288,64,
  320,160,80,1040,520,260,130,65,
  4615,(355),71,
  5183,73,
  (146,438),5694,78,
  6162,(474,158),79,
  237,711,2133,6399,81,
  6723,2241,747,249,83,
  (166,332,996),6972,84,
  7476,(1068,356,178),89,
  (267,534,1602),8010,90,
  ...

I think to reliably get much further a program will need to be written.
I have some drafts for that, but only for versions that ask for help
when they encounter a can't-do-it-in-the-minimal-numbers-of-steps case!

>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,...

The inverse sequence should use whatever offset the main one is
entered into OEIS with. I feel it would be quite unnatural for
that to be anything other than 1.

-- 
Chris Thompson
Email: cet1 at cam.ac.uk