A335503 Triangle read by rows, 0 <= k < n, n >= 1: T(n,k) is the eventual period of the sequence x(j) (or 0 if x(j) never enters a cycle) defined as follows: x(0) = 1 and for j > 1 x(j) is obtained from 3*x(j-1) by deleting all occurrences of the digit k in base n.

0, 1, 1, 1, 1, 0, 12, 1, 2, 1, 28, 1, 0, 1, 2, 64, 1, 2, 1, 2, 4, 60, 4, 2, 1, 4, 0, 2, 54, 1, 2, 1, 62, 16, 2, 48, 2, 1, 0, 1, 0, 0, 0, 0, 0, 80, 40, 4, 1, 20, 2000, 60, 72, 4, 1, 40, 20, 5, 1, 85, 240, 5, 5, 20, 1, 320, 1260, 128, 2, 1, 272, 4, 2, 48, 68, 1, 20, 1440

Offset

1,7

Comments

T(1,0) = 0 is defined in order to make the triangle of numbers regular.

T(n,k) = 1 whenever k is a power of 3 and k>1.

Links

Pontus von Brömssen, Rows n = 1..32, flattened

Example

Triangle begins:
   n\k   0    1    2    3    4    5    6    7    8    9   10   11
  ---------------------------------------------------------------
   1:    0
   2:    1    1
   3:    1    1    0
   4:   12    1    2    1
   5:   28    1    0    1    2
   6:   64    1    2    1    2    4
   7:   60    4    2    1    4    0    2
   8:   54    1    2    1   62   16    2   48
   9:    2    1    0    1    0    0    0    0    0
  10:   80   40    4    1   20 2000   60   72    4    1
  11:   40   20    5    1   85  240    5    5   20    1  320
  12: 1260  128    2    1  272    4    2   48   68    1   20 1440
T(10,0) = 80, because A243845 eventually enters a cycle of length 80.

Prog

(Python)
from sympy.ntheory.factor_ import digits
from functools import reduce
def drop(x, n, k):
  # Drop all digits k from x in base n.
  return reduce(lambda x, j:n*x+j if j!=k else x, digits(x, n)[1:], 0)
def cycle_length(n, k, m):
  # Brent's algorithm for finding cycle length.
  # Note: The function may hang if the sequence never enters a cycle.
  if (m, n, k)==(5, 10, 7):
    return 0 # A little cheating; see A335506.
  p=1
  length=0
  tortoise=hare=1
  nz=0
  while True:
    hare=drop(m*hare, n, k)
    while hare and hare%n==0:
      hare//=n
      nz+=1 # Keep track of the number of trailing zeros.
    length+=1
    if tortoise==hare:
      break
    if p==length:
      tortoise=hare
      nz=0
      p*=2
      length=0
  return length if not nz else 0
def A335503(n, k):
  return cycle_length(n, k, 3) if n>1 else 0

Crossrefs

Cf. A243845.

Cf. A335502, A335504, A335505, A335506.

Cf. A243846, A306569, A306773.

Sequence in context: A172376 A289673 A010211 * A066786 A109015 A010210

Adjacent sequences: A335500 A335501 A335502 * A335504 A335505 A335506

Keyword

nonn,base,tabl

Author

Pontus von Brömssen, Jun 13 2020

Status

approved