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

Author

Peter Luschny, Jul 31 2024

Keywords

• nonn
• tabl
• fini
• full

Comments

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)

Examples

			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
		

Links

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

Crossrefs

Cf. A280864, A280866, A375029, A375030.

Programs

Python

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