A280866 -id:A280866 - cp's OEIS frontend

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

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

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