A326730 Number of iterations of A326729(x) starting at x = n to reach 0.

0, 1, 3, 2, 5, 4, 6, 3, 7, 6, 8, 5, 10, 7, 9, 4, 9, 8, 10, 7, 12, 9, 11, 6, 14, 11, 13, 8, 15, 10, 12, 5, 11, 10, 12, 9, 14, 11, 13, 8, 16, 13, 15, 10, 17, 12, 14, 7, 18, 15, 17, 12, 19, 14, 16, 9, 21, 16, 18, 11, 20, 13, 15, 6, 13, 12, 14, 11, 16, 13, 15, 10, 18, 15, 17, 12, 19, 14, 16, 9, 20, 17, 19, 14, 21, 16, 18, 11, 23, 18, 20, 13, 22, 15, 17, 8, 22, 19, 21, 16, 23

Offset

0,3

Comments

The sequence is well-defined, see Problem 5 of IMO 2019.

From Natalia L. Skirrow, May 24 2026: (Start)

The maximum a(n) for n in the range [0..2^l) is binomial(l+1,2), achieved by n = 2^l-2^floor(l/2) = A122746(l-1).

Sum_{n=0..2^l-1} a(n) = 2^(l-2)*l*(l+1) = A001788(l).

Sum_{n=0..2^l-1} a(n)^2 = 2^(l-4)*l*(l+1)*(l+2)*(l+1/3).

Thus, the waiting time for an n uniformly sampled in [0..2^l) has expectation l*(l+1)/4 and variance l*(l+1)*(l+1/2)/12.

If n is written as the binary word 1^(o_0) 0^(z_0) 1^(o_1) ..., then (with O_i = Sum_{j=0..i} o_j), a(n) = Sum_i 2*O_i*z_i + o_i. (End)

Links

Rémy Sigrist, Table of n, a(n) for n = 0..8192

International Mathematical Olympiad, Problem 5 of IMO 2019.

Rémy Sigrist, Scatterplot of the ordinal transform of the first 2^16 terms

Formula

a(n) = 2*A029931(n) - A000120(n)^2.

a(2*n) = a(n) + 2*A000120(n), a(2*n+1) = a(n)+1. - Natalia L. Skirrow, May 24 2026

Example

326730_10 = 1001111110001001010_2, whose run-length sequences are o = 1,6,1,1,1 and z = 2,3,2,1,1 with O = 1,7,8,9,10, so a(326730) = Sum_i 2*O_i*z_i+o_i = 2*1*2+1 + 2*7*3+6 + 2*8*2+1 + 2*9*1+1 + 2*10*1+1 = 126. - Natalia L. Skirrow, May 24 2026

Prog

(PARI) A326730(n) = my(b=Vecrev(binary(n)), m=vecsum(b)); 2*sum(i=1, #b, i*b[i]) - m^2;
(Python)
A326730=lambda n: n and A326730(n>>1)+(2*n.bit_count())**(~n&1) # Natalia L. Skirrow, May 24 2026
(Python)
def a(n): return 2*sum(i for i, bi in enumerate(bin(n)[2:][::-1], 1) if bi == "1") - n.bit_count()**2 # Michael S. Branicky, May 24 2026

Crossrefs

Cf. A000120, A029931, A326729, A326731, A326732.

Sequence in context: A316519 A062327 A075491 * A089279 A049820 A109712

Adjacent sequences: A326727 A326728 A326729 * A326731 A326732 A326733

Keyword

base,nonn

Author

Max Alekseyev, Jul 22 2019

Status

approved