A335502 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 2*x(j-1) by deleting all occurrences of the digit k in base n.

0, 1, 1, 4, 1, 1, 2, 1, 1, 0, 4, 1, 1, 3, 1, 12, 2, 1, 6, 1, 4, 78, 1, 1, 6, 1, 3, 6, 3, 1, 1, 0, 1, 0, 0, 0, 6, 1, 1, 18, 1, 4, 36, 4, 1, 36, 4, 1, 4, 1, 8, 4, 72, 1, 540, 100, 1, 1, 16, 1, 4, 17, 0, 1, 8, 4, 90, 2, 1, 12, 1, 4, 14, 6, 1, 4, 4, 240

Offset

1,4

Comments

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

One way of getting T(n,k) = 0 is to have x(j) = x(i)*n^e for some j > i and e > 0. For k < n <= 48, this is the only way to get T(n,k) = 0 (but see A335506 for another situation where the x-sequence is not periodic).

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

It seems that k = 0 and k = n-1 often lead to particularly long cycles.

Links

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

Example

Triangle begins:
   n\k  0   1   2   3   4   5   6   7   8   9  10  11
  ---------------------------------------------------
   1:   0
   2:   1   1
   3:   4   1   1
   4:   2   1   1   0
   5:   4   1   1   3   1
   6:  12   2   1   6   1   4
   7:  78   1   1   6   1   3   6
   8:   3   1   1   0   1   0   0   0
   9:   6   1   1  18   1   4  36   4   1
  10:  36   4   1   4   1   8   4  72   1 540
  11: 100   1   1  16   1   4  17   0   1   8   4
  12:  90   2   1  12   1   4  14   6   1   4   4 240
For n = 10 and k = 5, the x-sequence starts 1, 2, 4, 8, 16, 32, 64, 128, 26, 2, and then repeats with a period of 8, so T(10,5) = 8.
T(10,0) = 36, because A242350 eventually enters a cycle of length 36.
For n=11 and k=7, the x-sequence starts (in base 11) 1, 2, 4, 8, 15, 2A, 59, 10. Disregarding trailing zeros, the sequence then repeats with period 7 and x(i+7*j) = x(i)*11^j for positive i and j. The x-sequence itself is therefore not eventually periodic, so T(11,7)=0.

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 A335502(n, k):
  return cycle_length(n, k, 2) if n>1 else 0

Crossrefs

Cf. A242350.

Cf. A335503, A335504, A335505, A335506.

Cf. A243846, A306569, A306773.

Sequence in context: A353976 A363919 A368000 * A119591 A333782 A304876

Adjacent sequences: A335499 A335500 A335501 * A335503 A335504 A335505

Keyword

nonn,base,tabl

Author

Pontus von Brömssen, Jun 13 2020

Status

approved