A375030 -id:A375030 - cp's OEIS frontend

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

N. J. A. Sloane, Jul 26 2024

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

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

Rémy Sigrist, C++ program

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

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

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

# 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.

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

A374191 Triangle read by rows: T(n) is a permutation of [0, 1, 2, ..., n] subject to an extended Sigrist condition (A280864).

Original entry on oeis.org

0, 0, 1, 0, 2, 1, 1, 2, 0, 3, 0, 3, 1, 2, 4, 1, 2, 4, 3, 0, 5, 1, 2, 0, 5, 3, 6, 4, 2, 1, 3, 6, 4, 5, 0, 7, 1, 2, 4, 3, 6, 8, 5, 0, 7, 3, 1, 2, 4, 5, 0, 7, 8, 6, 9, 1, 2, 4, 3, 9, 5, 10, 8, 7, 0, 6, 6, 1, 2, 4, 3, 9, 5, 10, 8, 7, 0, 11, 1, 2, 4, 3, 6, 8, 5, 10, 12, 9, 7, 0, 11

Offset: 0

Peter Luschny, Jul 31 2024

In a series of submissions (A280864, A280866, A375029, A375030) Rémy Sigrist studies sequences whose terms are locally connected via their prime factors, i.e., where neighbors influence each other in their divisibility.
Sigrist chooses IN = {1, 2,...} as domain. The triangle discussed here is based on Sigrist's idea but chooses IN = {0, 1, 2,...} as the domain. We recall that all numbers divide 0, but 0 only divides 0. Neither 0 nor 1 have prime factors.
For a row of the triangle T(n) = [T(n, k) | k=0..n] and for a term t in this row, let 't be its predecessor and t' its successor. The terms of a row are subject to the following two conditions:
(1) For all k in 1..n-1 and t = T(n, k), t has no prime factor, or it is not the case that there is a prime factor of t such that (p | 't) <=> (p | t'). Expressed more succinctly (in pseudo-Python):
  all(not any((p | 't) <=> (p | t') for p in primefactors(t)) for k = 1..n-1).
(2) If t = T(n, n), then t has no prime factor or for all prime factors of t, (p | t) => (p | t').
The row itself must also satisfy two conditions:
(3) T(n) is a permutation of {0, 1, 2, ..., n}.
(4) T(n) is the lexicographically earliest list among all lists whose terms satisfy conditions (1) and (2).
From Peter Luschny, Aug 05 2024: (Start)
On StackExchange (see link), user Bubbler found by exhaustive analysis for n < 29 that only n <= 14 and n = 16 have a solution. Bubbler also states that "since the 4th Ramanujan prime is 29, there are at least four primes that are greater than n/2 (i.e., prime factors that appear only once) when n >= 29 but there are only 3 positions that such primes can go (both sides of 0 and the first element), which proves that there is no solution when n >= 29."
We set all terms of row 15 equal to 0 by convention to make the sequence finite and full. (End)

			Triangle starts:
  [ 0] (0)
  [ 1] (0, 1)
  [ 2] (0, 2, 1)
  [ 3] (1, 2, 0, 3)
  [ 4] (0, 3, 1, 2, 4)
  [ 5] (1, 2, 4, 3, 0, 5)
  [ 6] (1, 2, 0, 5, 3, 6,  4)
  [ 7] (2, 1, 3, 6, 4, 5,  0,  7)
  [ 8] (1, 2, 4, 3, 6, 8,  5,  0,  7)
  [ 9] (3, 1, 2, 4, 5, 0,  7,  8,  6,  9)
  [10] (1, 2, 4, 3, 9, 5, 10,  8,  7,  0,  6)
  [11] (6, 1, 2, 4, 3, 9,  5, 10,  8,  7,  0, 11)
  [12] (1, 2, 4, 3, 6, 8,  5, 10, 12,  9,  7,  0, 11)
  [13] (7, 1, 2, 4, 3, 6,  8,  5, 10, 12,  9, 11,  0, 13)
  [14] (2, 1, 3, 6, 4, 5, 10,  8,  7, 14, 12,  9, 11,  0, 13)         (*)
  [15] (0, 0, 0, 0, 0, 0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 0)
  [16](11, 1, 2, 4, 3, 6,  8,  5, 10, 12,  9,  7, 14, 16, 13, 0, 15)  (*)
  (*) Found by Bubbler (see link).
.
The terms of T(11, k) alongside their prime factors are:
    k   T(11,k)   prime factors
  --  -------  ---------------
   0     6      2  3
   1     1
   2     2      2
   3     4      2
   4     3         3
   5     9         3
   6     5            5
   7    10      2     5
   8     8      2
   9     7              7
  10     0
  11    11                11

User Bubbler, Comments and solution to challenge: Lexicographically earliest permutation of the initial segment of nonnegative integers subject to divisibility constraints, code golf, StackExchange.

Cf. A280864, A280866, A375029, A375030.

from sympy import primefactors
from itertools import permutations
def test(a: int, b: int, p: int) -> bool:
    return (a % p == 0) == (b % p == 0)
def isSolution(S: tuple[int,...]) -> bool:
    if len(S) == 1: return True
    if not all(test(S[-2], S[-1], p)
           for p in primefactors(S[-1])):
        return False
    return all(not any(test(S[i-1], S[i+1], p)
           for p in primefactors(S[i]))
           for i in range(1, len(S) - 1))
def Trow(r: int) -> tuple[int,...] | None:
    C = list(range(r + 1))
    for P in permutations(C):
        if isSolution(P): return P
for n in range(9): print(Trow(n))

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Python

Extensions

A374191 Triangle read by rows: T(n) is a permutation of [0, 1, 2, ..., n] subject to an extended Sigrist condition (A280864).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python