|
| |
|
|
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}.
|
|
5
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,4
|
|
|
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
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
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
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.)
|
|
|
PROG
|
(Python)
from itertools import permutations
from sympy import primefactors, primepi
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]):
(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))
(C++) // See Links section.
|
|
|
CROSSREFS
|
See A373800 for the right-hand side of (**).
|
|
|
KEYWORD
|
nonn,more
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
