

A237442


a(n) is the least number of 3smooth numbers that add up to n.


8



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, 2, 2, 2, 2, 2, 3, 3, 1, 2, 2, 2, 2, 3, 1, 2, 2, 2, 2, 2, 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, 2, 2
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,5


COMMENTS

Any number can be written as the sum of several 3smooth numbers. The 3smooth numbers themselves are the sum of 1 3smooth number. Others will need more. Any number n could be written as the sum of n ones (the smallest 3smooth number), which takes the greatest number of 3smooth numbers. This sequence gives the minimum number of 3smooth numbers that is needed to add up to n.
The index of first appearance of n in this sequence: 1, 5, 23, 431, ... . The first four terms are also 21, 3*21, 3*2^31, 3^3*2^41 respectively.
The smallest numbers which require 5 and 6 addends are 18431 and 3448733, respectively.  Giovanni Resta, Feb 09 2014
From Michael De Vlieger, Sep 30 2016: (Start)
Length of shortest partition of n such all elements are unique and in A003586.
Also a "canonic" representation of n in a dualbase number system (i.e., base(2,3)), as defined by the reference as having the lowest number of terms. The greedy algorithm defined in A276380 does not always render the canonic representation. a(41) = {1,4,36}, but {9,32} is the shortest possible partition of 41 such that all terms are in A003586. (End)


REFERENCES

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


LINKS

Lei Zhou, Table of n, a(n) for n = 1..10000


EXAMPLE

n = 23, 23 is not 3smooth. We have 23 = 1+22 = 2+21 = ... = 11+12. None of the 11 pairs are both 3smooth. However, we can find 23 = 1+4+18, a sum of three 3smooth numbers. So a(23) = 3.
a(7) = 2 since the shortest set of terms of the partitions of 7 {{7}, {6,1}, {5,2}, {5,1,1}, {4,3}, {4,2,1}, {4,1,1,1}, {3,3,1}, {3,2,2}, {3,2,1,1}, {3,1,1,1,1}, {2,2,2,1}, {2,2,1,1,1}, {2,1,1,1,1,1}, {1,1,1,1,1,1,1}} such that all the terms are in A003586 and none are repeated is {5,2} or {4,3}.  Michael De Vlieger, Sep 30 2016


MATHEMATICA

SplitN[m_, mt_, a_, s_, aa_, ss_] := Block[{i, j, f, g, a0, s0, a1 = aa, s1 = ss, a2, s2, found = 0}, i = mt + 1; While[i; (found == 0) && (i >= (m/3)), a0 = a; If[f = FactorInteger[i]; f[[Length[f], 1]] <= 3, j = m  i; s0 = s; If[g = FactorInteger[j]; g[[Length[g], 1]] <= 3, If[i >= j, a0++; AppendTo[s0, i]; If[j > 0, a0++; AppendTo[s0, j]]; If[ar > a0, ar = a0; If[a1 > a0, a1 = a0; s1 = s0]; found = 1]], a0++; AppendTo[s0, i]; If[ar > a0, {a2, s2} = SplitN[j, Min[i, j], a0, s0, a1, s1]; If[a1 > a2, a1 = a2; s1 = s2]]]]]; {a1, s1}]; (*This finds the shortest 3smooth train in decreasing order that sums to n*) Table[ar = n; {ac, sc} = SplitN[n, n, 0, {}, n, {}]; ac, {n, 1, 87}]
a[n_] := Block[{p = Select[Range@n, FactorInteger[#][[1, 1]] < 4 &], k = 1},
While[{} == Quiet@ IntegerPartitions[n, {k}, p, 1], k++]; k]; Array[a, 100] (* faster, Giovanni Resta, Feb 09 2014 *)


CROSSREFS

Cf. A003586, A018899, A276380, A277071.
Sequence in context: A244259 A094840 A035218 * A277070 A139355 A039736
Adjacent sequences: A237439 A237440 A237441 * A237443 A237444 A237445


KEYWORD

nonn,easy


AUTHOR

Lei Zhou, Feb 07 2014


STATUS

approved



