login
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.
4
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
KEYWORD
nonn,base,tabl
AUTHOR
STATUS
approved