[seqfan] Re: Xmas-challenge

[Peter Munn]

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