A355915 Number of ways to write n as a sum of numbers of the form 2^r * 3^s, where r and s are >= 0, and no summand divides another.

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 3, 1, 1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 1, 2, 1, 1, 3, 2, 2, 1, 1, 2, 2, 1, 2, 2, 1, 2, 1, 1, 2, 1, 1, 2, 2, 1, 3, 1, 2, 2, 3, 1, 2, 1, 2, 2, 2, 1, 3, 3, 2, 1

Offset

1,11

Comments

It is a theorem of Erdos [Erdős] that this representation is always possible.

Without the divisibility constraint the answer is A062051.

See A356792 for when k first appears.

Links

Michael S. Branicky, Table of n, a(n) for n = 1..10000

Michael S. Branicky, Python Program

William Lowell Putman Mathematical Competition, Number 66, 2005, Problem A-1.

Example

Illustration of initial terms:
1 = 2^0
2 = 2^1
3 = 3^1
4 = 2^2
5 = 2+3
6 = 2*3
7 = 2^2+3
8 = 2^3
9 = 3^2
10 = 2^2 + 2*3
11 = 2+3^2 = 2^3+3 (this is the first time there are 2 solutions)
12 = 2^2*3
13 = 2^2+3^2
14 = 2^3+2*3
...

Prog

(Python) # see linked program

Crossrefs

Cf. A062051, A356792.

Sequence in context: A238015 A257679 A056059 * A357900 A357732 A356428

Adjacent sequences: A355912 A355913 A355914 * A355916 A355917 A355918

Keyword

nonn

Author

Michael S. Branicky and N. J. A. Sloane, Sep 21 2022

Extensions

More than the usual number of terms are shown, to distinguish this from similar sequences.

Status

approved