A277070 Row length of A276380(n).

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

Offset: 1

Author

Michael De Vlieger, Sep 27 2016

Keywords

• nonn

Comments

a(n) represents the partition size generated by greedy algorithm at A276380(n) such that all parts k are unique and in A003586.

See A276380 for further comments about the greedy algorithm.

Row n = 1 for n that are in A003586.

A237442(n) represents the smallest possible partition size such that all k are distinct and in A003586. The reference defines the "canonic" representation of n in the "dual-base number system", i.e., base(2,3), essentially as those which have length A237442(n).

a(n) differs from A237442(n) at n = 41, 43, 59, 86, 88, 91, 113, 118, 123, 135, 155, 172, 176, 177, 182, 185, 209, 215, 226, 236, 239, 248, ... (i.e., A277071).

Examples

			a(n) Terms k in row n of A276380:
1    1
1    2
1    3
1    4
2    1,4
1    6
2    1,6
1    8
1    9
2    1,9
2    2,9
1    12
2    1,12
2    2,12
2    3,12
1    16
2    1,16
1    18
2    1,18
2    2,18
2    3,18
2    4,18
3    1,4,18
...
a(41) = 3 since A276380(41) = {1,4,36}, but {9,32} is the shortest possible partition of 41 such that all terms are distinct and in A003586.
a(88) = 3 since A276380(88) = {1,6,81}, but {16,72} and {24,64} are shorter and have A237442(88) = 2 terms.
		

References

• V. Dimitrov, G. Jullien, and R. Muscedere, Multiple Number Base System Theory and Applications, 2nd ed., CRC Press, 2012, pp. 35-39.

Links

• Michael De Vlieger, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A003586, A237442, A276380, A277071.

Programs

Mathematica

Table[Length@ DeleteCases[Append[Abs@ Differences@ #, Last@ #], k_ /; k == 0] &@ NestWhileList[# - SelectFirst[# - Range[0, # - 1], Block[{m = #, n = 6}, While[And[m != 1, ! CoprimeQ[m, n]], n = GCD[m, n]; m = m/n]; m == 1] &] &, n, # > 1 &], {n, 100}]

Python

from itertools import count, takewhile
N = 100
def B(p): return list(takewhile(lambda x: x<=N, (p**i for i in count(0))))
B23set = set(b*t for b in B(2) for t in B(3) if b*t <= N)
B23lst = sorted(B23set, reverse=True)
def a(n):
    if n in B23set: return 1
    big = next(t for t in B23lst if t <= n)
    return a(n - big) + 1
print([a(n) for n in range(1, N+1)]) # Michael S. Branicky, Sep 14 2022