A333979 - OEIS

A333979

Array read by antidiagonals, n >= 0, k >= 2: T(n,k) is the "digital derivative" of n in base k; if the base k representation of n is Sum_{j>=0} d_j*k^j, then T(n,k) = Sum_{j>=1} d_j*j*k^(j-1).

%I #20 May 05 2021 13:40:39

%S 0,0,0,0,0,1,0,0,0,1,0,0,0,1,4,0,0,0,0,1,4,0,0,0,0,1,1,5,0,0,0,0,0,1,

%T 2,5,0,0,0,0,0,1,1,2,12,0,0,0,0,0,0,1,1,2,12,0,0,0,0,0,0,1,1,2,6,13,0,

%U 0,0,0,0,0,0,1,1,2,6,13

%N Array read by antidiagonals, n >= 0, k >= 2: T(n,k) is the "digital derivative" of n in base k; if the base k representation of n is Sum_{j>=0} d_j*k^j, then T(n,k) = Sum_{j>=1} d_j*j*k^(j-1).

%H Pontus von Brömssen, <a href="/A333979/b333979.txt">Antidiagonals n = 0..99, flattened</a>

%H M. J. Bannister, Z. Cheng, W. E. Devanny, and D. Eppstein, <a href="http://dx.doi.org/10.7155/jgaa.00318">Superpatterns and universal point sets</a>, Journal of Graph Algorithms and Applications 18(2) (2014), 177-209.

%F T(n,k) = floor(n/k) + k*T(floor(n/k),k). Proof: With n = Sum_{j>=0} d_j*k^j we have floor(n/k) + k*T(floor(n/k),k) = Sum_{j>=1} (d_j*k^(j-1) + k*d_j*(j-1)*k^(j-2)) = Sum_{j>=1} d_j*j*k^(j-1) = T(n,k).

%F T(n,k) = T(n-1,k) + A055129(A286561(n,k),k). Proof: Let n = Sum_{j>=0} d_j*k^j and pick v so that d_j = 0 for j < v and d_v > 0 (so v = A286561(n,k)). Then n - 1 = sum_{j>=0} e_j*k^j, where e_j = k - 1 for j < v, e_v = d_v - 1, and e_j = d_j for j > v. We get T(n,k) - T(n-1,k) = Sum_{j>=1} j*(d_j-e_j)*k^(j-1) = v*k^(v-1) - (k-1)*Sum_{1<=j<v} j*k^(j-1). Working out the sum and simplifying, we get T(n,k) - T(n-1,k) = (k^v - 1)/(k - 1) = A055129(A286561(n,k),k).

%F For fixed k, T(n,k) ~ n*log(n)/(k*log(k)). (The proof for k = 2 by Bannister et al. (p. 182) can be adapted to general k.)

%F T(n,k) = Sum_{j>=0} k^j*floor(n/k**(j+1)).

%e Array begins:

%e n\k| 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

%e ---|---------------------------------------------

%e 0 | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

%e 1 | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

%e 2 | 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0

%e 3 | 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0

%e 4 | 4 1 1 0 0 0 0 0 0 0 0 0 0 0 0

%e 5 | 4 1 1 1 0 0 0 0 0 0 0 0 0 0 0

%e 6 | 5 2 1 1 1 0 0 0 0 0 0 0 0 0 0

%e 7 | 5 2 1 1 1 1 0 0 0 0 0 0 0 0 0

%e 8 | 12 2 2 1 1 1 1 0 0 0 0 0 0 0 0

%e 9 | 12 6 2 1 1 1 1 1 0 0 0 0 0 0 0

%e 10 | 13 6 2 2 1 1 1 1 1 0 0 0 0 0 0

%e 11 | 13 6 2 2 1 1 1 1 1 1 0 0 0 0 0

%e 12 | 16 7 3 2 2 1 1 1 1 1 1 0 0 0 0

%e 13 | 16 7 3 2 2 1 1 1 1 1 1 1 0 0 0

%e 14 | 17 7 3 2 2 2 1 1 1 1 1 1 1 0 0

%e 15 | 17 8 3 3 2 2 1 1 1 1 1 1 1 1 0

%e 16 | 32 8 8 3 2 2 2 1 1 1 1 1 1 1 1

%e 64 = 2*3^3 + 1*3^2 + 0*3^1 + 1*3^0, so T(64,3) = 2*3*3^2 + 1*2*3^1 + 0*1*3^0 = 60. Alternatively, using the formula T(n,k) = floor(n/k) + k*T(floor(n/k),k), we get T(64,3) = 21 + 3*T(21,3) = 21 + 3*(7 + 3*T(7,3)) = 42 + 9*(2 + 3*T(2,3)) = 60.

%o (Python)

%o import sympy

%o def A333979(n,k):

%o d=sympy.ntheory.factor_.digits(n,k)

%o return sum(j*d[-j-1]*k**(j-1) for j in range(1,len(d)-1))

%o (Python)

%o # Second program (faster)

%o def A333979(n,k):

%o return n//k+k*A333979(n//k,k) if n>=k else 0

%Y Cf. A136013 (column k=2), A080277 (every second term of column k=2), A080333 (every third term of column k=3).

%Y Cf. A007824, A055129, A286561.

%K nonn,base,tabl

%O 0,15

%A _Pontus von Brömssen_, Sep 04 2020