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

Author

Rémy Sigrist, Dec 21 2023

Keywords

• nonn
• base

Examples

			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.
		

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

Crossrefs

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

Programs

PARI

See Links section.

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.