This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
%I A373797 #110 Aug 03 2024 13:42:32
%S A373797 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 A373797 22,24,24,25,25
%N 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}.
%C A373797 This is a finite version of the "cup of coffee" sequence A280864.
%C A373797 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 A373797 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 A373797 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 A373797 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 A373797 a(m) >= max_{1 <= i <= A280774(m)} A280864(i).... (**)
%C A373797 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 A373797 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 A373797 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 A373797 Rémy Sigrist, <a href="/A373797/a373797_1.txt">C++ program</a>
%e A373797 Solutions for small n (the solutions are a long way from being unique, but see A375030):
%e A373797 n a(n) Solution S
%e A373797 1 1 1
%e A373797 4 3 1,2,4
%e A373797 6 4 1,2,6,3
%e A373797 8 6 1,2,4,3,6,8
%e A373797 10 8 1,2,4,3,9,5,10,8
%e A373797 12 10 1,2,4,3,6,8,5,10,12,9
%e A373797 14 11 1,2,4,3,6,10,5,7,14,12,9
%e A373797 16 13 1,2,4,3,6,8,5,10,12,9,7,14,16
%e A373797 As an example, let us verify that the prime-divisibility condition holds for the n=14 solution (we write Y to indicate divisibility):
%e A373797 S = 1,2,4,3,6,10,5,7,14,12,9
%e A373797 2?....Y.Y...Y..Y......Y..Y..
%e A373797 3?........Y.Y............Y.Y
%e A373797 5?.............Y.Y..........
%e A373797 7?.................Y..Y.....
%e A373797 The Y's occur in disjoint pairs, as required.
%e A373797 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 A373797 (Python)
%o A373797 from itertools import permutations
%o A373797 from sympy import primefactors, primepi
%o A373797 def A373797(n):
%o A373797 c = [set()]+[set(primefactors(i)) for i in range(1,n+1)]+[set()]
%o A373797 for k in range(n-primepi(n)+primepi(n>>1),0,-1):
%o A373797 for a in permutations(range(1,n+1),k):
%o A373797 alist = [0]+list(a)+[n+1]
%o A373797 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 A373797 return k # _Chai Wah Wu_, Jul 26 2024
%o A373797 (Python)
%o A373797 # 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 A373797 from sympy import primefactors
%o A373797 def isSolution(S: list[int]) -> bool:
%o A373797 return all(not any((S[i-1] % p == 0) == (S[i+1] % p == 0)
%o A373797 for p in primefactors(S[i])) for i in range(1, len(S)-1))
%o A373797 # _Peter Luschny_, Jul 27 2024
%o A373797 (C++) // See Links section.
%Y A373797 Cf. A280864, A280774, A375024, A375029, A375030.
%Y A373797 See A373800 for the right-hand side of (**).
%K A373797 nonn,more
%O A373797 1,4
%A A373797 _N. J. A. Sloane_, Jul 26 2024
%E A373797 a(20)-a(24) from _Rémy Sigrist_, Jul 27 2024
%E A373797 a(25) from _N. J. A. Sloane_, Jul 27 2024
%E A373797 a(26)-a(31) from _Rémy Sigrist_, Jul 28 2024