[seqfan] Re: Prime factor tour

[Peter Munn]

Hi Chris and seqfans,

On Wed, June 6, 2018 4:08 pm, Chris Thompson wrote:
> 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).
[...]
With your calculations confirming my first 57 terms (up to the appearance
of 58), it seems time to tidy my first draft for the sequence and place it
on OEIS. Please check
http://oeis.org/draft?user=Peter%20Munn later on Friday. I am not far from
confirming a(58)=174, having sketched out the sequence to get placings of
all integers to 149, but only thoroughly checked as far as the appearance
of 99.

I have further comments below, notably about ensuring the sequence is
well-defined. For conciseness, I'll trim the sections where all seems
agreed and clear.

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

> 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 [as determined
> solely by their factors], for in that case there are only a
> finite number of possibilities.

Agreed - the finite number is important for a well-defined sequence.

> 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
[8 more rows]
>  54 -> 108 -> 216 -> 72   -> 504 -> 168 -> 56
> (One can imagine more efficient representations than just
> a list of these 10 full sequences, of course.)

My instinct is, anyway, to choose simplicity over efficiency. My own
version of this table continues the rows further to show the transition
possibilities for 63->64, duplicating the 54->56 rows where new choices
arise. So it has 14 rows, which all fail to reach 64 in minimal steps, as
you say...

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

Among my less thoroughly checked terms there is a N->M transition 126->128
that can't be done in minimal steps and, to be achieved in only 2 further
steps, must be done by visiting only even numbers. Rather than the next
unused prime, which can be guaranteed not to be required for a transition
between lesser numbers, the tentative choice becomes
 126 -> 23*126 -> ... -> 138 -> ... 23*128 -> 128.
However, all missing numbers from 129 to 137 are placed without the chosen
waypoint, 138, being needed; so 138 becomes confirmed as appearing between
126 to 128.

No doubt more complex cases will arise later, and I imagine some
transitions will have to give up their first choice route when their
chosen waypoint has "a pressing subsequent engagement", so to speak. I
suspect there will never be cases where the choice of waypoint keeps
rising forever, but I don't expect a proof any time soon.

So my draft definition adds a condition and reads "A permutation of the
positive integers in which adjacent terms differ by a single prime factor
_and a(n) has no prime factor exceeding prime(n)_; this permutation having
an inverse that is lexicographically earlier than any other such
permutation." I'll append a conjecture that the sequence remains the same
without the added condition.

>>My hand-calculated terms (with pencilled-in guesses in brackets) are:
[...]
> There is a 69 missing between 483 and 23;
Yes.

> 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.
[...]
>   76,(152),760,40,
>   1640,(328,164),82,41,
>   1783,43,
>   86,1978,46,

I think your permutation may have missed 42. (Fortunately, I think this
has only local effects on the terms you have calculated so far: that is no
effect after the appearance of 46 at least until the appearance of 100.)

[...]
>   (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!

I have taken a similar approach with the spreadsheets I use to aid my
calculations.

Best Regards,

Peter

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