A373797 a(n) = maximal k such that there exists a sequence S = [s_1, s_2, ..., s_k] with s_i distinct and in the range 1 <= s_i <= n such that if any s_i is divisible by a prime p, then p also divides exactly one of s_{i-1} and s_{i+1}.

1, 1, 1, 3, 3, 4, 4, 6, 6, 8, 8, 10, 10, 11, 11, 13, 13, 14, 14, 16, 16, 17, 17, 19, 19, 21, 22, 24, 24, 25, 25

Offset: 1

Author

N. J. A. Sloane, Jul 26 2024

Keywords

• nonn
• more

Comments

This is a finite version of the "cup of coffee" sequence A280864.

An obvious upper bound is a(n) <= n-C, where C is the number of primes p <= n such that 2*p > n. For example a(4) <= 3, since we cannot make use of the prime 3.

Note that for a prime p <= n/2, the number of terms in S that are divisible by p must be even. So if floor(n/p) is odd for any p <= n/2, we have a(n) <= n-C-1.

When going from n=p-1 to n=p (where p is a prime), the new p cannot be used, so a(p) = a(p-1) for p prime.

We can obtain a sequence of lower bounds by taking S to consist of the first A280774(m) terms of A280864, for m = 1,2,3,... This gives

a(m) >= max_{1 <= i <= A280774(m)} A280864(i).... (**)

For example, with m=4, we can take the first A280774(4) = 10 terms of A280864, that is, the sequence S = 1,2,4,3,6,8,5,10,12,9, to get a(12) >= 10. In fact equality holds: a(12) = 10 (see EXAMPLES below).

It was possible that equality would always hold in (**). (**) gives a(4) >= 3, a(8) >= 6, a(12) >= 10, a(16) >= 13 (equality holds up to this point), then a(28) >= 23, a(45) >= 27, ... However, Rémy Sigrist has shown that a(28) = 24.

a(24) = 19 so a(25) >= 19. Here is an argument that shows that a(25) = 20 is impossible. We can't use the big primes 13 17 19 23. There are 5 multiples of 5 we could use, 5 10 15 20 25, but we can only use 4 of them. There are 3 multiples of 7 we could use, namely 7 14 21, but we can only use 2 of them. These two lists are disjoint. So a(25) >= 25 - 4 - 2 = 19. - N. J. A. Sloane, Jul 27 2024

Examples

			Solutions for small n (the solutions are a long way from being unique, but see A375030):
  n   a(n)    Solution S
  1    1        1
  4    3        1,2,4
  6    4        1,2,6,3
  8    6        1,2,4,3,6,8
  10   8        1,2,4,3,9,5,10,8
  12   10       1,2,4,3,6,8,5,10,12,9
  14   11       1,2,4,3,6,10,5,7,14,12,9
  16   13       1,2,4,3,6,8,5,10,12,9,7,14,16
As an example, let us verify that the prime-divisibility condition holds for the n=14 solution (we write Y to indicate divisibility):
  S = 1,2,4,3,6,10,5,7,14,12,9
  2?....Y.Y...Y..Y......Y..Y..
  3?........Y.Y............Y.Y
  5?.............Y.Y..........
  7?.................Y..Y.....
The Y's occur in disjoint pairs, as required.
Also, a(18) = 14, from S = 1,8,16,3,6,14,7,5,15,18,4,9,12,2. (We cannot use 11, 13, and 17, and there are an odd number of multiples of 2 and of 5, so we must lose at least one more term - we can take care of this by sacrificing 10 - so 18-4 = 14 is optimal. This implies a(19) = 14 also.)
		

Links

• Rémy Sigrist, C++ program

Crossrefs

Cf. A280864, A280774, A375024, A375029, A375030.

See A373800 for the right-hand side of (**).

Programs

Python

from itertools import permutations
from sympy import primefactors, primepi
def A373797(n):
    c = [set()]+[set(primefactors(i)) for i in range(1,n+1)]+[set()]
    for k in range(n-primepi(n)+primepi(n>>1),0,-1):
        for a in permutations(range(1,n+1),k):
            alist = [0]+list(a)+[n+1]
            if all((p in c[alist[i-1]])^(p in c[alist[i+1]]) for i, d in enumerate(alist[1:-1],1) for p in c[d]):
                return k # Chai Wah Wu, Jul 26 2024

Python

# Given a list S = [s_1, s_2, ..., s_k], this function checks if the terms s_i are such that if any s_i is divisible by a prime p, then p also divides exactly one of s_{i-1} and s_{i+1}.
from sympy import primefactors
def isSolution(S: list[int]) -> bool:
    return all(not any((S[i-1] % p == 0) == (S[i+1] % p == 0)
           for p in primefactors(S[i])) for i in range(1, len(S)-1))
# Peter Luschny, Jul 27 2024
(C++) // See Links section.

Extensions

a(20)-a(24) from Rémy Sigrist, Jul 27 2024

a(25) from N. J. A. Sloane, Jul 27 2024

a(26)-a(31) from Rémy Sigrist, Jul 28 2024