A277071 -id:A277071 - cp's OEIS frontend

A237442 a(n) is the least number of 3-smooth numbers that add up to 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, 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

Offset: 1

Lei Zhou, Feb 07 2014

Any number can be written as the sum of several 3-smooth numbers. The 3-smooth numbers themselves are the sum of 1 3-smooth number.  Others will need more.  Any number n could be written as the sum of n ones (the smallest 3-smooth number), which takes the greatest number of 3-smooth numbers.  This sequence gives the minimum number of 3-smooth 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 2-1, 3*2-1, 3*2^3-1, 3^3*2^4-1 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 dual-base 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)

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

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

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

Cf. A003586, A018899, A276380, A277071.

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 3-smooth 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 *)

A237442(n)={n+9>#M237442 && M237442=Vec(M237442,n+999); if(M237442[n], M237442[n], vecmax(factor(n)[,1]) < 5, M237442[n]=1, my(m=99, k=n\2); until(m==2||!k--, m=min(A237442(k)+A237442(n-k),m)); M237442[n]=m)} \\ M. F. Hasler, Sep 14 2022

A276380 Irregular triangle where row n contains terms k of the partition of n produced by greedy algorithm such that all elements are in A003586.

Original entry on oeis.org

1, 2, 3, 4, 1, 4, 6, 1, 6, 8, 9, 1, 9, 2, 9, 12, 1, 12, 2, 12, 3, 12, 16, 1, 16, 18, 1, 18, 2, 18, 3, 18, 4, 18, 1, 4, 18, 24, 1, 24, 2, 24, 27, 1, 27, 2, 27, 3, 27, 4, 27, 32, 1, 32, 2, 32, 3, 32, 36, 1, 36, 2, 36, 3, 36, 4, 36, 1, 4, 36, 6, 36, 1, 6, 36, 8, 36, 9, 36, 1, 9, 36, 2, 9, 36, 48, 1, 48

Offset: 1

Michael De Vlieger, Sep 25 2016

This sequence uses a greedy algorithm f(x) to find the largest number k <= n such that k is in A003586. The function is recursively applied to the result until it reaches 1. This is the algorithm described in the reference p. 36. This sequence presents the terms in order from least to greatest term.
The reference suggests the greedy algorithm is one way to render n in a "dual-base number system", essentially base (2,3) with bases 2 and 3 arranged orthogonally to produce a matrix of places with values that are the tensor product of prime power ranges of 2 and 3. Place values are signified by 0 or 1. Thus we can boil down the matrix to simply list the values of places harboring digit 1.
Row n = n for n that are in A003586.
The reference defines a "canonic" representation of n on page 33 as having the lowest number of terms. The greedy algorithm 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.
The terms in row n differ from the canonic terms 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).

			Triangle begins:
1
2
3
4
1,4
6
1,6
8
9
1,9
2,9
12
1,12
2,12
3,12
16
1,16
18
1,18
2,18
3,18
4,18
1,4,18
...

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

Michael De Vlieger, Table of n, a(n) for n = 1..11006 (Rows 1 <= n <= 3600)

Cf. A003586, A237442 (least number of 3-smooth numbers that add up to n), A277070 (row lengths), A277071, A347860, A348599.

Table[Reverse@ 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, 49}]

from itertools import count, takewhile
N = 50
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 row(n):
    if n in B23set: return [n]
    big = next(t for t in B23lst if t <= n)
    return row(n - big) + [big]
print([t for r in range(1, N) for t in row(r)]) # Michael S. Branicky, Sep 14 2022

A277070 Row length of A276380(n).

Original entry on oeis.org

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

Michael De Vlieger, Sep 27 2016

nonn

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

			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.

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

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

Cf. A003586, A237442, A276380, A277071.

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

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

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

A276380 Irregular triangle where row n contains terms k of the partition of n produced by greedy algorithm such that all elements are in A003586.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Python

A277070 Row length of A276380(n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Python