A018899 -id:A018899 - 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

A323047 Numbers that are not the sum of three (or fewer) 3-smooth numbers.

Original entry on oeis.org

431, 485, 509, 565, 637, 671, 719, 725, 727, 862, 887, 935, 941, 943, 959, 967, 970, 1130, 1151, 1175, 1199, 1205, 1274, 1293, 1319, 1342, 1367, 1373, 1391, 1415, 1421, 1423, 1438, 1439, 1445, 1447, 1450, 1453, 1454, 1455, 1481, 1527, 1535, 1559

Offset: 1

Carlos Alves, Jan 03 2019

nonn

Numbers below 431 may be written as a sum of three (or fewer) elements in A003586. These are the first exceptions.

Below 18431 every number can be written as a sum of 4 or fewer 3-smooth numbers, and below 3448733 every number can be written as a sum of 5 or fewer 3-smooth numbers (cf. sequence A018899).

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A003586, A018899, A237442, A323046, A323048, A323049, A323050.

N:= 1000: # for all terms <= N
S:= {seq(seq(2^i*3^j,i=0..ilog2(N/3^j)),j=0..floor(log[3](N)))}:
S2:= select(`<=`,map(t -> op(map(`+`, S,t)), S),N):
S3:= select(`<=`,map(t -> op(map(`+`, S,t)), S2), N):
A:= {$1..N} minus S minus S2 minus S3:
sort(convert(A,list)); # Robert Israel, May 19 2019

f[n_] := Union@ Flatten@ Table[2^a * 3^b, {a, 0, Log2[n]}, {b, 0, Log[3, n/2^a]}];
b=Block[{nn = 2000, s}, s = f[nn]; {0, 1, 2}~Join~Select[Union@ Flatten@ Outer[Plus, s, s, s], # <= nn &]]; Complement[Range[2000], b]

A172116 The smallest number without double base representation of length n.

Original entry on oeis.org

1, 5, 103, 4985, 641687, 326552783

Offset: 0

Jonathan Vos Post, Jan 26 2010

Portion of abstract from Dimitrov/Howe reference: A double-base representation of an integer n is an expression n = n_1 + ... + n_r, where the n_i are (positive or negative) integers that are divisible by no primes other than 2 or 3; the length of the representation is the number r of terms. It is known that there is a constant a > 0 such that every integer n has a double-base representation of length at most a log n / log log n.

			For example, 103 can be written in many ways as the sum of 3 integers, each with no prime divisors other than 2 and 3 (e.g. 103 = (-1) + (-4) + 108), but it cannot be written as the sum of 2 such integers.  103 is the smallest positive integer that requires more than 2 terms.

Vassil S. Dimitrov and Everett W. Howe, Lower bounds on the lengths of double-base representations, Proc. Amer. Math. Soc. 139 (2011), 3423-3430. Also arXiv:1001.4133.
Vassil S. Dimitrov and Everett W. Howe, Magma and C programs verifying these entries
Vassil Dimitrov, Laurent Imbert, and Pradeep Kumar Mishra, Efficient and secure elliptic curve point multiplication using double-base chains, Advances in cryptology, ASIACRYPT 2005, Lecture Notes in Comput. Sci., vol. 3788, Springer, Berlin, 2005, pp. 59-78.
Vassil Dimitrov, Laurent Imbert, and Pradeep K. Mishra, The double-base number system and its application to elliptic curve cryptography, Math. Comp. 77 (2008), no. 262, 1075-1104.
Pradeep Kumar Mishra and Vassil Dimitrov, A combinatorial interpretation of double base number system and some consequences, Adv. Math. Commun. 2 (2008), no. 2, 159-173.

Cf. A003586, A018899.

Prepended initial terms, updated references, modified comment, added example by Everett W. Howe, Jun 05 2015

A296840 The smallest positive integer whose greedy representation as a sum of 3-smooth numbers (A003586) requires n terms.

Original entry on oeis.org

1, 5, 23, 185, 1721, 15545, 277689, 5586105, 113081529, 2289863865, 46369706169, 986739675321, 26376728842425, 711906436354233, 19221208539173049, 518972365315281081, 22132599848083154505, 944314039112845753929, 40290722114409383329353

Offset: 1

David Eppstein, Dec 21 2017

nonn

			For n = 4, 185 = 162 + 18 + 4 + 1 requires four terms in its greedy representation even though it has the shorter non-greedy representation 185 = 144 + 32 + 9.

David Eppstein, Making Change in 2048, arXiv:1804.07396 [cs.DM], 2018.

Cf. A018899 (numbers requiring n terms in non-greedy representations as sums of A003586), A006892 and A066352 (sequences describing greedy representations as sums of squares and of primes respectively).

With[{nn = 19}, Block[{s = Sort@ Flatten@ Table[2^a * 3^b, {a, 0, Log[2, #]}, {b, 0, Log[3, #/2^a]}] &[10^Floor[8 nn/5]], t}, t = Transpose@ {Most@ s, Differences@ s}; Fold[Append[#1, Function[{a, n}, Last[a] + SelectFirst[t, Last[#] > Last@ a &][[1]]][#1, #2]] &, {1}, Range[2, nn]]]] (* Michael De Vlieger, Dec 22 2017 *)

a(n) is a(n-1) plus the smallest 3-smooth number s whose next successive 3-smooth number is greater than s + a(n-1). For instance, a(3) = 23 = 5 + 18, where a(2) = 5 is the predecessor of 23 in the sequence and where the first gap bigger than 5 among the 3-smooth numbers is the one from 18 to 24.

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

A323047 Numbers that are not the sum of three (or fewer) 3-smooth numbers.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

A172116 The smallest number without double base representation of length n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A296840 The smallest positive integer whose greedy representation as a sum of 3-smooth numbers (A003586) requires n terms.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula