A358095 a(n) is the number of ways n can be reached in the algorithm explained in A358094 if the last operation is summation.

1, 0, 1, 2, 2, 1, 0, 1, 1, 2, 3, 3, 2, 3, 3, 0, 2, 3, 1, 2, 2, 2, 2, 3, 3, 4, 4, 2, 3, 4, 3, 5, 5, 0, 3, 5, 2, 6, 6, 1, 3, 4, 2, 5, 5, 2, 5, 5, 2, 3, 3, 3, 5, 6, 4, 7, 7, 2, 3, 4, 3, 6, 6, 3, 5, 7, 5, 7, 7, 0, 2, 5, 3, 8, 8, 2, 5, 9, 6, 10

Offset: 1

Author

Yifan Xie, Nov 01 2022

Keywords

• nonn
• easy

Comments

From Yifan Xie, Jan 07 2025: (Start)

The following identities can be proved by induction (k, t are nonnegative integers):

a(n) = 0 iff n = 2 or n = 9*2^k - 2.

a(n) = 1 iff n = 1, 3, 6, 8, 9 or n = 21*2^k - 2.

If n > 71, a(n) = 2 iff n = m*3*2^k - 2, where m is in the set {26, 30, 32, 34, 40, 49}.

If n > 85, a(n) = 3 iff n = 108*2^k - 2, 108*2^k - 3, 108*2^k - 4, 108*2^k - 5, 123*2^k - 2, 126*2^k - 2, 132*2^k - 2, 150*2^k - 2, 174*2^k - 2, 210*2^k - 2, (108*2^t - 3)*2^k - 2.

If n > 60, a(n) = 4 iff n = 114*2^k - 2. (End)

Examples

			There are 3 ways to reach 11: (1*2+2)*2+3=11, (1+3)*2+3=11 and (1+2)*3+2=11.
		

Links

• Yifan Xie, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A358094, A358096.

Formula

a(n) = A358096(n-2) + A358096(n-3) for n > 3.

a(6k) = a(2k-1) + a(3k-1); a(6k+1) = a(3k-1); a(6k+2) = a(6k+3) = a(2k) + a(3k); a(6k+4) = a(3k+1); a(6k+5) = a(2k+1) + a(3k+1). - Yifan Xie, Jan 07 2025