A372152 Number of k in the range 2^n <= k < 2^(n+1) whose shortest addition chain does not have length n, n+1 or n+2.

0, 0, 0, 0, 2, 9, 30, 80, 193, 432, 925, 1928, 3953, 8024, 16189, 32544

Offset

0,5

Comments

The length of the shortest addition chain for k is A003313(k).

Dividing natural numbers into sections 2^n <= k < 2^(n+1), some of the 2^n numbers available in a section have the shortest addition chains given by

n (for k=2^n),

n+1 (for k=2^n+2^m, m in [0..n-1], A048645), or

n+2 (for some k in A072823).

The sequence gives the numbers of k within each section (N_oth) that have the shortest addition chains other than n, n+1, and n+2.

In particular for 4 <= n <= 6, N_oth = 2^n - n^2 + 2 and for n >= 7, N_oth = 2^n - n^2 + 1.

Links

Table of n, a(n) for n=0..15.

S. Łukaszyk and W. Bieniawski, Assembly Theory of Binary Messages, Mathematics, 12(10) (2024), 1600.

Crossrefs

Cf. A003313, A048645, A072823, A014701, A024012.

Sequence in context: A228932 A196421 A352405 * A056778 A177111 A290746

Adjacent sequences: A372149 A372150 A372151 * A372153 A372154 A372155

Keyword

nonn,more

Author

Szymon Lukaszyk, Apr 20 2024

Status

approved