login
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

%I #29 Jun 10 2024 23:22:13

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

%N 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.

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

%C 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

%C n (for k=2^n),

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

%C n+2 (for some k in A072823).

%C 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.

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

%H S. Ɓukaszyk and W. Bieniawski, <a href="https://doi.org/10.3390/math12101600">Assembly Theory of Binary Messages</a>, Mathematics, 12(10) (2024), 1600.

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

%K nonn,more

%O 0,5

%A _Szymon Lukaszyk_, Apr 20 2024