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

0, 1, 1, 2, 1, 1, 1, 1, 0, 0, 2, 24, 2, 2, 1, 16, 18, 1, 6, 1, 42, 33, 1, 1, 15, 1, 24, 3, 3, 1, 1, 0, 1, 0, 0, 0, 3, 1, 195, 27, 1, 465, 147, 2, 6, 1002, 18, 4, 42, 1, 66, 2, 10, 10, 738, 1660, 25, 5, 180, 1, 2, 15, 35, 150, 4, 1490

Offset: 1

Author

Pontus von Brömssen, Jun 13 2020

Keywords

• nonn
• base
• tabl

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 4 and k>1.

Examples

			Triangle begins:
   n\k   0    1    2    3    4    5    6    7    8    9
  -----------------------------------------------------
   1:    0
   2:    1    1
   3:    2    1    1
   4:    1    1    0    0
   5:    2   24    2    2    1
   6:   16   18    1    6    1   42
   7:   33    1    1   15    1   24    3
   8:    3    1    1    0    1    0    0    0
   9:    3    1  195   27    1  465  147    2    6
  10: 1002   18    4   42    1   66    2   10   10  738
		

Links

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

Crossrefs

Cf. A335502, A335503, A335505, A335506.

Cf. A243846, A306569, A306773.

Programs

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