login
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}.
5

%I #110 Aug 03 2024 13:42:32

%S 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,

%T 22,24,24,25,25

%N 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}.

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

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

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

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

%C 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

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

%C 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).

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

%C 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

%H Rémy Sigrist, <a href="/A373797/a373797_1.txt">C++ program</a>

%e Solutions for small n (the solutions are a long way from being unique, but see A375030):

%e n a(n) Solution S

%e 1 1 1

%e 4 3 1,2,4

%e 6 4 1,2,6,3

%e 8 6 1,2,4,3,6,8

%e 10 8 1,2,4,3,9,5,10,8

%e 12 10 1,2,4,3,6,8,5,10,12,9

%e 14 11 1,2,4,3,6,10,5,7,14,12,9

%e 16 13 1,2,4,3,6,8,5,10,12,9,7,14,16

%e As an example, let us verify that the prime-divisibility condition holds for the n=14 solution (we write Y to indicate divisibility):

%e S = 1,2,4,3,6,10,5,7,14,12,9

%e 2?....Y.Y...Y..Y......Y..Y..

%e 3?........Y.Y............Y.Y

%e 5?.............Y.Y..........

%e 7?.................Y..Y.....

%e The Y's occur in disjoint pairs, as required.

%e 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.)

%o (Python)

%o from itertools import permutations

%o from sympy import primefactors, primepi

%o def A373797(n):

%o c = [set()]+[set(primefactors(i)) for i in range(1,n+1)]+[set()]

%o for k in range(n-primepi(n)+primepi(n>>1),0,-1):

%o for a in permutations(range(1,n+1),k):

%o alist = [0]+list(a)+[n+1]

%o 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]):

%o return k # _Chai Wah Wu_, Jul 26 2024

%o (Python)

%o # 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}.

%o from sympy import primefactors

%o def isSolution(S: list[int]) -> bool:

%o return all(not any((S[i-1] % p == 0) == (S[i+1] % p == 0)

%o for p in primefactors(S[i])) for i in range(1, len(S)-1))

%o # _Peter Luschny_, Jul 27 2024

%o (C++) // See Links section.

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

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

%K nonn,more

%O 1,4

%A _N. J. A. Sloane_, Jul 26 2024

%E a(20)-a(24) from _Rémy Sigrist_, Jul 27 2024

%E a(25) from _N. J. A. Sloane_, Jul 27 2024

%E a(26)-a(31) from _Rémy Sigrist_, Jul 28 2024