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,5

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).

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

Example

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.

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}]

Prog

(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

Crossrefs

Cf. A003586, A237442, A276380, A277071.

Sequence in context: A094840 A035218 A237442 * A139355 A039736 A093921

Adjacent sequences: A277067 A277068 A277069 * A277071 A277072 A277073

Keyword

nonn

Author

Michael De Vlieger, Sep 27 2016

Status

approved