A368315 a(n) gives the number of ways to go from n to 1 with steps consisting of replacing a positive number without leading zero, say m, appearing in the binary expansion of a number, by a proper divisor of m.

1, 1, 1, 2, 2, 3, 2, 4, 4, 7, 6, 8, 6, 8, 6, 8, 8, 17, 14, 21, 18, 28, 18, 20, 16, 27, 26, 26, 18, 31, 22, 16, 22, 37, 34, 58, 48, 76, 52, 58, 48, 98, 80, 102, 80, 105, 76, 48, 40, 85, 80, 96, 80, 153, 104, 76, 70, 99, 98, 119, 82, 136, 116, 32, 44, 123, 98

Offset

1,4

Links

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

Rémy Sigrist, PARI program

Index entries for sequences related to binary expansion of n

Formula

a(1) = 1.

a(n) = Sum_{k = A368314(n)-1} a(A368313(k)) for any n > 1.

a(2^k) = A011782(k) for any k >= 0.

Example

a(10) = 7 for we have seven ways to go from 10 to 1:
    10 -> 1,
    10 -> 2 -> 1,
    10 -> 5 -> 1,
    10 -> 5 -> 3 -> 1,
    10 -> 6 -> 1,
    10 -> 6 -> 2 -> 1,
    10 -> 6 -> 3 -> 1.

Prog

(PARI) See Links section.

Crossrefs

Cf. A011782, A368198 (decimal variant), A368313, A368314.

Sequence in context: A355359 A144369 A033822 * A144428 A029638 A342297

Adjacent sequences: A368312 A368313 A368314 * A368316 A368317 A368318

Keyword

nonn,base

Author

Rémy Sigrist, Dec 21 2023

Status

approved