[seqfan] Re: Xmas-challenge

Tue Dec 29 12:17:00 CET 2020

Peter Luschny: "
*I like your observation. Have a look at my current draft. The lcms of
theexamples there are all in A025487. Maybe you can expand on that?"*

Thanks. I thought I couldn't but I can a bit. If we drop the upper bound
for a second then from one such sequence, like [3, 6, 2, 4, 1, 5] (taken
from one of your sequences), generate infinitely many of them.
A factor 3 can be assigned a factor p. A factor 2 the letter q and a factor
5 the letter r (for example, in order of appearance). And each letter will
be a different prime.

This gives [3, 6, 2, 4, 1, 5] = [p, p*q, q, q^2, 1, r].
Now we can freely assign values of primes to each letter. And if we have
such an expression we can choose any set of distinct primes. Most likely
the first three primes. Maybe this helps getting the number of such
sequences as well.
This assures that the lcm is at least from A055932 ("Numbers all of whose
prime divisors are consecutive primes starting at 2.") but with some more
thougths, can we prove it's from A025487?

I also made this (see below, from an earlier version of your example of
paths)
A * denotes "a number that's not in the previous row ('sequence')".
() denote: "the number in brackets occur in that order without any numbers
between them in the previous row".
R() denotes:  "the number in brackets occur reversed without any numbers
between them in the previous row"
I swapped some numbers so consecutive bits from the earlier row were
longer.
Like I swapped 4 and 8 in row 9.
Furthermore in row 7 i replaced an earlier 7 with a 5 as in earlier
discussion.
So looking at this row 16 to get to row 17 we'd miss 11, 13, 17. If we add
one new term we have one choice for the new number, namely 11. Adding 13 or
17 would be equivalent as they're new primes and have the same prime
signature.
Similar if we add two of them or three of them - there's one choice for
numbers.

*Can we generally create a new row from a previous row like this? *
*If some number m is new in row k (k > 1), are all its proper divisors in
row k-1?*
*Does it make sense to define use f(k, m) where f(k, m) is the number of
positive integers 1 <= t <= k such that (m|t or t|m) and t != m? *For
example f(6, 3) = 2 as t is in {1, 6}.

1:                  [1],

2:                 [2*, (1)],

3:                [(2, 1), 3*],

4:              [(2), 4*, (1, 3)],

5:              [(2, 4, 1, 3)],

6:           [(3), 6*, (2, 4, 1), 5*],

7:           [(3, 6, 2, 4, 1, 5)],

8:          [(3, 6, 2, 4), 8*, (1, 5)],

9:        [8, R(4, 2, 6, 3), 9*, (1, 5)],

10:     [(8, 4), (1, 5), 10*, (2, 6, 3, 9)],

11:     [(8, 4, 1, 5, 10, 2, 6, 3, 9)],

12:  [(5, 10, 2), (8, 4), 12*, (6, 3, 9), 1, 7*],

13:  [(5, 10, 2, 8, 4, 12, 6, 3, 9, 1, 7)] (IIRC earlier you had stopped
here and I made them myself. They differ from what you have now).

14:  [(5, 10, 2, 8, 4, 12, 6, 3, 9, 1, 7), 14*]

15: [R(6, 12, 4, 8, 2, 10, 5), 15*, (3, 9, 1, 7, 14)]

16: [(6, 12, 4), 16*, (8, 2, 10, 5, 15, 3, 9, 1, 7, 14)]

Best,
David

On Tue, Dec 29, 2020 at 8:47 AM Peter Munn <techsubs at pearceneptune.co.uk>
wrote:

> I think it useful to consider the graph having the following parts: a
> primary part consisting of nodes whose greatest prime factor is less than
> the square root of k = 99, and a satellite part for each prime p, sqrt(k)
> <= p <= k, consisting of nodes whose greatest prime factor is p.
>
> The path can only enter and/or leave a satellite part through particular
> gateway nodes in the primary part, and these are in short supply. A large
> part of the problem is then to allocate these gateways in the most
> productive way.
>
> Anyway, this discussion motivated me to upload (as A340114) some earlier
> results I calculated on a related problem: the longest sequences of
> distinct positive integers that have all adjacent terms differing by a
> prime factor and their k-th term not exceeding n*k. You see I restrict the
> ratio between adjacent terms to being prime. This made exhaustive search
> practical for n <= 4, but I think n = 5 will need some serious thinking.
>
> Best regards,
>
> Peter
>
> On Sun, December 27, 2020 1:10 am, Allan Wechsler wrote:
> > I don't know if my observations were all that interesting, but just in
> > case
> > they inspire somebody:
> >
> > First, my feeling is that it ought to be feasible to get at least a few
> > more elements of this sequence.
> >
> > Second, the divisibility graph always has a few "spurs" caused by primes
> > greater than n/2, which are linked only to 1. The optimal path can
> include
> > at most one of these; I wonder if we can prove that there is always an
> > optimal path with a lonely end. The alternative would be that *all* the
> > paths of the optimal length included 1 deep in the middle. (All optimal
> > paths must include 1, since any path that excludes 1 can be extended by
> > appending 1.)
> >
> > On Sat, Dec 26, 2020 at 4:43 PM Peter Luschny <peter.luschny at gmail.com>
> > wrote:
> >
> >> >
> >> > However, if this sequence is already in the OEIS,
> >> >
> >> don't reveal *its A-number* (this year).
> >> >
> >>
> >> The sequence has now been discovered in the OEIS.
> >> First by Rob Pratt, then by Georg Fischer and finally by
> >> Allen Wechsler. Allan made some interesting remarks
> >> that he will surely share here as well.
> >>
> >> I think it's a neat problem, and it's NP-hard. For this
> >> reason, it would be nice to develop a small program
> >> for this sequence that demonstrates the treatment
> >> of such a problem using a constraint satisfaction solver.
> >>
> >> --
> >> Seqfan Mailing list - http://list.seqfan.eu/
> >>
> >
> > --
> > Seqfan Mailing list - http://list.seqfan.eu/
> >
>
>
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>